If you just wanted to get a few points quickly on the hackathon, you could have done the Mancala challenge. Mancala is a simple game, and each turn there are only 6 possible moves. It would only take a minute or two to write some code that just checks which cells are occupied so it can return a random legal move. This code would have been enough to win a few games in the match-off to earn a few points and receive the free $100 AWS credit!
However, if you wanted to do well on the leaderboard, you would need to do a little analysis before picking a move. Most contestants didn’t have enough time to develop a sophisticated Mancala AI, so you you could try to just out-play their simple bots. adr2370’s approach to Mancala was pretty simple, but was enough to earn 36.6 points for the challenge. He looked at which move would get the most points that full turn, including any extra moves. If two moves had the same score, he picked the move that left the most marbles on your side at the end. This simple heuristic works since marbles on your own side are likely to end up in your own store, either through your own moves, or at the end of the game. (If the other player empties first, you place the marbles in your side in your own store.) Since many bots were using simpler approaches, this code was good enough to beat 71% of the other bots and come in 31st place on the Mancala Back-to-School Leaderboard. You can view adr2370’s full code on Github.
A Good Heuristic
With a better heuristic, you could score considerably higher, even without looking ahead at all. Mcjee used such an approach and received 41.3 points for the challenge. Mcjee wanted to try out Ruby and was able to write the code in under 40 lines (which could be shortened more), where the main part is only 14 lines (from lines 14 to 27):
In the main part, each move is analyzed with a couple of heuristics (‘overflows’, ‘scores’ and ‘extra) for its effect this turn. The first thing McJee examines is the “overflow” of a move, i.e. how many pieces are lost to the other side when they pass your own store. This goes further than adr2370’s check of the number of pieces left on each side, since Mcjee factors it into every move. This will cause Mcjee to move further back pieces earlier to avoid overflowing. This could lead to a buildup of pieces near your own store which will be forced to overflow later. However, by moving the further back pieces first, your pieces become safer from capture.
Next, Mcjee examines the ‘score’ of a move which simply looks at the index and the number of pieces of each cell. This might help counter the above tendency to move cells that are further back. The last metric is more intuitive: ‘extra’, the number of pieces captured that move (from the opponent). Capturing is the most important part of the game, since it immediately steals pieces from the opponent, and it helps cause the opponent to empty out sooner. Finally (line 26), Mcjee combines the metrics together with a special formula:
I don’t know why these particular numbers works exactly, but it managed to place Mcjee in 8th place on the back-to-school leaderboard, and 20th overall for Mancala. This is particularly impressive since the other high-ranked bots were looking many moves ahead before doing a move.
More Advanced Play
The best bots in the Hackathon used more advanced techniques to win the game. Instead of just analyzing one move ahead, they looked many moved ahead with minimax searches of game trees and even techniques like alpha-beta pruning. HackerRank has many game challenges where you can practice such techniques, and in the future we will be adding more challenges so people can learn the techniques by doing the challenges. I will just provide a brief overview of the minimax approach, and you find out more with these notes.
A game tree is a tree of future possible moves. Each node in the tree are possible moves, and a node’s children are possible moves of the opponent. Each leaf of the tree receives a score which evaluates how much the position will be worth to you. This can either be an absolute evaluation, such as a game victory, or rely on some heuristic, such as current pieces per side. The score then gets passes up the tree through the minimax search. In minimax search, you pick the maximum score for each of your turn branches and assume your opponent will pick the move which minimizes your score for each of his turns. The actual move each turn will be the move on top of the tree with the highest minimax score.
The top bots in the Mancala competition all used such techniques to analyze each move. The 1st-place bot was created by Neal Wu (nealwu on HackerRank, @WuNeal on Twitter). It was able to search 14 moves ahead and even more moves if there was still time left! It could do this by using an efficient search in C++ and making use of alpha-beta pruning to optimize the search. Since Mancala only has a few possible moves per turn, very deep searches are possible. The bot would then return the best move it found after evaluating the end positions with a simple heuristic:
(my_mancala – your_mancala) + (marbles_on_my_side – marbles_on_your_side)
This heuristic treated pieces on your side as equivalent to being in your own store, since most pieces end up that way, either during gameplay or when one side empties. Although the heuristic was simple, the powerful search was enough to defeat every opponent the bot played.
Do you think you can now improve your bot? Although the hackathon is over, you can submit it on the Mancala challenge on the regular HackerRank site.