time of generating moves

[Uri Blass]

Movei in the past always generated moves immediately after making moves before calling alphabeta.

I decided to change it and to generate moves only inside of alphabeta because it is possible that I do not need generating the moves in order to prune earlier.

The question is when to generate moves and I will try to do it as late as possible.

generating moves in the beginning of alphabeta is not equivalent to generating moves after making move before calling alphabeta.

The reason is that sometimes I call alphabeta not after making move and generating the move was already done.

I think to have some flag that tell me if generating moves was already done in the relevant path in order to save generating moves and I wonder what other programs do.

I tried to understand what fruit does about it and I did not see that it has such flag.

Uri

[Pallav Nawani]

Movei in the past always generated moves immediately after making moves before calling alphabeta.
I decided to change it and to generate moves only inside of alphabeta because it is possible that I do not need generating the moves in order to prune earlier.
The question is when to generate moves and I will try to do it as late as possible.
generating moves in the beginning of alphabeta is not equivalent to generating moves after making move before calling alphabeta.
Uri

I don't understand what you are trying to say. Can you give some psuedo code?

If you want to avoid generating extra moves, you can do incremental move generation like crafty does.

Pallav

[Uri Blass]

I will try to give pseudo code by making the code that I have more simple(I have more parameters for alphabeta and I check after every alphabeta if to stop the search)

old source:

makemove(gen_dat[i].m);
pruningfactor=calculatepruningconditions();
updateeval();
gen();
if (pruningfactor>0)
{
if (alphabeta(depth-PLY-pruningfactor,-beta,-alpha)>=-alpha)
val=alpha;
else
/*doing a research*/
/*here I save generating moves relative to pushing generating moves to alphabeta without more changes*/

val=-alphabeta(depth - PLY, -beta, -alpha);
}
else
{
...
}
undomove();




new source:
updateeval(); and gen(); are not done after make move but in the beginning of alphabeta

int alphabeta((int depth, int alpha, int beta)
{
...
if (lasteval<hply)
{
/*I calculate after every move that I make the evaluation and it is used for decisions like pruning and I have a global variable that tells me if I already calculated the evaluation in that path so I do not need to do it again(I added that variable to the new code and in the old code when updating the evaluation was done after make move it was not needed)

I think that there may be cases when I do not need to update the evaluation because I already did it but I need to generate moves so I may need to have another global variable that tells me if I generate the moves in that ply but in another thought I may decide to generate only part of the moves(after I change my code) and I plan to have a capture generator so it is not a good idea to have a variable that tells me only if I generated moves because there is more than yes and no answers and it is possible that I already generated captures that I do not need to repeat but I need to repeat generating non captures
*/
updateeval();
gen();
}

Uri

[Uri Blass]

Movei in the past always generated moves immediately after making moves before calling alphabeta.
I decided to change it and to generate moves only inside of alphabeta because it is possible that I do not need generating the moves in order to prune earlier.
The question is when to generate moves and I will try to do it as late as possible.
generating moves in the beginning of alphabeta is not equivalent to generating moves after making move before calling alphabeta.
Uri

I don't understand what you are trying to say. Can you give some psuedo code?

If you want to avoid generating extra moves, you can do incremental move generation like crafty does.

Pallav

I hope that the code that I wrote is clear
(I edited it after writing it because there were mistakes when I tried to simplify my code)
I want to avoid generating moves that I already generated in the same path.
I also think to have a capture generator and not only to generate all moves in the same time

If you have incremental move generator you need to remember exactly what you generated in the same path in order to avoid doing what you did in the past again so the task is more complicated.

Uri

[Peter Fendrich]

I think that the typical simplyfied code is:

Code: Select all

Generate_moves(...)    //Fill a move list with moves
while ( move=Pick_move_from_movelist(...) ) {
    Make_move(move)
    AlphaBeta(.......)
    UnMake_move(move)
    .
    .
}


If you want to do Generate_moves incrementally some changes are needed.
I let Generate_moves not only fill the movelist when needed but also return a move each time.

Code: Select all

while ( move=Generate_moves(...)  ) {
    Make_move(move)
    AlphaBeta(.......)
    UnMake_move(move)
    .
    .
}

Now Generate_moves first generates captures and keep track of if there are moves left in the list and when it's time to generate the rest of the moves.
That needs some kind of flag that is initiated before my code above and then updated within Generate_moves.

The true story also includes the hash moves but with the same logic.
/Peter

[Uri Blass]

The problem is that alphabeta is not called only after making move
and if I change your example I get generating unnecassary moves
after research conditions.

The changed code is like this:

Generate_moves(...) //Fill a move list with moves
while ( move=Pick_move_from_movelist(...) ) {
Make_move(move)
AlphaBeta(.......)
if (reseach_conditions)
Alphabeta(.....)
UnMake_move(move)

If you generate them incremently

while ( move=Generate_moves(...) ) {
Make_move(move)
AlphaBeta(.......)

if (reseach_conditions)
Alphabeta(.....)
UnMake_move(move)

.
.
}

[Peter Fendrich]

I suppose you meant UnMake_move after the second AlphaBeta...

I still don't understand what you mean by generating unnecessary moves after research conditions
Why should that happen?
/Peter

Edit: Maybe you meant that in the research you reach the same child a second time with the same conditions? That seems clever but on a second thought, how often does that happen and is it really worth complicating the code for it?

[Uri Blass]

I suppose you meant UnMake_move after the second AlphaBeta...

Right
I will fix it.


I still don't understand what you mean by generating unnecessary moves after research conditions
Why should that happen?
/Peter

Edit: Maybe you meant that in the research you reach the same child a second time with the same conditions? That seems clever but on a second thought, how often does that happen and is it really worth complicating the code for it?

This is exactly what I meant.

speed is one reason but not the main reason.

When I generated move after making them and not inside alphabeta
I had the same condition of not generating moves twice.

I want to have confidence of no bugs so I want to have the same analysis when I analyze the position after changing the code when I only delay generating moves in order to save the job that I may I do later.

The problem is that if I generate the moves twice I also get different analysis.

The reason is that the pieces in the piece list are not in the same order when I generate moves second time (after making a lot of moves) so the move generator does not generate the moves in the same order in the second time and it cause different order of moves and different number of nodes in analyzing the same position.

I know that in the future I will need to change the number of nodes in the same analysis if I generate only captures because generating only captures will mean that the order of the moves will not be the same but I want as first step to avoid bugs only to save generating moves when I do not need it without changing the number of nodes so I can check if the program only give the same number of nodes faster in analysis.

Uri

[Gerd Isenberg]

Hi Uri,

if i understand correct, you need a kind of statefull movegenerator.

You have to keep a "state"-variable per ply, with a defined set of states. Also, you probably need at least two indices into the movelist per depth. One put-, and one get-index. put[ply] to store the next generated move with postincrement.

Each time getNextMove is called:
If get[ply] < put[ply], a move is taken from the movelist, postincrementing get[idx].
Otherwise state[ply] is interpreted to generate moves accordingly.
Also state[ply] has to be changed, until something like "AllMovesGenerated" finally occures and no more next move is available.

Fur cut-nodes in full search may be with following switch(state):

Code: Select all

case MGFullCutInitState:
  genHashMove();
  state = MGFullCutGoodSEECaptures;
  if ( get < put )
    break; // hash move generated
case MGFullCutGoodSEECaptures:
  genGoodSEECaptures();
  state = MGFullCutKiller0;
  if ( get < put )
    break; // good capture(s) generated
case MGFullCutKiller0:
  genKiller0();
  state = MGFullCutKiller1;
  if ( get < put )
    break;
  ...
case MGFullCutKillerN:
  genKillerN();
  state = MGFullCutRemaining;
  if ( get < put )
    break;
case MGFullCutRemaining:
  genRemaining();
  state = AllMovesGenerated;
  break;


With other Initial States one may implement different move generators for different node types, like "cut", "all" or "pv", and maybe also for different depth from/to horizon, including quiescence and/or in Check or in double Check.
Depending on window related stuff, different "incarnations" of genRemaining may do more or less effort to evaluate generated moves for more accurate sorting.

As you already mentioned, a problem might be be to keep track of already generated moves to avoid multiple generation of same moves in several movegen states. One obvious solution is to keep a third movelist index per ply - firstPut[ply]. Before pushing a fresh generated move, one has to loop from firstPut[ply] to put[ply] over the movelist, to look whether the move was already tried. The more moves already tried - without cut, the more expensive the lookup becomes.
One may keep track disjoint source/target sets and/or also disjoint movelists for captures and quite moves. For instance obvoius winning captures (without SEE?) {P,N,B}x{Q,R} or {all}x{hanging pieces} are only generated in genGoodSEECaptures and skipped in genRemaining.

To avoid any bookholding in expected all-nodes, it probably makes sense to generate all at once here:

Code: Select all

case MGFullAllInitState:
       genAllAndSort();
       state = AllMovesGenerated;


-------------------------------------------------------------

Is it worth the trouble?
So nice such FSM-like movegen sounds - it is more and error-prone code.
You need a lot of additional code in a debug-version.

IMHO it is important to search exactly the same trees, both with generating moves all at once and incrementally, assuming same move evaluation and pick up by best value.

Cheers,
Gerd