TicTacToe like an AI (part 1)
“AI is programming a computer to do the right thing when you don’t know for sure what the right thing is” — Peter Norvig
As I mentioned before, a mainstay of Artificial Intelligence is the idea of constructing a problem space and using search to find a solution. For most interesting problems, the space can be so large that searching it would take more time than is available in the universe so we apply “tricks” to cut down on how much of the space we have to search.
Adversarial search strategies are used in multi-agent environments where two or more agents are in competition a.k.a. games. The most common games studied in AI are deterministic, turn-taking, two-player, winner-takes-all games in fully observable environments.
The search space can naturally be expressed as a tree structure, with a child node generated to represent the result of each action permissible by the game rules from the state represented by the parent node. For turn-based games each level of the tree shows the possible outcomes for a specific player’s turn. Leaf nodes represent game endings.
Minimax algorithm
A player MAX can safely assume that the opponent MIN will always make an optimal decision. MIN’s optimal decision corresponds to the action that will give MAX the worst outcome. This way we cover the worst case scenario and ensure that our algorithm is guaranteed to give the best result.
The tree is navigated with depth-first search.
We assign a score to leaf nodes (game endings) depending on the outcome
- 1 if MAX wins
- -1 if MIN wins
- 0 if the players draw
This score is propagated to a parent node once all it’s children’s values have been determined. For a MAX node the value is the max of it’s children, For a MIN node the value is the minimum of it’s children to reflect that the opponent will choose the best move from their perspective.
The visualization at the top shows only a section of the search tree from Tic Tac Toe as the full tree gets pretty big, making it difficult to follow what is happening. The size of the search tree also means that computing the optimal move can be time-consuming, or even downright intractable, with minimax without some modifications. I will cover these in part II.
The nodes with > are MAX nodes and < are MIN nodes. Ass soon as we reach a leaf node we know the score and this gets propagated up from children to parent according to MIN/MAX nature of parent as soon as all the children’s score is known
Proceed to Part II:
https://medium.com/@petergelderbloem/tictactoe-like-an-ai-part-ii-4f10cc800c07