Information Technology Reference
In-Depth Information
original 40 strategies will turn out to be unstable within this set. The supports of can-
didate equilibria tend to concentrate on a fraction of the strategies, suggesting we may
limit consideration to this group. Thus, we employ the preceding analysis primarily
to identify promising strategies, and then refine this set through further evaluation in
preliminary rounds of the actual TAC tournament.
For the first stage—identifying promising strategies—the 1-player game is of little
use. Even discounting strategy S34 (the best strategy in the 1-player game, specially
crafted to do well with copies of itself) our experience suggests that strategic interaction
is too fundamental to TAC for performance in the 1-player game to correlate more
than loosely with performance in the unreduced game. The 4-player game accounts for
strategic interaction at a fine granularity, being sensitive to deviations by as few as two
of the eight agents. The 2-player game could well lead us astray in this respect. For
example, that strategy S34 appears in mixed-strategy equilibria in the 2-player game is
likely an artifact of the coarse granularity of that approximation to TAC.
Cooperative strategies like S34 might well survive when deviations comprise half
the players in the game, but in the unreduced game we would expect them to be far
less stable. Nonetheless, the correlation between the 2- and 4-player game is high. Fur-
thermore, we have a much more complete description of the 2-player game, with more
statistically meaningful estimates of payoffs. Finally, empirical payoff matrices for the
2-player game are far more amenable to our solution techniques, in particular, exhaus-
tive enumeration of symmetric (mixed) equilibria by
GAMBIT
[17]. For all of these
reasons, we focus on the 2-player game for choosing our final
Walverine
strategies,
augmenting our selections with strategies that appear promising in TAC
↓
4
.
Informally, our criteria for picking strong strategies include presence in many equi-
libria and how strongly the strategy is supported. We start with an exhaustive list of all
symmetric equilibria in all cliques of TAC
↓
2
, filtered to exclude any profiles that are
refuted in the full game (considering all strategies, not just those in the cliques). There
are 68 of these. We next operationalize our criteria for promising strategies with three
metrics that we can use to rank strategies given an exhaustive list of equilibria in all
cliques of the 2-player game:
-
number of equilibria in which the strategy is supported
-
maximum mixture probability with which the strategy appears
-
sum of mixture probabilities across all equilibria
Based primarily on these metrics, we chose
{
4
,
16
,
17
,
35
}
as the most promising
candidates, and added
↓
4
. Figure 3 re-
veals strategies 37 and 40 to be the top two candidates after the seeding rounds. In
the semifinals we played 37 and 40 and found that 37 outperformed 40, 4182 to 3945
(
p
=
.
05). Based on this, we played 37 as the
Walverine
strategy for the finals in
TAC-05.
{
3
,
37
,
39
,
40
}
based on their promise in TAC
7
TAC 2005 Outcome
Officially,
Walverine
placed third, based on the 80 games of the 2005 finals. In part this
reflected some poor luck, as a network glitch early that morning at Michigan caused our
