Remember last entry where I was talking about depth-first vs. breadth-first searching when trying to find the best chess move? Well, that particular tickled my organic memory banks, and I soon remembered that there's a section of Godel, Escher, Bach that expands and elucidates this topic. Computer, begin expansion and elucidation!
A classic example of a recursive procedure with parameters is one for choosing the "best" move in chess. The best move would seem to be the one which leaves your opponent in the toughest situation. Therefore, a test for goodness of a move is simply this: pretend you've made the move, and now evaluate the board from the point of view of your opponent. But how does your opponent evaluate the position? Well, he looks for his best move. That is, he mentally runs through all possible moves and evaluates them from what he thinks is your point of view, hoping they will look bad to you. But notice that we have now defined "best move" recursively, simply using the maxim that what is best for one side is worst for the other. The recursive procedure which looks for the best move operates by trying a move, and then calling on itself in the role of opponent! As such, it tries another move, and calls on itself in the role of its opponent's opponent---that is, itself.This recursion can go several levels deep---but it's got to bottom out somewhere! How do you evaluate a board position without looking ahead? There are a number of useful criteria for this purpose, such as simply the number of pieces on each side, the number of types of pieces under attack, the control of the center, and so on. By using this kind of evaluation at the bottom, the recursive move-generator can pop back upwards and give an evaluation at the top level of each different move. One of the parameters in the self-calling, then, must tell how many moves to look ahead. The outer-most call on the procedure will use some externally set value for this parameter. Thereafter, each time the procedure recursively calls itself, it must decrease this look-ahead parameter by 1. That way, when they parameter reaches zero, the procedure will follow the alternate pathway---the non-recursive evaluation.
- Hofstadter, p. 150-151
It goes without saying that if you haven't read GEB, we probably can't be friends.
One point that's not in that selection is how, while there are useful criteria for evaluating a board position without looking ahead, each specific criterion isn't that useful. That is to say, only a stupid chess program would select a move based solely on the number of pieces on each side. (I say that because, going only by that metric, 4 pawns + 1 king implies a stronger position than 1 rook + 1 queen + 1 king. I am a chess moron and even I wouldn't take that trade.)
The reason I've been on a chess tangent lately is because, for a while, I was working on a chess program. The part that Hofstadter's discussing here, weighing the strength of a potential move, is the part where I had a lot of trouble. Each metric he lists (number of pieces, pieces under attack, control of the center) is useful, but depending on how the application weighs each one (and several others), it gets very different optimal moves. If anyone has any good resources on weighing these factors when calculating the strength of a move, please let me know. (Also let me know if you have good resources on free money.)
Posted by Cody at January 17, 2007 09:05 PM