Leaving/Returning to Book Annoyance

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
JVMerlino
Posts: 1016
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Re: Leaving/Returning to Book Annoyance

Post by JVMerlino » Tue May 05, 2009 10:35 pm

bob wrote:In Crafty, the "search" has two parts. Part 1 is a book lookup. That code returns two moves, the first is the move the program should play according to the book, the second is the expected book reply to that move (the move to ponder). If that fails, the second part of tthe search is a normal alpha/beta search that returns a PV and score.

Since my book code returns a PV of length 2 (the book move and the book reply) I treat both results (book or search) the same. I get a PV from both, which has a move to play and a move to ponder. On occasion either can return a PV without the move to ponder. In the case of the book, that just means that the book ends after the move for the program, with no opponent move supplied. A search can also produce this result when you get a fail high and don't have enough time to get a real score back. There are ways to choose a move to ponder if you don't have one. We can discuss that if you want, although it is not related to your current question.

The point for pondering on a book move is simple. What do you do at the end of the book line? You just sit and wait until your opponent moves, only to discover you have no book move to play so you start a normal search. Why not find the opponent's book move and ponder that? If you find a book move to play, you can sit or do other things. If you do not find a book move when you ponder his book move, you can start a normal search and save some time.

I have a function, Iterate(), that is called to obtain the next move. It first tries the book, if that fails it does a normal search. This solves the issue completely.
This all makes sense, although is either a fair bit involved for the stage that my engine is at, and/or would require a bit of a rewrite.

I do have a (possibly) crude method of choosing a move to ponder in a fail high case, based on results from the previous iteration.

I'm sure I'll have plenty of other newbie questions over the coming months. Olivier's ChessWar tournament is definitely giving me plenty of inspiration and purpose to improve the engine (as well as some intense pain when bugs show up in games).

Thanks again,
jm

jhaglund
Posts: 173
Joined: Sun May 11, 2008 5:43 am

Re: Leaving/Returning to Book Annoyance

Post by jhaglund » Tue May 05, 2009 10:55 pm

JVMerlino wrote:
jhaglund wrote:IMO, take the book move, if it matches a variation within the book.

The moves within the book should be taken. That is why the book was created in the first place.

Otherwise, fclose() book at first ended variation, ExitBook(), then start the Ponder().

Have some sort of null character to decide when the book line is done, and ponder should start.

Jumping I/O of the book is generally from a book creation problem. To me, pondering should start after the book exits.

If your program can tell if it's the last move in the book, I would think it'd be safe to start pondering on your opponent's time.

if(moves_in_variation <= 1), start ponder.
Hi Joshua,

With the ProDeo book, it is possible to tell if a line has ended...sort of. But there is no way to determine if it is possible to go back into book later on.

Thanks for the reply,
jm
Why wouldn't the book have a previous move or FEN that was made to bring it back to the book?

If FEN == Next_FEN_in_book, continue book. If FEN != Next_FEN_in_book, close_book_4_good, start ponder.

Could you give a variation where this happens?

When a book is biased towards white or black's lines of play, this is generally where I see this happen. I don't like books like that for general use.

User avatar
JVMerlino
Posts: 1016
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Re: Leaving/Returning to Book Annoyance

Post by JVMerlino » Tue May 05, 2009 11:21 pm

Here are several PGNs from my speed tournament (game in 1 minute) to test pondering, which alerted me to the issue. My engine played White in all instances.

In every instance the engine hung after making one or two non-book moves, and I traced the problem to finding a book move after NOT finding a book move earlier in the game. This caused the engine to make a move based on the fact that it was pondering, then make a book move, due to some flags being incorrectly set. Therefore, it was out of sync with the actual game and lost.

1.d4 {00:00} 1...d5 {00:00 (Book)} 2.c4 {00:00} 2...c6 {00:00 (Book)}
3.Nf3 {00:00} 3...Nf6 {00:00 (Book)} 4.Nc3 {00:00} 4...e6 {00:00 (Book)}
5.Bg5 {00:00} 5...Bb4 {00:03 (Score: 0.50, Depth: 3/7)} 6.cxd5 {00:03}
6...exd5 {00:09 (Score: -0.33, Depth: 3/7)} 0-1

1.d4 {00:00} 1...Nf6 {00:00 (Book)} 2.c4 {00:00} 2...c5 {00:00 (Book)}
3.d5 {00:00} 3...b5 {00:00 (Book)} 4.cxb5 {00:00} 4...a6 {00:00 (Book)}
5.b6 {00:00} 5...e6 {00:00 (Book)} 6.Nc3 {00:00} 6...exd5 {00:00 (Book)}
7.Nxd5 {00:02} 7...Nxd5 {00:00 (Book)} 8.Qxd5 {00:04} 8...Nc6 {00:01
(Book)} 0-1

1.d4 {00:00} 1...d5 {00:00 (Book)} 2.c4 {00:00} 2...c6 {00:00 (Book)}
3.Nf3 {00:00} 3...Nf6 {00:00 (Book)} 4.Nc3 {00:00} 4...e6 {00:00 (Book)}
5.Bg5 {00:00} 5...Bb4 {00:01 (Score: -0.96, Depth: 2/5)} 6.cxd5 {00:03}
6...Qa5 {00:03 (Score: 0.48, Depth: 2/5)} 0-1

1.d4 {00:00} 1...Nf6 {00:00 (Book)} 2.c4 {00:00} 2...c5 {00:00 (Book)}
3.d5 {00:00} 3...b5 {00:00 (Book)} 4.cxb5 {00:00} 4...a6 {00:00 (Book)}
5.e3 {00:00} 5...Qa5+ {00:06 (Score: 0.27, Depth: 3/7)} 6.Bd2 {00:00}
6...Qb6 {00:11 (Score: -0.16, Depth: 3/8)} 7.Nc3 {00:00} 7...axb5 {00:12 (Score: 0.31, Depth: 2/6)} 8.Bxb5 {00:02} 8...e6 {00:14 (Score: 2.58, Depth: 3/7)} 0-1

1.d4 {00:00} 1...Nf6 {00:00 (Book)} 2.c4 {00:00} 2...c5 {00:00 (Book)}
3.d5 {00:00} 3...b5 {00:00 (Book)} 4.cxb5 {00:00} 4...a6 {00:00 (Book)}
5.e3 {00:00} 5...Qb6 {00:02 (Score: -0.99, Depth: 2/6)} 6.Nc3 {00:02}
6...axb5 {00:03 (Score: -0.53, Depth: 2/6)} 0-1

jm

jhaglund
Posts: 173
Joined: Sun May 11, 2008 5:43 am

Re: Leaving/Returning to Book Annoyance

Post by jhaglund » Wed May 06, 2009 1:28 am

In your examples,

Code: Select all

1.d4 &#123;00&#58;00&#125; 	  1...Nf6 &#123;00&#58;00 &#40;Book&#41;&#125; 
2.c4 &#123;00&#58;00&#125; 	  2...c5 &#123;00&#58;00 &#40;Book&#41;&#125;
3.d5 &#123;00&#58;00&#125; 	  3...b5 &#123;00&#58;00 &#40;Book&#41;&#125; 
4.cxb5 &#123;00&#58;00&#125; 	4...a6 &#123;00&#58;00 &#40;Book&#41;&#125;
5.b6 &#123;00&#58;00&#125; 	  5...e6 &#123;00&#58;00 &#40;Book&#41;&#125;
6.Nc3 &#123;00&#58;00&#125; 	 6...exd5 &#123;00&#58;00 &#40;Book&#41;&#125;
7.Nxd5 &#123;00&#58;02&#125;    7...Nxd5 &#123;00&#58;00 &#40;Book&#41;&#125; 
8.Qxd5 &#123;00&#58;04&#125;    8...Nc6 &#123;00&#58;01 &#40;Book&#41;&#125; 0-1
You're missing move 7. for white. Why isn't 7. Nxd5 (00:02) in your book?

Code: Select all

1.d4 &#123;00&#58;00&#125; 	  1...Nf6 &#123;00&#58;00 &#40;Book&#41;&#125; 
2.c4 &#123;00&#58;00&#125; 	  2...c5 &#123;00&#58;00 &#40;Book&#41;&#125;
3.d5 &#123;00&#58;00&#125; 	  3...b5 &#123;00&#58;00 &#40;Book&#41;&#125; 
4.cxb5 &#123;00&#58;00&#125; 	4...a6 &#123;00&#58;00 &#40;Book&#41;&#125;
5.e3 &#123;00&#58;00&#125; 	  5...Qa5+ &#123;00&#58;06 &#40;Score&#58; 0.27, Depth&#58; 3/7&#41;&#125; 
6.Bd2 &#123;00&#58;00&#125;	  6...Qb6 &#123;00&#58;11 &#40;Score&#58; -0.16, Depth&#58; 3/8&#41;&#125; 
7.Nc3 &#123;00&#58;00&#125; 	 7...axb5 &#123;00&#58;12 &#40;Score&#58; 0.31, Depth&#58; 2/6&#41;&#125; 
8.Bxb5 &#123;00&#58;02&#125;    8...e6 &#123;00&#58;14 &#40;Score&#58; 2.58, Depth&#58; 3/7&#41;&#125; 0-1
Here, you are missing black's 5th & 6th moves/FEN.

Your book function is going into an endless loop after 1 ply out of book for both sides. Something is not closing or something isn't opening when it is suppose too.

bob
Posts: 20892
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Leaving/Returning to Book Annoyance

Post by bob » Wed May 06, 2009 5:55 am

JVMerlino wrote:[quote="bobAnother idea I use, which came from Murray Campbell years ago, is to find the set of known book moves for my opponent, and remove this set from the set of legal moves he can play. I then do a short search on this remaining set, to find the "best" non-book move I can find. I then ponder this move wile waiting on my opponent. The idea is that if he plays a known book move, I have a quick response in the book. If he is now out of book, he will likely play the move my search suggests and I will already be pondering that move.

In Crafty, you turn this on by entering "mode tournament" or else putting that in the crafty.rc/.craftyrc file.
Sounds like a great idea, although isn't the data set huge? Or can Crafty only "prepare" for one opponent per run?

jm[/quote]

Not sure what you mean. This just works with the normal book. When I start a search, the first thing I do is find the best book move Crafty can play. I then generate the moves for the opponent, make and look up each one to find out which of those are known book moves. If I get a book "hit" that move is excluded, which eventually leaves me the set of moves for my opponent that do not have a book reply. I search those to find the best one, and then start to ponder with that move.

If a program doesn't play a book move, it is quite common that it will play the move pondered above.

User avatar
Bill Rogers
Posts: 3562
Joined: Thu Mar 09, 2006 2:54 am
Location: San Jose, California

Re: Leaving/Returning to Book Annoyance

Post by Bill Rogers » Wed May 06, 2009 7:13 am

Hi John
I expect my books moves to be the best for whatever side I am playing so if I can no longer find a book move I set a flag so it will not try to look for another book move after that. I do, however, take the last move that kicked me out of book and try to find an superior response to it.
Bill

bob
Posts: 20892
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Leaving/Returning to Book Annoyance

Post by bob » Wed May 06, 2009 5:31 pm

JVMerlino wrote:
MattieShoes wrote:Moving back into book is probably okay as long as rep draws are handled right. Otherwise I've seen engines get rep draws in the first 15 moves popping into and back out of book.
That's an interesting thought. It hasn't happened yet in the hundreds of games I've tested, but I think it is theoretically possible given that the book works off of FEN positions rather than a move list.

Thanks for that -- I'll keep it in mind.

jm
I have specific code in Crafty to catch this problem, or it will happen. Most likely, you will end up with a quick rep draw in your book itself, and you probably don't want to make that move unless it is the best you can do. I simply don't play book moves that lead to a 3-fold repetition, and let the search handle that instead, so that I can determine if not drawing is bad or not.

MattieShoes
Posts: 718
Joined: Fri Mar 20, 2009 7:59 pm

Re: Leaving/Returning to Book Annoyance

Post by MattieShoes » Wed May 06, 2009 8:00 pm

bob wrote: I have specific code in Crafty to catch this problem, or it will happen. Most likely, you will end up with a quick rep draw in your book itself, and you probably don't want to make that move unless it is the best you can do. I simply don't play book moves that lead to a 3-fold repetition, and let the search handle that instead, so that I can determine if not drawing is bad or not.
Does it pop out of book when 3-fold rep is possible, or does it just eliminate that response before it causes draw? It seems like the best solution would be to have the book code correctly evaluate rep draws -- if you're playing Rybka and can force a draw from within book, probably a good idea. If you're playing me, bad idea. Probably a solution in search of a problem though, no real advantage in realistic conditions.

Hmm mine doesn't have the popping back into book problem because it never goes back into book once it leaves. But it could get a draw within book anyway I suppose. Since it doesn't convert everything to a generic side to move, it hasn't happened though... Just about any un-move of a piece would pop it out of book.

User avatar
JVMerlino
Posts: 1016
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Re: Leaving/Returning to Book Annoyance

Post by JVMerlino » Wed May 06, 2009 10:47 pm

Never mind, Bob. I parsed your initial response rather stupidly, I must say.

When you said that you "find the set of known book moves for my opponent", I thought you meant that you had information about opposing BOOKS built into Crafy, and used that information to determine expected responses and moves to ponder.

Sorry, it's been a long week. :-/

jm

bob
Posts: 20892
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Leaving/Returning to Book Annoyance

Post by bob » Wed May 06, 2009 11:00 pm

MattieShoes wrote:
bob wrote: I have specific code in Crafty to catch this problem, or it will happen. Most likely, you will end up with a quick rep draw in your book itself, and you probably don't want to make that move unless it is the best you can do. I simply don't play book moves that lead to a 3-fold repetition, and let the search handle that instead, so that I can determine if not drawing is bad or not.
Does it pop out of book when 3-fold rep is possible, or does it just eliminate that response before it causes draw? It seems like the best solution would be to have the book code correctly evaluate rep draws -- if you're playing Rybka and can force a draw from within book, probably a good idea. If you're playing me, bad idea. Probably a solution in search of a problem though, no real advantage in realistic conditions.

Hmm mine doesn't have the popping back into book problem because it never goes back into book once it leaves. But it could get a draw within book anyway I suppose. Since it doesn't convert everything to a generic side to move, it hasn't happened though... Just about any un-move of a piece would pop it out of book.
I'll did not remember, but what I found is that if it finds any book move that leads to a repetition draw, it pops out of book and forces a normal search, which will see the draw, and the various moves that avoid it. I'd be afraid to just avoid the drawing move as the others might lose. I'd rather turn it over to the search to decide what to do since the draw will be seen for that move instantly, and all we need to know is that every other move comes up negative, to make us play the drawing move since the search would return that as best with a draw score to go with it.

Post Reply