Game Development Reference
In-Depth Information
6.3.3 Symbolic algorithms and antichains
Theorem 6.6 gives a natural algorithm for solving games with imperfect
information with observable objective: apply the algorithms for solving
games with perfect information to the knowledge-based subset construction
presented above. 1 The symbolic algorithms presented in Section 6.2 are based
on the controllable predecessor operator Cpre :2 S
2 S
whose definition can
be rewritten for all q
S as:
Cpre( q )= {s ∈ S |∃σ ∈ Σ ·∀s ∈ S :if( s, σ, s ) Δ K then s ∈ q}
=
:if s = post σ ( s )
then s
{
s
S
|∃
σ
Σ
·∀
o
∈O
o
=
q
}
.
A crucial property of this operator is that it preserves downward-closedness of
sets of cells. Intuitively, Player 1 is in a better situation when her knowledge
is more precise, i.e., when her knowledge is a smaller cell according to set
inclusion. A set q of cells is downward-closed if s
q implies s
q for all
s
s . If Player 1 can force the game G K to be in a cell of a downward-closed
set of cells q in the next round from a cell s , then she is also able to do so
from all cells s
s . Formally, if q is downward-closed, then so is Cpre( q ).
It is easy to show that
also preserve downward-closedness, and
therefore all sets of cells that are computed for solving games of imperfect
information are downward-closed.
As the symbolic algorithms are manipulating downward closed sets, it is
valuable to design a data-structure to represent them compactly. We define
such a data-structure here. The idea is to represent a set of cells by a set
of sets of locations and interpret this set as defining all the cells that are
included in one of its element. Clearly, in such a representation having a set
of sets with two
and
-comparable element is not useful, so we can restrict our
symbolic representations to be antichains , i.e., a set of sets of locations
that are -incomparable.
Antichains for representing downward-closed sets Let us denote by
A
the set of
-antichains of sets of locations, that is
A = {{s 1 ,s 2 ,...,s n }⊆ 2 L
|∀ 1 ≤ i, j ≤ n : s i ⊆ s j → i = j}.
Note that an antichain is a set of subsets of locations that are not necessarily
cells. We denote by
A
the set of antichains. The set
A
is partially ordered
as follows. For q, q ∈A
q iff
s
q : s
s . The least
, let q
s
q
·∃
upper bound of q, q ∈A
q =
q }
is q
{
s
|
s
q or s
, and their greatest
1 Note that the symbolic algorithm can be applied without explicitly constructing the
knowledge-based construction.