« Tooting Blankenhorn |
Main
| Cable TV Regulation »
November 21, 2003
Man Vs. Machine, Con't
Posted by Arnold
One of the people on the feedback forum for my essay on the Kasparov-X3D Fritz chess match pointed to a very helpful article from the Wikipedia.
Nalimov Endgame Tablebases, which use state of the art compression techniques, require 7.05 GB of hard disk space for all five-piece endings. It is estimated that to cover all the six-piece endings will require at least 1 Terabyte. Seven-piece tablebases are currently a long way off.
These are databases that cover endgames that can provably result in either a checkmate or a draw. I have a different suggestion.
Suppose that we define the objective to be not to obtain a provable win but to get the opponent to resign. For that purpose, you would want a database of positions in past high-level games in which one player resigned. When you evaluate a sequence of moves, you compare the end result to that database to see whether it leads to a position where the player would resign.
In choosing a move at, say, move 20, the computer would look ahead at a depth of, say, 20 moves, to move 40. Of all the moves to make at move 20, it chooses the one that leads to a position at move 40 that most closely resembles a position in which the opponent would resign, based on the characteristics derived from the database.
I assume that someone has tried that sort of thing.
Comments (5)
+ TrackBacks (0) | Category: Moore's Law
- RELATED ENTRIES
- › test entry
- › Taking a Break
- › Moore's Law and Military Technology
- › Biotech and Sports
- › I'll take Ohio
- › Email Innovation?
- › 99-cent rip-off
- › If Brad DeLong called me stupid
1.0
1. Foolish Jordan on November 24, 2003 09:18 AM writes...
I think you'll find in general that "positions similar to where somebody resigned" is not particularly useful because there are too many reachable resign-worthy positions that aren't "similar" to any of the others.
But, more importantly, any chess computer worth it's salt already knows that a position bad enough for a master player to resign is already an extremely good position for the other side.
Chess computer designers are always on the lookout for "characteristics" which don't just determine whether a position is a resign or not, but anything which can tell you the difference between an even game and a small advantage.
Permalink to Comment2. Arnold Kling on November 24, 2003 09:50 AM writes...
>Chess computer designers are always on the lookout for "characteristics" which don't just determine whether a position is a resign or not, but anything which can tell you the difference between an even game and a small advantage.<
Then the designers are wasting processing speed. At the margin, computers will play better if they look ahead farther, not if they try to come up with more subtle ways to evaluate a position. I will take a crude evaluation system and a 20-move look-ahead over a sophisticated evaluation system with a 12 move look-ahead any day.
Permalink to Comment3. John Thacker on November 24, 2003 12:07 PM writes...
Then the designers are wasting processing speed.
At the margin, computers will play better if they look ahead farther, not if they try to come up with more subtle ways to evaluate a position. I will take a crude evaluation system and a 20-move look-ahead over a sophisticated evaluation system with a 12 move look-ahead any day.
Not necessarily. At the margin, a better evaluation system is extremely cheap in processor time, whereas expanding the search tree is very expensive. Much more expensive than in Othello, where the number of moves is much more limited.
In addition, in the early stages of the game, you need a sophisticated evaluation system to be able to judge various positions, or at least some kind of opening book.
Permalink to Comment4. Arnold Kling on November 24, 2003 02:14 PM writes...
Of course you need an opening book. The computers use book openings in Othello as well. That doesn't mean the computer always uses the same opening. It chooses randomly from among playable openings.
Even if evaluation is "cheap," you get what you pay for. Ultimately, look-ahead is everything. Evaluation should be simple and pattern-based, in my opinion.
Permalink to Comment5. John Thacker on November 24, 2003 03:05 PM writes...
>Even if evaluation is "cheap," you get what you pay for. Ultimately, look-ahead is everything. Evaluation should be simple and pattern-based, in my opinion.<
Oh, certainly in the long run look-ahead is everything. The problem is that look-ahead really only improves with Moore's Law, with new hardware. It doesn't leave much for the programmers to do. In the short run, it makes sense at the margin to try to find more efficient evaluations.
In the game of chess, a more accurate evaluation can certainly be worth 8 moves of look-ahead or more, depending on exactly how far one can look ahead. Kasparov's 3rd game win over Fritz is a prime example of this. The simplest possible evaluation is "am I mated or not?," followed by ones involving the total value of pieces left on the board. Kasparov had achieved a winning position, but it would not have been obvious to an extremely simple evaluation scheme even with more moves of look-ahead. However, to humans, who usually use complicated evaluation schemes to compensate for their lack of brute force calculations, it was obvious. Thus the 3rd game was a clear victory for board evaluation over look-ahead. (And certainly other games where computers have one have demonstrated the superiority of look-ahead in certain situations.)
In the short run, there are effective ways for good human players to beat computers through anti-computer chess strategies if the evaluation scheme is particularly simple. Better evaluation schemes do improve the performance right now. But it's not a situation of 8 more moves of look-ahead. Evaluation costs close to nothing compared to the cost of expanding the search tree by one more move. In most cases, you might get maybe one more move of look-ahead, and it wouldn't be worth it.
There's certainly a turning point, where processors become fast enough that smarter evaluation is no longer efficient, and brute force a more effective use of resources. It's arguable that it would even now be a more efficient use of programmer time for them to do something else. But people want to have better chess programs now.
Permalink to Comment