Permalink
Browse files

Use correct occupancy in connected_threat()

When checking if a move defends the threatened piece
we correctly remove from the occupancy bitboard the
moved piece. This patch removes from the occupancy also
the threatening piece so to consider the cases of moves
that defend the threatened piece x-raying through the
threat move.

As example in this position:
r3k2r/p1ppqp2/Bn4p1/3p1n2/4P1N1/5Q1P/PPP2P1P/R3K2R w KQkq - 1 10

The threat black move is dxe4. With this patch we include
(and so don't prune) white's Bb7 that would be pruned otherwise.

The number of affected position is very low, around 1% of cases,
so we don't expect ELO changes, neverthless this is the logical
and natural thing to do.

Patch suggested by Hongzhicheng.

new bench: 5323798
  • Loading branch information...
1 parent 4e31c39 commit fe1cbe26383085a44809d56493d29ce9c1815aa8 @mcostalba committed Oct 30, 2012
Showing with 2 additions and 2 deletions.
  1. +2 −2 src/search.cpp
View
@@ -1426,8 +1426,8 @@ namespace {
&& ( PieceValue[MG][pos.piece_on(tfrom)] >= PieceValue[MG][pos.piece_on(tto)]
|| type_of(pos.piece_on(tfrom)) == KING))
{
- // Update occupancy as if the piece is moving
- Bitboard occ = pos.pieces() ^ mfrom ^ mto;
+ // Update occupancy as if the piece and the threat are moving
+ Bitboard occ = pos.pieces() ^ mfrom ^ mto ^ tfrom;
Piece piece = pos.piece_on(mfrom);
// The moved piece attacks the square 'tto' ?

7 comments on commit fe1cbe2

@hongzhicheng

Great job! I am so happy that I can contribute something to this great engine.

I really hope you can make some effort to try the idea of skipping the static evaluation right after making a null move. Among all the calls to search or qsearch subroutines, around 20% to 30% are following a null move. So this idea can really improve the search speed. I can think of two ways to achieve this:

  1. make the static evaluation symmetric. To do so, we need modify some codes of the eval function, for example, the tempo variable will become a Value variable but not a Score variable,
  2. accept a somewhat different static eval for the search node following a null move. The quality of this distorted eval might not be as good as the normal ones, but because we can save a lot of time by skipping a call to the function evaluate(), we might achieve some gain in playing strength

Now I have some other ideas you might be interested.

  1. In function do_null_move, Stockfish doesn't increase the node count, so it underestimates the actual number of nodes searched. If you add

    nodes++;

in do_null_move, you will see NPS jump by about 20% percent.

this can partially explain why NPS of IPPOLIT is so much higher than that of Stockfish. By the way, IPPOLIT does lazy eval, which makes NPS 10% higher, but makes little elo gain. The third reason why IPPOLIT is fast is that the branch factor of Stockfish is lower than IPPOLIT, so Stockfish dose more work to prune more potential nodes and yet the effort is not shown in NPS.

  1. Stockfish has material hash table for each search thread. This table is updated during the search. we can precalculate the material table for all possible material configurations and just keep one instance of it, and all search threads share it, since it will not be changed during a search. This seems to increase the search speed by about 1%.

  2. In function pop_lsb(), Stockfish uses the following command to get rid of the least significant bit.

    *b &= ~(1ULL << s);

On my intel CPU, this is much slower than
*b &= *b - 1;

As you've said before, this is due to the "lea" instructions in all x86 cpus. I'd suggest you use "*b &= *b - 1" for Intel and AMD x86 and x64 cpus. So you might need to add some codes to generate different comands for different cpu's.

  1. Some time ago, you add a line of code to function generate(),

    while (cur != end)
    if ( (pinned || from_sq(cur->move) == ksq || type_of(cur->move) == ENPASSANT)
    && !pos.pl_move_is_legal(cur->move, pinned))
    cur->move = (--end)->move;
    else
    cur++;

such that the perft speed goes up by 20% or so. unfortunately, this trick can't improve the search speed. Nevertheless, we still can play the trick inside the function Position::pl_move_is_legal, and it might help improve the search a little bit,

bool Position::pl_move_is_legal(Move m, Bitboard pinned) const {

assert(is_ok(m));
assert(pinned == pinned_pieces());

Square from = from_sq(m);
PieceType pt = type_of(piece_on(from))
bool kingMove = (pt == KING);
MoveType mt = type_of(m);

// Return true if piece to move is not king and there are no pinned pieces
// and squares
if (!kingMove && !pinned && mt != ENPASSANT)
return true;

Color us = sideToMove;

assert(color_of(piece_moved(m)) == us);
assert(piece_on(king_square(us)) == make_piece(us, KING));

// En passant captures are a tricky special case. Because they are rather
// uncommon, we do it simply by testing whether the king is attacked after
// the move is made.
if (mt == ENPASSANT)
{
Color them = ~us;
Square to = to_sq(m);
Square capsq = to + pawn_push(them);
Square ksq = king_square(us);
Bitboard b = (pieces() ^ from ^ capsq) | to;

  assert(to == ep_square());
  assert(piece_moved(m) == make_piece(us, PAWN));
  assert(piece_on(capsq) == make_piece(them, PAWN));
  assert(piece_on(to) == NO_PIECE);

  return   !(attacks_bb<  ROOK>(ksq, b) & pieces(them, QUEEN, ROOK))
        && !(attacks_bb<BISHOP>(ksq, b) & pieces(them, QUEEN, BISHOP));

}

// If the moving piece is a king, check whether the destination
// square is attacked by the opponent. Castling moves are checked
// for legality during move generation.
if (kingMove)
return type_of(m) == CASTLE || !(attackers_to(to_sq(m)) & pieces(~us));

// A non-king move is legal if and only if it is not pinned or it
// is moving along the ray towards or away from the king.
return !(pinned & from) || squares_aligned(from, to_sq(m), king_square(us));
}

BTW, I had this trick in my Chinese engine a year ago, and it did increase the perft speed a lot and the search speed a little.

Thanks again for your efforts to listen to a layman of computer chess. I'll keep you updated if I have any other ideas.

Hongzhi

@hongzhicheng

I forgot to mention that after making some changes to the codes of my Chinese chess engine so that the static evaluation function become symmetrical with respect to side_to_move and saving the call to evaluate() following a null move, the search speed of my chess program increases by 5%, and the playing strength is also improved(the modified version scores 60% in a 100 game match against the unmodified one. I repeated the match several times, the modified version always wins).

@mcostalba
Owner
@zamar
zamar commented on fe1cbe2 Oct 31, 2012
  1. King safety is almost symmetric already. Combining Aggressiviness and Cowardice to (Aggressiviness + Cowardice) / 2 is unlikely to cause any ELO change.
  2. I've also considered precalculated material tables: (2 * 3 * 3 * 3 * 9)^2 = 250k entries.
    [0-1 queens][0-2 rooks][0-2 bishops][0-2 knights][0-8 pawns] for both sides. For exotic configurations (e.g. 2 queens) we'd still need to calculate it manually in hash-table. But the possible improvement would be very minor and new version is of course less cache friendly, so don't know if this worth the effort...?
@hongzhicheng

I'd like to point out that Aggressiviness and Cowardice is related to the color of root position and they don't break the symmetry of static eval for any position, so there is no need to worry about them.

@Kingdefender

On Wed, Oct 31, 2012 at 5:36 AM, hongzhicheng notifications@github.comwrote:
I really hope you can make some effort to try the idea of skipping the
static evaluation right after making a null move.
This will require some effort but I think I will test this idea too.

I tried something very simple. In the search as in Stockfish 2.3.1, changed

    // Step 8. Null move search with verification search (is omitted in PV nodes)
    if (   !PvNode
        && !ss->skipNullMove
        &&  depth > ONE_PLY
        && !inCheck
        &&  refinedValue >= beta
        &&  abs(beta) < VALUE_MATE_IN_MAX_PLY
        &&  pos.non_pawn_material(pos.side_to_move()))
    {

to

    // Step 8. Null move search with verification search (is omitted in PV nodes)
    if (   !PvNode
        && !ss->skipNullMove
        &&  depth > ONE_PLY
        && !inCheck
        &&  refinedValue >= beta
        &&  ss->ply > 1
        &&  abs(beta) < VALUE_MATE_IN_MAX_PLY
        &&  pos.non_pawn_material(pos.side_to_move()))
    {

is probably not necessary as long as you don't do nullmove in the rootnode.

 // Step 5. Evaluate the position statically and update parent's gain statistics
    if (inCheck)
        ss->eval = ss->evalMargin = VALUE_NONE;
    else if (tte)
    {
        assert(tte->static_value() != VALUE_NONE);

        ss->eval = tte->static_value();
        ss->evalMargin = tte->static_value_margin();
        refinedValue = refine_eval(tte, ttValue, ss->eval);
    }
    else
    {
        refinedValue = ss->eval = evaluate(pos, ss->evalMargin);
        TT.store(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, ss->evalMargin);
    }

to

// Step 5. Evaluate the position statically and update parent's gain statistics
    if (inCheck)
        ss->eval = ss->evalMargin = VALUE_NONE;
    else if (tte)
    {
        assert(tte->static_value() != VALUE_NONE);

        ss->eval = tte->static_value();
        ss->evalMargin = tte->static_value_margin();
        refinedValue = refine_eval(tte, ttValue, ss->eval);
    }
    else
    {
        if ((ss)->skipNullMove && ((ss-1)->currentMove == MOVE_NULL))
        {
            refinedValue = ss->eval = -(ss-1)->eval;
            ss->evalMargin = -(ss-1)->evalMargin;
        }
        else
            refinedValue = ss->eval = evaluate(pos, ss->evalMargin);
        TT.store(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, ss->evalMargin);
    }

and

    // Evaluate the position statically
    if (inCheck)
    {
        bestValue = futilityBase = -VALUE_INFINITE;
        ss->eval = evalMargin = VALUE_NONE;
        enoughMaterial = false;
    }
    else
    {
        if (tte)
        {
            assert(tte->static_value() != VALUE_NONE);

            evalMargin = tte->static_value_margin();
            ss->eval = bestValue = tte->static_value();
        }
        else
            ss->eval = bestValue = evaluate(pos, evalMargin);

to

    // Evaluate the position statically
    if (inCheck)
    {
        bestValue = futilityBase = -VALUE_INFINITE;
        ss->eval = evalMargin = VALUE_NONE;
        enoughMaterial = false;
    }
    else
    {
        if (tte)
        {
            assert(tte->static_value() != VALUE_NONE);

            evalMargin = tte->static_value_margin();
            ss->eval = bestValue = tte->static_value();
        }
        else
        {
            if ((ss)->skipNullMove && ((ss-1)->currentMove == MOVE_NULL))
            {
                ss->eval = bestValue = -(ss-1)->eval;
                evalMargin = -(ss-1)->evalMargin;
            }
            else
                ss->eval = bestValue = evaluate(pos, evalMargin);
        }

(in the quiescence search)

See also some comments on Talkchess http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=490336&t=45818

Storing of the static evaluation is probably more a waste of space if you have a nullmove and do not actually do a static eval, have not tried it yet without. That should bring some savings if the hashtable does not fill up so fast, on very long searches! At least I hope so!
I wrote that there should be some inclusion of tempo but I am not certain anymore if that would be necessary. Did I overlook some serious bugs guys. At least it compiled and is not crashing etc. I think it is faster but I also added some other improvements from Hongzhi, as they were implemented in the Stockfish master by Marco. What do you guys think?

Regards, Eelco

@mcostalba
Owner
Please sign in to comment.