1
00:00:07,020 --> 00:00:12,118
Time for another field trip. Not a
physical trip, but a virtual one. Rather

2
00:00:12,118 --> 00:00:17,846
than discussing new ideas and logic, we'll
be instead looking at an application of

3
00:00:17,846 --> 00:00:23,084
the ideas we've already seen. The
destination for our trip this time is the

4
00:00:23,084 --> 00:00:28,462
sub-field of artificial intelligence
called general game playing. As we shall,

5
00:00:28,462 --> 00:00:33,072
shall see, GGP is an interesting
application in its own right. It's

6
00:00:33,072 --> 00:00:38,520
intellectually engaging, and I think more
than a little fun. But it's more than

7
00:00:38,520 --> 00:00:43,275
that, It serves as an analogue for
applications of logic in other areas such

8
00:00:43,275 --> 00:00:47,867
as business and law and science and
engineering. And more fundamentally, it

9
00:00:47,867 --> 00:00:52,356
raises questions about the nature of
intelligence. And serves as a laboratory

10
00:00:52,356 --> 00:00:56,668
in which to evaluate competing approaches
to artifical intelligence. We'll return to

11
00:00:56,668 --> 00:01:00,980
these points a little later in the lesson.
For now let's just begin at the beginning.

12
00:01:01,820 --> 00:01:06,648
Playing strategy games like chess and
checkers, couples intellectual activity

13
00:01:06,648 --> 00:01:11,601
with competition. By playing games we can
exercise and improve our intellectual

14
00:01:11,601 --> 00:01:15,739
skills. The competition, that's
excitement, allows us to compare our

15
00:01:15,739 --> 00:01:20,292
skills to those of others. The same
motivation accounts for interest in

16
00:01:20,292 --> 00:01:25,359
computer game playing as a test bit for
artificial intelligence. Programs that

17
00:01:25,359 --> 00:01:30,685
think better should be able to win more
games. And so we can use competition as an

18
00:01:30,685 --> 00:01:35,687
evaluation technique for intelligent
systems. Unfortunately, building programs

19
00:01:35,687 --> 00:01:40,892
to play specific games has limited value
in AI. To begin with, specialized game

20
00:01:40,892 --> 00:01:45,723
players are very narrow. They can be good
at one thing but not another. Deep Blue,

21
00:01:45,723 --> 00:01:50,735
for example, may have beaten the world
chess champion, but has no clue at all how

22
00:01:50,735 --> 00:01:55,464
to play checkers and it cannot even check,
balance a checkbook. The second problem

23
00:01:55,464 --> 00:02:00,781
with specialized game playing systems is
that they do only part of the work. Most

24
00:02:00,781 --> 00:02:06,229
of the interesting analysis and design is
done in advance by their programmers. The

25
00:02:06,229 --> 00:02:11,626
systems themselves might just as well be
tele-operated. Well, all is not lost. Many

26
00:02:11,626 --> 00:02:17,124
believe that the idea of game playing can
be used to good effect, to inspire and

27
00:02:17,124 --> 00:02:22,210
evaluate good work in artificial
intelligence, but it requires moving more

28
00:02:22,210 --> 00:02:27,708
of the men-, mental work to the computer
itself. And, this can be done by focusing

29
00:02:27,708 --> 00:02:34,521
our attention on general game playing.
Gen-, general game players are systems

30
00:02:34,521 --> 00:02:40,405
able to play arbitrary strategy games
based solely on formal descriptions

31
00:02:40,405 --> 00:02:46,766
supplied at run time. In a typical general
game playing session, the players know

32
00:02:46,766 --> 00:02:52,070
nothing about the game in advance. Once
the game begins, they receive a game

33
00:02:52,070 --> 00:02:56,953
description and based solely on that
description they must figure out how to

34
00:02:56,953 --> 00:03:01,392
play the game legally and effectively.
Furthermore, they must deal with

35
00:03:01,392 --> 00:03:06,846
uncertainty about the actions of the other
players and resource bounds in the form of

36
00:03:06,846 --> 00:03:12,401
a game clock that limits their computation
time. Unlike specialized game players such

37
00:03:12,401 --> 00:03:18,102
as Deep Blue, general game players cannot
rely on algorithms designed in advance for

38
00:03:18,102 --> 00:03:23,328
specific games. General game playing
expertise must depend on intelligence on

39
00:03:23,328 --> 00:03:29,029
the part of the game player, and not just
intelligence of the programmer of the game

40
00:03:29,029 --> 00:03:34,391
player. In order to perform well, general
game players must incorporate multiple

41
00:03:34,391 --> 00:03:39,820
artificial intelligence technologies such
as knowledge representation, reasoning,

42
00:03:39,820 --> 00:03:46,756
learning and rational decision making.
Also, unlike generalized, specialized game

43
00:03:46,756 --> 00:03:52,532
players. General game players must be able
to play different kinds of games. They

44
00:03:52,532 --> 00:03:58,453
should be able to play simple games, like
Tic Tac Toe, and complex games like Chess.

45
00:03:58,453 --> 00:04:03,868
Games with simultaneous moves like
Diplomacy, and games of alternating play,

46
00:04:03,868 --> 00:04:09,866
like Risk. Games with complete information
or games with incomplete information for

47
00:04:09,866 --> 00:04:15,576
example Battleship. Games with different
numbers of players, Black swirl, Rubik's

48
00:04:15,576 --> 00:04:21,281
cube, Chess, Chinese Checkers. Games with
or without communication among the

49
00:04:21,281 --> 00:04:28,304
players, for example Bughouse chess. Zero
sum games and cooperative games. The

50
00:04:28,304 --> 00:04:33,263
various aspects to general game playing
and we need to address them all in order

51
00:04:33,263 --> 00:04:37,915
to understand the field. In this lesson,
we'll start by, discussing game

52
00:04:37,915 --> 00:04:43,985
description. Here as we shal l see logic
plays a key role as a language for writing

53
00:04:43,985 --> 00:04:48,857
game rules. Next, we'll discuss, game
management with the focus on use of

54
00:04:48,857 --> 00:04:54,212
technology to coordinate the play among
automated game players and possibly

55
00:04:54,212 --> 00:04:59,567
humans. We then sketch the main techniques
used in today's general game playing

56
00:04:59,567 --> 00:05:04,651
programs and we'll, we'll look at some of
the problems that have yet to be solved.

57
00:05:04,651 --> 00:05:09,600
Finally, we will close with some
philosophical remarks about general game

58
00:05:09,600 --> 00:05:15,906
playing and an overview of international
general game playing competition. before

59
00:05:15,906 --> 00:05:20,546
closing however, there are a couple of
introductory words worth mentioning.

60
00:05:20,546 --> 00:05:25,749
General game playing resembles a couple of
other disciplines. There are significant

61
00:05:25,749 --> 00:05:30,952
overlaps but there are also some important
differences. And it's worthwhile to keep

62
00:05:30,952 --> 00:05:36,156
these relationships in mind as we look at
the details of general game playing. Like

63
00:05:36,156 --> 00:05:41,219
general game theory traditional game
theory is concerned with games in general.

64
00:05:41,219 --> 00:05:45,828
However, game theory is primarily
concerned with the analysis of game trees.

65
00:05:45,828 --> 00:05:50,867
There's no concern for how these trees are
communicated to the players, or for how

66
00:05:50,867 --> 00:05:55,537
the descriptions are used. There's also
little concern for tradeoffs between

67
00:05:55,537 --> 00:06:00,515
deliberation and action. In general game
playing, the game tree is communicated at

68
00:06:00,515 --> 00:06:05,370
run time. Hence, there is an emphasis on
description, and use of this description.

69
00:06:05,370 --> 00:06:09,542
And by bringing game description into the
picture, there's a possibility of more

70
00:06:09,542 --> 00:06:14,699
refined notions of rationality. General
game playing also resembles the field of

71
00:06:14,699 --> 00:06:19,223
action planning. In fact, they're very
closely related. The inputs are the same,

72
00:06:19,223 --> 00:06:23,513
the state machine with initial states and
goal states. However, the purpose is

73
00:06:23,513 --> 00:06:27,743
slightly different. In the case of
planning, the objective is to create a

74
00:06:27,743 --> 00:06:32,327
plan that transforms the initial state
into a goal state. There's no execution

75
00:06:32,327 --> 00:06:36,792
environment and hence no concern for
deliberation, inaction, and interleaving

76
00:06:36,792 --> 00:06:41,317
of those activities. In general game
playing, the objective is to actually get

77
00:06:41,317 --> 00:06:45,993
the world into the goal state, to actually
execute the actions. The main differe nce

78
00:06:45,999 --> 00:06:50,489
is the presence in GGP of an execution
environment that allows the general game

79
00:06:50,489 --> 00:06:54,699
player to execute its plan. As a result,
players can interleave planning and

80
00:06:54,699 --> 00:06:59,415
execution. By so doing they can sometimes
solve problems that would be unsolvable by

81
00:06:59,415 --> 00:07:01,380
pre-planning alone, as we shall see.