Engine improvement ?

[nionita]

Hi Sven,

Thinking a bit more about it and........ my search is like this:

1. Qsearch if depth=0
2. Get TT and look for immediate exit.
3. Null move and look for an immediate exit
4. 2 Killer moves and look for an immediate exit.
5. Generate other moves...and sort to with PV move, TT move, Captures/promotions,
history of quiet moves, in that order.
6. Search the move list.


So 2,3,4 should count as cuts on the first move shouldn't they ?

Regards
Laurie.

Hm, 1 and 2 should be interchanged, I think. 4 and 5 too, killers come after TT move and winning captures.

[lauriet]

>>>
How do Killer Moves give you an immediate exit ? Shouldnt u just use them for ordering your MoveList ?


I update the killer move array when I get a beta cut in the search.....so in other branches I do an early reduced search looking for another beta cut.
If this doesn't give a cut off, the killer move is placed later in the move list. (and will be researched) By doing it early I'm hoping not to have to generate the moves and save some effort.
This is a bit like doing the null move before you do too much work.


Laurie

[Sven]

>>>
How do Killer Moves give you an immediate exit ? Shouldnt u just use them for ordering your MoveList ?


I update the killer move array when I get a beta cut in the search.....so in other branches I do an early reduced search looking for another beta cut.
If this doesn't give a cut off, the killer move is placed later in the move list. (and will be researched) By doing it early I'm hoping not to have to generate the moves and save some effort.
This is a bit like doing the null move before you do too much work.

The killer move heuristic is not intended to be used for captures, only for quiet moves. It will not work as expected otherwise. You could of course search killer moves before generating and searching quiet moves but captures should always come first, so in that case you would also need to generate captures first. Usually people also distinguish between "good captures" and "losing captures", where killer moves would be tried between those both groups, but that is another issue. So the typical order goes like this:

1. TT move (which should already include the PV move if there is one)
2. good captures (probably also including promotions)
3. killer moves
4. losing captures
5. other quiet moves

[Sven]

1. Qsearch if depth=0
2. Get TT and look for immediate exit.
3. Null move and look for an immediate exit
4. 2 Killer moves and look for an immediate exit.
5. Generate other moves...and sort to with PV move, TT move, Captures/promotions,
history of quiet moves, in that order.
6. Search the move list.

So 2,3,4 should count as cuts on the first move shouldn't they ?

No, because the cutoff statistics is about move ordering only, not about all other kinds of reducing tree size. So "cutoff on first move" should really be counted if you get a cutoff after the first move in the move loop.

Regarding killer moves, please see also my other post.

[Sven]

Hi Sven,

Thinking a bit more about it and........ my search is like this:

1. Qsearch if depth=0
2. Get TT and look for immediate exit.
3. Null move and look for an immediate exit
4. 2 Killer moves and look for an immediate exit.
5. Generate other moves...and sort to with PV move, TT move, Captures/promotions,
history of quiet moves, in that order.
6. Search the move list.


So 2,3,4 should count as cuts on the first move shouldn't they ?

Regards
Laurie.

Hm, 1 and 2 should be interchanged, I think. 4 and 5 too, killers come after TT move and winning captures.

You would only do 2 before 1 if you use TT in Qsearch as well. Some engines do, others don't. Also 4 and 5 should not be interchanged but combined in the right way.

[lauriet]

My killer moves may or may not be captures. They are any move that caused a beta cut at this paticular ply before. Since my move generation is not very quick, i hope to avoid it.
If i try a killer early it may save the job. It does reduce my node count for a fixed depth search by about about 25%. Of course i dont know how it effects play over 1000 games.


Regards
Laurie

[Evert]

My killer moves may or may not be captures. They are any move that caused a beta cut at this paticular ply before. Since my move generation is not very quick, i hope to avoid it.
If i try a killer early it may save the job. It does reduce my node count for a fixed depth search by about about 25%. Of course i dont know how it effects play over 1000 games.

There may be a gain by having something like a killer slot for captures, but storing captures in killer slots seems like a bad idea.
The reason is that captures are already sorted high in the list, so there is less to be gained. For quiet moves, you typically have no idea how to sort them and so killers help.

[Sven]

My killer moves may or may not be captures. They are any move that caused a beta cut at this paticular ply before. Since my move generation is not very quick, i hope to avoid it.
If i try a killer early it may save the job. It does reduce my node count for a fixed depth search by about about 25%. Of course i dont know how it effects play over 1000 games.

So you say that this move ordering:

1. Killer moves (not restricted to quiet moves)
2. PV move
3. TT move
4. Captures/promotions
5. Quiet moves

is better for your engine than without killers:

1. PV move
2. TT move
3. Captures/promotions
4. Quiet moves

But it seems you did not try it the way how the killer heuristic is intended:

1. PV move (again, should not be necessary since it will be provided by TT)
2. TT move
3. Captures/promotions (again, usually losing captures are tried after killer moves)
4. Killer moves (restricted to quiet moves)
5. Quiet moves

Maybe you should give it a try

[Sven]

My killer moves may or may not be captures. They are any move that caused a beta cut at this paticular ply before. Since my move generation is not very quick, i hope to avoid it.
If i try a killer early it may save the job. It does reduce my node count for a fixed depth search by about about 25%. Of course i dont know how it effects play over 1000 games.

There may be a gain by having something like a killer slot for captures, but storing captures in killer slots seems like a bad idea.
The reason is that captures are already sorted high in the list, so there is less to be gained. For quiet moves, you typically have no idea how to sort them and so killers help.

The point is that he sorts killers (possibly including captures that caused a cutoff) even before TT move and captures. I could imagine that this is still better than without killers (although the reported 25% of saved nodes are surprising) but I think it misses a lot of potential.

[lauriet]

I better clarify this.....

1: lookup TT.
2: try a null move
3: try the 2 killer moves. (These caused a beta cut somewhere else in the tree)
4: generate moves
5: sort moves in order of PV, Captures, Killers, Quiet moves.

So if the killers did not cause an early cut they are research will the full depth.
I have tried the conventional move order but this method does give me speed up.
My main intention is to identify the type on node and avoid move generation.
Maybe with other engines that can do fast move gen it would be irrelevant.