Newbie needs help: the TT breaks my PV scheme

[P. Villanueva]

I've been working several months in my own chess engine: RuyLopez. Now it has a transposition table but it doesn't work well.
The problem is that sometimes the PV is not updated, like in the next examples:
First is a search using TT (semi-filled) , second a search without TT, and third a search with the TT full. In both first and third the PV is not updated as it should. In the third case the search returns a illegal move.

[d] 8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1

Code: Select all

Jug  Nodos  Valor  Tiempo  Variante principal
  1     15    104    46ms  b4f4
  2    180     99    46ms  b4f4 h4g5 f4f7
  3   1088    107    62ms  b4f4 h4g5 f4f7 h5h2 f7c7 h2g2
  4  15394     55    93ms  b4f4 h4g3 f4f7 h5c5 f7g7 g3f2 e2e4 f2e3
  5  24130     55   109ms  b4f4 h4g3
  6  80981     29   234ms  b4f4 h4g3 f4f7 h5c5 f7g7 g3f2 e2e4 c7c6 a5b6 c6b5
  7   300K     25   639ms  b4f4 h4g3 f4c4 h5h7 b5b6 c7b6 a5b6 h7h2 b6c7 h2g2 c7d6 g2e2
  8  1004K     31  1856ms  b4f4 h4g3 f4c4 h5h7 b5b6 c7c5 a5b5 g3g2 b5c6 h7h6
  9  3134K     27  5444ms  b4f4 h4g3 f4c4 h5h7 b5b6 h7h5 a5b4 c7b6 c4c6 h5h2 c6d6 h2g2
 10    10M     36   17seg  b4f4 h4g3 f4c4 h5h7 b5b6 h7h5 a5a6 c7b6 a6b6 g3g2 b6c6 g2f2 c4e4 h5h6
Nps: 595000
TT hits: 10%
Movimiento de RuyLopez: b4f4

Jug  Nodos  Valor  Tiempo  Variante principal
  1     15    104    47ms  b4f4
  2    180     99    47ms  b4f4 h4g5 f4f7
  3   1104    107    62ms  b4f4 h4g5 f4f7 h5h2 f7c7 h2g2
  4  12625     53    93ms  b4f4 h4g3 f4f7 c7c6 f7g7 g3f2 a5b6 c6b5
  5  32298     55   125ms  b4f4 h4g3 f4f7 h5c5 f7g7 g3f2 e2e4 f2e3
  6   124K     29   234ms  b4f4 h4g3 f4f7 h5c5 f7g7 g3f2 e2e4 c7c6 a5b6 c6b5
  7   548K     25   733ms  b4f4 h4g3 f4c4 h5h7 b5b6 c7b6 a5b6 h7h2 b6c7 h2g2 c7d6 g2e2
  8  2201K     31  2714ms  b4f4 h4g3 f4c4 h5h7 b5b6 c7c5 a5b5 g3g2 b5c6 h7h6
  9  9464K     27   11seg  b4f4 h4g3 f4c4 h5h7 b5b6 h7h5 a5b4 c7b6 c4c6 h5h2 c6d6 h2g2
 10    36M     36   42seg  b4f4 h4g3 f4c4 h5h7 b5b6 h7h5 a5a6 c7b6 a6b6 g3g2 b6c6 g2f2 c4e4 h5h6
Nps: 854000
Movimiento de RuyLopez: b4f4

Jug  Nodos  Valor  Tiempo  Variante principal
  1      1     36     1ms
  2      2     36    16ms
  3      3     36    16ms
  4      4     36    16ms
  5      5     36    16ms
  6      6     36    16ms
  7      7     36    16ms
  8      8     36    16ms
  9      9     36    31ms
 10     10     36    31ms
Nps: 0
Tiempo: 31 ms
TT hits: 100%
Movimiento de RuyLopez: a1a1p

To store the PV i use a triangular array (like in TSCP) , wich is updated every time negamax() or quiesce() return a score bigger than alpha.
The TT has 10 million entries and uses an always replace strategy.
Do i need a new PV scheme? Could anyone give me some advice?
Thanks

[Zach Wegner]

I've been working several months in my own chess engine: RuyLopez.

Well, first off, that name has already been used for a private engine. Sorry.

Other than that though, welcome to the community!

Now it has a transposition table but it doesn't work well.
The problem is that sometimes the PV is not updated, like in the next examples:
First is a search using TT (semi-filled) , second a search without TT, and third a search with the TT full. In both first and third the PV is not updated as it should. In the third case the search returns a illegal move.

[d] 8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1

Code: Select all

Jug  Nodos  Valor  Tiempo  Variante principal
  1     15    104    46ms  b4f4
  2    180     99    46ms  b4f4 h4g5 f4f7
  3   1088    107    62ms  b4f4 h4g5 f4f7 h5h2 f7c7 h2g2
  4  15394     55    93ms  b4f4 h4g3 f4f7 h5c5 f7g7 g3f2 e2e4 f2e3
  5  24130     55   109ms  b4f4 h4g3
  6  80981     29   234ms  b4f4 h4g3 f4f7 h5c5 f7g7 g3f2 e2e4 c7c6 a5b6 c6b5
  7   300K     25   639ms  b4f4 h4g3 f4c4 h5h7 b5b6 c7b6 a5b6 h7h2 b6c7 h2g2 c7d6 g2e2
  8  1004K     31  1856ms  b4f4 h4g3 f4c4 h5h7 b5b6 c7c5 a5b5 g3g2 b5c6 h7h6
  9  3134K     27  5444ms  b4f4 h4g3 f4c4 h5h7 b5b6 h7h5 a5b4 c7b6 c4c6 h5h2 c6d6 h2g2
 10    10M     36   17seg  b4f4 h4g3 f4c4 h5h7 b5b6 h7h5 a5a6 c7b6 a6b6 g3g2 b6c6 g2f2 c4e4 h5h6
Nps: 595000
TT hits: 10%
Movimiento de RuyLopez: b4f4

Jug  Nodos  Valor  Tiempo  Variante principal
  1     15    104    47ms  b4f4
  2    180     99    47ms  b4f4 h4g5 f4f7
  3   1104    107    62ms  b4f4 h4g5 f4f7 h5h2 f7c7 h2g2
  4  12625     53    93ms  b4f4 h4g3 f4f7 c7c6 f7g7 g3f2 a5b6 c6b5
  5  32298     55   125ms  b4f4 h4g3 f4f7 h5c5 f7g7 g3f2 e2e4 f2e3
  6   124K     29   234ms  b4f4 h4g3 f4f7 h5c5 f7g7 g3f2 e2e4 c7c6 a5b6 c6b5
  7   548K     25   733ms  b4f4 h4g3 f4c4 h5h7 b5b6 c7b6 a5b6 h7h2 b6c7 h2g2 c7d6 g2e2
  8  2201K     31  2714ms  b4f4 h4g3 f4c4 h5h7 b5b6 c7c5 a5b5 g3g2 b5c6 h7h6
  9  9464K     27   11seg  b4f4 h4g3 f4c4 h5h7 b5b6 h7h5 a5b4 c7b6 c4c6 h5h2 c6d6 h2g2
 10    36M     36   42seg  b4f4 h4g3 f4c4 h5h7 b5b6 h7h5 a5a6 c7b6 a6b6 g3g2 b6c6 g2f2 c4e4 h5h6
Nps: 854000
Movimiento de RuyLopez: b4f4

Jug  Nodos  Valor  Tiempo  Variante principal
  1      1     36     1ms
  2      2     36    16ms
  3      3     36    16ms
  4      4     36    16ms
  5      5     36    16ms
  6      6     36    16ms
  7      7     36    16ms
  8      8     36    16ms
  9      9     36    31ms
 10     10     36    31ms
Nps: 0
Tiempo: 31 ms
TT hits: 100%
Movimiento de RuyLopez: a1a1p

To store the PV i use a triangular array (like in TSCP) , wich is updated every time negamax() or quiesce() return a score bigger than alpha.
The TT has 10 million entries and uses an always replace strategy.
Do i need a new PV scheme? Could anyone give me some advice?
Thanks

Your PV scheme is fine, many people use it, including me.

There are a few issues though. First, you always need to store a move at the root. Most people use a separate function for the root (though it's probably not that important for you right now), and I don't think anyone probes the hash in the root position. If you do decide to probe the hash in the root position, at least take the hash move and put it as the best move. It doesn't matter if you know the score for the position if you don't know what move to play!

Second, most people don't allow cutoffs in PV nodes, where alpha + 1< beta, though that is only meaningful in a PVS framework (see http://chessprogramming.wikispaces.com/ ... ion+Search).

Third, some people extend the PV with hash moves. This is a little complex, but it involves making each move in the PV to the end. Then, the hash is probed, and if there is a move there, it is appended to the PV and the process continues. Be sure to check that a move doesn't end the game or cause a repetition (in which case you will try to construct an infinitely long PV).

Hope that helps,
Zach

[bob]

One quick question: when you get an EXACT TT hit, do you stuff the current PV moves into the PV and back that up along with the TT score? That is an easy thing to forget, once you are used to your q-search backing up the PV as a normal part of what it does. But when you get an EXACT TT hit, you stop the search immediately and you have to manually save the moves in the current path to create a "short PV". Short, because it does not show the entire line leading to the score, just the PV that leads to the TT hit but nothing beyond...

[bob]

I've been working several months in my own chess engine: RuyLopez.

Well, first off, that name has already been used for a private engine. Sorry.

Other than that though, welcome to the community!

Now it has a transposition table but it doesn't work well.
The problem is that sometimes the PV is not updated, like in the next examples:
First is a search using TT (semi-filled) , second a search without TT, and third a search with the TT full. In both first and third the PV is not updated as it should. In the third case the search returns a illegal move.

[d] 8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1

Code: Select all

Jug  Nodos  Valor  Tiempo  Variante principal
  1     15    104    46ms  b4f4
  2    180     99    46ms  b4f4 h4g5 f4f7
  3   1088    107    62ms  b4f4 h4g5 f4f7 h5h2 f7c7 h2g2
  4  15394     55    93ms  b4f4 h4g3 f4f7 h5c5 f7g7 g3f2 e2e4 f2e3
  5  24130     55   109ms  b4f4 h4g3
  6  80981     29   234ms  b4f4 h4g3 f4f7 h5c5 f7g7 g3f2 e2e4 c7c6 a5b6 c6b5
  7   300K     25   639ms  b4f4 h4g3 f4c4 h5h7 b5b6 c7b6 a5b6 h7h2 b6c7 h2g2 c7d6 g2e2
  8  1004K     31  1856ms  b4f4 h4g3 f4c4 h5h7 b5b6 c7c5 a5b5 g3g2 b5c6 h7h6
  9  3134K     27  5444ms  b4f4 h4g3 f4c4 h5h7 b5b6 h7h5 a5b4 c7b6 c4c6 h5h2 c6d6 h2g2
 10    10M     36   17seg  b4f4 h4g3 f4c4 h5h7 b5b6 h7h5 a5a6 c7b6 a6b6 g3g2 b6c6 g2f2 c4e4 h5h6
Nps: 595000
TT hits: 10%
Movimiento de RuyLopez: b4f4

Jug  Nodos  Valor  Tiempo  Variante principal
  1     15    104    47ms  b4f4
  2    180     99    47ms  b4f4 h4g5 f4f7
  3   1104    107    62ms  b4f4 h4g5 f4f7 h5h2 f7c7 h2g2
  4  12625     53    93ms  b4f4 h4g3 f4f7 c7c6 f7g7 g3f2 a5b6 c6b5
  5  32298     55   125ms  b4f4 h4g3 f4f7 h5c5 f7g7 g3f2 e2e4 f2e3
  6   124K     29   234ms  b4f4 h4g3 f4f7 h5c5 f7g7 g3f2 e2e4 c7c6 a5b6 c6b5
  7   548K     25   733ms  b4f4 h4g3 f4c4 h5h7 b5b6 c7b6 a5b6 h7h2 b6c7 h2g2 c7d6 g2e2
  8  2201K     31  2714ms  b4f4 h4g3 f4c4 h5h7 b5b6 c7c5 a5b5 g3g2 b5c6 h7h6
  9  9464K     27   11seg  b4f4 h4g3 f4c4 h5h7 b5b6 h7h5 a5b4 c7b6 c4c6 h5h2 c6d6 h2g2
 10    36M     36   42seg  b4f4 h4g3 f4c4 h5h7 b5b6 h7h5 a5a6 c7b6 a6b6 g3g2 b6c6 g2f2 c4e4 h5h6
Nps: 854000
Movimiento de RuyLopez: b4f4

Jug  Nodos  Valor  Tiempo  Variante principal
  1      1     36     1ms
  2      2     36    16ms
  3      3     36    16ms
  4      4     36    16ms
  5      5     36    16ms
  6      6     36    16ms
  7      7     36    16ms
  8      8     36    16ms
  9      9     36    31ms
 10     10     36    31ms
Nps: 0
Tiempo: 31 ms
TT hits: 100%
Movimiento de RuyLopez: a1a1p

To store the PV i use a triangular array (like in TSCP) , wich is updated every time negamax() or quiesce() return a score bigger than alpha.
The TT has 10 million entries and uses an always replace strategy.
Do i need a new PV scheme? Could anyone give me some advice?
Thanks

Your PV scheme is fine, many people use it, including me.

There are a few issues though. First, you always need to store a move at the root. Most people use a separate function for the root (though it's probably not that important for you right now), and I don't think anyone probes the hash in the root position. If you do decide to probe the hash in the root position, at least take the hash move and put it as the best move. It doesn't matter if you know the score for the position if you don't know what move to play!

Second, most people don't allow cutoffs in PV nodes, where alpha + 1< beta, though that is only meaningful in a PVS framework (see http://chessprogramming.wikispaces.com/ ... ion+Search).

That's a new one on me, and I've been around long enough that there is not much "new" left to run into. Why would you not allow a cutoff _anywhere_ that it is appropriate? I have no restrictions of any kind. But more importantly, I don't understand the basic idea, in that any score >= beta, or <= alpha, whatever alpha and beta are, should cause a cutoff... Whether the result comes from the TT, or from a backed-up search result.

Third, some people extend the PV with hash moves. This is a little complex, but it involves making each move in the PV to the end. Then, the hash is probed, and if there is a move there, it is appended to the PV and the process continues. Be sure to check that a move doesn't end the game or cause a repetition (in which case you will try to construct an infinitely long PV).

Hope that helps,
Zach

[Zach Wegner]

That's a new one on me, and I've been around long enough that there is not much "new" left to run into. Why would you not allow a cutoff _anywhere_ that it is appropriate? I have no restrictions of any kind. But more importantly, I don't understand the basic idea, in that any score >= beta, or <= alpha, whatever alpha and beta are, should cause a cutoff... Whether the result comes from the TT, or from a backed-up search result.

I believe the idea came from Fruit. At least it gained a lot of popularity then, I'm sure it's been tried before. It seems illogical to me, and I tried for a very long time to avoid it. But my engine would overlook repetition draws a lot until it was too late, and not allowing cutoffs on PV nodes solved it (and made my engine significantly stronger). I tried another "proprietary" method to avoid this (read my source if you want to learn about it ), but that didn't help much, unfortunately.

How do you avoid repetition draws? I still check for repetitions before probing the hash, but I still got the same problem...

[bob]

That's a new one on me, and I've been around long enough that there is not much "new" left to run into. Why would you not allow a cutoff _anywhere_ that it is appropriate? I have no restrictions of any kind. But more importantly, I don't understand the basic idea, in that any score >= beta, or <= alpha, whatever alpha and beta are, should cause a cutoff... Whether the result comes from the TT, or from a backed-up search result.

I believe the idea came from Fruit. At least it gained a lot of popularity then, I'm sure it's been tried before. It seems illogical to me, and I tried for a very long time to avoid it. But my engine would overlook repetition draws a lot until it was too late, and not allowing cutoffs on PV nodes solved it (and made my engine significantly stronger). I tried another "proprietary" method to avoid this (read my source if you want to learn about it ), but that didn't help much, unfortunately.

How do you avoid repetition draws? I still check for repetitions before probing the hash, but I still got the same problem...

I check for repetitions first. And the problem can show up, but I see it so rarely that I don't want to cripple the search for all cases, just to work around a problem that is very rarely seen in Crafty's games... It sounds about the same as the often-mentioned ideas about "never store draw scores", "never store mate scores or bounds" and such. I've always found it better to do what makes sense from a theoretical perspective, and then solve any issues that show up in practice. I always have, and always will, store and use as much TT stuff as is physically possible, the only exception I make deals with where I begin to approach a 50-move draw in a simple ending where hash hits can hide this. I occasionally run thru the hash table and mark scores as invalid (best moves are kept however) so that they won't hide 50-move draws...

[Zach Wegner]

I check for repetitions first. And the problem can show up, but I see it so rarely that I don't want to cripple the search for all cases, just to work around a problem that is very rarely seen in Crafty's games...

It also probably has something to do with you returning draw scores on the second repetition. I used to do that, but I removed it, I think because of the same problem. I'll test with it, with also allowing PV hash cutoffs. I have way too many ideas and tweaks that little stuff like that rarely gets a chance to be tested...

...the only exception I make deals with where I begin to approach a 50-move draw in a simple ending where hash hits can hide this. I occasionally run thru the hash table and mark scores as invalid (best moves are kept however) so that they won't hide 50-move draws...

There is a better way to solve this, now. See my new thread.

[bob]

I check for repetitions first. And the problem can show up, but I see it so rarely that I don't want to cripple the search for all cases, just to work around a problem that is very rarely seen in Crafty's games...

It also probably has something to do with you returning draw scores on the second repetition. I used to do that, but I removed it, I think because of the same problem. I'll test with it, with also allowing PV hash cutoffs. I have way too many ideas and tweaks that little stuff like that rarely gets a chance to be tested...

...the only exception I make deals with where I begin to approach a 50-move draw in a simple ending where hash hits can hide this. I occasionally run thru the hash table and mark scores as invalid (best moves are kept however) so that they won't hide 50-move draws...

There is a better way to solve this, now. See my new thread.

I suppose it depends on your definition of "better". It would seem (to me anyway) that anything that prevents matching key "EXACT" entries, however infrequently it might be, is a bad idea still...

As always, the proof is in the testing. If it produces better results in matches, it's a good idea. If it doesn't...

[Zach Wegner]

Did you read my whole post?? Specifically this part:

I bring it up also because it elegantly solves the problem that Bob brought up. When the fifty move counter gets close to fifty, he runs through the hash table and invalidates old entries. Here's a better way to do this:

Code: Select all

if (fifty_count < 80) /* I.e. less than 40 reversible moves */
    path_hashkey = hashkey; /* No change, we can just accept cutoffs regardless of path */
else
    path_hashkey = hashkey ^ some_constant; /* If we are getting close to 50, then only accept cutoffs from newer searches, BUT, still use the hash move */

You can take this even further, and make the last line:

Code: Select all

path_hashkey = hashkey ^ some_constant[fifty_count - 80];

So that when the fifty move count is big, we only accept searches with the exact same fifty count.

The _only_ place this has any effect is when the fifty move counter gets big, which is the same place where you blindly invalidate the whole hash table.

[michiguel]

That's a new one on me, and I've been around long enough that there is not much "new" left to run into. Why would you not allow a cutoff _anywhere_ that it is appropriate? I have no restrictions of any kind. But more importantly, I don't understand the basic idea, in that any score >= beta, or <= alpha, whatever alpha and beta are, should cause a cutoff... Whether the result comes from the TT, or from a backed-up search result.

I believe the idea came from Fruit. At least it gained a lot of popularity then, I'm sure it's been tried before. It seems illogical to me, and I tried for a very long time to avoid it. But my engine would overlook repetition draws a lot until it was too late, and not allowing cutoffs on PV nodes solved it (and made my engine significantly stronger). I tried another "proprietary" method to avoid this (read my source if you want to learn about it ), but that didn't help much, unfortunately.

How do you avoid repetition draws? I still check for repetitions before probing the hash, but I still got the same problem...

I do not allow hash table cutoffs in the first two plies of the search.

Miguel