Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

   

2009 Research Summary

Adversarial Reasoning with Partial Information

View Current Project Information

Jason A. Wolfe and Stuart J. Russell

Defense Advanced Research Projects Agency

In a wide variety of real-world adversarial situations, we must make decisions with only partial information about the current state of the world. This poses a considerable challenge, since in reasoning about which actions are desirable, we also must consider the relative likelihood of different possible world states (including the information states of all opponent(s)) if we are to reason optimally. Theoretically, algorithms exist to solve such problems exactly, but in practice these algorithms are too slow to be of use for all but the most trivial problems.

Our current research focuses on techniques for reasoning in the game of Kriegspiel, a partially observable variant of chess in which players cannot see their opponents' pieces (a referee provides the players with percepts after each move). This game exhibits many of the difficult features of real-world, partially-observable, adversarial problems, while having a relatively small state space (compared to, for instance, real-time strategy games). Whereas computers can now routinely beat expert human chess players, the best Kriegspiel-playing agents can still be beaten easily by novice human players.

Our research aims towards bridging this gap, by developing practical approximate algorithms for reasoning in partially observable games. Our past research in this area has focused on a particular subproblem: finding guaranteed wins under partial observation. As part of this effort, we designed a new family of algorithms that outperform previous ones by more than an order of magnitude [1].

Figure 1
Figure 1: A Kriegspiel game in progress, from the perspective of the white player. Black's pieces are hidden from white.

Figure 2
Figure 2: An abstract belief-state AND/OR tree representing a partially observable, nondeterministic domain, and the order in which three of our new algorithms (described in [1]) would explore this tree.

[1]
S. Russell and J. Wolfe, "Efficient Belief-State AND-OR Search, with Application to Kriegspiel," Proc. IJCAI, 2005.
[2]
J. Wolfe and S. Russell, "Exploiting Belief State Structure in Graph Search," ICAPS Workshop on Planning in Games, 2007.