How to design a algorithm for bigger Tic Tac Toe game boards?

Question

I have created a tactactoe game in Android and it is great. But this game has 3*3 game play. In 3*3 game we can implement our manual AI(Filling corner position first) or we can use Minimax algorithm to get best move. This is great for 3*3 board. But when I tried the same algorithm for 4*4 and 5*5 the algorithm is taking a huge time to determine the best move. Hence I can not use minimax algorithm.

So what can I do now? I want to implement different level with different goal like below

Here it is 6*6 board and the goal(Consecutive symbol to win) is 5. So I want to design an ai for this dynamic board with dynamic goal.Goal can be 3,4,5 etc. How can I do that? Thanks in advance.

Answer 1

ohh boy.. I'd rather use strategies instead of actual AI paradigms on this type of game. Make a hardcore strategy, and then for lower levels of difficulty make it dumb with random moves with a p probability.

Basically your strategy is what any 5 year old would do: if the opponent is 1 or 2 steps* away from making a full line, block him. else, work on expanding one of your longest lines.

• 1 step, if his line is closed on the other end, 2 steps if his line is open on both ends.

Of course, you might trick this strategy if you're given the opportunity to make a cross, or develop 2 lines simultaneously. But you can make a program to watch out for that too.

But if you really want to go the AI route, why not try a genetic algorithm that saves and cumulates its results (best individuals) after each game? if calibrated correctly it will run pretty fast and then all you have to do is train it like a dog a couple of rounds.