A Hybrid SSS*/Alpha-Beta Algorithm for Parallel Search of Game Trees
Proceedings of the Ninth International Joint Conference on Artificial Intelligence. Planning and Search. Pages 1044-1045.
Abstract
This paper explores the issues that ar!se when SSS*-llke search algorithms are implemented in parallel. There is an important imp!icit assumpt!on regard!ng the OPEN Iist of sss• (and A*-like algorithms): those states wh!ch are guaranteed never to become part of an optimal solution are forced down !nto the OPEN Ii st and never rise to the top for expansion. Howev e r, when multiple proce ssors are introduced in a parallel version of sss·. these buried states become subject to expansion despite their provable suboptimality. If such states are not !dent!fied and purged , they may exert an enormaus drag on the parallel algorithm because cons!derable processor effort will be wasted. However , the pruning mechanisms of alpha-beta can be adapted by a parallel SSS*; the resulting algorithm HYBRID is su!table for searc hing game trees and general AND / OR trees in parallel.
@inproceedings{ijcai1985p211,
title = {A Hybrid SSS*/Alpha-Beta Algorithm for Parallel Search of Game Trees},
author = {Leifker, Daniel B. and Kanal, Laveen N.},
booktitle = {Proceedings of the Ninth International Joint Conference on
Artificial Intelligence, {IJCAI-85}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Aravind Joshi},
pages = {1044--1045},
year = {1985},
note = {Planning and Search},
url = {https://ijcai.org/proceedings/1985/211},
}
TY - CPAPER TI - A Hybrid SSS*/Alpha-Beta Algorithm for Parallel Search of Game Trees AU - Leifker, Daniel B. AU - Kanal, Laveen N. T2 - Proceedings of the Ninth International Joint Conference on Artificial Intelligence, IJCAI-85 PB - International Joint Conferences on Artificial Intelligence PY - 1985 SP - 1044 EP - 1045 UR - https://ijcai.org/proceedings/1985/211 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
