# What AI scheme is appropriate for a 4 player, Tic-Tac-Toe style game?

I am about to release an android game that is like tic tac toe, but on a bigger board, and 4 player. Instead of winning when you get 3 in a row, you get points for chains, and the most points at the end wins.

I'm going to have a later release that will include AI, but I'm quite new to this. Would minimax be a good choice, but does it work in 4 player? I'm worried that because there are around 90 possible moves for each turn then this would get slow too slow for large enough searches.

Any suggestions?

• Please post a link here when you release it. I would love to try it. May 1, 2012 at 2:42

If you don't have any idea how one can win the game, you can go with minmax. But there are too many other complicated algorithms you can implement. Here is an small list:

• If you do have an idea about what would result in a player win a game, you can directly implement that idea. This will result in human like behavior, while giving other players a chance to win.
• As you said you can go with a min-max tree, but you can also use branch and bounding to reduce searching area. As you said having 90 possible moves is a little bit to high!
• You also can use sampling and for every move approximate an score you might get. To explain it more you pick a valid move, and for that valid move predict what the board might look like after 10 or 20 random moves. Use those data to estimate how good that move is relative to other moves.
• Also you can use an scoring system giving score to each valid board state. Those scores doesn't need to be precise, or exactly the score AI will get if he plays that way but they're only an approximation of how much score AI will gain until the game finishes. and use a greedy algorithm to always do the best move possible now.

You can also combine those algorithms, for example for late game that number of valid move are very limited you can go for a simple min-max tree. But for the early game scenarios you might want to implement faster algorithm like sampling or scoring. you also can provide sampling mechanism by better searching method, such as picking moves with higher heuristic values each turn instead of some random moves.

• thanks for your ideas, I will probably aim for a combination of them. May 2, 2012 at 12:22

No hard game theory exist for interactive games with more that 2 sides. Some multi-side games still allow a fair amount of skill, but there is no well defined optimal play.

Anything Gomoku-like however completely fall apart, since players tend to always pick on the strongest opponent there is no advantage of getting ahead.

Min-max simply ain't defined for such games since there is no way of telling how the opponents will prioritize.

• you can use same minmax algorithm to determine your enemies priorities. May 1, 2012 at 2:42
• @Gajet You may be able to use the same algorithm, but it's not minmax, and there is no similar measure for its correctness. May 1, 2012 at 7:51

The problem using minmax in your circumstances is that you're unlikely to get enough depth to make a significant improvement over a simple static evaluator - consider that a 5 ply search is necessary to see your position after all oppenent's responses.

A UCT search might work very well.