Game Development Reference
InDepth 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 knowledgebased 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 downwardclosedness 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
downwardclosed
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 downwardclosed
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 downwardclosed, then so is Cpre(
q
).
It is easy to show that
also preserve downwardclosedness, and
therefore all sets of cells that are computed for solving games of imperfect
information are downwardclosed.
As the symbolic algorithms are manipulating downward closed sets, it is
valuable to design a datastructure to represent them compactly. We define
such a datastructure 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 downwardclosed 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
knowledgebased construction.
Search Nedrilad ::
Custom Search