History heuristic and quiet move generation

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.
Post Reply
User avatar
cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

History heuristic and quiet move generation

Post by cdani » Sun Jul 16, 2017 7:11 am

Many engines try a few moves before generating quiet moves, namely killers, countermoves, and others.

In Andscacs I try hash move and null move threat before generating quiets, that is done immediately before trying the first killer. So the history [piece][to] of other moves than the one that caused a possible cutoff is updated when the killer moves are being tried. This history update of course cannot happen on other late quiet generation engines until this generation is done.

The idea of late generation of course is to save the time of generation of quiets on most possible nodes, but has this lack of history update drawback.

Is not that I can say if this is good or bad. Just that the engine obviously behaves differently and will be tuned differently once the decision of when to do the quiet move generation is made. Lmr will be tuned differently, different flavors of late move pruning also, etc.

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

Re: History heuristic and quiet move generation

Post by hgm » Sun Jul 16, 2017 9:52 am

I don't get what you are saying at all. Why can you not update history before move generation? You know the piece & to of the cut move, whether it was generated or not.

User avatar
cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: History heuristic and quiet move generation

Post by cdani » Sun Jul 16, 2017 10:24 am

I was referring about decreasing the history of the other moves that have not caused the cutoff. The ones that the engine have tried but it don't have in a list, cannot be decreased.

User avatar
cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: History heuristic and quiet move generation

Post by cdani » Sun Jul 16, 2017 10:33 am

I think I have to change this, and I will try to store the already tried moves before quiet generation, so I can defer the quiet move generation safely.

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

Re: History heuristic and quiet move generation

Post by hgm » Sun Jul 16, 2017 12:41 pm

cdani wrote:I was referring about decreasing the history of the other moves that have not caused the cutoff. The ones that the engine have tried but it don't have in a list, cannot be decreased.
And I suppose you could not do that right when you try them, because you want to make it dependent on whether there is a cutoff in that node?

But I don't see the problem. You know what you tried, so you can put that in a list. That list will never be very long. (Hash move + 2 killers?)

I put moves in a list anyway, before I try them. Only the null move has a separate recursive call, the only other recursion is when looping through the move list. Initially the list only contains the hash move, and each time you reach the end of the list, the next stage of the move generation is called to provide more moves. So hash move and killers would be in the list, if a killer fails high. And in particular, the killers would be in the non-capture section of the list.

User avatar
Steve Maughan
Posts: 1061
Joined: Wed Mar 08, 2006 7:28 pm
Location: Florida, USA
Contact:

Re: History heuristic and quiet move generation

Post by Steve Maughan » Sun Jul 16, 2017 1:46 pm

In the main search (ie not the quiescent search) I generate all the moves after the null move has been tried. This keeps things simple (which is one of my design goals), and hardly impacts speed. In most engines they spend most of their time in the evaluation and generating captures in the quiescent search, so I believe doesn't impact speed too much (although I haven't tested it). It also means move ordering decisions and metrics are "pure", as they occur at the same time.

Steve
http://www.chessprogramming.net - Maverick Chess Engine

User avatar
cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: History heuristic and quiet move generation

Post by cdani » Sun Jul 16, 2017 6:11 pm

hgm wrote: And I suppose you could not do that right when you try them, because you want to make it dependent on whether there is a cutoff in that node?

But I don't see the problem. You know what you tried, so you can put that in a list. That list will never be very long. (Hash move + 2 killers?)

I put moves in a list anyway, before I try them. Only the null move has a separate recursive call, the only other recursion is when looping through the move list. Initially the list only contains the hash move, and each time you reach the end of the list, the next stage of the move generation is called to provide more moves. So hash move and killers would be in the list, if a killer fails high. And in particular, the killers would be in the non-capture section of the list.
Yes, as I have commented after, adding a list of tried moves is the way to go. All this come due to having a bug in Andscacs that went unnoticed until after your first comment, that made me think that all was working as expected :-)
Steve Maughan wrote:In the main search (ie not the quiescent search) I generate all the moves after the null move has been tried.
At least saving the generation if the hash move works, is worth trying.

Post Reply