order of generating moves in chess programs

[Uri Blass]

I think that the order of generating moves may change the playing strength of the program because of the following reasons:

If you generates the best move first you may play a better move in some cases.

1)It is obvious in case of only material evaluation and a program with only material evaluation that generates 1.e4 first is going to play 1.e4 that is better than a program that generates 1.a4 first.

2)In the case of not only material evaluation the possible difference is smaller but you still may have cases of 2 moves with exactly the same evaluation and it is better to generate the better move first in most of the cases.

3)Even when you play the same move if you generate the first move first you may save time later in ordering the moves.

I wonder if programmers tried testing changing the order of generating moves and if they found a difference in playing strength.

Looking at the code of stockfish I wonder what is the reason for oposite order of generating moves between captures and non captures.

It seems to me that it may be better to change the order of generating captures and start with pawn captures(and I also think that it may be better to start with generating castling moves in the second function because castling is the most logical move in case that it is possible)

I wonder if the programmers tested it and found no elo gain from it.
Here is the relevant code of stockfish.

Code: Select all

/// generate_captures() generates all pseudo-legal captures and queen
/// promotions. Returns a pointer to the end of the move list.

MoveStack* generate_captures(const Position& pos, MoveStack* mlist) {

  assert(pos.is_ok());
  assert(!pos.is_check());

  Color us = pos.side_to_move();
  Bitboard target = pos.pieces_of_color(opposite_color(us));

  mlist = generate_piece_moves<QUEEN>&#40;pos, mlist, us, target&#41;;
  mlist = generate_piece_moves<ROOK>&#40;pos, mlist, us, target&#41;;
  mlist = generate_piece_moves<BISHOP>&#40;pos, mlist, us, target&#41;;
  mlist = generate_piece_moves<KNIGHT>&#40;pos, mlist, us, target&#41;;
  mlist = generate_piece_moves<PAWN, CAPTURE>&#40;pos, mlist, us, target&#41;;
  return  generate_piece_moves<KING>&#40;pos, mlist, us, target&#41;;
&#125;


/// generate_noncaptures&#40;) generates all pseudo-legal non-captures and
/// underpromotions. Returns a pointer to the end of the move list.

MoveStack* generate_noncaptures&#40;const Position& pos, MoveStack* mlist&#41; &#123;

  assert&#40;pos.is_ok&#40;));
  assert&#40;!pos.is_check&#40;));

  Color us = pos.side_to_move&#40;);
  Bitboard target = pos.empty_squares&#40;);

  mlist = generate_piece_moves<PAWN, NON_CAPTURE>&#40;pos, mlist, us, target&#41;;
  mlist = generate_piece_moves<KNIGHT>&#40;pos, mlist, us, target&#41;;
  mlist = generate_piece_moves<BISHOP>&#40;pos, mlist, us, target&#41;;
  mlist = generate_piece_moves<ROOK>&#40;pos, mlist, us, target&#41;;
  mlist = generate_piece_moves<QUEEN>&#40;pos, mlist, us, target&#41;;
  mlist = generate_piece_moves<KING>&#40;pos, mlist, us, target&#41;;
  mlist = generate_castle_moves<KING_SIDE>&#40;pos, mlist&#41;;
  return  generate_castle_moves<QUEEN_SIDE>&#40;pos, mlist&#41;;
&#125;

[hgm]

In micro-Max this was very noticeable: with white is was stronger than with black, even when you gave black the first move! The reason seemed to be that the board-scan in the move generator typically found Pawns first for white, and pieces first for black.

[mcostalba]

Looking at the code of stockfish I wonder what is the reason for oposite order of generating moves between captures and non captures.

On some very old (and possibly inadeguate for today's standards) test it seems that trying first non capture pawn moves was better. But I really cannot consider this result for granted.

I would think that to reorder the captures generation calls should not impact ELO in any way because captures are fully scored and sorted indipendently to where have been generated. For non captures is different, scoring and sorting don't guarantee 100% coverage in all cases, for instance when there is no history for the moves, in that case is the generation order that leads.

...perhaps we could try some tweak also in that area, although I would not see it as an high priority stuff....

[Dann Corbit]

There was a clear increase in strength changing the default promotion order of GnuChess so that underpromotion to knight was the second choice after queen (it used to be last). Obviously, knight underpromotion is far more probable to be actually useful than bishop or rook.

[Uri Blass]

There was a clear increase in strength changing the default promotion order of GnuChess so that underpromotion to knight was the second choice after queen (it used to be last). Obviously, knight underpromotion is far more probable to be actually useful than bishop or rook.

obviously underpromotion are not very important and I am surprised to read it.

I expect no reduction in playing strength if you simply consider only queen promotions in the move generator(some programs like old Junior do it and the reason that Junior considered later knight promotion is not playing strength).

I believe that the reason that most programmers consider underpromotion in the move generator is not playing strength and not considering non queen promotions is simpler and better.

Maybe there is a doubt about considering knight promotions but I think that there should be no doubt about rook promotions or bishop promotions.

If the target is to increase playing strength then considering rook or bishop promotions is an obvious mistake and without testing I feel sure that considering them reduce the playing strength because even if you do not pay a price in speed you earn less than 0.01 elo and I do not believe that the reduction in speed is so small that you lose less than 0.01 elo.

Uri

[bob]

There was a clear increase in strength changing the default promotion order of GnuChess so that underpromotion to knight was the second choice after queen (it used to be last). Obviously, knight underpromotion is far more probable to be actually useful than bishop or rook.

It must have been a very tiny increase. under-promotions are only rarely significant...

[Dann Corbit]

There was a clear increase in strength changing the default promotion order of GnuChess so that underpromotion to knight was the second choice after queen (it used to be last). Obviously, knight underpromotion is far more probable to be actually useful than bishop or rook.

obviously underpromotion are not very important and I am surprised to read it.

I expect no reduction in playing strength if you simply consider only queen promotions in the move generator(some programs like old Junior do it and the reason that Junior considered later knight promotion is not playing strength).

I believe that the reason that most programmers consider underpromotion in the move generator is not playing strength and not considering non queen promotions is simpler and better.

Maybe there is a doubt about considering knight promotions but I think that there should be no doubt about rook promotions or bishop promotions.

If the target is to increase playing strength then considering rook or bishop promotions is an obvious mistake and without testing I feel sure that considering them reduce the playing strength because even if you do not pay a price in speed you earn less than 0.01 elo and I do not believe that the reduction in speed is so small that you lose less than 0.01 elo.

Uri

Versions 4.80 and prior used this sequence (rook is out of order):

Code: Select all

#if !defined CHESSTOOL
            Link(f, t, flag | queen, s - 20000);
            s -= 200;
            Link(f, t, flag | rook, s - 20000);
            s -= 50;
            Link(f, t, flag | knight, s - 20000);
            flag |= bishop;
            s -= 50;
#else
            flag |= queen;
#endif

Version 5.02 used this terrible sequence (queen is LAST):

Code: Select all

#define ADDPROMOTE(a,b) ADDMOVE (a, b, KNIGHTPRM); \
            		ADDMOVE (a, b, BISHOPPRM); \
            		ADDMOVE (a, b, ROOKPRM); \
            		ADDMOVE (a, b, QUEENPRM);

Version 5.03 forward used this correct sequence:

Code: Select all

#define ADDPROMOTE(a,b)           \
  do {                            \
    ADDMOVE (a, b, QUEENPRM);     \
    ADDMOVE (a, b, KNIGHTPRM);    \
    ADDMOVE (a, b, ROOKPRM);      \
    ADDMOVE (a, b, BISHOPPRM);    \
  } while (0)

The jump in strength was measured between 5.02 and 5.03 and I seem to recall it was significant enough to be easily measured but I don't remember what it was.

[Dann Corbit]

There was a clear increase in strength changing the default promotion order of GnuChess so that underpromotion to knight was the second choice after queen (it used to be last). Obviously, knight underpromotion is far more probable to be actually useful than bishop or rook.

It must have been a very tiny increase. under-promotions are only rarely significant...

If you see my response to Uri, the measurable increase was because they had set queen promotions to last place.