transposition tables

[flok]

is 1-2% in 7 plies/ply's a reasonable value?

This 1-2% is a bit misleading. What I meant was: of every node it visits(!), for 2% of them the tree below it is not visited.
If I look instead at the number of total nodes visited, the difference is a lot bigger.
In the following output, you see what the program did in response to e2-e4:

without transposition tables:

Code: Select all

Depth reached: 8 (thread: main)
Nodes/s 97983
Total nodes searched: 49534383
Time searched: 505540ms
Best move: E7-E5 (20)
extensions: 67791

with transposition tables:

Code: Select all

Depth reached: 8 (thread: main)
Nodes/s 65561
Total nodes searched: 10862875
Time searched: 165690ms
Best move: D7-D5 (20)
extensions: 24034, transposition table hits: 184364

so that is 78% less nodes visited with 8 plies.
This is with a tp-table of 26843545 entries.

[jdart]

I think what you want to measure is what is usually called the "hit rate".

This (for me, anyway) is the number of hash probes that result in a position being found in the table, divided by the number of total probes.

(For this purpose it doesn't matter if the hash result produces a cutoff, or is valid based on the depth criteria).

--Jon

[syzygy]

I differed from the wikipedia(http://en.wikipedia.org/wiki/Zobrist_hashing) implementation by also including the "first move"-status of a piece.

Why? To avoid useful transposition hits and lower the effectiveness of the transposition table?

Because you need to know if a king is still allowed to do castling.

Ok, if it only and exactly takes care of castling rights then this is not really different (if at all) from normal Zobrist hashing.

Locking hash entries is a waste of time.

Won't that give interesting effects in a multithreaded search?

As long as your engine doesn't crash or gets confused upon a collision, any effects are a million times less noticeable than the effect of slowing down the search by locking (even if the slowdown effect would be small).

There is no need to make the hash key positive by and'ing with 0x7f...f.

If I don't do that, the module might return negative values. A long in java is always signed.

I suppose what you mean is that "hash % nTableElements" may be negative if hash is negative. That can be solved by setting nTableElements to a power of 2 and replacing the module by an and-operation. Ok, no big deal of course.

It is not efficient to have separate arrays for key / score / depth (/ move).

Java does not have structs. I could use class for it but that would only use more memory.

I guess you're right. Java doesn't have arrays of objects, only arrays of object references... Reminds me of one of the reasons I don't use Java - I don't want a language to artificially restrict me in making use of the machine's hardware.

I could sacrifice a couple of bits from the long (64b) value and use that to store the score/depth but that would increase the chance for hash collisions.

If Java had a 16-byte scalar type, the solution would be to use an array of those. Using two arrays of (8-byte) longs is possible, but still not very efficient.

[flok]

v

I differed from the wikipedia(http://en.wikipedia.org/wiki/Zobrist_hashing) implementation by also including the "first move"-status of a piece.

<...>
Because you need to know if a king is still allowed to do castling.

Ok, if it only and exactly takes care of castling rights then this is not really different (if at all) from normal Zobrist hashing.[/quote]

Castling, and pawn first moves. Hmmm, that might be a bit redundant as a pawn on its base-line implicitly tells you that it can do a double-move.

I also did it for en-passant but that is not correct I realise now: I need to look at the move and see if it is a double-move and set the bit for that.

Locking hash entries is a waste of time.

Won't that give interesting effects in a multithreaded search?

As long as your engine doesn't crash or gets confused upon a collision, any effects are a million times less noticeable than the effect of slowing down the search by locking (even if the slowdown effect would be small).

Hmmm. Feels a bit pentium-bug alike. Because those incorrect scores end up in the transpostable so they might get re-used later on and re-introduce that incorrect score in a situation where e.g. only 1 score-point makes a big difference.

There is no need to make the hash key positive by and'ing with 0x7f...f.

If I don't do that, the module might return negative values. A long in java is always signed.

I suppose what you mean is that "hash % nTableElements" may be negative if hash is negative. That can be solved by setting nTableElements to a power of 2 and replacing the module by an and-operation. Ok, no big deal of course.

Yeah I moved the AND now to the code which initializes the zobrist table.

[syzygy]

As long as your engine doesn't crash or gets confused upon a collision, any effects are a million times less noticeable than the effect of slowing down the search by locking (even if the slowdown effect would be small).

Hmmm. Feels a bit pentium-bug alike. Because those incorrect scores end up in the transpostable so they might get re-used later on and re-introduce that incorrect score in a situation where e.g. only 1 score-point makes a big difference.

You have to realise that your search tree is full of inaccurate scores anyway, much much much worse than the pentium FDIV bug. It took one and a half year before the first person (outside Intel) noticed the bug, while even top engines are still losing matches while playing white on a daily basis.

A few incorrect probes deep in the tree (and 99.9999% of the nodes are deep in the tree) have 0.0000001% chance of backing up to the root. Gaining 0.1% speed offsets this easily.

See also here.

There is no need to make the hash key positive by and'ing with 0x7f...f.

If I don't do that, the module might return negative values. A long in java is always signed.

I suppose what you mean is that "hash % nTableElements" may be negative if hash is negative. That can be solved by setting nTableElements to a power of 2 and replacing the module by an and-operation. Ok, no big deal of course.

Yeah I moved the AND now to the code which initializes the zobrist table.

That's possible too, but now you lose 1 bit that you were using to distinguish positions from each other.