• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.

crybot

Members
  • 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[i], pinned)) { board.MakeMove(moves[i]); score = -search(depth - 1, -beta, -alpha, board); board.UndoMove(moves[i]); 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[i]; } } } 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[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