Game AI with the Minmax Algorithm and Alpha-Beta Pruning
In the first two topics, we saw how hard it was to create a winning strategy for a simple game such as Tic-Tac-Toe. The last topic introduced a few structures for solving search problems with the A* algorithm. We also saw that tools such as the simpleai library help us reduce the effort we put in to describe a task with code.
We will use all of this knowledge to supercharge our game AI skills and solve more complex problems.
Search Algorithms for Turn-Based Multiplayer Games
Turn-based multiplayer games such as Tic-Tac-Toe are similar to pathfinding problems. We have an initial state, and we have a set of end states, where we win the game.
The challenge with turn-based multiplayer games is the combinatoric explosion of the opponent's possible moves. This difference justifies treating turn-based games differently than a regular pathfinding problem.
For instance, in the Tic-Tac-Toe game, from an empty board, we can select one of the nine...
