Jump to content
  • Advertisement

crybot

Member
  • Content Count

    9
  • Joined

  • Last visited

Community Reputation

143 Neutral

About crybot

  • Rank
    Newbie
  1.   sorry then, I misunderstood what you said. Now I think i have no more problems and dubts with search, I just have to improve move ordering and try to apply more advanced search strategies.   Thank you for all
  2. I understand.   I finally completely debugged my engine and found an other few bugs and now the transposition table is bug free (tested with my perft suite). Despite this, when i make my program match itself it still produce a different end state with and without transposition table. What could be the problem? Are we sure that it should produce the same result?   for clarity i post my actual code:   alpha-beta search: int Search::search(int depth, int alpha, int beta, Board& board) { int bound = Alpha; int pos = 0; int score; Move best = Constants::NullMove; Move moves[Constants::MaxMoves]; if((score = board.Table.Probe(board.zobrist, depth, alpha, &best, beta)) != TranspositionTable::Unknown) return score; if(depth == 0) return quiesce(alpha, beta, board); BitBoard pinned = board.GetPinnedPieces(); // tries best move first (if there is one) if(best != Constants::NullMove) { assert(board.IsMoveLegal(best, pinned)); legal++; board.MakeMove(best); score = -search(depth - 1, -beta, -alpha, board); board.UndoMove(best); if( score >= beta ) return beta; if( score > alpha ) { bound = Exact; alpha = score; } } MoveGenerator::GetPseudoLegalMoves<false>(moves, pos, board); // get captures and non-captures for (int i=0; i<pos; i++) { if (board.IsMoveLegal(moves, pinned)) { board.MakeMove(moves); score = -search(depth - 1, -beta, -alpha, board); board.UndoMove(moves); if( score >= beta ) { board.Table.Save(board.zobrist, depth, beta, best, Beta); return beta; // fail hard beta-cutoff } if( score > alpha ) { bound = Exact; alpha = score; // alpha acts like max in MiniMax best = moves; } } } board.Table.Save(board.zobrist, depth, alpha, best, bound); return alpha; }     transposition table class:   TranspositionTable::TranspositionTable(unsigned long size) { Size = size; Table = new HashEntry[size]; // dynamic allocation is fine during program initialization } void TranspositionTable::Save(ZobristKey key, Byte depth, int score, Move move, Byte bound) { HashEntry* hash = &Table[key % Size]; if (depth >= hash->Depth) // it runs faster than depth > hash->Depth { hash->Hash = key; hash->Score = score; hash->Depth = depth; hash->Bound = bound; hash->BestMove = move; } } int TranspositionTable::Probe(ZobristKey key, Byte depth, int alpha, Move* move, 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; } *move = hash->BestMove; // get best move on this position } return TranspositionTable::Unknown; }     could it be a replacement scheme problem or maybe a hash collision one?
  3.     you are right... I didn't know that even if a char should be of size 1 byte the compiler allocate 4 byte for it(I still don't get why)...
  4.   I know, I planned to change move encoding not just for the hashentry, but also for move generation. It will take some time, so i'll do it when i can. Anyway now a HashEntry is a 18 bytes object.   Can you tell me something about what i wrote in my previous post?
  5.   namespace Napoleon { enum ScoreType { Exact, Alpha, Beta }; class HashEntry { public: ZobristKey Hash; // unsigned long long Byte Depth; // unsigned char Byte Bound; // unsigned char Move BestMove; // 32 bit integer wrapper int Score; HashEntry(); HashEntry(ZobristKey, Byte, int, Move, Byte); }; }
  6.   I've just implemented a sort of iterative deeping (without time control, just for testing the engine) and started checking correctness of the transposition table. I have found a few bugs and the engine seems to work properly now:   point 1 and 2 are ok, but point at point 3 i noticed that then engine doesn't produce the same final state after a "self-play" with and without transposition table. I also tried to build a perft routine with the transposition table and, probably for some kind of collision error, i got, at depth 6, a node count of 119060316 instead of 119060324 (that i can obtain if I reduce the table size...). I think zobrist keys are ok, so what's going on?   The last thing I have doubts about is principal variation: I'm triyng to improve move ordering and it seems that principal variation moves are the most important moves to try during alpha-beta search, but, with transposition table implemented, aren't them already the first moves tried (best moves)?   Thanks.
  7.   That's sound cheaper than what I implemented now, I'll try. You said that you can encode a move in 16 bit, but as far as I know the minimum is 32 bit (how do you manage castle and en passants?). Omitting this, I made some test when i was working on the move generator and it came out that my move encoding (which is a class with 4 byte fields ) is faster than using a single 32 bit integer for representing it. Should I change encode method for saving some memory in the transposition table?     for trying  point one I should first implement iterative deeping (when should i do that?). I will try point 2 and 3 right now.   Thank you for your detailed answers.   P.S. I've just implemented MVV-LVA and the search is now MUCH faster! thank you.
  8. Thanks for your answer, now I see all more clear,  but I still have some doubts: regarding Transposition tables, should i save leaf nodes during alphabeta (and maybe also during quiescence search)? I tried to run the program without saving them and it seems to work faster. For storing the best move, can i just use the index of the move inside the array?   That's all, thank you, again.   P.S. i forgot one important thing: How can i prove my transposition table is working correctly?
  9. 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, pinned)) { board.MakeMove(moves); score = -search(depth - 1, -beta, -alpha, board); board.UndoMove(moves); 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
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!