Pondering? Yes. Ponder move? Maybe not.

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Pondering? Yes. Ponder move? Maybe not.

Post by sje » Thu Jul 30, 2009 6:11 pm

An idea:

Let's assume that a chess program, capable of pondering, stores nearly all of its search results in a traditional transposition table. The usual ponder technique is to take the second move of the predicted variation, execute that move, and start an indefinitely lasting ponder search assuming that the opponent will make the predicted move. If the opponent makes the move, then everything's fine, the ponder search is converted into a direct search, and no work was wasted. But if a different move was made by the opponent, then a new direct search has to be started and much work was done for nothing.

How about NOT making the predicted move prior to a ponder search? Instead, just start a search with the opponent on the move. When the opponent actually makes a move, the ponder search is killed, but all of its goodness remains in the transposition table. That data is used on the direct search and there should be a good amount of valuable data there regardless of what move the opponent actually made.

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

Re: Pondering? Yes. Ponder move? Maybe not.

Post by Bill Rogers » Thu Jul 30, 2009 6:19 pm

That sounds like a good idea but if when pondering is on "old style" and it actually hits or guesses the correct move say 50% of the time then in the long run you can save a lot of time for you side which is one of its good points.
I would like to see some averages using your proposed system before making any final conclusions.
Bill

User avatar
Desperado
Posts: 638
Joined: Mon Dec 15, 2008 10:45 am

Re: Pondering? Yes. Ponder move? Maybe not.

Post by Desperado » Thu Jul 30, 2009 6:36 pm

Hmmm...

why not doing a multi-pv ponder search. The following search would profit
in any case. Let s say a _normal_ ponder search hits, there maybe
a higher profit, but on mpv pondering you would make perhaps small
profits but everytime (or not?). Just flowing to my mind...

i will try this when my engine is ready for pondering, perhaps someone
has already done ? and if not i would like to know why ?

so the _mpv_ would be additional to what you suggested steven.
Last edited by Desperado on Thu Jul 30, 2009 6:39 pm, edited 1 time in total.

User avatar
Matthias Gemuh
Posts: 3238
Joined: Thu Mar 09, 2006 8:10 am
Contact:

Re: Pondering? Yes. Ponder move? Maybe not.

Post by Matthias Gemuh » Thu Jul 30, 2009 6:38 pm

sje wrote:An idea:

How about NOT making the predicted move prior to a ponder search? Instead, just start a search with the opponent on the move. When the opponent actually makes a move, the ponder search is killed, but all of its goodness remains in the transposition table. That data is used on the direct search and there should be a good amount of valuable data there regardless of what move the opponent actually made.

I do this part only if I (for any strange reason) don't have a move to ponder on.

Matthias.
My engine was quite strong till I added knowledge to it.
http://www.chess.hylogic.de

User avatar
hgm
Posts: 23004
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Pondering? Yes. Ponder move? Maybe not.

Post by hgm » Thu Jul 30, 2009 8:08 pm

This is called pondering the position, rather than pondering the move. Many engines do it. (They usually give it away by the score changing sign when they ponder.) Joker does it. It might be slightly inferior to pondering the best move, but it is much simpler to implement.

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

Re: Pondering? Yes. Ponder move? Maybe not.

Post by bob » Thu Jul 30, 2009 10:13 pm

sje wrote:An idea:

Let's assume that a chess program, capable of pondering, stores nearly all of its search results in a traditional transposition table. The usual ponder technique is to take the second move of the predicted variation, execute that move, and start an indefinitely lasting ponder search assuming that the opponent will make the predicted move. If the opponent makes the move, then everything's fine, the ponder search is converted into a direct search, and no work was wasted. But if a different move was made by the opponent, then a new direct search has to be started and much work was done for nothing.

How about NOT making the predicted move prior to a ponder search? Instead, just start a search with the opponent on the move. When the opponent actually makes a move, the ponder search is killed, but all of its goodness remains in the transposition table. That data is used on the direct search and there should be a good amount of valuable data there regardless of what move the opponent actually made.
This is simply flawed, although it gets suggested about once every year or so.

Here's why:

Current approach results in at _least_ 50% ponder hits. That means that 50% of the time you ponder correctly, and can probably make a move in zero time, which saves 50% of your time for use on other moves.

If you just flip sides, you will search just as deeply as normal in a given amount of time, and find the best move for the opponent. But when time runs out, you are one ply short of the depth you would have reached. So you can not stop the search after the opponent moves, you are a ply short, so you have to use your own time as well, to make up that ply, and you don't save a thing.

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

Re: Pondering? Yes. Ponder move? Maybe not.

Post by bob » Thu Jul 30, 2009 10:14 pm

Desperado wrote:Hmmm...

why not doing a multi-pv ponder search. The following search would profit
in any case. Let s say a _normal_ ponder search hits, there maybe
a higher profit, but on mpv pondering you would make perhaps small
profits but everytime (or not?). Just flowing to my mind...

i will try this when my engine is ready for pondering, perhaps someone
has already done ? and if not i would like to know why ?

so the _mpv_ would be additional to what you suggested steven.
And it will cost you _another_ ply or two in reduced depth. multi-PV is horrifically slow compared to a normal alpha/beta best-move-only search.

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

Re: Pondering? Yes. Ponder move? Maybe not.

Post by bob » Thu Jul 30, 2009 10:14 pm

Matthias Gemuh wrote:
sje wrote:An idea:

How about NOT making the predicted move prior to a ponder search? Instead, just start a search with the opponent on the move. When the opponent actually makes a move, the ponder search is killed, but all of its goodness remains in the transposition table. That data is used on the direct search and there should be a good amount of valuable data there regardless of what move the opponent actually made.

I do this part only if I (for any strange reason) don't have a move to ponder on.

Matthias.
I do that but with a very short time limit, to get a "best move" for the opponent...

Dann Corbit
Posts: 9332
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Pondering? Yes. Ponder move? Maybe not.

Post by Dann Corbit » Thu Jul 30, 2009 10:34 pm

Logically, pondering on the projected move is a benefit if you can guess the right move at least 50% of the time. Statistically, it appears that most engines achieve at least that hit rate for ponder against all peers:
http://www.computerchess.org.uk/ccrl/40 ... =by+rating

Daniel Shawul
Posts: 3572
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Pondering? Yes. Ponder move? Maybe not.

Post by Daniel Shawul » Thu Jul 30, 2009 10:41 pm

Before I switched to "pondering on the move" I tried to do some anlaysis.
I could be well of the mark though...


Assuming the total time taken for all moves in a game is T.
Type I - ponder on the move
Type II - ponder on position (simpler one)

case I) very well predicted moves like obvious recapture, single replies and other forced moves. --> 10% of all moves
Here Type I has no significant advantage over Type II because 95% of the time is spent on the singular move.
So it is 10% * 5% * T = 0.005T time advantage for Type I.

Case II) well predicted moves. Assume 60% prediction rate (that will be 10 + 60 = 70% overall, a bit generous i suppose)
Here let us assume 50% of the time is spen on the first move. That means 50% is wasted by II so
70% * 50% * T = 0.35T time advantage for Type I.

Case III) prediction failure (30% of the moves). This is where I think Type II's advantage comes from. Type I is completely lost here while
II has some information on every move. So *disregarding previous search* that will be 100% advantage for II.
That will be 30% * 100% * T = 0.3T


So in summary we are roughly looking at 0.355T time advantage to I , as compared to 0.3T for II. Of course all of this depends
on the assumptions I made above but I think it is safe to say I tends to win over all.

Post Reply