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

**Edited by crybot, 21 April 2013 - 04:07 PM.**