Author: Frank Schneider
Date: 00:27:52 07/21/99
Go up one level in this thread
On July 20, 1999 at 12:12:14, Dann Corbit wrote: >I think it would be interesting to benchmark chess algorithms: >0. Move generators -- all types >1. Alpha-Beta vs MTD(f) >2. Bitboards vs 0x88 >3. etc. > >Prepare a large crosstable and do a large number of runs with as many >implementations as possible and under as many different conditions as possible. I agree that it would be interesting to have such a table. > >Change the search time from very short searches (10 sec or less) up to half an >hour to find the bit O(f(n)) properties of the algorithms. > >A systematic study might eliminate a lot of guesswork or even tell us *where* >certain algorithms work better than others. For instance, we might use one >algorithm at a certain time control and a different algorithm at a longer time >control and yet another at correspondence chess time controls. I'm not sure if 0. and 2. can be compared like this. I see some problems: 1. It seems it is possible to write a good chessprogram in different ways using very different movegenerators, boardrepresentations, ... For example Hiarcs and Fritz are of comparable strenght but seem to use very different approaches. I guess Fritz spends a larger ratio of time for generating and doing/undoing moves, although his movegenerator is very likely faster than Hiarcs'. 2. Gromits movegeneration (0.) relies on its boardrepresentation (2.), therefore it is not be possible to combine it with any other boardrepresentation. 3. There is always a tradeoff between the information in the boardrepresentation and information computed in other parts of the program (evaluation, see). On the one hand when doing a move Gromit updates attacktables which is relatively slow. On the other hand check-detection and see are very fast. 4. There are also hardware-dependencies. Bitboard-based programs seem to gain more when moved from 32 to 64-bit processors. 5. more subtle dependencies like this: a program that generates pseudo legal moves and detects them when the king is captured will show an increase in nps when check-extensions are added, simply because there are more illegal positions in the tree. 6. The number 'xyz generates 15 million nodes after e4 e5 nf3 nc6' is is less important than one might expect, because most of the nodes in a searchtree are quiescence-nodes and that is where you have to be fast. ... I think it would be interesting to investigate what kind of boardrepresentations, movegenerators, static-exchange-evaluators, check-detectors, ... 1. are used 2. can be combined well For example I'd like to know something like - How do people who use rotated bitboards detect check? - How to detect passed pawns using a 0x88-board? - How to generate all (and only) captures using a 10x12 board without attacktables. ... Frank
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.