TicTacToe like an AI (part II)
Search Tree space too big
In our previous approach we expanded the search tree until we reached an end game state to determine the value of intermediate states. It turns out that for all but the most trivial cases this approach is too expensive in computational time and space. We have to find ways to cope with an exponentially expanding search space.
Cutting down search space
Heuristics
This involves using a heuristic to calculate the value of a state that does not require knowledge of subsequent end states. This means we don’t have to traverse the tree all the way to the end states to know whether an intermediate state is good or not
Iterative deepening
This involves limiting how deep the search goes. Effectively multiple searches are done, each one a level deeper than the one before until end states are reached or until you hit the depth limit
Alphabeta pruning
Eliminating sections of the tree that cannot possibly give us more information is another strategy for cutting down the search space. Given two nodes to navigate, if one of them is obviously worse than the other, there is no point in evaluating the children of the one that cannot give a better solution
Problem-specific way to cut down search space
Some problems have a search space that is symmetrical and that allows us to treat positions in the search space mirrored by a symmetry axis as having a similar value.
In tic tac toe edges and corners are effectively equivalent. You can think of this as rotating the board around the center. The following all have similar value
