Abstract
This chapter presents the results of a study for improving the performance of the quiescence phase of Alpha-Beta (α-β) search. The Minimax algorithm's α-β enhancement enhances depth-first search performance by optimizing solutions in near best-first order, thereby reducing the computational effort from O(bd) to O(√bd) where b is the branching factor of the game-tree and d is the depth of the search. This research uses a full breath search to delay the asymptotic behavior of the combinatorial explosion to five levels of depth. A narrow width search involves expanding solutions involving material exchange, pawn promotion, or king-in-check until the position reaches quiescence without any material exchanges or promotions. When quiescence is reached, the evaluation function scores the leaf nodes of the game-tree. This chapter's research shows that α-β pruning is enhanced when a solution without material exchange or promotion is attempted first during the quiescence phase of α-β search which applies to chess playing programs as well.
TopThe Prisoner's Dilemma
The Prisoner's Dilemma is a well-known illustration of Nash Equilibrium in game theory in which two people are arrested for the commission of a crime and each one is given a choice by the prosecutor: confess to the crime that they both committed in exchange for more moderate sentence for both or betray the other by keeping quiet. The incentives are such that if either betrays the other, they will both face a severe punishment. If one betrays the other while the other keeps silent, the betrayer is let off while the silent person is given a harsh punishment. If neither speaks, they will each receive a moderate punishment.
The problem occurs because each prisoner must choose between putting their faith in the other to keep quiet (cooperate) or give up on the other (defect). Regardless of what the other does, from an individual perspective, betrayal is a powerful tactic. One prisoner will betray the other if they both assume the other will keep quiet (cooperate). Betrayal also lessens the penalty if one anticipates the other will do so. Because of this, it happens frequently that both convicts wind up betraying one another, which results in a less favorable outcome for both, than if they had both remained silent.
Key Terms in this Chapter
Alpha-Beta Search: Alpha-Beta (a-ß) search is an extension of minimax complemented by a heuristic technique used in game tree search that prunes branches at minimizing or maximizing nodes whose values fall outside of the a-ß window, streamlining the search process to quickly identify the best option.
Alpha-Beta (a-ß) Pruning: An extension to the minimax search algorithm employed in game trees to cut down on the number of nodes considered and increase efficiency by removing branches that do not have an impact on the outcome.
Data Leakage: This term refers to the risk of giving full data autonomy to AI systems for data management and the risk of data loss by third-party data management agencies and cloud data repositories.
One Move Generator: An algorithm that generates only the first legal move and plays it to see if that move will cause the branch of the game tree to be pruned before calling the full-move generator to generate the full list of legal moves if pruning does not occur.
NLP: This is an acronym for Natural Language Processing.
Look-Ahead: This refers to the ability of minimax to search the consequences of proposed actions and counter actions into the future by simulating those proposed actions and counter actions and weighing the outcome to find and suggest the best course of action that results in the minimum loss and the maximum gain of a proposed action.
Nash Equilibrium (NE): In game theory John Nash contributed to the field of non-cooperative games in which players cannot communicate and must make their decision only on what they anticipate other players will do.
Combinatorial Explosion: Also ‘Combinatorial effect,’ refers to the increase in the number of possibilities as the depth of search (denoted as d) increases. In a combinatorial problem there are multiple options at each level of the game tree and the number of possible combinations grows exponentially with the increasing depth of the game tree which is given by the expression b d .
Quiescence Search: Also known as singular-extension will extend the full-width, fixed-depth search beyond its maximum search depth by one additional level of depth if the move on the search horizon is a capture, pawn promotion or king-in-check move. These narrow singular extensions will repeat until there are no more such moves to consider. At which point, the search is known to have reached quiescence.
Ply: This is one level of depth of the game tree. If a game tree has 6 levels of depth it is known as a 6-ply game tree.
Negamax: An a-ß variant of the Minimax algorithm that makes it easier to implement as a recursive algorithm. It evaluates both players' moves from the perspective of one player, always maximizing for the player whose turn it is to move.
Game Tree: A graphical representation in game theory and artificial intelligence that shows every possible action and counteraction in a decision-making process that progresses sequentially as the game tree grows, allowing for algorithmic optimization and strategic analysis to occur.
The Horizon Effect: This refers to the limitation where the evaluation of a game position is influenced by moves or positions within a certain depth limit and fails to predict future actions that might lead to a better or worse outcome beyond that terminal depth.
Minimax Search: A game theory decision rule that reduces the potential for loss and increases the potential for gain in two-player games of strategy. Minimax is commonly implemented in artificial intelligence for game-playing strategies in zero-sum games where a gain for one player is an equal loss for the other player, the sum of which is zero.
Alpha-Beta Window: In game playing algorithms employing minimax search with alpha-beta pruning, the alpha-beta window refers to the set of values (alpha and beta) that are used to prune game tree branches at nodes that are less than alpha or greater than beta to optimize the search, when the real score is outside of this range.
Provisional Backed up Value (PBV): A temporary evaluation of the game state assigned during the search process in a game playing algorithm with an assumption that the optimum value for the state is within the given range.
Game Theory: Forms a theoretical framework for social situations among competing players as generally applied strategically to situations involving economic behavior, and all two-player games of strategy.
HAL (Heuristic Associative Linear-Algorithm): A chess playing program designed and developed by Dr. Stephen F. Wheeler. It is named after the fictional HAL 9000 computer from the Space Odyssey series by Arthur C. Clarke.