bennett-zhang
commented
5 years ago Hello, @rbstrachan,
I'm delighted that you are interested in my program.
The "Impossible" difficulty setting is named as such, because it is the hardest difficulty level that I implemented in the program.
The program uses the minimax algorithm with alpha-beta pruning in order to create a search tree of possible moves, then evaluates the state of the game after each move and picks the move which scores the highest. It's possible to make the AI even smarter by bumping up the number of moves it forecasts, however in doing so, this causes the algorithm to run exponentially slower. The "Impossible" difficulty setting was the sweet spot that allowed my AI to consistently outperform similar programs I found online, while maintaining exceptional performance.
To evaluate the game state and determine how well each player is doing, the program looks at every possible "line", that is, row, column, or diagonal. If the line contains only X's or only O's, the line is assigned a score based on the number of X's or O's it contains. Otherwise, the line's score is set to zero. Every time a move is made inside of a cell, the lines containing that cell have their score updated. This allows the AI to evaluate how well a move performs compared to other possible moves.
You can play a working demo of the game at: http://ultimate-t3.herokuapp.com/
Hi @bennett-zhang,
I am just curious to know how the AI knows what the best possible move is on the "Impossible" difficulty. I am currently studying the mathematics of ultimate-t3 and I am very curious as to the strategy of the AI.
Thankyou in advance, @rbstrachan