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

For the asian 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.

Answer 2

Place the first token on row 3 column 3. If the opponent places his token on row 3, place the next token on row 2, column 3, otherwise on row 3, column 2. Your should be able to figure out the next (winning) move.

If the opponent starts, choose an empty 4x4 block and start in the middle like outlined above. If the opponent completes his triple before you, you lose.

I would dare to say, that this is an optimal strategy for 4x4 boards and above.

Answer 3

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 4

Wouldn't it be alright to use a greedy algorithm that searches the neighboring space of the last move and tries to put down a block in any empty space inline with an adjacent opponent piece? As long as the player can't win, you sort of do win.

Answer 5

Alpha Beta is absolutely the best thing you can use. Importance in Alpha beta is in its evaluation function. Which not return only 1/0/-1 (win/nothing/lost) (from one player point of view) but also qualty of position.

Check this article (he uses tic-tac-toe but mostly chess as example game) http://www.fierz.ch/strategy1.htm

Answer 6

You can use Rule-based system

Rules are faster then any tree search algorithms and can be mixed with them. You can create rules by yourself or use (for example) a Genetic algorithm

Answer 7

Take a look at Gomoku or Five in a row. There are a number of general strategies on the web. The wikipedia article also has a good paper on threat based search with gomoku that you might look at.