Jump to content

  • Log In with Google      Sign In   
  • Create Account

crybot

Member Since 21 Apr 2013
Offline Last Active Jun 20 2013 01:46 PM

Topics I've Started

Chess Engine - search development priority

21 April 2013 - 08:51 AM

hi, I'm currently developing a chess engine in c++ (here is the github repository: https://github.com/crybot/NapoleonPP), it is called NapoleonPP (probably i will change the name...) and it is based on magic bitboards move generation. 

I've recently completed move generation which i think is fast enough (it can calculate perft 6 in about 1,2 seconds without special improvements like threading or transposition tables) . So I started working on search and evaluation, my primary goal was to build a nice search function so i just created a very simple evaluation function that takes care only of material, movement of some pieces and center control.

Now i'm stuck...

I tried to play with the program, and i must say it plays a discrete chess, but it is sooo slow... at some point it takes more than 10 seconds to search under ply 6...

 

what i need now is to know what to do first to improve my engine speed.

 

I need to implement move ordering (by now i search first captures and then non captures), Null move pruning, pv-search, principal variation extraction, iterative deeping, transposition tables(actually i've implemented transposition tables, but i didn't see benefits on speed, maybe i did something wrong? ), ecc.ecc.

 

If someone could direct me to the right way (maybe with description and some resources on the argument) I would be very happy. 

Here is my actual search function:

 

int Search::search(int depth, int alpha, int beta, Board &board)
    {
        int bound = Alpha;
        int score;

        if((score = board.Table.Probe(board.zobrist, depth, alpha, beta)) != TranspositionTable::Unknown)
            return score;

        if( depth == 0 )
        {
            score = quiesce(alpha, beta, board);
            board.Table.Save(HashEntry(board.zobrist, depth, score, 0, Exact)); // should i save leaf nodes??
            return score;
        }

        int pos = 0;
        Move moves[Constants::MaxMoves];

        BitBoard attackers = board.KingAttackers(board.KingSquare[board.SideToMove], board.SideToMove);

        if (attackers)
            MoveGenerator::GetEvadeMoves(board, attackers, moves, pos);
        else
            MoveGenerator::GetAllMoves(moves, pos, board);

        BitBoard pinned = board.GetPinnedPieces();

        for (int i=0; i<pos; i++)
        {
            if (board.IsMoveLegal(moves[i], pinned))
            {
                board.MakeMove(moves[i]);
                score = -search(depth - 1, -beta, -alpha, board);
                board.UndoMove(moves[i]);

                if( score >= beta )
                {
                    board.Table.Save(HashEntry(board.zobrist, depth, beta, 0, Beta));
                    return beta;   //  fail hard beta-cutoff
                }
                if( score > alpha )
                {
                    bound = Exact;
                    alpha = score; // alpha acts like max in MiniMax
                }
            }
        }

        board.Table.Save(HashEntry(board.zobrist, depth, alpha, 0, bound));
        return alpha;
    }

 

 

Here is Transposition Table Code:

 

    TranspositionTable::TranspositionTable(unsigned long size)
    {
        Size = size;
        Table = new HashEntry[size];
    }

    void TranspositionTable::Save(HashEntry entry)
    {
        HashEntry* hash = &Table[entry.Hash % Size];

        hash->Hash = entry.Hash;
        hash->Score = entry.Score;
        hash->Depth = entry.Depth;
        hash->Bound = entry.Bound;
    }

    int TranspositionTable::Probe(ZobristKey key, int depth, int alpha, int beta)
    {
        HashEntry* hash = &Table[key % Size];

        if (hash->Hash == key)
        {
            if (hash->Depth >= depth)
            {
                if (hash->Bound == Exact)
                    return hash->Score;
                if (hash->Bound == Alpha && hash->Score <= alpha)
                    return alpha;
                if (hash->Bound == Beta && hash->Score >= beta)
                    return beta;
            }
        }

        return TranspositionTable::Unknown;
    }

 

I made some test, in particular i calculated kNodes per second by incrementing a variable every time i call alphabeta and quiesce:

I got about 3000-4000 kn/s using 32 MB for the transposition table (even if it does not make almost any difference).

My system configuration:

 

O.S.: Arch linux 64 bit (xfce)

CPU: Intel i5 760 2.80 Ghz (Quad core)

 

It is fast enough? I'm average with other non professional engines?

 

 

Any advice is welcome.

thanks all smile.png


PARTNERS