Information Technology Reference
In-Depth Information
a game where both players can force a tie or better (as in tic-tac-toe);
a game where the player who plays second can force a win (as in Boxes or Race
to 21);
a game where the player who plays first can force a win (none considered).
What does this mean? For a game of type 1, if your opponent does not make a
mistake, you will not win no matter what you do. For a game of type 2, if you play
first and your opponent does not make a mistake, you will not win no matter what
you do. For a game of type 3, if you play second and your opponent does not make a
mistake, you will not win no matter what you do.
So why should you even bother to play games like these? You could simply do the
following:
?- initial_state(S,P), win_move(S,P,Move).
This would tell you, once and for all, what a proper first move should be. Then you
could find a proper second move, and so on. Where is the fun in playing?
The answer is that for sufficiently complex games, it cannot be determined what
the best first move is once and for all because the game trees are too large to explore
fully:
For checkers, the game tree is estimated to have 10 70 nodes.
For chess, the game tree is estimated to have 10 120 nodes.
For Go, the game tree is estimated to have 10 750 nodes.
So the win_move predicate as written here is practical only for very small games. For
big games, finding a best move must be possible without examining the entire game
tree. This is why playing a game like chess remains challenging, and why it is still not
known whether white (who plays first) can guarantee a win. (In 2007 checkers was
solved by Jonathan Schaeffer and his team. It is a type 1 game like tic-tac-toe: both
players can avoid losing.)
10.3.1 Numerical game trees and minimax
This section considers a second general game player, one that can decide on a best
move without looking at the entire game tree. For this purpose, it is useful to imagine
a numerical game tree similar to the one in figure 10.3 except that numbers are put on
the leaves of the tree.
From now on, the two game players will always be called Max and Min, and a
big positive number (say, 999 ) indicates that Max wins the game, and a big negative
 
Search WWH ::




Custom Search