I am making a series of mancala games(currently kalah,oware and dakon). I made human-human playable game already. Now I am moving towards AI. How can I make a invincible computer mancala player? What are the properties that should be used as good evalution functions? please help me to figure out this? Thank You Mahfuz

Have you checked out the info at the mancala wiki? eg. Modular arithmetic of mancala games

Thanks. Nice reading.

This gives the idea about where should the last stone will be, but depending on this how can I say, which is most likely to be a good move, specially in the case of multi lap or Indian style Lap.

Quote: Original post by Mahfuzur Rahman
How can I make a invincible computer mancala player? What are the properties that should be used as good evalution functions?

Standard competitive tree search algorithms like minimax apply. The most commonly implemented variant of minimax is alpha-beta pruning; you should start there.

I implemented alpha-beta for mancala 15 years ago and after a few hours of work I had a program that played way better than me. Mancala seems to be a very computer-friendly game (as opposed to games like arimaa or go).

If you have trouble with the details, I'll probably be able to help.

How Can I find good evaluation functions for mancala?

Mahfuz

For a game like Mancala, simple and quick-to-execute functions are best. The difference in captured stones between the two players times some constant, plus the difference in controlled stones between the two players, is probably good enough. Remember, evaluation functions that only serve to look one or two moves ahead probably aren't as good as evaluation functions that look zero moves ahead, particularly if they're more expensive to execute than another ply of minimax. Reserve the trickery for identifying long-term attributes of power, of which there are few in Mancala.

How Can I find out whether the game is at a never ending state like in the game oware or awele?

Well, you can't predict it. Draws of that sort are a function not only of the rules of the game, but of each player's strategy as well. In chess, the game ends in a draw once the same game state has been reached three times. It is not possible to predict such a draw without full knowledge of both players' full decision making processes.

You can analyze all the situations with few seeds left, using the equivalent of chess's endgame tablebases. You can probably cover all situations where a draw will happen because of a cycle. If you go far enough, you might be able to solve the game.