Hash internal nodes of perft tree

[rgoomes]

Any idea how to do that? So far I can only hash leaf nodes.. Assume everything is implemented including zobrist keys with incremental update.

Code: Select all

typedef struct{
	uint64_t key;
	uint8_t nodes;
}perft_t;

perft_t table[TABLESIZE];

uint64_t perft(Chessboard *b, int8_t depth){
	if(depth <= 0)
		return 1;

#if HASH_LEAFS
	uint64_t pos = b->key % TABLESIZE;
	
	if(depth == 1 && table[pos].key == b->key)
		return table[pos].nodes;
#endif

	uint64_t nodes = 0;
	uint8_t n_moves, i;

    move_t moves[256];
    n_moves = gen_moves(moves);
    
#if HASH_LEAFS
	table[pos] = (perft_t){b->key, n_moves};
#endif
    
    if(depth == 1)
		return n_moves;
    
    for(i = 0; i < n_moves; ++i) {
        make_move(b, moves[i]);
        nodes += perft(b, depth - 1);
        undo_move(b, moves[i]);
    }
    return nodes;
}

[lucasart]

It's trivial. You hash entries are simply:

• zobrist key
• depth
• perft

I don't understnad why you are hashing leaves. What's to hash at a leaf ? (perft=1)

[rgoomes]

It's trivial. You hash entries are simply:

• zobrist key
• depth
• perft

I don't understnad why you are hashing leaves. What's to hash at a leaf ? (perft=1)

I don't think that's the case.. because I cannot return the hashed nodes if the branch that contains current node hasn't been fully searched to depth zero..

If I change my lookup code to:

Code: Select all

if(depth == table[pos].depth && table[pos].key == b->key)
      return table[pos].nodes;

and store to:

Code: Select all

table[pos] = (perft_t){b->key, n_moves, depth};

I get wrong total nodes.. What am I doing wrong?

[rgoomes]

I don't understnad why you are hashing leaves. What's to hash at a leaf ? (perft=1)

The leaves here aren't actually the real leaves but their parents. Hashing leaves was to avoid generating moves at depth 1, since this is the last depth and I can ensure that the hashed nodes are already calculated.

[Octopus]

I get wrong total nodes.. What am I doing wrong?

Maybe your zobrist keys are not distinct over all the inspected nodes.
One main goal for to run a hashed perft is to find out about such.

[rgoomes]

I get wrong total nodes.. What am I doing wrong?

Maybe your zobrist keys are not distinct over all the inspected nodes.
One main goal for to run a hashed perft is to find out about such.

No, Zobrist keys are working correctly. If I hash only the leafs I get correct results but the speedup is low.
I do understand why I get wrong total nodes if I change the code like I said because you can't just return the nodes, these nodes may have other moves until reach depth zero and I need to make them.

I just can't understand how to hash the internal nodes of the search tree..

[Octopus]

Some nodes may occur several times e.g. by move and remove of pieces.
Thus it is important in case of perft also to cover the depth inside of the
zobrist key. I did this by xoring the position zobrist by a seperate level zobrist.

[rgoomes]

Some nodes may occur several times e.g. by move and remove of pieces.
Thus it is important in case of perft also to cover the depth inside of the
zobrist key. I did this by xoring the position zobrist by a seperate level zobrist.

Isn't it easier to just add the depth to my hash table (perft_t struct), like I did above?
But yeah.. now how I use the depth? Can you show me some code?

[Octopus]

Isn't it easier to just add the depth to my hash table (perft_t struct), like I did above?
But yeah.. now how I use the depth? Can you show me some code?

There are two considerations:

a) the integrity of used zobrist keys in perft demands for a unique behaviour in generating such keys.
If you can secure that by simply adding a number, fine. I instead am using specialized zorbrist atoms
having an equal amount of zero- and one-bits. Adding a depth value to the key also might exceed the
hashing range area.

b) zobrist keys should distribute widely over the hashing area. Simply adding numbers will place them
probably as neighbours. I have a replacement sceme searching within a short range area to the original
key entry, thus your approach there would be performance killing.

I will add no code, because my hashed perft does a lot more. It additionally separates move types:

Code: Select all

XFEN 00: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
   +-*--b--c--d--*--f--g--*-+
 8 |[r][n][b][q][k][b][n][r]|  Compiled on Feb 19 2015
 7 |[p][p][p][p][p][p][p][p]|  MS Vis.Studio C/C++ 64-Bit Vers. 18.0
 6 |   :::   :::   :::   :::|
 5 |:::   :::   :::   :::   |  Break, when time >= 250.0 sec
 4 |   :::   :::   :::   :::|
 3 |:::   :::   :::   :::   |  (run with 4-fold TT hashing)
 2 |<P><P><P><P><P><P><P><P>|
 1 |<R><N><B><Q><K><B><N><R>|
(w)+-*--b--c--d--*--f--g--*-+

Ply         Moves      all [x]      [ep]     all [+]    [++]     Prom       Cstl     Time
 1:            20            0         0           0       0        0          0     0.00
 2:           400            0         0           0       0        0          0     0.00
 3:          8902           34         0          12       0        0          0     0.00
 4:        197281         1576         0         469       0        0          0     0.01
 5:       4865609        82719       258       27351       0        0          0     0.10
 6:     119060324      2812008      5248      809099      46        0          0     0.53
 7:    3195901860    108329926    319617    33103848    1628        0     883453     6.34
 8:   84998978956   3523740106   7187977   968981593  147215        0   23605205  1:29.37
 9: 2439530234167 125208536153 319496827 36095901903 6315946 17334376 1784356000 26:11.63

[rgoomes]

Isn't it easier to just add the depth to my hash table (perft_t struct), like I did above?
But yeah.. now how I use the depth? Can you show me some code?

There are two considerations:

a) the integrity of used zobrist keys in perft demands for a unique behaviour in generating such keys.
If you can secure that by simply adding a number, fine. I instead am using specialized zorbrist atoms
having an equal amount of zero- and one-bits. Adding a depth value to the key also might exceed the
hashing range area.

b) zobrist keys should distribute widely over the hashing area. Simply adding numbers will place them
probably as neighbours. I have a replacement sceme searching within a short range area to the original
key entry, thus your approach there would be performance killing.

I will add no code, because my hashed perft does a lot more. It additionally separates move types:

Code: Select all

XFEN 00: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
   +-*--b--c--d--*--f--g--*-+
 8 |[r][n][b][q][k][b][n][r]|  Compiled on Feb 19 2015
 7 |[p][p][p][p][p][p][p][p]|  MS Vis.Studio C/C++ 64-Bit Vers. 18.0
 6 |   :::   :::   :::   :::|
 5 |:::   :::   :::   :::   |  Break, when time >= 250.0 sec
 4 |   :::   :::   :::   :::|
 3 |:::   :::   :::   :::   |  (run with 4-fold TT hashing)
 2 |<P><P><P><P><P><P><P><P>|
 1 |<R><N><B><Q><K><B><N><R>|
(w)+-*--b--c--d--*--f--g--*-+

Ply         Moves      all [x]      [ep]     all [+]    [++]     Prom       Cstl     Time
 1:            20            0         0           0       0        0          0     0.00
 2:           400            0         0           0       0        0          0     0.00
 3:          8902           34         0          12       0        0          0     0.00
 4:        197281         1576         0         469       0        0          0     0.01
 5:       4865609        82719       258       27351       0        0          0     0.10
 6:     119060324      2812008      5248      809099      46        0          0     0.53
 7:    3195901860    108329926    319617    33103848    1628        0     883453     6.34
 8:   84998978956   3523740106   7187977   968981593  147215        0   23605205  1:29.37
 9: 2439530234167 125208536153 319496827 36095901903 6315946 17334376 1784356000 26:11.63

That's a bit complicated