LMR, Razoring, Futility.... with chess varient with drops?

[jdm64]

I'm currently working on a chess engine to play my chess variant (Genesis Chess). The variant starts out with a blank board and pieces can be dropped in on a turn. The branching factor is huge, and is probably the main reason my engine is so slow. On my 1.8GHz cpu, the engine finishes ply (half-turns) 5 in about 20 secs. Going for 6, results in over 1 minuet. My perft function returns:

Code: Select all

depth  nodes
1      64
2      3,612
3      953,632
4      248,188,772
5      64,518,625,428

The engine currently implements:

• Negascout Search
  Quiescence Search
  Iterative Deepening
  Killer Move
  Simple transposition table
  Simple evaluation (material + piece-square tables)

It's still very slow, but plays very aggressively (at least against humans). I want to add advanced pruning and reduction functions to improve the speed. I have a few questions:

1) In LMR, is the reductions recursive? I created a recursive LMR and it exponentially improved the speed, but killed the strength of the engine! It was missing many good moves.

2) Given the unique nature of the piece drops, what would be the safest "advanced feature" to add first. I think the game tree is "unstable" with the piece placements happening at any time (that's why my simple implementations are failing to strengthen the engine -- I think).

3) While the engine plays aggressively, it has a weakness with pawns as they are the lowest value. What could I do to improve play with pawns? In my variant, pawn are used for quick attack/defence, but also as a good strategy for trapping the king.

4) My eval is simple, what would be the next logical step after material and piece-square tables?

5) Any other suggestions or things I should keep in mind.

I can supply source code on request.

[FlavusSnow]

Did you try Null-move?

[jdm64]

Did you try Null-move?

Not, yet. But, I'm assuming that just adding null-move is not the solution to everything. I mean, most engines have other advanced features beside null-move -- right?

Also what about zugzwang positions? Does piece placements increase those from happening or reduce? With my variant, each side is creating the placements they want. So because both sides are doing this, after a while both sides are in a position where all pieces are protected as long as nobody moves. Once this balance is thrown off, a chain of captures usually results. At least this this is how two humans usually play.

And I'm assuming null-move is applied recursively? I don't exactly understand the recursive part of null-move

[hgm]

In my Shogi engine I use null-move pruning and LMR. Null-move is very effective in drop games, as they are the ideal refutation for senseless drops. Usually a drop has a negative impact on eval, because pieces in hand are worth more than pieces on the board (PST-wise).

For LMR I reduce (most) non-captures by 1ply, and (non-check) drops by 2 ply. But if the following null move is refuted by a capture with the dropped or moved piece, I undo the reduction.

[jdm64]

Would the following code be a correct implementation of nullmove?

Code: Select all

makeNull()
{
    ply++
    wtm ^= true // change color to move
    key += hashbox[wtm] // update hash key for change of color
}
unmakeNull()
{
    ply--
    wtm ^= true // change color to move
    key -= hashbox[wtm] // update hash key for change of color
}

int nullDepth = 3; // the null-move R value?

negascout(alpha, beta, depth)
{
    // try hash move first

    // try null move
    if (notInCheck && nullDepth) {
        nullDepth--;
        score = -nullmoveSearch(-beta, -alpha, depth-1);
        nullDepth++;
        if (score >= beta)
            return score;
    }
    // continue searching
}
nullmoveSearch(alpha, beta, depth)
{
    // Like negascout but without any null move
    // calls negascout to search deeper
}

1) Are there any restrictions (other than check) that I should know, especially with the piece drops.
2) What if the score returned improved alpha, but not beta-cutoff, do I do anything special?

[hgm]

No, that is not the way null move works. More like this:

Code: Select all

makeNull()
{
    ply++
    wtm ^= true // change color to move
}
unmakeNull()
{
    ply--
    wtm ^= true // change color to move
}

negascout(alpha, beta, depth)
{
    // try hash move first

    // try null move
    if (notInCheck) {
        score = -nullmoveSearch(-beta, -alpha, depth-1-R);
        if (score >= beta)
            return score;
    }
    // continue searching
}
nullmoveSearch(alpha, beta, depth)
{
    // Like negascout but without any null move
    // calls negascout to search deeper
}

And adding the stm key in stead of XORing it incrementally is suspect (although it might work forproper choice of the hashbox elements). I would not do that incrementally, but just before you use the key for the hash probe (without disturbing the incremental key). Then you only have to do it once per node, rather than in make and unmake.

[jdm64]

No, that is not the way null move works. More like this:

Code: Select all

makeNull()
{
    ply++
    wtm ^= true // change color to move
}
unmakeNull()
{
    ply--
    wtm ^= true // change color to move
}

negascout(alpha, beta, depth)
{
    // try hash move first

    // try null move
    if (notInCheck) {
        score = -nullmoveSearch(-beta, -alpha, depth-1-R);
        if (score >= beta)
            return score;
    }
    // continue searching
}
nullmoveSearch(alpha, beta, depth)
{
    // Like negascout but without any null move
    // calls negascout to search deeper
}

And adding the stm key in stead of XORing it incrementally is suspect (although it might work forproper choice of the hashbox elements). I would not do that incrementally, but just before you use the key for the hash probe (without disturbing the incremental key). Then you only have to do it once per node, rather than in make and unmake.

I have an index in my hashbox for white to move and add/sub depending on side to move. I think this is what you said here.

I also don't understand why my method using a nullDepth counter wouldn't work and why depth-1-R is the correct way. My method would do a deeper search, as the depth is only being -1. So, wouldn't that be safer?

[hgm]

It is safer in that branch. But the nodes you spent extra to make it safer, are taken out of the node budget for other branches, making those unsafer.

The whole reason that null-move pruning makes engines so much stronger is that the nodes are used where they resort the most effect: economize on nodes in branches that do not need them, and reallocate them to branches that might benifit from them.

To spot trouble after a null move requires much less depth than usual, because the null move gives the opponent the opportunity to start any nastiness immediately. And even if there would be some nastiness waiting foryou just behind the horizon, you always have a null-move slot available to pre-empt it. So searching null moves at the same depth as other moves is simply a waste of nodes.

About the hash key:

What I said referred to the update of the key for the board position. I did not mention side-to-move key. I do not treat that incrementally, as this is not faster than applying it from scratch (and in many cases even faster).

The proper procedure is to first decide how you would calculate the key from scratch, like

SUM(key[piece][square]) + key[stm]

and then determine the incrementaleffect onemove has on it.In this case that would be

hashKey += key[piece][to] - key[piece][from] - key[victim][to] + key[newStm] - key[oldStm]

But this makes the stm part needlessly complex.

[jdm64]

So, my null-move would work, but the node saving would be mostly worthless. What about the R value? Is that always 2 or 3 or what's the best way to set it?

Also, I'm fairly sure I'm doing the hash key right. My incremental update in make/unmake results in the same key as my rebuildHash function. I handle the stm like:

key += (stm == WHITE)? -hashBox[WTM_HASH] : hashBox[WTM_HASH];

[micron]

Fixed R = 2 is OK for starters. Later, after you have null move pruning working, you can test a refinement to see if it gives better results:
if ( depth < 6 ) R = 2; else R = 3;

A hash key is normally modified by bitwise xor, not by an arithmetic operation. A common way to change sides is to invert all the bits:
key ^= 0xffffffffffffffffULL;

Robert P.