Move Tables - explain as if I'm five.

[hgm]

The chances that your keys would cluster so much to the end of the table that they would cascade to 150 is actually astronomically small. but I admit this was just a guess, and you could still make it larger to be absolutely sure. Wrapping would also give absolute protection against overflow, at the expense of an AND instruction. I guess one would have to count on more than 100 ply: the game history can already contain 99, and you have to add the maximum depth of the search to that.

Note that the code as I gave it is buggy, because it can use repetition uninitialized. In real life I don't use that flag at all, but jump a goto to behind the Make/Search/Unmake code in stead of the break.

The disadvantage of this method is that the accesses scatter over the table, leading to higher cache footprint. The conventional linear search always searches the entries at the tip of the list, and frequent null moves would screen the bulk from being probed in most of the tree. A micro-optimalization could be to not repTab a pointer in stead of an array, and set it to point to an (initially empty) secondary table for every irreversible move you make in the tree (and restore the original value on UnMake). That way you won't have to drag along the game history after the first irreversible move, so you could use a tighter table. Of course it is also not really needed to use the full 64-bit key; probably 3 bytes would already be fine (and then 1 byte for the ply number), and reduce false positives to an acceptable level (together with the 7 bits used for the index). So two tables of 128 x 4 bytes (or 128 char + 128 int) would be fine, and during almost all the search you would only use one of them. And 640 bytes should be quite affordable as permanent L1 resident.

[hgm]

What about SMP search? During the split() operation you would need to copy the entire repetition hash structure. It is way more costly than to copy just a few entries from a list of keys (since long chains of reversible moves are rare in the search tree, most of the time the rule50 counter is some small value, say <= 10).

The way I would do SMP would only need to copy the move list of the current branch. The table would be built in the threads private memory as a side effect of performing the moves.

[wgarvin]

This file contains a description of GNU's new move generation algoritm.
Copyright (C) 1989 Free Software Foundation, Inc.

This file is part of CHESS.

Its worth noting that the performance characteristics of typical CPUs have changed radically since 1989. The first 80486 came out in 1992. On its predecessor the 80386, every instruction took a minimum of 2 cycles to execute because it didn't have hardware to detect AGIs. It was a shallow-pipeline [edit: 5 stage, IIRC], in-order chip with a throughput of 0.5 instructions/cycle or less, and at the speeds chips ran at back then, a cache miss was only a couple of cycles. So table-driven techniques with long data dependencies were competitive back then (e.g. game developers evaluated functions like "sin" and "cos" by doing memory lookups with a big table). Nowadays, chips achieve throughput of >2 instructions/cycle, are aggressively out-of-order (so latency is determined mostly by data dependencies) and an L2 cache miss delays instruction(s) that depend on it by dozens of cycles. Nowadays, "sin" or "cos" would be evaluated by a dozen SSE instructions and still run faster than the table-driven version.

My point is simply this: don't implement this table-driven thing expecting it to give you a big performance boost!

A mispredicted branch costs something, but a cache miss often costs more. Something like 0x88 move generation seems pretty hard to beat on modern hardware, even with the kinda-unpredictable branch. To get fast code, an important thing is to try and avoid long dependence chains between the instructions. Doing a bunch of small calculations that don't depend on each other is much faster than doing a long chain of small calculations where each one depends on the result of the previous one. Independent calculations can get executed in parallel, and re-ordered to hide delays from cache misses etc. Dependent calculations can't run until the results they depend on are ready, and that's why the power of modern CPUs is often less than 50% utilized, as they encounter a bunch of cache misses and run out of other useful stuff to do while they wait for that data to arrive from the cache.