Searching minimax game trees under memory space constraint |
| |
Authors: | Toshihide Ibaraki Yoshiroh Katoh |
| |
Affiliation: | (1) Department of Applied Mathematics and Physics, Faculty of Engineering, Kyoto University, 606 Kyoto, Japan;(2) Toho Gas Information Systems Inc., Japan |
| |
Abstract: | Games such as CHESS, GO and OTHELLO can be represented by minimax game trees. Among various search procedures to solve such game trees, - and SSS* are perhaps most well known. Although it is proved that SSS* explores only a subset of the nodes explored by - , - is commonly believed to be faster in real applications, since it requires very little memory space and hence its storage management cost is low. Contrary to this folklore, however, this paper reports, using the OTHELLO game as an example, that SSS* is much faster than - . It is also demonstrated that SSS* can be modified to make the required memory space controllable to some extent, while retaining the high efficiency of the original SSS*.This research was partially supported by the Ministry of Education, Science and Culture of Japan, under a Scientific Grant-in-Aid. |
| |
Keywords: | Minimax game trees - gif" alt="agr" align="BASELINE" BORDER="0">- " target="_blank">gif" alt="beta" align="MIDDLE" BORDER="0"> SSS* memory space constraint OTHELLO game |
本文献已被 SpringerLink 等数据库收录! |
|