Duc Tran
Reputation: 6294
Is applying Minimax possible with 4 * 4 board Tic Tac Toe or need Alpha-Beta pruning?
I've implement a 3 * 3 Tic Tac Toe game in java applying Minimax algorithm only. However, when I change the board size to 4 * 4, the program seems to hang. I wanna ask whether I should apply Minimax with alpha-beta pruning to solve this problem or it is ok with Minimax itself?
Upvotes: 0
Views: 559
Answers (1)
Kyle Jones
Reputation: 5532
IF you're trying to do a full depth search, you need to use alpha-beta. A naive 4 x 4 search tree has 16! or about 21 trillion nodes. A lot of those nodes need not be searched because the other side refutes an ancestor position by winning on the next move or creating a position that forces a win 2 ply later. Alpha-beta will let you carve away some of these search spaces without traversing them.
Upvotes: 1
Related Questions
- How to solve Tic Tac Toe 4x4 game using Minimax Algorithm and Alpha Beta Pruning
- Tic Tac Toe alpha-beta MiniMaxfor 4x4 board (JavaScript)
- Minimax won’t work with both 3x3 and 4x4 grids
- Find possible moves for Tic Tac Toe's minimax algorithm
- TicTacToe minimax algorithm returns unexpected results in 4x4 games
- Implementing alpha beta pruning in a TicTacToe minimax algorithm
- Tic Tac Toe implements with min - max method with alfa-beta pruning is there any better solution?
- MiniMax Algorithm for Tic Tac Toe failure
- Minimax and tic tac toe - is my algorithm correct?
- Twist on tic tac toe