Author: Robert Hyatt
Date: 06:22:13 02/10/98
A while back, we had a short discussion about two approaches to handling the "move list" in a chess program. I explained that I have a large move_list[N] array, with a pointer for each ply last[ply] that points to the last move for that ply (plus 1). So that ply N's moves lie between last[N-1] and last[N]-1 inclusive. I did this to handle the wildly varying number of legal moves. But there was another reason as well. In the Q-search, where very few moves are produced per ply (*if* you only generate capture moves of course, or if you only consider a sub-set of valid moves) the above seems to be a better approach from a performance perspective. Because when one ply has only 3 moves, and you access any one of them, you load the other two in cache, plus moves from the previous and next plies as well (8 words are fetched on Pentium machines and most others, although some have an even longer cache line-size such as the alpha). I tested the idea of adding "int move_list[256]" as a local declaration in Quiesce() and things slowed down a tad. When a friend of mine ran this on a simulator, he found this had a higher frequency of cache misses than what I was doing before, which wasn't a surprise after I thought about it. In short, what seems simple sometimes turns out to hurt performance. As I said, the *single* most important thing to do on modern micro- processor architectures is to do everything possible to ensure cache hits. *every* miss is expensive. Every hit is basically free. Of course it is also slightly more efficient to have the move list declared statically as I do, rather than dynamically allocating it on recursive procedure invocations, but that appears to be minor and only impacts the first few calls as the stack space is expanded to hold this for deep searches...
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.