In a small, simple game like tic-tac-toe, you can build a tree, where:
- each node is a board position
- each leaf node is a finished game with a score of +1 is X wins, -1 if O wins, 0 for a draw
- each child node is the result of a legal move from its parent
Then X is searching for a move which will maximize the minimum result, knowing that O will search (on his subsequent turn) for a move which will minimize the maximum result, knowing that X will search (on his subsequent turn to that) for a move which will...
This is the minimax algorithm.
In Tic-Tac-Toe, the tree can only get 9 layers deep, and if you want to be slick, you can take advantage of some board symmetries and keep the computations and data structures manageable.
Note that for more complex games this will fail for one reason or another (chess is deterministic, but too large to handle this way; backgammon needs probabilistic techniques, etc) but many approaches are variations on this theme.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…