Mancala

Note: in this entire blog, the only Mancala board that is considered is the classic board with 6 slots per side and 2 banks.

Some years ago I started playing Clubhouse Games on the Nintendo Switch, and I discovered this game named "Mancala". After learning how to play it I got some questions... "How many possible games are there?" "Do I win more often if I'm first or if I go as second" "How often do you tie?". So being the programmer that I am, I started working on an answer to all of these questions.

Research

Mancala is a game that is more than 2000 years old (sources differ drastically), but despite that, I haven't found anyone who reported any statistics about this game. The closest information that I actually found was a reddit post with a comment saying that the rough estimate of possible games being "6^20" (3656158440062976). I also found some integer sequences on OEIS, but they only got sequences about a solitaire version of Mancala. The street leading to the answers I'm looking doesn't exist, so I'll have to create one myself.

Coding

Since computing approximately 6^20 games would require great performance, I obviously used Rust.

Rust is an high-level programming language that compiles to an executable that is as fast as C/C++.

Before starting coding, I checked out crates.io (rust's libraries) and I found what I was looking for, the library mancala_board. I instantly started contributing to the library, improving it and making it faster. After that, I started writing my "Mancala Calculator" and I discovered the followig things:

• Mancala is a HUGE game

  Already a "simple" game of 24 pieces (2 per slot) has more than 15 million possible games

• Caching is POWERFUL

  Caching stores the input and the output into memory, so if you give it the same input, it will retrieve the output from memory instead of computing it once again.

  Despite consuming up a lot of RAM, it's really worth it

• Multithreading is actually slower in this scenario

  If you use caching with multithreading, all threads will need to access the cached data, and each one needs to wait until the previous one is done reading and writing for it to be safe.

• Making the computer play as humans play it, is slow

  In the worst case scenario, the computer would need to do 3 round trips around the entire board to place all pieces in the right spots. This "multiple round trips procedure" can be saved by dividing the pieces in the hand by how many slots there are (actually, minus one, since you don't want to place your pieces in the opponent's bank), so you can drop multiple pieces in a slot at once and therefore only doing one round trip.