Author: Robert Hyatt
Date: 13:36:44 06/13/02
Go up one level in this thread
On June 13, 2002 at 15:07:25, Dann Corbit wrote: >On June 13, 2002 at 14:45:06, stuart taylor wrote: >[snip] >>That's great! I didn't realize it was you. >>I wish you great success, and I'm sure you might eventually become no.1 on >>ssdf! (but don't waste too much time over it).] > >I think Uri has taken a very wise approach. He spent a great deal of time >optimizing a move generator. This is the heart of a chess program. A program >that has everything else excellent, but an average move generator can become >strong but not a superstar, because it will become a bottleneck at some point. > From experience, his approach is backward. Why? Because as the total program evolves, the data structures will necessarily change several times. If you spend months on one particular part, only to find later that it has to be basically re-written because of other parts of the engine, then that is time wasted. My approach was to first get everything working. Settle on specific data structures where feasible and design around them. Then, as it became obvious that certain parts of the program had become "static" then those parts could be studied and optimized carefully. The "dynamic" parts of the program (notably the search itself and the evaluation) are tough to optimize because they change significantly over a developmental cycle. For example, imagine that I had spend months on only my move generator: 4.28 54.78 3.82 1306347 0.00 0.00 GenerateCaptures 2.62 72.19 2.34 433594 0.01 0.01 GenerateMoves GenerateCaptures is 4.2% of the _total_ search time. GenerateMoves() adds another 2.62%. Total is 6.8% of the total time. Optimizing that is not really very productive. That is one reason I always recommend "get the whole thing working first" so that you will have to get the data structures right before you start doing the fine-tuning/speed optimizations... Were GenerateMoves() 75% of the total time, working on it extensively might be the right thing to do, early in the development cycle. Unfortunately for a "mature" engine, it will be a small contributor to overall speed. That's why I don't get excited about all the "perft" results... IE my book parser is probably as fast or faster than anybody's out there. I can build a book from 2M games in 10+ minutes on my quad. But so what? I didn't spend a lot of time making it fast. Others didn't either. I spent most of my time on the parts that are critical to overall engine performance. Unfortunately, a new "engine writer" really won't know what parts are going to be time-critical until the whole thing is done. And then re-done. And re-done yet again. You eventually learn enough to recognize that your current engine approach is a dead-end and you start over. Several times, as you learn more and more. Spending a lot of time on something that will most likely be thrown out is going to slow progress down... >Once you have a vast framework in place, it becomes more difficult to change the >powerplant that sits underneath. If you have chosen objects and encapsulate >everything well, it becomes less difficult, but you would have to be very clever >to have no rippling effects to doing major surgery on your move generator. It >is pretty hard to write a capture function (for instance) that does not have >intimate knowledge of the move generator. As an interesting exercise, try to >imagine a capture function that can operate identically without knowing whether >the board is in 0x88 or in bitboard format. That isn't hard at all. It wouldn't be as efficient, of course, but such encapsulation could be done if the reasons were strong enough to offset the performance loss. > >But a move generator is one of the necessary (but not sufficient) techniques on >the way to a great chess program. It must also be tactically excellent. It >must be relatively bug free (probably one of the hardest to achieve). It will >have to have an excellent search method (either pvs, mtd(f), or something equal >to it undiscovered). It will need some innovations and some positional >understanding. > >However, I think Uri's approach is a very sound one. Start with a solid >foundation and build upon that. Take incremental steps towards a goal. Since >he is also an excellent chess player, I expect that he can insert special >knowledge into his program and know when it is doing something awful (not always >as easy as it sounds for us patzers). Nothing wrong with doing it that way, so long are you are practical and don't spend a ton of time on something that is <10% of the total cost of doing a tree search.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.