Browse Prior Art Database

Using parallel processing to Improve Alpha Beta pruning algorithm

IP.com Disclosure Number: IPCOM000237179D
Publication Date: 2014-Jun-06
Document File: 3 page(s) / 33K

Publishing Venue

The IP.com Prior Art Database

Abstract

We present a new method of computing the best move in two player game e.g. chess or checkers. Classical approach of computing best move is to search a game tree. The main challenge with searching a game tree is its size; exponential number of nodes that have to be visited. The most efficient algorithm significantly reducing number of nodes to be visited is alpha beta pruning. Alpha beta pruning algorithm is single threaded. We show how to improve performance of the alpha beta pruning in multi processor architecture by having number of threads that searches the game tree. This task is not trivial since naive distribution of the searching task may result in no improvement over the single threaded search.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 01 of 3

Using parallel processing to Improve Alpha Beta pruning algorithm

We present a new method of computing the best move in two player game e.g. chess or checkers. The classical approach of computing best move is searching a game tree

where nodes on odd levels represents moves of the player A while the nodes of even levels represents moves of the player B. The root node of the tree represents the current position. Node of a tree on level d (depth) represents board position after d moves. The branching factor b of the tree is determined by number of possible moves from a node. The main problem with searching a game tree, to compute an optimal move, is its size; exponential number of nodes that have to be visited. More precisely, if each player has got b possible moves and player wants to analyze board positions with depth d (d moves forward) it would have to visit O(b^d) nodes.

The most efficient algorithm significantly reducing number of the nodes to be visited is alpha beta pruning. This algorithm reduces number of nodes to be visited to O(b^(3d/4)). The classical implementation is single threaded. We show how to improve performance of the alpha beta pruning in multi processor architecture by having number of threads that searches the game tree. This task is not trivial since naive distribution of the searching task may result in no improvement over the single threaded search. This is because a thread could search subtrees that would be pruned in single threaded implementation. So, extra threads would execute unnecessary work.

We present a heuristic for distributed alpha beta search of the game tree. Our distributed approach significantly improves performance over the single threaded alpha beta algorithm. The speed up factor depends on the number of CPUs in the system. A pool of all available processors is being created at the beginning of tree search. Let us assume the average branching factor is b. A MinDepth parameter value is set so that the number of branches below is close to the number of available processors.

The game tree is already sorted. We analyze nodes starting from the best moves first. We are analyzing Depth X starting from the root. The Depth is decreasing every time

we go down to sub branch.
if MinDepth is not reached, algorithm works as standard alpha-beta pruning. if MinDepth is reached a search task for every branch is created.

All tasks in nodes are executed on a diff...