Staged move generation and killers

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
hgm
Posts: 22896
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Staged move generation and killers

Post by hgm » Tue Jan 01, 2019 4:37 pm

Ras wrote:
Tue Jan 01, 2019 2:48 pm
Most of the move generation is in quiescence, and making none of the moves there sounds strange. Or do you exclude high takes low captures e.g. via SEE? Of course, in QS, you only generate captures and not quiet moves (except maybe for check evasions).
Even if you don't prune bad captures, QS branches will typically terminate in leaves where all captures are futile. Nodes where there are no captures at all are of course a special case of that. But even there you would also know that after running a move generation.

Ras
Posts: 1081
Joined: Tue Aug 30, 2016 6:19 pm
Contact:

Re: Staged move generation and killers

Post by Ras » Tue Jan 01, 2019 5:10 pm

hgm wrote:
Tue Jan 01, 2019 4:37 pm
But even there you would also know that after running a move generation.
Ah right, that makes sense because all the loops and stuff are still being run, only that there is no capture anymore to be added to the move list, and then of course no make/unmake either.
Rasmus Althoff
https://www.ct800.net

Michael Sherwin
Posts: 2850
Joined: Fri May 26, 2006 1:00 am
Location: OH, USA

Re: Staged move generation and killers

Post by Michael Sherwin » Sat Jan 12, 2019 2:46 am

One trick that I do in RomiChess that I got a lot of consternation over at the time was for the remaining moves Romi does a very shallow search of 1 or 3 additional plies and then plays the move with the best score first. No one believed that it would help so I modified TSCP1.81 to do the same and TSCP gained about a 1.5 ply deeper search in the same amount of time. Here is the code in RomiChess.

Code: Select all

    case ADDMOVES:
      h->phase = NEXTMOVE;
      AddMoves(h->node, depth);
      if(h->node == (h+1)->t) return FALSE;
      if(depth > 3) {
        for(node = h->node; node < (h+1)->t; node++) {
          Sort(node, (h+1)->t);
          MakeMove((moves *)&node->m);
          if(GetReps())
            node->score = 0;
          else {
            inShort++;
            node->score = -Search(-beta - 180, -alpha + 20, depth > 7 ? 3 : 1, 0);
            inShort--;
          }
          ClrReps();
          TakeBack();
        }
      }        
    case NEXTMOVE:
      if(h->node + 1 == (h+1)->t) {
        h->phase = NOMOVES;
        return TRUE;
      }
      Sort(h->node, (h+1)->t);
  }
And Sven, if you go to post negatively about this idea, Romi has asked Jumbo to sit on you! 😜
Regards,
Mike

tmokonen
Posts: 956
Joined: Sun Mar 12, 2006 5:46 pm
Location: Vancouver

Re: Staged move generation and killers

Post by tmokonen » Wed Jan 16, 2019 12:17 am

It looks similar in concept to internal iterative deepening to me. Am I missing a subtlety here?

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

Re: Staged move generation and killers

Post by hgm » Wed Jan 16, 2019 7:48 am

The difference is that he opens the window, so that he gets exact scores that he can sort on, rather than an upper bound that is meaningless for other purposes than singling out the best move.

Post Reply