beginner: how to reduce branching factor?

[Anonymous]

Hi all! This is my first post in this forum, so be nice

Some weeks ago i started programming a chess engine for the fun of it. I jumped right into the cold water only knowing about the negamax algorithm. however, after 3 re-writes, it looks like i'm slowly getting a grip onto things.

there is one issue that i seem not to be able to resolve: due to a too high branching factor in my engine, i'm not able to search past ply 8. even searching the initial position to ply 8 takes nearly 2 minutes.

i found out that my branching factor is way too high. (i'm using alpha-beta, PV search and aspiration windows). it's something around 7! the crappy presorting of my moves is responsible for that, it also renders the PV search useless (too many re-searches).
i could try looking at other engines' source and copy the move pre-evaluation, but i'd really hate to do so since i like to figure things out myself.

maybe you guys could help me out. i would appreciate it if you could tell me which approaches you use for move presorting, and what your average branching factors are (without considering things like null-move and quiescene).

maybe you even can tell me if i have some major bug in my code i overlooked.
my method is the following:

the score used for pre-sorting the moves score is an integer based on a value of 100 for a pawn.
i'm iterating through each move before doing the actual search. each move has a estimated score already stored during move generation.
the score is the captured piece's value if the move captures a piece. if the move leaves the piece on a threatened square, 1/10th of the piece's value is subtracted from the score.
if the move is one of my 2 killer moves i keep for each ply, it's score is set to something around 1000. if it's no killer move, but the best move in any previous search (found via TT), it's also set to an artificial maximum.
if the move is neither found in the TT nor a killer move, the move's prescore which was calculated during move generation is used. a score from the history heuristics is added. and, yes, it gets a high bonus if it checks the enemy's king.

the code goes here:

Code: Select all

// CALCULATE PRESCORES
   for (ctr = MoveStacks[depth].top - 1; ctr >= 0; ctr--) {

      Move = &MoveStacks[depth].Stack[ctr];

      used[depth][ctr] = false;

      if (Move->UID == KillerMove[depth][0].UID) {
         Move->prescore = KillerMove[depth][0].value + 1000;
      } else if (Move->UID == KillerMove[depth][1].UID) {
         Move->prescore = KillerMove[depth][1].value + 1000;
      } else if (TranspositionTable[numPlayer].lookupBestMove(boardKey, boardLock) == Move->UID) {
         Move->prescore = PRESCORE_PV;
      } else {
         Move->makeMove(ChessBoard, &Players[numPlayer], &Players[1 - numPlayer]);
         if (chessRulesV2::isCheck(ChessBoard, &Players[1 - numPlayer])) Move->prescore += PRESCORE_GIVE_CHECK;
         Move->undoMove(ChessBoard, &Players[numPlayer], &Players[1 - numPlayer]);
         Move->prescore += HistoryHeuristic[Move->startIndex][Move->endIndex];
      }
   }


i know it could be optimized code-wise, but at the moment, i'm more interested in getting the branching factor down.

this still leaves me with a branching factor of around seven. i'm slowly getting mad about this

thanks in advance!

[Sven Schüle]

Hi Robert,

welcome to this forum!

To address your branching factor problem first: many engines use either MVV/LVA move ordering or SEE (static exchange evaluation). Refer for example to Bruce Moreland's page (click on "More links" on top of this page and then scroll to the bottom ) for an excellent description. One idea for you could be to let the value of the capturing piece have an influence, too, in order to always try "pawn takes pawn" earlier than "rook takes pawn", or the like.

One question: what is the reason for making and unmaking each move within your prescore calculation? Is it for the "inCheck" test? Then I assume this might be very expensive. Did you already consider to leave out this "inCheck" test?

Furthermore, you're doing the TT lookup ("lookupBestMove") once for each move within your prescoring loop, is this right? You may try to do this only once and compare each move with the returned TT move. (An optimization, of course, as you have mentioned, but not an unimportant one.)

I hope this helps.

Sven

[Tord Romstad]

Hi all! This is my first post in this forum, so be nice

Welcome on board, Robert!

You have nothing to fear. I have found everybody here to be very friendly and helpful.

Some weeks ago i started programming a chess engine for the fun of it. I jumped right into the cold water only knowing about the negamax algorithm. however, after 3 re-writes, it looks like i'm slowly getting a grip onto things.

You started just a few weeks ago, and you already have something which is mostly working? You're fast.

maybe you guys could help me out. i would appreciate it if you could tell me which approaches you use for move presorting, and what your average branching factors are (without considering things like null-move and quiescene).

I order the moves in the following way:

1. Move from hash table, if present.
2. Mate killer, if present.
3. Captures of the last moved piece, ordered by static exchange evaluation.
4. All other captures, ordered by SEE.
5. Killer move 1.
6. Killer move 2.
7. Killer move 1 from two plies earlier in the tree.
8. Killer move 2 from two plies earlier in the tree.
9. Remaining moves ordered by history heuristic.

Between 1 and 2, I also do an internal iterative deepening search when the remaining depth is big and the current node is a PV node or I expect a fail high.

It is very important to search the hash table move first, and also that you search winning (and probably also equal) captures before killer moves. A common mistake is to store captures in the killer moves. Use killer moves only for non-captures.

My average effective branching factor in the middle game when using recursive null move pruning is around or slightly above 2, I think.

maybe you even can tell me if i have some major bug in my code i overlooked.
my method is the following:

the score used for pre-sorting the moves score is an integer based on a value of 100 for a pawn.
i'm iterating through each move before doing the actual search. each move has a estimated score already stored during move generation.
the score is the captured piece's value if the move captures a piece. if the move leaves the piece on a threatened square, 1/10th of the piece's value is subtracted from the score.
if the move is one of my 2 killer moves i keep for each ply, it's score is set to something around 1000. if it's no killer move, but the best move in any previous search (found via TT), it's also set to an artificial maximum.

It sounds like you use killer moves even for captures. As mentioned above, you almost certainly shouldn't do this.

if the move is neither found in the TT nor a killer move, the move's prescore which was calculated during move generation is used. a score from the history heuristics is added. and, yes, it gets a high bonus if it checks the enemy's king.

The history heuristic, like the killer heuristic, should probably only be used for non-captures. And I doubt that it is a good idea to assign a bonus for checks.

the code goes here:

Code: Select all

// CALCULATE PRESCORES
   for (ctr = MoveStacks[depth].top - 1; ctr >= 0; ctr--) {

      Move = &MoveStacks[depth].Stack[ctr];

      Move->makeMove(ChessBoard, &Players[numPlayer], &Players[1 - numPlayer]);

      used[depth][ctr] = false;

      if (Move->UID == KillerMove[depth][0].UID) {
         Move->prescore = KillerMove[depth][0].value + 1000;
      } else if (Move->UID == KillerMove[depth][1].UID) {
         Move->prescore = KillerMove[depth][1].value + 1000;
      } else if (TranspositionTable[numPlayer].lookupBestMove(boardKey, boardLock) == Move->UID) {
         Move->prescore = PRESCORE_PV;
      } else if (chessRulesV2::isCheck(ChessBoard, &Players[1 - numPlayer])) {
         Move->prescore += PRESCORE_GIVE_CHECK;
         Move->prescore += HistoryHeuristic[Move->startIndex][Move->endIndex];
      }

      Move->undoMove(ChessBoard, &Players[numPlayer], &Players[1 - numPlayer]);
   }


i know it could be optimized code-wise, but at the moment, i'm more interested in getting the branching factor down.

That's the right approach. An efficient and bug-free search is more important than everything else. Nevertheless, making and unmaking all moves during move ordering seems rather strange and unnecessary. Why do you want to do this?

Without seeing the rest of your code it is hard to be sure, but the way you use the transposition table here looks rather suspicious. You look up the best move from the transposition table after you have made the move. Could this mean that you look up the wrong position?

this still leaves me with a branching factor of around five. i'm slowly getting mad about this

If you don't use recursive nullmove pruning or some other kind of selective search, a branching factor of five probably isn't catastrophically bad. You should be able to improve it a bit by following the advice above, though (or so I hope).

Tord

[Sven Schüle]

Hi Robert,

your "makeMove"/"undoMove" code appears to have changed while I wrote my first answer ... so now you're making/unmaking every move except for the killer+TT moves, in order to do the "inCheck" test only for the remaining moves.

You said that checking moves always get a high bonus. I would consider this quite dangerous. If you always try checks first, even if they give away material, then this might affect your branching factor, I think. Perhaps give them a smaller bonus?

Only an idea!

Sven

[Alessandro Scotti]

Hi Robert,
there is a very interesting paper by Ed Schroeder (author of Rebel and ProDeo) that also deals with move ordering. You can find it in PDF format here:

http://www.ascotti.org/programming/ches ... 0Rebel.pdf

Although my ordering uses simpler methods, when I adjusted the weights according to the paper the engine (Kiwi) improved noticeably, so here's what I'm using now:

Code: Select all

const int   BonusForWinningCapture      = 200 * BonusMultiplier;
const int   BonusForPromotionCapture    = 190 * BonusMultiplier;
const int   BonusForMajorPromotion      = 180 * BonusMultiplier;
const int   BonusForGoodCapture         = 170 * BonusMultiplier;
const int   BonusForKiller1             = 100 * BonusMultiplier;
const int   BonusForKiller2             =  90 * BonusMultiplier;
const int   BonusForMinorPromotion      =  80 * BonusMultiplier;


The move from the transposition table is always considered first and when all of the above fails then the history table is used. I use MVV/LVA and possibly SEE if MVV/LVA returns a losing capture.

[Zach Wegner]

Hi Robert,

I don't think you should be too worried about the branching factor being around 7 when you don't have quiescence or null move. This probably isn't that bad for the opening position without these. Quiescence is needed for search accuracy, and null move or some type of forward pruning is needed to search to any useful depth.

Also, if you are going to consider checks in move ordering, you should give them a penalty, unless they are known to make progress tactically; this is because you are looking for not necessarily the best move, but rather the move that can give you a cutoff with the least search effort. Most checks in the search will do nothing but stall, and will just trigger an extension leading to a bigger subtree.

Zach

[Anonymous]

Wow, thanks for the response

You guys really made my day!
Now, lots of things start to make sense for me. I understood that i need to do a lot more thinking before implementing stuff, as the check test and other things you mentioned are really pointless. Looks like i have some homework to do

I'll keep you updated on how things are going.