Branch & Bound Formulation for Sequential and Parallel Game Tree Searching: Preliminary Results
Proceedings of the Seventh International Joint Conference on Artificial Intelligence. Search. Pages 569-570.
Abstract
In this paper we present a Branch and Bound (B&B} formulation for finding the minimax value of a game tree and show, that in case a subset with the best bound is chosen for branching, the resulting algorithm is identical to the SSS* algorithm which Stockman [1) has shown to be better than the AlphaBeta algorithm for game tree searching. We propose parallel implementations of B&B search for the minimax evaluation of game trees which lead to a parallel implementation of SSS*. The Branch and Bound approach provides a unified way of formulating and analyzing tree searching algorithms such as SSS* and Alpha-Beta. Viewing SSS* this way, its correctness proof is much easier than given in Stockman, as is a correctness proof for parallel implementations of SSS*.
@inproceedings{ijcai1981p106,
title = {Branch & Bound Formulation for Sequential and Parallel Game Tree Searching: Preliminary Results},
author = {Kanal, Laveen N. and Kumar, Vipin},
booktitle = {Proceedings of the Seventh International Joint Conference on
Artificial Intelligence, {IJCAI-81}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Roger C. Schank},
pages = {569--570},
year = {1981},
month = {8},
note = {Search},
url = {https://ijcai.org/proceedings/1981/106},
}
TY - CPAPER TI - Branch & Bound Formulation for Sequential and Parallel Game Tree Searching: Preliminary Results AU - Kanal, Laveen N. AU - Kumar, Vipin T2 - Proceedings of the Seventh International Joint Conference on Artificial Intelligence, IJCAI-81 PB - International Joint Conferences on Artificial Intelligence PY - 1981 SP - 569 EP - 570 UR - https://ijcai.org/proceedings/1981/106 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
