The little pseudo-code I gave in the previous entry is a pretty straightforward algorithm to determine the result of a game state. Nevertheless, that is not quite how I do it. It actually had never occured to me to implement the program this way, and now that I have thought about the reasons, I can give you two.
First of all, it is not sufficient for me that my program tells me the result of a state: I need it to be able to prove what it claims. By this I mean that taking on the role of the player to move in that state, the program must be able to achieve the claimed result against any opponent, against any sequence of moves; and on the other hand, it must be able to prove that a better result can always be prevented by the opponent. This is a pretty abstract formulation, so let me be more concrete. Suppose that we are in a state where it is White's turn to move. If the program says that White will win, proving this means providing a move, and (recursively) proving that the state after the move is also a win for White. To prove a draw result, it has to be able to indicate a move, proving that the state after the move is a draw, and also proving that none of White's moves will bring her victory. Finally, Black's win can be proven by showing that the state after every single one of White's moves is a loss for her.
Maybe I'm talking a bit too much about the concept of proving a result, but I'll just describe it from another aspect. Suppose that the program has solved the initial state of a game. If it turns out to be a win for White, the fact that my program can prove this claim means that by playing White, it can always win, against anyone, no matter what. In case of a draw, my program playing White can always achieve at least draw (so it will never lose), but this alone isn't enough, it needs to be shown that White has no winning move. Proving this means that the program has to also be able to achieve at least a draw when playing Black. Finally, if chess is actually winnable by Black, then of course my program must be able to win with the black pieces. And one last thing: when the program is actually playing one of these games, I want it to be able to give the correct moves in a very short time, basically using some look-up method, and not by performing a search like chess engines do. This would not be possible using the simple algorithm.
The second reason against it is that there are a lot of possibilities in a game. And I mean lot. I did say that I disregard any actual time and storage requirements, but still, there is one significant way of reducing the size of the work needed to prove results that I won't ignore. And it is to avoid calculating the result of a state multiple times.
Let us consider chess. Suppose that, after ten years of work, the program has finally obtained the result of the state after moves 1. e2-e4, e7-e6; 2. d2-d3, d7-d5. Suppose also that later the program finds itself at a point where it needs the result of the state after moves 1. e2-e4, d7-d5; 2. d2-d3, e7-e6. This is the exact same state as the previous one, but the naive little algorithm doesn't know that, and spends another ten years wth this state. I definitely want to avoid this. Now let me go one step further. There are also states that are, although different, similar enough so that the proof the program finds for the result of one is applicable to the other. I call this relationship either symmetry or equivalence. Reversi is an excellent example. In the starting position, White has four possible moves, but the resulting positions are symmetrical, basically the same. You just have to apply a transformation to the board (a rotation or a reflection) to get one from the other, and the proof for one is applicable to the other by applying the same transformation to the moves themselves.
So these were my two needs: the ability to prove claims about results of game states, and the ability to avoid computation of equivalent states. Next time, I'll describe how I've built GameCracker with these requirements in mind.
Nincsenek megjegyzések:
Megjegyzés küldése