ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

SEE with alpha beta
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Onno Garms



Joined: 12 Mar 2007
Posts: 224
Location: Bonn, Germany

PostPost subject: SEE with alpha beta    Posted: Sun Aug 14, 2011 8:06 pm Reply to topic Reply with quote

There are two different ways to implement SEE.

One is to have some early shortcuts (e.g. in see_sign) and if they don't lead to cutoffs, build the complete swap list first and evaluate it at the end. This approach was for example taken by Fruit and Stockfish.

At first glance this approach seems to be inferior, because once the swap list is started, it is always built completely even if its later evaluation shows that only the first terms would be needed.

Several people have written SEE with alpha beta independently. Me in Onno, Fritz in Loop and HGM here: http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=310782&t=30905
(Note that HGM seems not to prevent moving into check. This cannot be handled with infinite king value if the king is captured by the other king which in turn can be recaptured. Test with this position: 8/8/3p4/4r3/2RKP3/5k2/8/8 b - - ).

I thought that alpha beta SEE would be better. Marco disagreed because of the extra branches.

I gave an alpha beta SEE a try in Stockfish. My result was that the speed is practically the same. nps on "stockfish bench" has no significant differences. Cachegrind estimates time for SEE in at 6.8% in the original and 6.7% with alpha beta (both with my probcut patch, at depth 11). Your mileage may vary, but I would be surprised if either version is significantly faster than the other if a different computer is used.

Anyway, here is the SEE function. Supposed to replace both see and see_sign. Call with update=false if the search window has zero width.

Code:

template<bool update> int Position::see (Square from, Square to, int alpha, int beta) const
{
    assert(square_is_ok(from));
    assert(square_is_ok(to));

    // handle castle moves
    if (color_of_piece_on(from)==color_of_piece_on(to))
        return 0; // TODO: for FRC, consider to compute SEE of rook move instead

   
    // remove his piece from target square
    // -------------------------------------------------------------

    // get his piece to remove
    PieceType capturedType = type_of_piece_on(to);
   
    // King cannot be recaptured; illegal moves are pruned at higher level
    if (type_of_piece_on(from) == KING)
        return seeValues[capturedType];

    Bitboard occupied = occupied_squares();

    // Handle en passant moves
    if (st->epSquare == to && type_of_piece_on(from) == PAWN)
    {
        Square capQq = (side_to_move() == WHITE ? to - DELTA_N : to - DELTA_S);
       
        assert(capturedType == PIECE_TYPE_NONE);
        assert(type_of_piece_on(capQq) == PAWN);
       
        // Remove the captured pawn
        clear_bit(&occupied, capQq);
        capturedType = PAWN;
    }
   
    int eval = seeValues[capturedType];

    // Assume that my piece cannot be (re)captured.
    // If the move is still not good enough, return.
    if (eval <= alpha)
        return alpha;

    // update
    if (update && eval < beta)
        beta = eval;

   
    // my initial move
    // -------------------------------------------------------------

    // get my moving piece
    capturedType = type_of_piece_on (from);

    // early check: assume that my piece can be (re)captured.
    //              If the move is still good, return.
    eval -= seeValues[capturedType];
    if (eval >= beta)
        return beta;

    // update
    if (update && eval > alpha)
        alpha = eval;

    // execute the move
    clear_bit(&occupied, from);


    // some setup
    // -----------------------------------------------------------

    // Find all attackers to the destination square
    Bitboard attackers =  (rook_attacks_bb(to, occupied)  & pieces(ROOK, QUEEN))
                        | (bishop_attacks_bb(to, occupied)& pieces(BISHOP, QUEEN))
                        | (attacks_from<KNIGHT>(to)       & pieces(KNIGHT))
                        | (attacks_from<KING>(to)         & pieces(KING))
                        | (attacks_from<PAWN>(to, WHITE)  & pieces(PAWN, BLACK))
                        | (attacks_from<PAWN>(to, BLACK)  & pieces(PAWN, WHITE));

    // setup colors
    Color me = color_of_piece_on(from);
    Color him = opposite_color (me);

   
    while (true)
    {
        // his (re)capture
        // ------------------------------------------------------------
       
        // get his attackers
        Bitboard stmAttackers = attackers & pieces_of_color(him);
       
        // no more captures possible: return
        if (!stmAttackers)
            return beta;

        // last move or capture was illegal
        if (capturedType==KING)
            return alpha;
       
        // find his cheapest attacker
        for (capturedType = PAWN; !(stmAttackers & pieces(capturedType)); capturedType++);
       
        // early check: assume that his piece can be recaptured
        //              if that would not be sufficient, return
        eval += seeValues[capturedType];
        if (eval <= alpha)
            return alpha;

        // update
        if (update && eval < beta)
            beta = eval;
       
        // execute his (re) capture
        Bitboard b = stmAttackers & pieces(capturedType);
        occupied ^= b & (~b + 1);
        attackers |=  (rook_attacks_bb(to, occupied)   & pieces(ROOK, QUEEN))
                    | (bishop_attacks_bb(to, occupied) & pieces(BISHOP, QUEEN));
        attackers &= occupied;


        // my recapture
        // -----------------------------------------------------------
       
        // get my attackers
        stmAttackers = attackers & pieces_of_color(me);
       
        // no more captures possible: return
        if (!stmAttackers)
            return alpha;

        // last (re)capture was illegal
        if (capturedType==KING)
            return beta;
       
        // find my cheapest attacker
        for (capturedType = PAWN; !(stmAttackers & pieces(capturedType)); capturedType++);
       
        // early check: assume that my piece can be recaptured.
        //              If the move is still good, return
        eval -= seeValues[capturedType];
        if (eval >= beta)
            return beta;

        // update
        if (update && eval > alpha)
            alpha = eval;
       
        // execute my capture
        b = stmAttackers & pieces(capturedType);
        occupied ^= b & (~b + 1);
        attackers |=  (rook_attacks_bb(to, occupied)   & pieces(ROOK, QUEEN))
            | (bishop_attacks_bb(to, occupied) & pieces(BISHOP, QUEEN));
        attackers &= occupied;
    }
}
Back to top
View user's profile Send private message
Display posts from previous:   
Subject Author Date/Time
SEE with alpha beta Onno Garms Sun Aug 14, 2011 8:06 pm
      Re: SEE with alpha beta H.G.Muller Sun Aug 14, 2011 9:11 pm
      Re: SEE with alpha beta Michael Hoffmann Sun Aug 14, 2011 10:16 pm
      Re: SEE with alpha beta Don Dailey Fri Aug 19, 2011 10:11 pm
            Re: SEE with alpha beta H.G.Muller Sun Aug 21, 2011 10:09 am
                  Re: SEE with alpha beta Don Dailey Sun Aug 21, 2011 3:03 pm
                        Re: SEE with alpha beta H.G.Muller Sun Aug 21, 2011 3:55 pm
                              Re: SEE with alpha beta Don Dailey Sun Aug 21, 2011 5:27 pm
                                    Re: SEE with alpha beta H.G.Muller Sun Aug 21, 2011 6:25 pm
                                          Re: SEE with alpha beta Don Dailey Sun Aug 21, 2011 6:37 pm
                                                Re: SEE with alpha beta Rein Halbersma Sun Aug 21, 2011 6:51 pm
                                                Re: SEE with alpha beta H.G.Muller Sun Aug 21, 2011 7:29 pm
                                                      Re: SEE with alpha beta Don Dailey Sun Aug 21, 2011 8:12 pm
                                    Re: SEE with alpha beta Zach Wegner Sun Aug 21, 2011 7:35 pm
                                          Re: SEE with alpha beta H.G.Muller Sun Aug 21, 2011 8:19 pm
                                                Re: SEE with alpha beta Zach Wegner Sun Aug 21, 2011 8:27 pm
                                                      Re: SEE with alpha beta H.G.Muller Sun Aug 21, 2011 9:29 pm
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads