Strategic planning for imperfect-information games

摘要: Although game-tree search works well in perfectinformation games, there are problems trying to use it for imperfect-information games such as bridge. The lack of knowledge about the opponents’ possible moves gives game tree a very large branching factor, making ~ree so immense that searching is infeasible. In this paper, we describe our approach overcoming problem. We develop model and how represent information using modified version task network extended multi-agency uncertainty. present game-playing procedure uses generate trees which set alternative choices determined not by actions, but available tactical strategic schemes. tests on bridge, found generated having much smaller factor than would have been conventional techniques. Thus, even ill worst case, contained only 1300 nodes, opposed approximately 6.01 x 1044 nodes produced brute-force tile case. Furthermore, successfully solved typical bridge matched situations its base. These preliminary suggest has potential yield bridge-playing programs better existing ones--and thus begun build full implementation. This work supported part an ATT Levy Newborn, 1982), checkers (Samuel, 1967), othello (Lee Mahajan, 1990)), does ways other games. One example Bridge game, no player complete state world, their effects. As consequence, tree--and size itself--is large. Searching completely infeasible, because deal must be played just few minutes (in contrast chess can go several hours). different needed. problem, based observation planning. literature describes number schemes dealing with various card-playing situations. It appears small each hand, them expressed relatively simply. To play many humans these create plans. They then follow those plans some tricks, replanning when appropriate. taken advantage planning nature adapting extending ideas from task-network instances multi-agent methods--structures similar decompositions used hierarchical singleagent systems Nonlin (Tate, 1976; Tate, 1977), NOAH (Sacerdoti, MOLGEN (Stefik, 1981), trees, decomposition. produces branches actions agent perform, instead employ. If at node tree, applicable From: AAAI Technical Report FS-93-02. Compilation copyright © 1993, (www.aaai.org). All rights reserved.