0
\$\begingroup\$

I am currently developing a bot for a game board called Fanorona. The game is not as popular as other board games such as chess or backgammon, but still it brings a lot of fun. Some of you may know it from Assassins Creed 3, specifically the game Connor and Achilles play together.

http://gasy-fanorona.sourceforge.net/docs/fanorona_rules.html

In this link I provided the basic rules.

I have studied what people usually use for bots for chess, algorithms like Alpha-Beta Minimax. These algorithms require a score system in order to make specific decisions, take into account the branching factor, which in this game is hard to estimate. Additionally, the bot could be trained to recognize patterns.

I have never worked with AI algorithms before, therefore I would like find out your opinion concerning this subject. What course of action would you employ in order to build a bot for this kind of game?

\$\endgroup\$
  • \$\begingroup\$ The current advancements in bord game AI can basically be boiled down to "throw a deep learning algorithm at it and hope for the best" xkcd.com/1838 \$\endgroup\$ – Bálint May 19 '17 at 7:45
  • \$\begingroup\$ I wrote the AI for Fanarona in Assassin's Creed III. Philipp is right, just use a Minimax. The trick is deciding what your value function is. Also, there's some source code somewhere for this game that I saw before writing my own. Fun fact: if you flip the sign on the minimax to make the worst possible moves, you can almost force the player to win. :) \$\endgroup\$ – Almo Jul 15 at 18:30
1
\$\begingroup\$

I am not proficient in this game, but the number of possible moves per turn seems to be quite limited, making it quite applicable for MiniMax.

As usual with MiniMax, the biggest challenge is to write a good rating function. Finding out how to tell a good position apart from a bad one requires some in-depth experience with the game.

A trivial solution to start out with to get the game running could be to simply consider material advantage only. Simply count the number of pieces each player has left. Whoever has more pieces on the board appears to be winning. This simple AI could already be strong enough to at least entertain a novice player. Even without alpha-beta pruning and a simple breadth-first search with a hard limit on the number of evaluated positions.

We have a completely deterministic game without information hiding here. That means this alone would in fact be enough to create a perfectly playing AI, if you have enough computing resources available to calculate the whole game from start to end. But that would 1. be very boring to play against and 2. you likely don't have enough computing resources available. That means you need to limit your search-tree depth. That means a more advanced rating function could make the AI much stronger.

When this AI turns out to be too weak, you could add some tactical analysis. One tactical rating criteria could be to account for the number of move-options each piece has left (more being better) and from how many positions each piece could be captured (less being better).

Another rating criteria could be a strategic analysis. You could, for example, reduce the rating of any stones which are in a formation which potentially allows the opponent to make multiple captures at once. Because even if the opponent might not be able to do that in the moves which appear in the current search tree depth, they might get an opportunity to exploit this formation in the future.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.