I have to double-check, because this is old stuff. There is no rehash on miss. Just a calculation and a store (overwrite). For convenience, this is the implementation.hgm wrote:This means you store a signature in the hash table to verify a hit,and rehash on a miss?mvk wrote:The hit rate for the imperfect hash of attacks^defenders is good enough, where attackers and defenders are just the linear combination of the piece counts, each of 12 bits if I recall correctly.
I like the idea of hashing on some difference measure of the attacker and protector set, as often equal pieces would cancel.
Code: Select all
/*----------------------------------------------------------------------+
| exchange_evaluate |
+----------------------------------------------------------------------*/
/*
* Static Exchange Evaluation (SEE).
*
* We assume that the attacker has just moved, thus the defending side
* is to move next. This function calculates the maximum retaliation that
* the defender can obtain by following an optimal exchange sequence.
*
* Input are the two piece sets, each represented by a compact word.
* Returned is the static exchange evaluation, scaled by EXCHANGE_UNIT
* for convenience.
*
* Defenders
* 14-13 12 11-0
* +-------+---------+-------------------------------+
* | 0 |last_rank| set of defending pieces |
* +-------+---------+-------------------------------+
*
* 'defenders' represents the set of defending pieces. 0 means none.
* The 'last_rank' flag indicates that the exchange occurs on the last rank.
* We assume that the defender will always capture with its least-valued
* piece. Interestingly, this is also the optimal strategy on the last rank.
*
* Attackers
* 14-13 12 11-0
* +-------+---------+-------------------------------+
* |upfront|last_rank| set of attacking pieces |
* +-------+---------+-------------------------------+
*
* 'attackers' represents the set of attacking pieces. This set can't be
* empty because of the assumption that this side has just moved.
* This set has a 2-bit field 'first' which indicates what piece moved
* just before, because that is the first to get captured by the defender.
*
* The piece encoded in 'first' is not present in the 12 bit set. The
* reason is that this allows for 3 pawns (one just moved, 2 defending)
* while the set only has space for 2 (otherwise more than 12 bits are
* needed for the set and everything doesn't fit anymore).
* Therefore in this set 0 means: one unsupported pawn.
*
* The returned result can't be negative because the side to move has the
* right not to continue the exchange sequence.
*
* The function caches earlier results for improved performance.
*/
int exchange_evaluate_fn(int defenders, int attackers)
{
/*
* Input check
*/
xassert(defenders != 0);
xassert((defenders & 0x1fff) == defenders);
xassert((attackers & 0x7fff) == attackers);
xassert((defenders & attackers & EXCHANGE_LAST_RANK) == 0);
int store = defenders & 0x0fff;
int hash = (store << 3) ^ defenders ^ attackers;
xassert(hash >= 0);
xassert(hash < 0x8000);
/*
* Hashing should be such that we can reconstruct the two inputs
* from the hash and the stored lower 12 bits of the defenders.
* There is one ambiguity allowed: which of the two inputs has the
* LAST_RANK bit set, if any.
* Verify the hashing inverse with assertions.
*/
xassert(((hash ^ (store << 3)) & EXCHANGE_LAST_RANK) ==
((attackers ^ defenders) & EXCHANGE_LAST_RANK));
xassert(((hash ^ (store << 3) ^ store) & ~EXCHANGE_LAST_RANK) ==
(attackers & ~EXCHANGE_LAST_RANK));
/*
* Consult the lookup table first
*/
unsigned short lookup = exchange_table[hash]; /* Thread-safe */
if (((lookup ^ defenders) & 0x0fff) == 0) {
xassert(EXCHANGE_UNIT == 0x0100);
return (lookup & 0xf000) >> 4;
}
/*
* Table missed, calculate exchange sequence result
*/
board_exchange_table_miss_counter++;
/*
* Value of captured piece
*/
static const int victim_value[4] = {
1 * EXCHANGE_UNIT, // pawn
3 * EXCHANGE_UNIT, // minor (bishop or knight)
5 * EXCHANGE_UNIT, // rook
9 * EXCHANGE_UNIT, // royal (king or queen)
};
int result = victim_value[ attackers >> 13 ];
/*
* Fix up a false LAST_RANK flag in some promotions captures
*/
if (defenders == EXCHANGE_LAST_RANK) {
return 0; // TODO: fix the flow of control (and cache)
}
/*
* Select next capturer
*/
if ((defenders & EXCHANGE_LAST_RANK) != 0) {
/*
* Capture with pawn and promotion
*/
switch ((defenders & 0x0fff) % RANGE_PAWN) {
case 0:
/* No pawn present... Clear the LAST_RANK flag and proceed as normal */
defenders = next_upfront(defenders & ~EXCHANGE_LAST_RANK);
break;
case 1:
result += 8 * EXCHANGE_UNIT;
defenders += (3 << 13) - EXCHANGE_LIST_PAWN - EXCHANGE_LAST_RANK;
xassert((defenders & EXCHANGE_LAST_RANK) == 0);
break;
default:
result += 8 * EXCHANGE_UNIT;
defenders += (3 << 13) - EXCHANGE_LIST_PAWN;
xassert((defenders & EXCHANGE_LAST_RANK) != 0);
break;
}
} else {
/*
* Regular capture
*/
defenders = next_upfront(defenders);
xassert(defenders >= 0);
}
/*
* Recursive evaluation
*/
attackers &= 0x1fff; /* remove the upfront piece */
if (attackers != 0) {
result -= exchange_evaluate_fn(attackers, defenders);
/*
* If result is negative, don't capture but stand pat
*/
if (result < 0) {
result = 0;
}
}
xassert(result >= 0);
/*
* Clip at +14 so that the SEE result always fits in 5 bits
* 0xfe00 -> +14 == maximum gain
* 0xf000 -> +0 == neutral with capture
* 0x0f00 -> -0 == neutral, no capture
* 0x0100 -> -14 == maximum loss
*/
if (result > 14 * EXCHANGE_UNIT) {
result = 14 * EXCHANGE_UNIT;
}
/*
* Update the lookup table and return
*/
exchange_table[hash] = (result << 4) | store; /* Thread-safe */
return result;
}
