What algorithm would you use to solve a very large tic-tac-toe game?

Question

A small (3x3, 4x4) tic-tac-toe can be easily solved by considering all the cases. But for example, you have a 30x30 tic-tac-toe. What algorithm would you use to decide the next best move in that case?

Minimax + alpha-beta pruning is one way that I know.

Is there some other way that is more efficient/not more efficient but cooler?

---

I know it would not be a very interesting game to play. I said 30x30 just to ask what I wanted to i.e. which algorithms work best at these sort of games where the number of cases to consider for a perfect solution is very very high and thus not feasible.

Answer 1

I don't think this is probably a very fruitful problem. Reason being:

• If the number of marks in a row you need to win is high, the game will (it seems to me) be drawn at any reasonable level of skill, because it's much easier to prevent a possible victory than to achieve one yourself. For example, if you need 20-in-a-row to win on a 30x30 board, all you need to prevent victory is a mark on each row and column roughly near the middle of the board, and a mark near the middle of each long diagonal.

• If the number of marks in a row you need to win is low, I suspect that the extra space on the board isn't going to make much of a difference in strategy, and the only sensible strategy for the second player to defend will involve playing near your opponent. As a result, some kind of alpha-beta method is fine.

Answer 2

For the game of Go, which is difficult for computers for the same reasons that are troubling you for 30x30 tic-tac-toe (note that I am not saying that 30x30 tic-tac-toe is as difficult as Go and that more direct techniques do not apply), the Monte Carlo tree search has given good results recently.