Evaluate(board, depth,\n numeric_limits<float>::min(), numeric_limits<float>::max(), isBlack);<\/pre><\/div>\n\n\n\nI think the logic here is slightly hard to follow. Think about what happens when it is looking at the moves for black. It keeps track of the best evaluation it has found for black, it will return that evaluation. It also keep track of alpha<\/code>, the best evaluation here or in earlier branches. If the best evaluation is greater than beta<\/code> it knows that white never let this branch be taken. As the branch won’t be taken it doesn’t have to do any more work.<\/p>\n\n\n\nHow much can be skipped is very dependant on the order we examine the moves in.\nIf we’re lucky we only have to look at the first move and can skip all the rest.\nIf we’re unlucky we have to look at them all.\nIs there some way to choose the order to be lucky?<\/p>\n\n\n\n
Recursive decent<\/h2>\n\n\n\n
Let’s ignore alpha-beta pruning briefly.\nWe have an easy way to control how long a search will take, how deep we let it go.\nIf searching to a depth of 10 took 10 seconds then searching to a depth of 11 might take 20 seconds.\nThe deeper we go the slower it will be.\nConversely the shallower we go the faster it will be.\nGoing to a depth 9 will only take 5 seconds.\nThe evaluations we get won’t be as good<\/em> but they should still be pretty good<\/em>.<\/p>\n\n\n\nNow let’s think about alpha-beta pruning again.\nWe’ve a technique which could drastically speed up our search if only we could guess the right order to search.\nWe’ve a technique to quickly get a pretty good set of evaluation.\nLet’s combine them.<\/p>\n\n\n\n
Recursive decent makes a series of calls to Evaluate<\/code> each deeper than the last.\nThe evaluations from the previous calls are used to choose the order to consider moves.<\/p>\n\n\n\nfloat function Evaluate(BoardEvaluations& boardEvaluations,\n const Board& board, size_t depth, float alpha, float beta, bool isBlack) {\n if (depth == 0 || board.IsCheckmate()) {\n return board.GetEvaluation();\n }\n\n if (isBlack) {\n float evaluation = numeric_limits<float>::min();\n const auto newBoards = board.GetBoardsAfterMove(isBlack);\n for (const auto& newBoard : ReorderBoards(newBoards, boardEvaluations))) {\n evaluation = std::max(evaluation, Evaluate(boardEvaluations, newBoard, depth - 1, !isBlack));\n alpha = std::max(evaluation, alpha);\n boardEvaluations[newBoard] = evaluation;\n\n if (evaluation >= beta) {\n break;\n }\n }\n }\n else {\n float evaluation = numeric_limits<float>::max();\n const auto newBoards = board.GetBoardsAfterMove(isBlack);\n for (const auto& newBoard : ReorderBoards(newBoards, boardEvaluations))) {\n evaluation = std::min(evaluation, Evaluate(boardEvaluations, newBoard, depth - 1, !isBlack));\n beta = std::min(evaluation, beta);\n boardEvaluations[newBoard] = evaluation;\n\n if (evaluation <= alpha) {\n break;\n }\n }\n }\n return evaluation;\n}<\/pre><\/div>\n\n\n\nand is called like this:<\/p>\n\n\n\n
for (size_t depth = 0; depth < maxDepth; depth++) {\n Evaluate(boardEvaluations, board, depth,\n numeric_limits<float>::min(), numeric_limits<float>::max(), isBlack);\n }<\/pre><\/div>\n\n\n\nAs the previous evaluations were pretty good then we will probably be lucky.\nAs we’re probably lucky a great deal of each tree can be skipped.\nEven though we make more<\/em> calls to Evaluate<\/code> each call is going to be faster so we take less time overall.<\/p>\n\n\n\nAssuming you want your chess engine to win this is a situation where it is worth spending time on optimisation.\nA faster algorithm lets you search a bigger tree in the same amount of time.\nA bigger tree means looking more moves ahead.<\/p>\n\n\n\n
There’s a lot<\/strong> more to chess algorithms than this but it’s an important part.<\/p>\n\n\n\nCode presentation<\/h2>\n\n\n\n
While writing this I had to decide how to present the code. The examples I was cribbing from on Wikipedia aren’t something that I’d use in a project. However they might make things easier for anyone who wants to follow those links. In the end I stuck close to the original examples as they emphasis the min<\/code> and max<\/code>.<\/p>\n\n\n\nIf I making my own project then it would:<\/p>\n\n\n\n
\n- Reduce repetition. To make
alpha<\/code> and beta<\/code> work they swap back and forth between calls.<\/li>\n\n\n\n- Use explicit types.<\/li>\n\n\n\n
- Combine the board and player.<\/li>\n\n\n\n
- Store board evaluations as a member variable.<\/li>\n<\/ul>\n\n\n\n
Evaluation Evaluator::Get(\n const GameState& state, size_t depth, Evaluation alpha, Evaluation beta) {\n if (depth == 0 || state.IsCheckmate()) {\n return state.GetEvaluation();\n }\n\n const auto player = state.GetActivePlayer();\n const auto pick = player.GetPickFunction();\n const auto cutoff = player.GetCutoffFunction();\n \n auto evaluation = player.GetWorstEvaluation();\n\n const auto newBoards = state.GetBoardsAfterMove();\n for (const auto& newBoard : ReorderBoards(newBoards))) {\n evaluation = pick(evaluation, Evaluate(newBoard, depth - 1, beta, alpha));\n alpha = pick(evaluation, alpha);\n m_BoardEvaluations[newBoard] = evaluation;\n\n if (cutoff(evaluation, beta)) {\n break;\n }\n }\n return evaluation;\n}<\/pre><\/div>\n","protected":false},"excerpt":{"rendered":"There are problems that are hard to solve. There are problems that are easy to solve if you don’t care about speed. At university the algorithms course was one of my favourites. Finding the right algorithm can mean being able to solve the problem much faster. Maybe you’ll have to discover it yourself but there […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"categories":[1],"tags":[22,7],"class_list":["post-107","post","type-post","status-publish","format-standard","hentry","category-general","tag-algorithms","tag-performance"],"_links":{"self":[{"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/posts\/107","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/comments?post=107"}],"version-history":[{"count":3,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/posts\/107\/revisions"}],"predecessor-version":[{"id":170,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/posts\/107\/revisions\/170"}],"wp:attachment":[{"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/media?parent=107"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/categories?post=107"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/tags?post=107"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}