---
title: "Branch & Bound Formulation for Sequential and Parallel Game Tree Searching: Preliminary Results"
authors:
  - "Laveen N. Kanal"
  - "Vipin Kumar"
doi: ""
url: "https://ijcai.org/proceedings/1981/106"
pdf: "https://ijcai.org/proceedings/1981/0106.pdf"
venue: "Proceedings of the Seventh International Joint Conference on Artificial Intelligence"
year: 1981
pages: "569-570"
track: "Search"
keywords:
---

# Branch & Bound Formulation for Sequential and Parallel Game Tree Searching: Preliminary Results

Laveen N. Kanal, Vipin Kumar

*Proceedings of the Seventh International Joint Conference on Artificial Intelligence*, 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*.