1
00:00:04,440 --> 00:00:10,666
In general game playing, every game can be
thought of as a state graph, like the one

2
00:00:10,666 --> 00:00:16,743
shown here. The nodes represent states and
the arcs represent actions. For example,

3
00:00:16,743 --> 00:00:22,862
if the player performs action A in state
S1, the world goes into state S2. Action B

4
00:00:22,862 --> 00:00:28,434
leads to state S3, action C leads to state
S4, and action D has no effect on, in

5
00:00:28,434 --> 00:00:33,992
other words the world stays in the same
state. Start state is denoted by an

6
00:00:33,992 --> 00:00:39,713
incoming arrow. Here, s1 is the start
state. Goal states for the player are

7
00:00:39,713 --> 00:00:45,355
denoted by color. Here, s8 and s11 are
goal states for the player. more

8
00:00:45,355 --> 00:00:51,154
generally, in general game playing, we
allow states with varying degrees of

9
00:00:51,154 --> 00:00:57,295
goalhood. Ranging from zero meaning bad to
100 meaning very good. Terminal states are

10
00:00:57,295 --> 00:01:01,741
denoted here by slightly heavier circles.
barely visible. In this case, that's

11
00:01:01,741 --> 00:01:06,186
three, S9 and S11 are terminal states.
Beginning in the start state, the player's

12
00:01:06,186 --> 00:01:10,857
objective is to arrive at a terminal state
that's also a goal state. Or in the case

13
00:01:10,857 --> 00:01:15,584
of multiple levels of goals, to arrive at
a terminal state that has as high a reward

14
00:01:15,584 --> 00:01:22,237
as possible. In the case of multiple
players with simultaneous moves, the arcs

15
00:01:22,237 --> 00:01:28,262
become multi-arcs, with one arc for each
combination of the player's actions. Here,

16
00:01:28,262 --> 00:01:34,212
here's an example of a simultaneous move
game with two players. If in status one

17
00:01:34,212 --> 00:01:40,087
both players perform action a, we follow
the arc labeled aa. If the first player

18
00:01:40,087 --> 00:01:45,889
does a, and the second player does b, we
follow the arc ab. And similarly for ba

19
00:01:45,889 --> 00:01:50,625
and bb. We also had different goals for
the different players notated with

20
00:01:50,625 --> 00:01:55,596
different colors here in brown and purple.
Multi-player games are a little more

21
00:01:55,596 --> 00:02:00,881
difficult than single player games as each
player cannot control the other player's

22
00:02:00,881 --> 00:02:05,726
actions, so it's more search involved.
Okay, that's pretty much it. Most purists

23
00:02:05,726 --> 00:02:11,559
strategy games can be conceptualized, can
be thought of in this framework. Since all

24
00:02:11,559 --> 00:02:17,486
the state graphs that we're considering
are finite. It is possible, at least in

25
00:02:17,486 --> 00:02:23,564
principle, to describe such games in the
form of lists, states, actions and tables.

26
00:02:23,564 --> 00:02:29,034
That express legality, goals, update and
so forth. Unfortunately direct

27
00:02:29,034 --> 00:02:35,265
representations are not practical in most
cases. Even though the numbers of states

28
00:02:35,265 --> 00:02:40,694
and actions are finite, they can be
extremely large. And the tables relating

29
00:02:40,694 --> 00:02:45,876
them can be even larger. for example, in
chess there are thousands of possible

30
00:02:45,876 --> 00:02:51,123
moves, and more than ten to the thirtieth
states. In order to be practical we need

31
00:02:51,317 --> 00:02:57,421
somewhat more compact en, encoding. Okay.
This is the job of the Game Description

32
00:02:57,421 --> 00:03:03,560
Language, or GDL. GDL's a formal language
for encoding finite discrete games. It

33
00:03:03,560 --> 00:03:10,249
supports compact representation of games
by one relying on a conceptualization of

34
00:03:10,249 --> 00:03:16,545
games states as databases. And two, using
logic to define the notions of legality,

35
00:03:16,545 --> 00:03:21,714
update, goals, terminations, so forth. In
the vast majority of games, states and

36
00:03:21,714 --> 00:03:26,190
actions have composite structure that
allows us to define a large number of

37
00:03:26,190 --> 00:03:30,902
states and actions in terms of a smaller
number of more fundamental entities. In

38
00:03:30,902 --> 00:03:35,613
games like tic-tact-toe, states are not
monolithic. They can be conceptualized in

39
00:03:35,613 --> 00:03:40,443
terms of cells and marks. Here for example
are two representations of a state in a

40
00:03:40,443 --> 00:03:44,468
game of tic-tact-toe. On the left we have
the traditional two dimensional

41
00:03:44,468 --> 00:03:48,758
representation. On the right we have a
representation of the state as a database

42
00:03:48,758 --> 00:03:53,209
of facts. the first fact says that the
cell in the first row in the first column

43
00:03:53,209 --> 00:03:58,204
contains an X. Second cell in the first
row in the, the, second column contains a

44
00:03:58,204 --> 00:04:03,754
blank, denoted here by the constant B and
so forth. And finally this last assertion

45
00:04:03,754 --> 00:04:09,813
says that it's O's turn to make a mark. In
other words it has control. Okay. Using

46
00:04:09,813 --> 00:04:15,811
this conceptualization of states, we can
define the game of tic tac toe with a

47
00:04:15,811 --> 00:04:21,942
small database of logical sentences, as
shown here. these are all sentences in her

48
00:04:21,142 --> 00:04:26,941
brown logic syntax written with the pure
ASCII character set. First, we define the

49
00:04:26,941 --> 00:04:33,435
roles of the game. There are two players
named X and O. Next we characterize the

50
00:04:33,435 --> 00:04:40,436
initial state. In this case, all of the
cells are blank and X has control. Next we

51
00:04:40,436 --> 00:04:45,665
characterize the player's legal actions.
GDL makes extensive use of reductions

52
00:04:45,866 --> 00:04:50,694
which are written using the left arrow
operator. A reductoin's simply an

53
00:04:50,694 --> 00:04:55,789
implication in reverse, with the
conclusion first and the conditions

54
00:04:55,789 --> 00:05:01,248
afterward. It's more convenient to write
things this way than to use forward

55
00:05:01,248 --> 00:05:06,980
implications. Also in GDL, symbols that
begin with capital letters are variables,

56
00:05:06,980 --> 00:05:12,494
and those that begin with lower case
letters or digits are constants. For

57
00:05:12,494 --> 00:05:18,299
example, capital P, capital X and capital
Y here, are variables. While lower case b,

58
00:05:18,299 --> 00:05:23,756
lower case x, lower case y and noop are
object constants. Okay, with that

59
00:05:23,756 --> 00:05:30,029
introduction, lets look at this definition
for legality. First sentence says that

60
00:05:30,029 --> 00:05:35,989
it's legal for an arbitrary player P to
mark the cell in row X and column Y

61
00:05:35,989 --> 00:05:42,412
provided that it contains a blank and
provided that P has control. Second

62
00:05:42,412 --> 00:05:48,087
sentence tells us that it's legal for x to
do the no-op action if o has control. The

63
00:05:48,087 --> 00:05:53,627
no-op action means the x does nothing, it
passes. Analogously, it's legal to o to do

64
00:05:53,627 --> 00:05:59,099
the no-op action if x has control. These
three axioms assure us that both players

65
00:05:59,099 --> 00:06:06,185
have legal moves at every non-terminal
state. Okay. Next we look at the update

66
00:06:06,185 --> 00:06:12,214
rules for the game. The cell is marked
with an X or an O if the corresponding

67
00:06:12,214 --> 00:06:18,420
player marks that cell in the previous
step. sentence two says that it

68
00:06:18,420 --> 00:06:24,180
self-contains a mark that is not blank,
then it retains that mark on the

69
00:06:24,180 --> 00:06:30,599
subsequent state. The cell is blank and is
not marked in that step, then it remains

70
00:06:30,599 --> 00:06:36,232
blank. And finally, the last two sentences
tell us that control alternates on each

71
00:06:36,232 --> 00:06:43,908
play. The game terminates if either player
has a line of marks or if there are no

72
00:06:43,908 --> 00:06:51,391
empty cells. The goal is to find the
players' rewards. The X player gets 100

73
00:06:51,391 --> 00:06:56,001
points if there's a line of X's and no
line of O's. Gets 50 points if neither

74
00:06:56,001 --> 00:07:01,030
player has a line. And he gets zero points
if there's a line of O's and no line of X,

75
00:07:01,030 --> 00:07:05,640
no line of O's and no line of Xs. The
rewards for the O player are analogous.

76
00:07:07,660 --> 00:07:12,577
And finally, we define some helper
relations. A line is a roll of marks of

77
00:07:12,577 --> 00:07:18,168
the same type or a column or a diagonal. A
roll of marks means that there are three

78
00:07:18,168 --> 00:07:23,557
marks with the same first coordinate.
Column of marks means that there are three

79
00:07:23,557 --> 00:07:29,148
marks with the same second coordinate and
a diagonal is a line from the upper left

80
00:07:29,148 --> 00:07:34,671
to the lower right or from the upper right
to the lower left. And that's it. That's

81
00:07:34,671 --> 00:07:40,965
the entire description of the Tic-Tac-Toe
rules, okay? One more final twist on game

82
00:07:40,965 --> 00:07:45,882
description, and that's obfuscation. In,
in order to prevent programmers from

83
00:07:45,882 --> 00:07:51,586
building in specialized capabilities that
recognize based on specific words in game

84
00:07:51,586 --> 00:07:56,569
descriptions, it's common for game
managers to obfuscate descriptions before

85
00:07:56,569 --> 00:08:01,552
game begins. All words are consistently
replaced by nonsense words, as in the

86
00:08:01,552 --> 00:08:06,928
example shown here. The only exceptions
are variables and a selection of constants

87
00:08:06,928 --> 00:08:10,600
common to all games such as next, does,
true, and so forth.