1
00:00:03,450 --> 00:00:07,776
Having a formal description of a game is
one thing. Being able to use that

2
00:00:07,776 --> 00:00:12,219
description to play the game effectively
is something else entirely. In this

3
00:00:12,219 --> 00:00:17,071
segment we discuss strategies for building
general gameplayers. And we discuss some

4
00:00:17,071 --> 00:00:21,281
of the difficulties that need to be
handled along the way. Since the end

5
00:00:21,281 --> 00:00:26,075
descriptions are written in Logic, it's
obviously necessary for a gameplayer to do

6
00:00:26,075 --> 00:00:30,869
some amount of automated reasoning. There
are two extremes here. One possibility is

7
00:00:30,869 --> 00:00:35,487
for the gameplayer to process the game
description interpretively throughout a

8
00:00:35,487 --> 00:00:39,563
game. Second extreme is for the player to
use the description to devise a

9
00:00:39,563 --> 00:00:43,903
specialized program. And then use that
program to play the game. So effectively

10
00:00:43,903 --> 00:00:48,298
automatic programming. But this is just an
introduction to general game playing.

11
00:00:48,298 --> 00:00:52,693
We'll discuss just the first possibility
and leave it to you to think about the

12
00:00:52,693 --> 00:00:58,020
second possibility and various hybrid
approaches. As we mentioned earlier, in

13
00:00:58,020 --> 00:01:03,994
GDL we can conceptualize a state as a set
of facts that are true in that state. Such

14
00:01:03,994 --> 00:01:11,552
as the facts here about the state of
Tic-Tac-Toe shown on the left. Computing

15
00:01:11,552 --> 00:01:16,333
the legal moves in any such state is
straight forward. We simply use the rules

16
00:01:16,333 --> 00:01:21,359
defining legality together with the facts
about the state, to deduce statements of

17
00:01:21,359 --> 00:01:26,140
that legality. For example, in the state
shown on the right here, we can compute

18
00:01:26,140 --> 00:01:30,983
the conclusions shown at the bottom. The O
player has six legal moves and the X

19
00:01:30,983 --> 00:01:38,881
player has only one, namely the no op
action. Given a state, and actions for

20
00:01:38,881 --> 00:01:44,188
each of the players, we can compute the
facts true in the next state using the

21
00:01:44,188 --> 00:01:49,360
update rules. In the case shown here, we
use the update rule at the bottom to

22
00:01:49,360 --> 00:01:54,531
compute the facts show in red on the
right. The other facts on the right are

23
00:01:54,531 --> 00:01:59,635
computed using the other update rules.
These sentences mention next, they're,

24
00:01:59,635 --> 00:02:05,079
they can then be rewritten with true in
place of next to form a description for

25
00:02:05,079 --> 00:02:13,434
the resulting state. One way for a player
to decide on a course of action is to use

26
00:02:13,434 --> 00:02:18,373
these two computations to expand the game
tree. Starting in a known state, it

27
00:02:18,373 --> 00:02:23,767
computes the legal actions for itself and
its opponents, as we previously discussed.

28
00:02:23,767 --> 00:02:29,096
For each combination of actions of the
players, it simulates, the combination to

29
00:02:29,096 --> 00:02:33,515
compute the next state, and thereby
expands the tree. Here we see the

30
00:02:33,515 --> 00:02:39,569
Tic-Tac-Toe tree expanded from this
initial state down one level. Repeating

31
00:02:39,569 --> 00:02:47,711
this, we can expand the tree to two
levels, three levels, and so forth. Until,

32
00:02:47,711 --> 00:02:52,138
finally, we encounter terminal states on
every branch. Such as the one shown here

33
00:02:52,138 --> 00:02:56,343
in the middle of the bottom row. By
examining various branches, we can choose

34
00:02:56,343 --> 00:03:00,881
the one that produces the best payoff.
now, of course, this choice depends on the

35
00:03:00,881 --> 00:03:05,362
moves over the other players. And we must
consider all possible opponent moves, or

36
00:03:05,362 --> 00:03:09,844
make some assumptions about things that
the other players will or will not do. In

37
00:03:09,844 --> 00:03:14,105
principle, this procedure allows us to
identify the best possible strategy to

38
00:03:14,105 --> 00:03:19,551
play the game. Unfortunately, even in
cases where there is a clear cut solution,

39
00:03:19,551 --> 00:03:24,513
a tree may be so large as to make it
practically impossible for any player to

40
00:03:24,513 --> 00:03:29,602
expand the game tree. Tic-Tac-Toe there's
just 5,000 states. It's a manageable

41
00:03:29,602 --> 00:03:34,628
number, but there are more than ten to the
thirtieth states in chess. Using this

42
00:03:34,628 --> 00:03:39,899
approach the player would run out of time
and memory long before finishing. The

43
00:03:39,899 --> 00:03:44,809
alternative is to do incremental search,
when each move expanding the tree as much

44
00:03:44,809 --> 00:03:48,880
as possible, and then making a choice
based on the apparent value of

45
00:03:48,880 --> 00:03:53,490
non-terminal states. In traditional
game-playing where the rules are known in

46
00:03:53,490 --> 00:03:58,100
advance the programmer can invent
game-specific evaluation functions to help

47
00:03:58,100 --> 00:04:02,890
in this regard. For example in chess, we
know that states with higher piece count

48
00:04:02,890 --> 00:04:07,800
and greater board control are better than
ones with less material or less control.

49
00:04:07,800 --> 00:04:13,470
Unfortunately, this is not possible for
Jake, for GG and GGP program cannot invent

50
00:04:13,470 --> 00:04:19,280
such game specific rules in advance as the
games rules aren't even known until the

51
00:04:19,280 --> 00:04:25,458
game begins. The program must evaluate
states for itself. One possibility is to

52
00:04:25,458 --> 00:04:30,406
use general heuristics. A number of such
heuristics have been proposed over the

53
00:04:30,406 --> 00:04:35,543
years. gold proximity is one. Proponents
of this heuristic argued that, all other

54
00:04:35,543 --> 00:04:40,366
things being equal, it's a good idea to
prefer states that are closer to goal

55
00:04:40,366 --> 00:04:45,377
states than states that are farther away.
The distance here is usually judged by

56
00:04:45,377 --> 00:04:50,138
similarity between the states. You know,
the number of facts in common in the

57
00:04:50,138 --> 00:04:56,003
descriptions of the two states. Mobility
is another general heuristic. Proponents

58
00:04:56,003 --> 00:05:00,443
argue that, all other things being equal,
it's better to move to a state that

59
00:05:00,443 --> 00:05:05,235
affords the player greater mobility. And
that is more possible actions. It's better

60
00:05:05,235 --> 00:05:09,442
than being boxed into a corner. And
symmetrically, proponents of mobility

61
00:05:09,442 --> 00:05:15,552
argue that it's good to minimize the
mobility of one's opponents. Monte Carlo,

62
00:05:15,552 --> 00:05:20,507
originally known as Depths Charge, is a
particularly powerful heuristic for

63
00:05:20,507 --> 00:05:25,792
evaluations, evaluating states. Suppose a
player is comparing two states, with too

64
00:05:25,792 --> 00:05:31,342
little time to search the entire game tree
descending from those states. The idea of

65
00:05:31,342 --> 00:05:36,495
Depths Charge is to play through a few
complete games from each of the states

66
00:05:36,495 --> 00:05:41,866
being compared, making random choices
until a terminal state is attained. After

67
00:05:41,866 --> 00:05:47,418
doing this a few times we compare the
numbers of wins and losses and select the

68
00:05:47,418 --> 00:05:54,027
state that leads to the largest number of
wins. All of these heuristics have been

69
00:05:54,027 --> 00:05:59,052
shown to be effective in some games. Of
these, Monte Carlo is by far the most

70
00:05:59,052 --> 00:06:04,453
successful. Unfortunately they're just
heuristics. They frequently fail,

71
00:06:04,453 --> 00:06:10,512
sometimes with comical consequences. Final
match of GDP 06 is an example. The game

72
00:06:10,512 --> 00:06:16,861
was cylinder checkers, that is checkers
played on a cylinder. The board here is,

73
00:06:16,861 --> 00:06:21,505
well you can't see it, wraps around
vertically. Recall that in checkers a

74
00:06:21,505 --> 00:06:26,731
player is permitted to move one of his
ordinary pieces, those pieces that are not

75
00:06:26,731 --> 00:06:31,892
kings, one square forward on each turn.
Here red is moving from top to bottom and

76
00:06:31,892 --> 00:06:37,117
black is moving from bottom to top. If a
piece is blocked by an opponent's player,

77
00:06:37,117 --> 00:06:42,020
he can jump that player, that piece, if
there is an empty square on the other

78
00:06:42,020 --> 00:06:47,712
side. Mor eover the player must make a
jump is one is available. Objective of the

79
00:06:47,712 --> 00:06:51,943
game is to take all or as many of the
opponent's pieces as possible while

80
00:06:51,943 --> 00:06:56,633
preserving one's own pieces. Here we see
this snapshot of the game. It's red's turn

81
00:06:56,633 --> 00:07:07,218
to play. What should he do? And what do
you think he did? Here's the hint. Player

82
00:07:07,218 --> 00:07:12,164
in this case was clone player. And, it
decided for some reason or the other that

83
00:07:12,164 --> 00:07:16,508
limiting the opponent's mobility was a
good heuristic. If we were to move the

84
00:07:16,508 --> 00:07:21,303
most rear most piece, the rear most piece,
black would have multiple possible moves.

85
00:07:21,303 --> 00:07:25,760
However, if it were to move the piece in
front, black would be forced to capture

86
00:07:25,760 --> 00:07:30,048
it's piece. In other words, it would have
at most one move. Clearly moving the

87
00:07:30,048 --> 00:07:34,777
forward piece minimizes the opponents
mobility. So, that's what clone player

88
00:07:34,777 --> 00:07:39,666
did. Actually the whole match played out
this way, with red giving black captures

89
00:07:39,666 --> 00:07:44,554
at every single opportunity. It was sad to
watch, but also I have to say a little

90
00:07:44,554 --> 00:07:49,565
comical. The moral is, that non-guaranteed
heuristics are sometimes useful, but they

91
00:07:49,565 --> 00:07:54,168
are not always useful. That said, there
are some evaluation techniques that always

92
00:07:54,168 --> 00:07:58,310
work. For example, there's no harm
preferring new states to states that have

93
00:07:58,310 --> 00:08:02,673
previously been seen, provided there's a
way to get back to the original states.

94
00:08:02,673 --> 00:08:07,147
Also, if a player is able to determine
some observable condition that corresponds

95
00:08:07,147 --> 00:08:11,234
to actual distance from the goal, then
it's good to minimize that quantity.

96
00:08:11,234 --> 00:08:15,431
Suppose the player, for example, were in a
cave, trying to get out. If it saw a

97
00:08:15,431 --> 00:08:19,518
brighter light in one tunnel than in
another, it might go for the brighter

98
00:08:19,518 --> 00:08:23,820
light. And finally, there are some states
that can be determined to be bad and

99
00:08:23,820 --> 00:08:28,013
avoided. Even if other states are not
known to be good. For example, stepping

100
00:08:28,013 --> 00:08:32,207
off the roof of a tall building is
probably not the best way to get to the

101
00:08:32,207 --> 00:08:38,510
store. You know, at least not in the real
world. this discussion of game tree search

102
00:08:38,510 --> 00:08:44,712
in heuristics reveals just how difficult
the general game playing problem is. Monte

103
00:08:44,712 --> 00:08:50,690
Carlo works fairly well, but it breaks
down badly in certain cases just like the

104
00:08:50,690 --> 00:08:56,220
others. Fortunately, there's another
complementary approach to general game

105
00:08:56,220 --> 00:09:02,109
playing that has a lot of power. And that
is Metagaming. Metagaming is the process,

106
00:09:02,290 --> 00:09:07,241
of analyzing and/or modifying the game, in
general. That is, out of the context of a

107
00:09:07,241 --> 00:09:12,251
specific match. Metagaming is usually done
during the start collect period of a

108
00:09:12,251 --> 00:09:16,960
match. Or sometimes during, in a separate
thread, while the game is being played.

109
00:09:17,840 --> 00:09:22,748
typical Metagaming techniques include
presearching the game tree, optimizing the

110
00:09:22,748 --> 00:09:27,595
game description and various ways of
compiling the game description to achieve

111
00:09:27,595 --> 00:09:32,381
higher performance. Some cases it's
possible we formulate the game into one or

112
00:09:32,381 --> 00:09:37,351
more simple, simpler games and were to
discover that there are some game specific

113
00:09:37,351 --> 00:09:43,544
evaluation functions. As an example of,
reformulation potential, consider this

114
00:09:43,544 --> 00:09:49,165
game called Hodgepodge. Hodgepodge is
actually two games glued together. Here we

115
00:09:49,165 --> 00:09:54,785
show Chess and Othello. But it could be
any two games. One move in a joint game of

116
00:09:54,785 --> 00:10:00,519
Hodgepodge corresponds to one move in each
of the two constituent's games. Winning

117
00:10:00,519 --> 00:10:05,815
requires winning at least one of the two
games while not loosing the other. What

118
00:10:05,815 --> 00:10:11,309
makes Hodgepodge interesting is that it's
factorial. That is, that it can be divided

119
00:10:11,309 --> 00:10:17,068
into independents. Realizing that this can
have a dramatic benefit, see this consider

120
00:10:17,068 --> 00:10:22,563
the size of the game tree for Hodgepodge.
Suppose that one game tree has, for one of

121
00:10:22,563 --> 00:10:28,057
the subgames has a branch tree factor A
and the game tree factor for the other has

122
00:10:28,057 --> 00:10:33,715
a branch tree factor B. And then the
branching factor of the joint game is A

123
00:10:33,715 --> 00:10:40,114
times B. And the size of the fringe of the
game tree at level N is A times B to the

124
00:10:40,114 --> 00:10:45,249
N. However the two games are independent.
Moving in one game does not affect the

125
00:10:45,249 --> 00:10:49,778
state of the other game. So the player
really should be searching two smaller

126
00:10:49,778 --> 00:10:54,542
game trees, one with a branching factor A
and the other with a branching factor B.

127
00:10:54,542 --> 00:10:59,836
In this way, adepts ten there would only
be A to the N plus B to the N states. It's

128
00:10:59,836 --> 00:11:05,758
a huge decrease in the size of the search
space. Factor ing's just one example of

129
00:11:05,758 --> 00:11:10,255
game reformulation. There are many others.
For example, it may be possible to find

130
00:11:10,255 --> 00:11:14,470
symmetries in games that cut down on
search, the search base. Some games are

131
00:11:14,470 --> 00:11:18,685
bottlenecks that allow for type of
factoring. Consider for example, a game

132
00:11:18,685 --> 00:11:23,126
made up of one or more sub games strung
together. Which is necessary to win one

133
00:11:23,126 --> 00:11:27,791
game before moving on to the second game,
and the second before moving to the third

134
00:11:27,791 --> 00:11:32,287
and so forth. In such cases, there's no
need to search to a terminal state in the

135
00:11:32,287 --> 00:11:36,784
overall game. It's suffiicient to limit
search to the termination in the current

136
00:11:36,784 --> 00:11:42,269
sub game These are examples of extreme
cases. But there are many simpler everyday

137
00:11:42,269 --> 00:11:47,802
examples of finding structure of this sort
that can be, help out in curtailing a

138
00:11:47,802 --> 00:11:53,074
search. The trick in metagaming is to
analyze or reformulate games without

139
00:11:53,074 --> 00:11:57,582
expanding entire game trees. The
interesting thing about general game

140
00:11:57,582 --> 00:12:03,004
playing is this, that sometimes the cost
of analysis is proportional to the size of

141
00:12:03,004 --> 00:12:09,098
the description rather than the size of
the game tree, as the examples we were

142
00:12:09,098 --> 00:12:15,285
just examining. Such players, cases,
players can expend a little time and gain

143
00:12:15,285 --> 00:12:21,466
a lot in search savings. That's pretty
much it for our quick tour of general game

144
00:12:21,466 --> 00:12:25,660
playing strategies. I, I want to close
this segment with an anecdote about my own

145
00:12:25,660 --> 00:12:30,016
early experience in general game playing.
after building my first general game

146
00:12:30,016 --> 00:12:34,317
player, I decided to see how well it
performed on a game of Tic-Tac-Toe. I let

147
00:12:34,317 --> 00:12:38,404
it play blue while I played red. And
here's the state of the match after six

148
00:12:38,404 --> 00:12:42,598
moves. I was intentionally playing badly
to see what my player would do. The

149
00:12:42,598 --> 00:12:47,231
question is, what did my player do at this
point? Now, if you or I were playing blue,

150
00:12:47,231 --> 00:12:51,938
we would probably play in the lower left,
maybe in the lower right, winning the

151
00:12:51,938 --> 00:12:56,827
game. But, that's not what the player did,
instead it played in the upper right, the

152
00:12:56,827 --> 00:13:01,353
next legal move in lexicographic order.
So, I scratched my head and wondered

153
00:13:01,353 --> 00:13:06,361
exactly why I did this? I wondered if I
was too stupid to see the obvious win. in

154
00:13:06,361 --> 00:13:11,118
the end, that's not wha t it, not at all
the case. It was playing perfectly. It had

155
00:13:11,118 --> 00:13:15,995
already realized that it had a guaranteed
win, no matter what I did at this point,

156
00:13:15,995 --> 00:13:20,873
so why not play in the upper right. It's
aggravating for me as a human to have my

157
00:13:20,873 --> 00:13:27,184
defeat dragged out in this way. but this
sort of delay gratification is not unusual

158
00:13:27,184 --> 00:13:32,760
in general game playing. It's just
frustrating for us humans to watch.