1
00:00:00,000 --> 00:00:01,924
>> [Speel van musiek]

2
00:00:01,924 --> 00:00:10,600

3
00:00:10,600 --> 00:00:13,280
>> Spreker: Welkom terug, almal.

4
00:00:13,280 --> 00:00:15,440
Dit is CS50.

5
00:00:15,440 --> 00:00:21,040
En vandag, ons het 'n baie
interessante dinge om oor te praat.

6
00:00:21,040 --> 00:00:25,500
Eerstens, al is, ek het om te herinner
jy 'n paar administratiewe dinge.

7
00:00:25,500 --> 00:00:30,160
Hierdie week is quiz een Woensdag
of vir die artikel Yale

8
00:00:30,160 --> 00:00:32,940
op Dinsdae en Donderdae, op Donderdag.

9
00:00:32,940 --> 00:00:38,170
Daar is quiz resensies
vanaand by Yale, 5:30-07:00.

10
00:00:38,170 --> 00:00:40,030
By Harvard, aangeteken hulle een gister.

11
00:00:40,030 --> 00:00:43,000
En almal kan dit aanlyn te kyk.

12
00:00:43,000 --> 00:00:49,406
>> Ook hierdie week of vroeg volgende week,
ons het ons laaste CS50 lesing.

13
00:00:49,406 --> 00:00:51,450
[Kreun] Ek weet.

14
00:00:51,450 --> 00:00:54,140
Dit het so gou.

15
00:00:54,140 --> 00:00:57,820
Yale studente sal 'n lewendige het
lesings hier in die wet skool

16
00:00:57,820 --> 00:00:59,920
ouditorium op Vrydag.

17
00:00:59,920 --> 00:01:01,140
Daar sal die koek wees.

18
00:01:01,140 --> 00:01:05,570
Harvard studente sal die
laaste lesing in Sanders op Maandag.

19
00:01:05,570 --> 00:01:08,050
Daar sal ook die koek wees.

20
00:01:08,050 --> 00:01:14,000
>> Ook hierdie week op Vrydag, vir diegene
van julle wat kom na New Haven,

21
00:01:14,000 --> 00:01:15,740
ons het die CS50 Expo.

22
00:01:15,740 --> 00:01:18,850
Ons het meer as 30
verskillende groepe geregistreer

23
00:01:18,850 --> 00:01:22,530
om jou te wys alles
van outonome seilbote,

24
00:01:22,530 --> 00:01:27,170
om stelsels wat erken
digitale portrette, rekenaar

25
00:01:27,170 --> 00:01:32,100
musiek en rekenaar geproduseer musiek.

26
00:01:32,100 --> 00:01:33,610
So asseblief saam met ons.

27
00:01:33,610 --> 00:01:36,460
Ek dink dit gaan 'n goeie tyd wees.

28
00:01:36,460 --> 00:01:40,320
>> Vandag, al is, kry ons
voortgaan praat oor AI,

29
00:01:40,320 --> 00:01:43,150
oor kunsmatige intelligensie.

30
00:01:43,150 --> 00:01:46,070
En een van die dinge wat
ons gaan vandag te kry

31
00:01:46,070 --> 00:01:51,750
is die idee van hoe om
gebruik AI om probleme op te los.

32
00:01:51,750 --> 00:01:54,690
Nou, soos altyd, laat ons begin
met iets eenvoudig.

33
00:01:54,690 --> 00:01:57,120
En ons gaan om te begin
met 'n eenvoudige idee.

34
00:01:57,120 --> 00:01:59,920
En dit is met 'n soektog.

35
00:01:59,920 --> 00:02:06,990
>> So dink vir 'n oomblik dat ek
'n taak wat ek nodig het om uit te voer.

36
00:02:06,990 --> 00:02:11,970
En ek wil graag die taak het
outomatiese deur sommige sagteware agent.

37
00:02:11,970 --> 00:02:17,100
Stel jou voor dat ek probeer om 'n stel te bespreek
vlug van, kom ons sê, Boston

38
00:02:17,100 --> 00:02:20,040
San Francisco.

39
00:02:20,040 --> 00:02:24,230
Ek kon deur te gaan en ek kan gebruik
een van die wonderlike online soek

40
00:02:24,230 --> 00:02:28,790
gereedskap, wat gaan doen
basies dieselfde proses wat ons is

41
00:02:28,790 --> 00:02:30,030
gaan om te loop deur vandag.

42
00:02:30,030 --> 00:02:34,100
Maar as jy het nie daardie
instrument, wat sou jy doen?

43
00:02:34,100 --> 00:02:37,570
>> Wel, kan jy kyk en
sien en sê: Ek is in Boston.

44
00:02:37,570 --> 00:02:41,520
Wat is daar vlug na my toe?

45
00:02:41,520 --> 00:02:44,390
Nou, miskien het ek drie
moontlike vlugte uit Boston

46
00:02:44,390 --> 00:02:47,180
Dit sal die tyd te pas
wanneer ek nodig het om te gaan.

47
00:02:47,180 --> 00:02:48,830
Ek kon vlieg na Chicago.

48
00:02:48,830 --> 00:02:50,130
Of ek kan vlieg na Miami.

49
00:02:50,130 --> 00:02:53,340
Of ek kan vlieg na New York.

50
00:02:53,340 --> 00:02:56,980
Ek kan dan kyk van elke
een van daardie bestemming stede

51
00:02:56,980 --> 00:03:00,650
en dink oor wat plekke
Ek kan moontlik bereik

52
00:03:00,650 --> 00:03:03,020
uit elk van dié individuele stede.

53
00:03:03,020 --> 00:03:07,390
>> So miskien van Chicago, kan ek
'n direkte vlug na San Francisco.

54
00:03:07,390 --> 00:03:09,550
Dit is 'n uitstekende.

55
00:03:09,550 --> 00:03:12,360
Of ek kan 'n vlug na Denver kry.

56
00:03:12,360 --> 00:03:16,970
Nou, miskien vlug na San Francisco
is die ideale oplossing vir my,

57
00:03:16,970 --> 00:03:19,530
maar miskien nie.

58
00:03:19,530 --> 00:03:22,180
Miskien is ek op soek na iets
dit is 'n bietjie goedkoper

59
00:03:22,180 --> 00:03:24,920
of 'n bietjie beter vir my skedule.

60
00:03:24,920 --> 00:03:29,197
En so het ek kan kyk vir wat ander
moontlikhede kan wees daar buite.

61
00:03:29,197 --> 00:03:30,280
So ek kan kyk na Denver.

62
00:03:30,280 --> 00:03:33,870
En van Denver, goed, miskien
Ek kan 'n vlug na Austin kry.

63
00:03:33,870 --> 00:03:37,080
En van Austin, miskien kan ek kry '
vlug na Phoenix, en van Phoenix

64
00:03:37,080 --> 00:03:40,190
San Francisco.

65
00:03:40,190 --> 00:03:42,730
Nou, ek nog nie gedoen het nie.

66
00:03:42,730 --> 00:03:45,640
Want miskien is daar 'n
direkte vlug van New York

67
00:03:45,640 --> 00:03:47,850
San Francisco dis perfek vir my.

68
00:03:47,850 --> 00:03:53,354
Of miskien is daar 'n vlug van Miami
deur Denver dit is 'n baie goedkoper.

69
00:03:53,354 --> 00:03:54,270
So ek het nog om te gaan.

70
00:03:54,270 --> 00:03:58,200
En ek het nog steeds om te kyk na al daardie
stede wat ek nog nie ondersoek nie.

71
00:03:58,200 --> 00:04:04,220
Ek moet uitvoerig check al
die moontlikhede wat ek mag hê.

72
00:04:04,220 --> 00:04:09,610
>> So van New York, miskien kan ek kry '
vlug na Nashville, en van Nashville

73
00:04:09,610 --> 00:04:10,336
Austin.

74
00:04:10,336 --> 00:04:11,460
En dan weet ek waar ek is.

75
00:04:11,460 --> 00:04:14,252
En dan weet ek van Austin, ek kan
vlieg na Phoenix, en van Phoenix

76
00:04:14,252 --> 00:04:14,960
San Francisco.

77
00:04:14,960 --> 00:04:18,240

78
00:04:18,240 --> 00:04:22,830
As ek vlieg eers Miami, al is,
Miskien kan ek 'n vlug van Miami kry

79
00:04:22,830 --> 00:04:25,080
Nashville, of van Miami Austin.

80
00:04:25,080 --> 00:04:27,950

81
00:04:27,950 --> 00:04:30,860
>> En nou het ek al probeer
van die moontlikhede.

82
00:04:30,860 --> 00:04:36,310
Ek het hierdie grafiek opgebou wat
wys my al die moontlike roetes

83
00:04:36,310 --> 00:04:37,790
dat ek dalk in staat wees om te neem.

84
00:04:37,790 --> 00:04:40,510

85
00:04:40,510 --> 00:04:43,640
Wanneer ons hierdie verteenwoordig
soorte probleme,

86
00:04:43,640 --> 00:04:47,870
ons is nie van plan om te verteenwoordig
uitdruklik as hierdie grafiek,

87
00:04:47,870 --> 00:04:51,590
want dit grafiek verteenwoordig nie
die geskiedenis van waar ons gegaan het.

88
00:04:51,590 --> 00:04:55,260
Wetende dat ek gevlieg vanaf
Phoenix na San Francisco

89
00:04:55,260 --> 00:05:01,690
my nie sê of ek via gekom
Nashville, of via Denver, of via Miami.

90
00:05:01,690 --> 00:05:06,430
>> So, wat ek sal doen in plaas is
Ek sal dit dieselfde probleem te neem,

91
00:05:06,430 --> 00:05:09,140
en ek sal dit as 'n boom verteenwoordig.

92
00:05:09,140 --> 00:05:14,300
En aan die wortel van die boom, by die
top, ek sal die plek wat ek begin het,

93
00:05:14,300 --> 00:05:16,590
Boston.

94
00:05:16,590 --> 00:05:19,310
En van Boston, sal ek kyk na
al die moontlike plekke

95
00:05:19,310 --> 00:05:20,380
dat ek kan reis na.

96
00:05:20,380 --> 00:05:25,480
Wel, in hierdie geval, het ek drie,
Chicago, New York, en Miami.

97
00:05:25,480 --> 00:05:29,850
En dan sal ek elkeen van verken
hierdie kinders in die boom.

98
00:05:29,850 --> 00:05:32,690
>> Van Chicago, het ek gesien
dat ek het twee vlugte.

99
00:05:32,690 --> 00:05:35,940
Ek kon direk vlieg na
San Francisco of Denver.

100
00:05:35,940 --> 00:05:37,740
Nou San Francisco, dit is my doel te bereik.

101
00:05:37,740 --> 00:05:39,790
Dit is my bestemming.

102
00:05:39,790 --> 00:05:42,220
Dit gaan om 'n blaar van die boom wees.

103
00:05:42,220 --> 00:05:45,340
Dit is, ek is nooit gaan om te gaan
iewers ná San Francisco.

104
00:05:45,340 --> 00:05:47,850

105
00:05:47,850 --> 00:05:50,340
Van Denver, al is,
Ek kan vlieg van Denver

106
00:05:50,340 --> 00:05:54,220
Austin, van Austin aan Phoenix,
en van Phoenix na San Francisco.

107
00:05:54,220 --> 00:05:56,050
En nou weer, ek het 'n blaar bereik.

108
00:05:56,050 --> 00:05:59,470

109
00:05:59,470 --> 00:06:03,980
>> Ek kan dan terug te gaan na die volgende
stad wat ek nie ten volle ondersoek.

110
00:06:03,980 --> 00:06:07,440
Dit sou wees New York, gaan
terug na die top van my boom

111
00:06:07,440 --> 00:06:09,160
Kom af na New York.

112
00:06:09,160 --> 00:06:12,700
Van New York, kan ek vlieg
Nashville, van Nashville om Austin,

113
00:06:12,700 --> 00:06:17,290
van Austin aan Phoenix, en
van Phoenix na San Francisco.

114
00:06:17,290 --> 00:06:20,170
En ten slotte, die een stad ek
het nog nie gekyk, Miami.

115
00:06:20,170 --> 00:06:24,600
>> Wel, van Miami Ek het gesê ek het twee
moontlikhede, Nashville of Austin.

116
00:06:24,600 --> 00:06:28,810
As ek vlieg na Nashville, goed dan vlieg ek
van Nashville, Austin, om Phoenix,

117
00:06:28,810 --> 00:06:29,640
San Francisco.

118
00:06:29,640 --> 00:06:33,600
As ek vlieg na Austin, ek vlieg Austin,
Phoenix, San Francisco.

119
00:06:33,600 --> 00:06:36,340
En nou het ek 'n boom.

120
00:06:36,340 --> 00:06:37,230
Dit is 'n volledige boom.

121
00:06:37,230 --> 00:06:41,890
Dit is al die moontlikhede en
al die paaie wat ek kon neem.

122
00:06:41,890 --> 00:06:44,310
Dit is, as ek begin by die
wortel van die boom aan die bokant

123
00:06:44,310 --> 00:06:47,860
en ek gaan af na een van die
laat dit my vertel nie net

124
00:06:47,860 --> 00:06:50,480
waar ek gaan
beland, San Francisco,

125
00:06:50,480 --> 00:06:53,670
maar dit vertel my die roete wat
Ek nodig het om te neem om daar te kom.

126
00:06:53,670 --> 00:06:56,400

127
00:06:56,400 --> 00:06:59,690
>> Nou, wat een van hierdie is die beste?

128
00:06:59,690 --> 00:07:02,430
Wel, niks oor hierdie
nog probleem vertel my

129
00:07:02,430 --> 00:07:04,710
watter een van dié is die beste oplossing.

130
00:07:04,710 --> 00:07:09,270
Miskien het ek die meeste omgee
hoeveel keer dat ek in die lug,

131
00:07:09,270 --> 00:07:12,350
of die afstand wat ek vlieg.

132
00:07:12,350 --> 00:07:16,410
In daardie geval, Chicago na San
Francisco dalk die kortste getal wees

133
00:07:16,410 --> 00:07:18,910
myle in die lug.

134
00:07:18,910 --> 00:07:20,860
>> Miskien het ek omgee koste.

135
00:07:20,860 --> 00:07:23,680
En ons almal weet direkte vlugte
is gewoonlik duurder.

136
00:07:23,680 --> 00:07:26,610
So miskien as ek dit neem
soort agtertoe roete

137
00:07:26,610 --> 00:07:30,650
deur Miami, Nashville,
Austin, Phoenix, miskien dan

138
00:07:30,650 --> 00:07:34,070
Ek kry 'n laer prys.

139
00:07:34,070 --> 00:07:36,440
Maar ek kon optimaliseer op enige
kriteria wat ek omgee.

140
00:07:36,440 --> 00:07:39,790
Wie het die beste in
vlug Wi-Fi, of wat

141
00:07:39,790 --> 00:07:43,110
lughawens het die beste kos beskikbaar is.

142
00:07:43,110 --> 00:07:47,280
En elkeen van daardie mag
gee my 'n ander oplossing

143
00:07:47,280 --> 00:07:49,215
wat ek sien as die beste.

144
00:07:49,215 --> 00:07:51,990

145
00:07:51,990 --> 00:07:54,400
>> Hierdie soort probleme,
waar ons gaan

146
00:07:54,400 --> 00:07:58,480
om te bou uit die boom van
moontlikhede, en dan

147
00:07:58,480 --> 00:08:02,100
kyk na elkeen van daardie
individuele paaie, en ondersoek

148
00:08:02,100 --> 00:08:05,270
watter een van dié vervul
'n kriteria vir ons,

149
00:08:05,270 --> 00:08:08,790
ons gaan om te bel
diegene search probleme.

150
00:08:08,790 --> 00:08:11,280
En ons het baie van
algoritmes, waarvan sommige

151
00:08:11,280 --> 00:08:15,270
ons het reeds gesien, om te gaan
en verken die bome.

152
00:08:15,270 --> 00:08:19,270
Ons kan dit doen op die manier wat ek
net gedoen het, 'n diepte-eerste soek,

153
00:08:19,270 --> 00:08:22,900
om af te gaan so ver as wat ons kan, totdat ons
getref 'n blaar, en dan terug te kom op,

154
00:08:22,900 --> 00:08:24,787
en gaan terug sit.

155
00:08:24,787 --> 00:08:26,870
Of ons kan doen wat
genoem breedte-eerste soek.

156
00:08:26,870 --> 00:08:29,675
Ons kan alles uit te brei
aan die bokant, en dan

157
00:08:29,675 --> 00:08:31,550
alles een reël
onder daardie, en dan

158
00:08:31,550 --> 00:08:35,240
alles een reël onder dit.

159
00:08:35,240 --> 00:08:41,250
Diegene search bome
is fundamenteel tot AI.

160
00:08:41,250 --> 00:08:46,570
Maar hulle het nie heeltemal kry
dit reg om al die tyd.

161
00:08:46,570 --> 00:08:51,600
Trouens, in 'n groot deel van die gevalle
dat ons regtig omgee,

162
00:08:51,600 --> 00:08:54,430
ons wil 'n boom te bou,
Maar ons het nie eintlik

163
00:08:54,430 --> 00:08:57,140
kry om al die besluite te neem.

164
00:08:57,140 --> 00:09:00,940
>> Dit is situasies genoem
opponerende soek, ook bekend

165
00:09:00,940 --> 00:09:05,390
hoe om te speel spel skryf
stelsels en betaal vir dit.

166
00:09:05,390 --> 00:09:07,940
Maar hierdie is die soort
stelsels waar ek

167
00:09:07,940 --> 00:09:12,920
kan kry om van te kies wanneer ek gaan van
Boston, watter stad Ek gaan na die volgende.

168
00:09:12,920 --> 00:09:19,990
Maar daarna het iemand anders kan kry
die besluit oor waar ek vlieg.

169
00:09:19,990 --> 00:09:24,040
So om hierdie te bou
soorte strukture, ons is

170
00:09:24,040 --> 00:09:28,510
gaan hê om 'n effens te neem
ander benadering om dit te.

171
00:09:28,510 --> 00:09:31,060
Ons gaan nie in staat wees om
net soek deur die boom

172
00:09:31,060 --> 00:09:35,000
nie, want ons is nie
die een wat in beheer

173
00:09:35,000 --> 00:09:38,180
van elk van daardie besluit punte.

174
00:09:38,180 --> 00:09:42,590
>> So laat dink 'n eenvoudige
spel soos tic-tac-toe.

175
00:09:42,590 --> 00:09:46,730
Ek kon met 'n begin
heeltemal leeg raad.

176
00:09:46,730 --> 00:09:49,580
En in tic-tac-toe,
X kry om eerste te speel.

177
00:09:49,580 --> 00:09:53,890
En so het ek kon dink oor al die
moontlike beweeg wat X kan maak.

178
00:09:53,890 --> 00:09:57,420
En as ek die een speel
die X, dit is 'n groot.

179
00:09:57,420 --> 00:10:01,020
Ek het nege moontlike
beweeg wat ek kan maak.

180
00:10:01,020 --> 00:10:05,000
Ek kon 'n X in een sit
van die nege posisies.

181
00:10:05,000 --> 00:10:10,710
>> En dan van elkeen van daardie, ek
kon dink wat gebeur volgende.

182
00:10:10,710 --> 00:10:14,130
Wel, in hierdie geval, die ander
speler sou kry om 'n beurt te neem.

183
00:10:14,130 --> 00:10:15,660
O sou kry om 'n beurt te neem.

184
00:10:15,660 --> 00:10:19,510
En uit elk van bogenoemde, is daar
sou wees agt verskillende plekke

185
00:10:19,510 --> 00:10:22,980
dat O kon hul merker.

186
00:10:22,980 --> 00:10:25,790
>> Kom ons sê ek het besluit dat ek was
gaan 'n X in die middel sit.

187
00:10:25,790 --> 00:10:28,810
Dit lyk altyd so
'n goeie opening beweeg.

188
00:10:28,810 --> 00:10:34,870
Ek kon sien onder dat die
agt moontlike beweeg wat O maak.

189
00:10:34,870 --> 00:10:37,320
Nou, as ek speel X, dit is wonderlik.

190
00:10:37,320 --> 00:10:41,740
Ek kry om watter een ek kies
gaan, die een in die middel.

191
00:10:41,740 --> 00:10:45,000
Maar nou O kry om van te kies.

192
00:10:45,000 --> 00:10:48,750
En ek het nie beheer het
oor die besluit.

193
00:10:48,750 --> 00:10:51,670
>> Maar uit elk van dié
moontlike raad posisies,

194
00:10:51,670 --> 00:10:54,020
daar is dan nog
stel moontlikhede.

195
00:10:54,020 --> 00:10:56,700
Wanneer dit kom by wees
My terugkom, sou ek

196
00:10:56,700 --> 00:11:01,500
kry om te kies en te sê, goed,
As O beweeg in die, wel,

197
00:11:01,500 --> 00:11:06,110
die middel plek op die links, dan
Ek het 'n stel van moontlikhede

198
00:11:06,110 --> 00:11:09,740
waar ek my volgende skuif kan plaasvind.

199
00:11:09,740 --> 00:11:14,140
Van diegene, kon ek al oorweeg
die moontlikhede onder hulle.

200
00:11:14,140 --> 00:11:18,030
En dan O sou kry
om te kies tussen hulle.

201
00:11:18,030 --> 00:11:22,290
>> En ek kon hou die bou van hierdie
boom uit totdat ek het tot die punt

202
00:11:22,290 --> 00:11:26,960
waar óf iemand
wen die game-- dis

203
00:11:26,960 --> 00:11:31,070
het om as 'n blaar node--
of die raad is heeltemal vol

204
00:11:31,070 --> 00:11:32,704
en niemand het gewen.

205
00:11:32,704 --> 00:11:34,370
En dit is ook van plan om 'n blaarnodus wees.

206
00:11:34,370 --> 00:11:35,411
Dit gaan om 'n das te wees.

207
00:11:35,411 --> 00:11:37,820

208
00:11:37,820 --> 00:11:41,680
>> Maar die moeilike ding met hierdie is
As dit was net 'n gereelde soek

209
00:11:41,680 --> 00:11:44,269
probleem, sou ek in staat wees om
sê, goed, X moet hier gaan.

210
00:11:44,269 --> 00:11:45,560
En O moet weg oor daar te gaan.

211
00:11:45,560 --> 00:11:46,770
En dan moet X hier gaan.

212
00:11:46,770 --> 00:11:48,269
En dan moet O weg oor daar te gaan.

213
00:11:48,269 --> 00:11:51,860
En dan X kan drie kry
in 'n ry, en ek wen.

214
00:11:51,860 --> 00:11:54,870
En die spel sal wees oor
in vyf beweeg, drie vir my,

215
00:11:54,870 --> 00:11:57,710
twee vir my teenstander.

216
00:11:57,710 --> 00:12:01,300
Maar ek kry nie altyd te kies nie.

217
00:12:01,300 --> 00:12:03,720
>> So in plaas, wat ons is
gaan hê om te doen

218
00:12:03,720 --> 00:12:06,270
is ons gaan hê
om 'n nuwe strategie.

219
00:12:06,270 --> 00:12:09,350
En die strategie wat
spel-speel algoritmes gebruik dikwels

220
00:12:09,350 --> 00:12:12,000
is wat minimaks genoem.

221
00:12:12,000 --> 00:12:15,500
Die sentrale idee van
minimaks is dat ons

222
00:12:15,500 --> 00:12:21,365
gaan na die skuif wat gee pluk
ons opponent die ergste moontlike stel

223
00:12:21,365 --> 00:12:22,790
beweeg dat hulle kan maak.

224
00:12:22,790 --> 00:12:25,570

225
00:12:25,570 --> 00:12:28,870
Dit maak my nie 'n goeie
om 'n skuif te kies waar

226
00:12:28,870 --> 00:12:31,952
Ek kan in staat wees om te wen nadat
dat omdat my teenstander is nie

227
00:12:31,952 --> 00:12:33,160
gaan vir my dat 'n kans gee.

228
00:12:33,160 --> 00:12:37,770
Hulle gaan 'n paar kies
verskriklike uitslag vir my.

229
00:12:37,770 --> 00:12:42,010
So ek gaan die maak
beweeg wat kragte my opponent

230
00:12:42,010 --> 00:12:45,760
om iets vir my beter te doen.

231
00:12:45,760 --> 00:12:46,260
Alles reg.

232
00:12:46,260 --> 00:12:48,410
Kom ons kyk hoe dit speel nie.

233
00:12:48,410 --> 00:12:51,640
So hier is ons algoritme in pseudokode.

234
00:12:51,640 --> 00:12:54,450
Ons gaan om te genereer
die hele wedstryd boom.

235
00:12:54,450 --> 00:12:56,757
Ons gaan bou
die hele struktuur.

236
00:12:56,757 --> 00:12:57,840
En dan sal ons deur te gaan.

237
00:12:57,840 --> 00:13:02,100
En op die heel onderste by elk van die
terminale nodes, by elk van die blare,

238
00:13:02,100 --> 00:13:07,850
ons sal evalueer hoe
waardevolle is dat na my toe?

239
00:13:07,850 --> 00:13:11,690
En ons gaan om waarde dinge wat
is goed vir my as positief.

240
00:13:11,690 --> 00:13:14,460
Dinge wat nie goed vir my
minder positief sal wees, of nul,

241
00:13:14,460 --> 00:13:16,480
of selfs negatief.

242
00:13:16,480 --> 00:13:19,240
>> So in tic-tac-toe, miskien
'n oorwinning vir my goed is.

243
00:13:19,240 --> 00:13:20,290
Dit is 'n een.

244
00:13:20,290 --> 00:13:22,400
En 'n das is nul.

245
00:13:22,400 --> 00:13:26,230
En iets wat 'n verlies vir
my, miskien is dit 'n negatiewe een.

246
00:13:26,230 --> 00:13:29,620
Al wat saak maak, is dat die beter
Dit is vir my, hoe hoër die telling

247
00:13:29,620 --> 00:13:32,160
dit ontvang.

248
00:13:32,160 --> 00:13:36,690
Van dié moontlikhede by die
bodem, dan sal ons opwaartse filtreer.

249
00:13:36,690 --> 00:13:40,650
En wanneer dit is my kans om te kies
onder 'n stel van alternatiewe,

250
00:13:40,650 --> 00:13:44,460
Ek sal die een wat kies
het die hoogste telling.

251
00:13:44,460 --> 00:13:47,200
>> En wanneer dit is my
teenstanders draai om van te kies,

252
00:13:47,200 --> 00:13:52,350
Ek sal aanvaar dat hulle gaan
kies die een met die laagste telling.

253
00:13:52,350 --> 00:13:56,090
En as ek doen dit al die pad
op die top van die boom,

254
00:13:56,090 --> 00:14:03,150
Ek sal 'n pad wat gee gekies
my die beste uitkoms wat ek kan kry,

255
00:14:03,150 --> 00:14:09,110
veronderstelling dat my opponent
maak al die regte skuiwe.

256
00:14:09,110 --> 00:14:11,940
>> Alle reg, so laat ons sien
hierdie in aksie eerste.

257
00:14:11,940 --> 00:14:14,980
En dan sal ons werklik
kyk na die kode vir dit.

258
00:14:14,980 --> 00:14:16,780
So dink ek het hierdie groot boom.

259
00:14:16,780 --> 00:14:18,280
En nou is ek nie speel tic-tac-toe.

260
00:14:18,280 --> 00:14:20,405
Ek wou om jou te gee
iets wat 'n bietjie ryker.

261
00:14:20,405 --> 00:14:23,560
So ek het 'n paar spel waar het
daar is baie verskillende tellings

262
00:14:23,560 --> 00:14:26,390
dat ek kan hê aan die einde.

263
00:14:26,390 --> 00:14:27,980
En so het ek bou hierdie volledige boom.

264
00:14:27,980 --> 00:14:29,070
En ek kry om eers te beweeg.

265
00:14:29,070 --> 00:14:31,290
Ek is die wortel van die boom.

266
00:14:31,290 --> 00:14:36,150
>> En ek kry om te kies that-- so ek kry
om te maksimeer oor daardie eerste knoop.

267
00:14:36,150 --> 00:14:38,410
En dan my opponent kry om te gaan.

268
00:14:38,410 --> 00:14:41,910
En dan kry ek weer gaan.

269
00:14:41,910 --> 00:14:46,830
So af aan die onderkant, ek het 'n stel van
moontlikhede wat ek kan kies uit,

270
00:14:46,830 --> 00:14:50,570
verskillende terminale state van die spel.

271
00:14:50,570 --> 00:14:54,980
As ek in daardie
ver linker hoek,

272
00:14:54,980 --> 00:14:58,867
en ek sien dat ek 'n keuse het
tussen 'n agt, sewe, en 'n twee,

273
00:14:58,867 --> 00:15:00,450
Wel, ek is die een wat kry om van te kies.

274
00:15:00,450 --> 00:15:02,910
So ek gaan om te kies
die beste een van daardie.

275
00:15:02,910 --> 00:15:05,650
Ek gaan die agt kies.

276
00:15:05,650 --> 00:15:10,090
>> So ek weet dat as ek ooit
kom neer op daardie punt,

277
00:15:10,090 --> 00:15:13,890
Ek sal in staat wees om daardie agt punte te kry.

278
00:15:13,890 --> 00:15:17,410
As ek uiteindelik by die volgende punt
oor die volgende node oor,

279
00:15:17,410 --> 00:15:20,760
'n nege, 'n een of 'n ses, goed, ek is
gaan na die beste van diegene te kies.

280
00:15:20,760 --> 00:15:21,950
Ek sal die nege te kies.

281
00:15:21,950 --> 00:15:24,880
As ek 'n keuse tussen
twee en vier, en een,

282
00:15:24,880 --> 00:15:28,240
Ek sal die vier, het die hoogste kies.

283
00:15:28,240 --> 00:15:31,990
>> Nou, as ek kyk na die vlak
bo, my opponent

284
00:15:31,990 --> 00:15:34,440
is die een kry om daardie keuse te maak.

285
00:15:34,440 --> 00:15:37,040
So my opponent kry om
kies, wil ek aan hom gee

286
00:15:37,040 --> 00:15:39,250
die ding wat gaan
om hom agt punte te kry,

287
00:15:39,250 --> 00:15:41,916
of ek gee hom die ding wat
gaan hom nege punte te gee,

288
00:15:41,916 --> 00:15:45,240
of die ding wat gaan
hom vier punte te gee?

289
00:15:45,240 --> 00:15:49,130
En my opponent, wat
rasionele, gaan

290
00:15:49,130 --> 00:15:53,470
tot die minimum van die kies,
gaan die vier te kies.

291
00:15:53,470 --> 00:15:56,020
>> En ek kan dit doen
deur die hele boom.

292
00:15:56,020 --> 00:15:59,110
Ek kan daal tot daardie
middel stel van drie.

293
00:15:59,110 --> 00:16:01,517
En ek kan kies tussen
een, drie en vyf.

294
00:16:01,517 --> 00:16:02,350
En ek kry om te kies.

295
00:16:02,350 --> 00:16:03,810
So ek kies 'n vyf.

296
00:16:03,810 --> 00:16:05,340
Ek kan drie, nege, of twee te kies.

297
00:16:05,340 --> 00:16:07,570
Ek kry om te kies, so ek kies die nege.

298
00:16:07,570 --> 00:16:09,290
Ses, vyf, of twee, ek kies.

299
00:16:09,290 --> 00:16:11,539
Ek kry die ses te kies.

300
00:16:11,539 --> 00:16:13,080
Vlak bo, wie kry om te kies?

301
00:16:13,080 --> 00:16:16,280

302
00:16:16,280 --> 00:16:18,140
Wie kry om van te kies?

303
00:16:18,140 --> 00:16:20,000
Die ander man, my teenstander.

304
00:16:20,000 --> 00:16:22,583
Sodat hulle kies vyf,
nege of ses, waarvan een?

305
00:16:22,583 --> 00:16:23,410
>> GEHOOR: Die vyf.

306
00:16:23,410 --> 00:16:25,250
>> Spreker: Hulle kies die vyf.

307
00:16:25,250 --> 00:16:27,400
Hulle kry tot die minimum te kies.

308
00:16:27,400 --> 00:16:29,690
En dan is die laaste een,
kies een, twee, of drie.

309
00:16:29,690 --> 00:16:31,720
Ek kry om te kies, so ek drie te kies.

310
00:16:31,720 --> 00:16:34,370
Nege, sewe, of twee, ek kies nege.

311
00:16:34,370 --> 00:16:37,070
En 11, ses, of vier, ek kies 11.

312
00:16:37,070 --> 00:16:41,190
My teenstander kies dan drie,
nege of 11, kies die minimum te beperk.

313
00:16:41,190 --> 00:16:43,290
Hy gee my 'n drie.

314
00:16:43,290 --> 00:16:47,780
En dan uiteindelik by die top van
die boom, ek kry om weer te kies.

315
00:16:47,780 --> 00:16:51,190
En ek kry om te kies tussen
'n vier, vyf, of 'n drie.

316
00:16:51,190 --> 00:16:52,270
So ek neem die vyf.

317
00:16:52,270 --> 00:16:55,070

318
00:16:55,070 --> 00:17:00,891
>> As ek om alles te beheer, sou ek
neem die pad wat gelei het tot die 11.

319
00:17:00,891 --> 00:17:02,390
Maar ek kry nie daardie keuse te maak.

320
00:17:02,390 --> 00:17:04,220
As ek gaan neer dat die pad.

321
00:17:04,220 --> 00:17:10,710
My teenstander sal my dwing om in
Die keuse wat lei tot 'n drie.

322
00:17:10,710 --> 00:17:14,530
Dus is die beste wat ek kan doen, is om
dat die middel-tak neem,

323
00:17:14,530 --> 00:17:19,859
maak dat die keuse wat uiteindelik
gaan my lei tot vyf punte.

324
00:17:19,859 --> 00:17:23,230
Dit is wat minimaks doen.

325
00:17:23,230 --> 00:17:23,807
>> Alles reg.

326
00:17:23,807 --> 00:17:24,890
Kom ons neem 'n blik op dit.

327
00:17:24,890 --> 00:17:27,480

328
00:17:27,480 --> 00:17:32,330
So hier in die CS50
IDE is 'n program wat

329
00:17:32,330 --> 00:17:36,540
implemente minimaks om tic-tac-toe te speel.

330
00:17:36,540 --> 00:17:40,100
Ons gaan bou
'n verteenwoordiging.

331
00:17:40,100 --> 00:17:44,390
Ons gaan twee opponent-- het
of twee spelers, ons rekenaar

332
00:17:44,390 --> 00:17:46,090
speler en 'n mens speler.

333
00:17:46,090 --> 00:17:48,980

334
00:17:48,980 --> 00:17:53,090
Speler nommer een sal speel
die O. Dit sal die masjien speler.

335
00:17:53,090 --> 00:17:55,747
Hulle kry om die tweede te beweeg.

336
00:17:55,747 --> 00:17:57,830
En die ander speler, ons
menslike speler, sal X.

337
00:17:57,830 --> 00:17:59,880
>> En om my lewe te maak 'n
bietjie eenvoudige, ek gaan

338
00:17:59,880 --> 00:18:03,060
om die speler negatiewe etiketteer.

339
00:18:03,060 --> 00:18:05,026
So ek kan net vermeerder
deur negatiewe een te ruil

340
00:18:05,026 --> 00:18:06,400
tussen een speler en die ander.

341
00:18:06,400 --> 00:18:09,030

342
00:18:09,030 --> 00:18:12,250
Alle reg, so laat ons neem 'n blik op
wat ons eintlik gaan doen.

343
00:18:12,250 --> 00:18:15,840
Ons gaan ons raad te definieer.

344
00:18:15,840 --> 00:18:19,060
Dit gaan wees, wel, ons gaan
toelaat dat dit tot drie deur drie wees,

345
00:18:19,060 --> 00:18:21,580
of ons kan selfs speel
vyf deur vyf of sewe

346
00:18:21,580 --> 00:18:28,870
met sewe tic-tac-toe as jy wil
soos, gebaseer op sommige dimensie D.

347
00:18:28,870 --> 00:18:31,260
>> En ons sal 'n paar het
van helper funksies

348
00:18:31,260 --> 00:18:34,360
dit sal dinge te doen soos
inisialiseer die screen-- of jammer,

349
00:18:34,360 --> 00:18:38,900
inisialiseer ons veranderlikes, duidelik die
skerm, trek die raad op die skerm,

350
00:18:38,900 --> 00:18:41,060
een wat 'n raad tjeks
om te sien of

351
00:18:41,060 --> 00:18:44,520
daar is 'n wenner, een wat
ontleed deur die opdrag lyn,

352
00:18:44,520 --> 00:18:50,670
net om uit te help, die een wat lees in
insette en een funksie genoem minimaks.

353
00:18:50,670 --> 00:18:52,746
En dit is die een
ons sal omgee oor.

354
00:18:52,746 --> 00:18:54,120
Maar laat ons kyk eers by die hoof.

355
00:18:54,120 --> 00:18:57,490

356
00:18:57,490 --> 00:18:58,510
>> Wat doen ons?

357
00:18:58,510 --> 00:19:00,570
Wel, ons gaan
ontleed ons opdrag lyn,

358
00:19:00,570 --> 00:19:04,300
net lees in en kyk wat
dimensie raad wat ons wil hê.

359
00:19:04,300 --> 00:19:07,330
Ons sal ons raad inisialiseer.

360
00:19:07,330 --> 00:19:10,360
En dan sal ons 'n tree
groot wilde lus, herhaaldelik

361
00:19:10,360 --> 00:19:16,630
aanvaar beweeg totdat die spel is
gewen het, of is daar geen beweeg links.

362
00:19:16,630 --> 00:19:20,560
Elke keer as ons gaan deur daardie
lus, ons sal die skerm skoon te maak.

363
00:19:20,560 --> 00:19:23,290
Ons sal die bord teken op die skerm.

364
00:19:23,290 --> 00:19:28,750
En ons is doelbewus soort
ekserpering hierdie weg as subroetines,

365
00:19:28,750 --> 00:19:32,030
sodat ons nie hoef te bekommer te veel
oor die besonderhede van hoe dit gebeur.

366
00:19:32,030 --> 00:19:33,480
>> Jy sal die kode later vandag.

367
00:19:33,480 --> 00:19:37,970
En as jy wil om te kyk deur
en uit te vind, kan jy hulle almal te sien.

368
00:19:37,970 --> 00:19:39,890
Maar ons sal 'n raad te trek op die skerm.

369
00:19:39,890 --> 00:19:43,620
En dan sal ons gaan en
sien, ons het 'n wenner?

370
00:19:43,620 --> 00:19:46,290
Het iemand hierdie wedstryd gewen het?

371
00:19:46,290 --> 00:19:49,260
As hulle het, sal ons druk
uit 'n oorwinning boodskap.

372
00:19:49,260 --> 00:19:51,680
En ons sal die spel eindig.

373
00:19:51,680 --> 00:19:54,510
>> Ons sal ook kyk en
kyk of daar 'n das.

374
00:19:54,510 --> 00:19:56,620
Dit sal maklik wees om te sien of daar is 'n das.

375
00:19:56,620 --> 00:20:00,700
Dit beteken dat al die ruimtes is vol,
maar daar is nog nie 'n wenner is.

376
00:20:00,700 --> 00:20:03,580
Ons kan nie 'n das te verklaar en gedoen moet word.

377
00:20:03,580 --> 00:20:10,530
Toe die werklike meat-- as
dit is 'n masjien-speler,

378
00:20:10,530 --> 00:20:14,120
ons sal toelaat dat
masjien speler om te soek

379
00:20:14,120 --> 00:20:19,500
deur die gebruik van hierdie minimaks algoritme,
om die beste skuif wat dit kan kry.

380
00:20:19,500 --> 00:20:22,310
En dan sal ons die gewemel sit.

381
00:20:22,310 --> 00:20:27,640
>> Andersins, as dit 'n mens speler,
ons sal 'n paar insette van die menslike lees.

382
00:20:27,640 --> 00:20:30,800
En dan of dit die menslike
speler of die rekenaar speler,

383
00:20:30,800 --> 00:20:32,800
ons sal 'n paar doen min
stukkies foutopsporing,

384
00:20:32,800 --> 00:20:36,910
maak seker dit bly binne die grense
van die werklike afmetings van die raad

385
00:20:36,910 --> 00:20:40,040
wat ons het, maak seker
dat die ruimte is leeg,

386
00:20:40,040 --> 00:20:43,570
dat niemand se sit '
stuk in reeds daar.

387
00:20:43,570 --> 00:20:45,810
En dan sal ons net sit
'n stuk op die bord,

388
00:20:45,810 --> 00:20:51,550
verander die speler na die volgende laag, en
inkrementeer hoeveel beweeg gebeur het nie.

389
00:20:51,550 --> 00:20:54,090
>> Dit is die belangrikste lus vir
ons tic-tac-toe spel.

390
00:20:54,090 --> 00:20:57,000

391
00:20:57,000 --> 00:21:02,340
Minimax dan is presies
die algoritme wat ons voor.

392
00:21:02,340 --> 00:21:04,710
Die enigste aanpassing wat
ons gemaak het, sodat ons

393
00:21:04,710 --> 00:21:07,290
kan hoër speel
dimensionele borde is ons het

394
00:21:07,290 --> 00:21:11,070
gehou Hierdie ekstra parameter genoem diepte.

395
00:21:11,070 --> 00:21:14,870
En diepte sê net, as ek
afwaartse soek deur die boom

396
00:21:14,870 --> 00:21:19,022
en ek kry so ver af
buite 'n sekere vlak diepte

397
00:21:19,022 --> 00:21:20,730
dat ek wil net nie
om verder te gaan,

398
00:21:20,730 --> 00:21:25,630
Ek gaan om te stop en net
die direksie by daardie punt.

399
00:21:25,630 --> 00:21:27,310
Ek sal kyk en kyk of daar 'n wenner.

400
00:21:27,310 --> 00:21:29,240
As daar 'n wenner, ek hulle terug.

401
00:21:29,240 --> 00:21:31,720
Andersins, sal ek gaan deur 'n lus.

402
00:21:31,720 --> 00:21:34,380
En ek sal sê, vir al
die moontlike plekke

403
00:21:34,380 --> 00:21:38,080
dat ek kon moontlik
neem as my skuif, sal ek

404
00:21:38,080 --> 00:21:43,760
bou van 'n hipotetiese raad wat
sluit my skuif op daardie raad,

405
00:21:43,760 --> 00:21:45,960
en dan rekursief roep minimaks.

406
00:21:45,960 --> 00:21:49,360

407
00:21:49,360 --> 00:21:53,900
>> As dit is my skuif, ek kry die vind
een wat het die grootste telling.

408
00:21:53,900 --> 00:21:58,710
As dit skuif my opponent se, vind ons
die een wat het die minimum telling.

409
00:21:58,710 --> 00:22:02,240
En alles anders is
net rekordhouding.

410
00:22:02,240 --> 00:22:04,789
Alle reg, so laat ons sien dit hardloop.

411
00:22:04,789 --> 00:22:06,830
Eintlik, miskien kan ons
kry 'n paar vrywilligers

412
00:22:06,830 --> 00:22:09,930
om te kom en speel tic-tac-toe.

413
00:22:09,930 --> 00:22:12,780
[Onhoorbaar] een en een
meer, twee, reg daar.

414
00:22:12,780 --> 00:22:13,550
Kom up.

415
00:22:13,550 --> 00:22:19,290

416
00:22:19,290 --> 00:22:23,650
>> So laat ons gaan voort en
weer hierdie heeltemal.

417
00:22:23,650 --> 00:22:24,150
So, hi.

418
00:22:24,150 --> 00:22:24,920
>> GEHOOR: Hi.

419
00:22:24,920 --> 00:22:25,420
>> Spreker: Wat is jou naam?

420
00:22:25,420 --> 00:22:26,086
>> GEHOOR: Gorav.

421
00:22:26,086 --> 00:22:26,840
Spreker: Gorav.

422
00:22:26,840 --> 00:22:27,800
>> GEHOOR: Ek is Layla.

423
00:22:27,800 --> 00:22:29,490
>> Spreker: En Layla en Layla, jammer.

424
00:22:29,490 --> 00:22:30,384
Kom up.

425
00:22:30,384 --> 00:22:32,050
Gorav, ons gaan hê jy eers gaan.

426
00:22:32,050 --> 00:22:37,710
En ek gaan om jou te vra om 'n nie
verskriklik goeie tic-tac-toe-speler.

427
00:22:37,710 --> 00:22:40,130
OK, so al die druk af op jou.

428
00:22:40,130 --> 00:22:44,660
Kom ons kyk, al is, dat ons masjien
speler kan eintlik iets smart te doen.

429
00:22:44,660 --> 00:22:45,310
So gaan voort.

430
00:22:45,310 --> 00:22:49,830
Jy gaan om te tik in wat koördineer
jy wil om jou X in plaas.

431
00:22:49,830 --> 00:22:55,170
A0, OK, en die masjien het gegaan
dadelik en sit sy merk in A1.

432
00:22:55,170 --> 00:22:56,640
>> Sit die O op die bord.

433
00:22:56,640 --> 00:22:58,970
Alle reg, nou gaan voort.

434
00:22:58,970 --> 00:23:00,193
Waar wil jy gaan?

435
00:23:00,193 --> 00:23:03,510

436
00:23:03,510 --> 00:23:05,090
C2.

437
00:23:05,090 --> 00:23:08,430
Ons masjien speler geneem het
die middel vierkante, geblokkeer jou.

438
00:23:08,430 --> 00:23:10,320
So dit was 'n goeie,
slim ding om dit te doen nie.

439
00:23:10,320 --> 00:23:13,430

440
00:23:13,430 --> 00:23:14,250
Jy het geblokkeer nie.

441
00:23:14,250 --> 00:23:15,210
Dit is 'n uitstekende.

442
00:23:15,210 --> 00:23:16,390
Dit neem die hoek is daar.

443
00:23:16,390 --> 00:23:23,890

444
00:23:23,890 --> 00:23:30,430
>> En dit gaan om jou te dwing om
neem die een laaste ruimte, B0.

445
00:23:30,430 --> 00:23:32,220
En die spel eindig in 'n das.

446
00:23:32,220 --> 00:23:35,030
Maar dit het 'n redelike
spel teen jou, reg?

447
00:23:35,030 --> 00:23:36,956
Alle reg, baie dankie, Gorav.

448
00:23:36,956 --> 00:23:40,860
>> [Applous]

449
00:23:40,860 --> 00:23:44,723
>> Alle reg, Layla, ons gaan
die spel op jou hier.

450
00:23:44,723 --> 00:23:46,940
>> GEHOOR: O, groot.

451
00:23:46,940 --> 00:23:49,950
>> Spreker: Ons gaan om te gee
jy vier deur vier tic-tac-toe.

452
00:23:49,950 --> 00:23:54,760
Nou, in vier deur vier, jy het om te wen
met vier in 'n ry, nie drie in 'n ry.

453
00:23:54,760 --> 00:23:56,135
En dit is alles joune.

454
00:23:56,135 --> 00:24:02,180

455
00:24:02,180 --> 00:24:04,420
So Layla het D1.

456
00:24:04,420 --> 00:24:11,730
Ons is nou gaan volg
ons rekenaar speler hier.

457
00:24:11,730 --> 00:24:16,910
Drie deur drie tic-tac-toe is die soort
ding dit is maklik vir ons almal.

458
00:24:16,910 --> 00:24:21,960
Maar dit is nog steeds lekker om te sien die
rekenaar speler om slim beweeg.

459
00:24:21,960 --> 00:24:23,725
Vier deur vier kry om
'n bietjie moeiliker.

460
00:24:23,725 --> 00:24:42,960

461
00:24:42,960 --> 00:24:44,230
>> Mooi gedoen.

462
00:24:44,230 --> 00:24:46,210
Alle reg, sodat Layla se afgewerk.

463
00:24:46,210 --> 00:24:48,270
O ja, en ons moes daar geëindig.

464
00:24:48,270 --> 00:24:51,870
Maar laat ons nie een meer hier.

465
00:24:51,870 --> 00:24:53,480
So Layla, dankie.

466
00:24:53,480 --> 00:24:55,112
Mooi gedoen.

467
00:24:55,112 --> 00:24:57,517
>> [Applous]

468
00:24:57,517 --> 00:25:00,410

469
00:25:00,410 --> 00:25:04,750
>> So ons tic-tac-toe speler gaan
deur en vind plekke,

470
00:25:04,750 --> 00:25:07,040
los hulle met behulp van die minimaks.

471
00:25:07,040 --> 00:25:08,990
En ek het 'n diepte omgewing
op daardie sodat dit

472
00:25:08,990 --> 00:25:11,010
sou nie te vinnig hardloop,
wat is waarskynlik die rede waarom

473
00:25:11,010 --> 00:25:16,790
Layla was om voort te gaan in staat mooi
soos sy gedoen het, en het baie goed.

474
00:25:16,790 --> 00:25:20,450
Maar hierdie stelsels wat net
gaan deur en brute krag

475
00:25:20,450 --> 00:25:23,870
gaan dieper, en dieper en dieper,
en hou die vind van die oplossing

476
00:25:23,870 --> 00:25:29,890
wat hulle nodig het, diegene soorte stelsels
is baie suksesvol by hierdie, wel,

477
00:25:29,890 --> 00:25:32,700
standaard bordspeletjies.

478
00:25:32,700 --> 00:25:37,060
>> En in die feit, as ons kyk na 'n
drie deur drie tic-tac-toe spel,

479
00:25:37,060 --> 00:25:40,040
Dit is basies 'n probleem opgelos.

480
00:25:40,040 --> 00:25:45,430
En dit is 'n wonderlike diagram
van Randall Munroe op Kletskerk,

481
00:25:45,430 --> 00:25:52,130
vertoning wat beweeg jy moet
neem, gegewe beweeg jou teenstander.

482
00:25:52,130 --> 00:25:56,420
Dit is iets wat ons kon
maklik voor die tyd te gee.

483
00:25:56,420 --> 00:26:00,180
Maar wat gebeur as ons meer
komplekse speletjies, meer ingewikkelde speletjies,

484
00:26:00,180 --> 00:26:05,690
waar daar groter borde meer
moontlikhede, dieper strategie?

485
00:26:05,690 --> 00:26:09,660
>> Dit blyk dat hierdie
brute krag soek steeds

486
00:26:09,660 --> 00:26:14,150
doen redelik goed nie, behalwe
wanneer jy die punt

487
00:26:14,150 --> 00:26:19,230
waar daardie boom is so groot
dat jy nie kan verteenwoordig dit alles.

488
00:26:19,230 --> 00:26:22,370

489
00:26:22,370 --> 00:26:28,280
Wanneer jy die hele boom nie kan bereken,
wanneer jy nie vorentoe en druk kan gaan

490
00:26:28,280 --> 00:26:32,204
jouself tot op die punt waar jy het
gekry die hele boom in die geheue,

491
00:26:32,204 --> 00:26:34,370
of jy kan dit kry
in die geheue en dit sal net

492
00:26:34,370 --> 00:26:39,200
neem jou te lank om deur te soek
dit, jy het om iets slimmer te doen.

493
00:26:39,200 --> 00:26:42,620

494
00:26:42,620 --> 00:26:46,450
>> Om dit te kan doen, moet jy
het twee dinge te doen.

495
00:26:46,450 --> 00:26:49,030
Eerstens, jy het om 'n paar te vind
manier van die beperking van jou diepte.

496
00:26:49,030 --> 00:26:50,370
Wel, dit is OK.

497
00:26:50,370 --> 00:26:55,740
Ons kan 'n paar mooi, absolute minimum te vind
en sê, jy kan net gaan so diep.

498
00:26:55,740 --> 00:27:00,890
Maar wanneer jy dit doen, dit beteken dat jy
het hierdie gedeeltelik onvoltooid planke.

499
00:27:00,890 --> 00:27:04,770
En jy het om van te kies, doen ek graag
hierdie gedeeltelik onvoltooid raad,

500
00:27:04,770 --> 00:27:08,600
of hierdie gedeeltelik onvoltooid raad?

501
00:27:08,600 --> 00:27:11,910
>> En op ons vier deur
vier tic-tac-toe spel,

502
00:27:11,910 --> 00:27:15,240
ons rekenaar speler het af
aan die onderkant en dit het gesê,

503
00:27:15,240 --> 00:27:16,800
Ek het twee verskillende planke.

504
00:27:16,800 --> 00:27:17,940
Nie een is 'n wen.

505
00:27:17,940 --> 00:27:19,120
Nie een is 'n verlies.

506
00:27:19,120 --> 00:27:22,070
Nie een is 'n das.

507
00:27:22,070 --> 00:27:24,100
Hoe kies ek tussen hulle?

508
00:27:24,100 --> 00:27:26,200
En dit het nie 'n het
slim manier om dit te doen.

509
00:27:26,200 --> 00:27:28,910

510
00:27:28,910 --> 00:27:32,850
>> Ons sien hierdie soort
evaluering gebeur al die tyd

511
00:27:32,850 --> 00:27:35,290
as ons in meer komplekse speletjies.

512
00:27:35,290 --> 00:27:37,600
Skaak is 'n goeie voorbeeld.

513
00:27:37,600 --> 00:27:41,550
In skaak, ons het, in die eerste
van alles, 'n groter bord.

514
00:27:41,550 --> 00:27:43,370
Ons het baie meer stukke.

515
00:27:43,370 --> 00:27:47,930
En die plasing van hierdie stukke
en die manier waarop hierdie stukke te beweeg

516
00:27:47,930 --> 00:27:50,370
is krities belangrik.

517
00:27:50,370 --> 00:27:53,700
So as ek wil minimaks gebruik,
Ek moet in staat wees om te spesifiseer

518
00:27:53,700 --> 00:27:58,240
en sê hierdie bord waar
niemand het gewen of verloor nie,

519
00:27:58,240 --> 00:28:04,310
is een of ander manier beter as dit ander
raad, waar niemand het gewen of verloor.

520
00:28:04,310 --> 00:28:06,740
>> Om dit te doen, kan ek doen
dinge soos ek dalk net

521
00:28:06,740 --> 00:28:10,787
tel hoeveel stukke moet ek
en hoeveel stukke het jy?

522
00:28:10,787 --> 00:28:12,870
Of ek dalk anders te gee
stukke verskillende punte.

523
00:28:12,870 --> 00:28:14,420
My koningin is 20 punte werd.

524
00:28:14,420 --> 00:28:16,500
Jou pion is een punt werd.

525
00:28:16,500 --> 00:28:18,920
Wie het meer punte totaal?

526
00:28:18,920 --> 00:28:22,300
Of ek kan oorweeg dinge soos,
wie het die beter raad posisie?

527
00:28:22,300 --> 00:28:26,820
Wie se beurt is dit langs,
enigiets wat ek kan

528
00:28:26,820 --> 00:28:31,220
doen om meer akkuraat te evalueer
watter van hierdie moontlikhede

529
00:28:31,220 --> 00:28:34,660
is beter sonder
uitvoerig oorweeg

530
00:28:34,660 --> 00:28:36,565
elke beweging wat daarna kon kom.

531
00:28:36,565 --> 00:28:39,740

532
00:28:39,740 --> 00:28:45,130
>> Nou dat die werk te maak,
een van die dinge wat

533
00:28:45,130 --> 00:28:48,680
gaan regtig belangrik geword
vir ons is nie net beweeg reguit

534
00:28:48,680 --> 00:28:53,720
af na 'n bepaalde diepte
limiet, maar in staat is om te sê,

535
00:28:53,720 --> 00:28:59,380
een van hierdie idees wat ek
het, is so erg dat dit

536
00:28:59,380 --> 00:29:02,280
nie die moeite werd oorweging
al die moontlike maniere

537
00:29:02,280 --> 00:29:06,680
dat dinge kan gaan van kwaad na erger.

538
00:29:06,680 --> 00:29:12,760
Om dit te doen, sal ons voeg in minimaks
'n beginsel genoem Alfa-beta.

539
00:29:12,760 --> 00:29:16,340
En alfa-beta sê,
as jy 'n slegte idee nie,

540
00:29:16,340 --> 00:29:22,840
mors nie jou tyd probeer om
uit te vind presies hoe sleg dit is.

541
00:29:22,840 --> 00:29:24,990
>> So hier is wat ons gaan doen.

542
00:29:24,990 --> 00:29:28,620
Ons gaan dieselfde doen
beginsels wat ons voorheen gehad het,

543
00:29:28,620 --> 00:29:32,200
dieselfde minimaks tipe
soek nie, net ons

544
00:29:32,200 --> 00:29:37,570
gaan hou, nie net van die
werklike waardes wat ons het, maar ons sal

545
00:29:37,570 --> 00:29:41,440
hou van die beste moontlike
waarde wat ek kon kry,

546
00:29:41,440 --> 00:29:45,700
en die ergste moontlike
uitkoms Ek kon hê.

547
00:29:45,700 --> 00:29:50,470
En enige tyd die ergste moontlike
ding is op soek waarskynlik,

548
00:29:50,470 --> 00:29:52,694
Ek sal daardie deel van die boom te laat vaar.

549
00:29:52,694 --> 00:29:54,610
En Ek sal nie eens die moeite
kyk na dit nie.

550
00:29:54,610 --> 00:29:57,680

551
00:29:57,680 --> 00:30:02,600
>> Alle reg, sodat dink dat ons begin
met hierdie presies dieselfde spel boom.

552
00:30:02,600 --> 00:30:05,200
En nou is ons gaan om te gaan
weer af, al die pad af

553
00:30:05,200 --> 00:30:07,200
dat die onderste linkerhoek.

554
00:30:07,200 --> 00:30:11,180
En in dié onderste linkerhoek ons
kyk en ons evalueer hierdie bord.

555
00:30:11,180 --> 00:30:15,700
Miskien is dit 'n vier deur vier tic-tac-toe
direksie, of miskien is dit 'n skaakbord.

556
00:30:15,700 --> 00:30:18,620
Maar ons kyk na dit, en ons evalueer
dit, en ons kry 'n waarde van agt.

557
00:30:18,620 --> 00:30:22,290

558
00:30:22,290 --> 00:30:28,030
>> Op daardie punt, ons weet dat
ons gaan ten minste kry

559
00:30:28,030 --> 00:30:32,380
agt punte uit hierdie bodem besluit.

560
00:30:32,380 --> 00:30:36,620
Dit maak nie saak wat die ander
twee is, sewe en dat twee.

561
00:30:36,620 --> 00:30:38,580
Hulle kon enige waardes
hulle wou wees.

562
00:30:38,580 --> 00:30:41,279
Ons gaan op om te kry
Minstens agt punte.

563
00:30:41,279 --> 00:30:43,070
Alle reg, maar ons kon
gaan voort en te keur.

564
00:30:43,070 --> 00:30:45,080
Miskien een van hulle is beter as agt.

565
00:30:45,080 --> 00:30:46,000
>> Ons kyk na die sewe.

566
00:30:46,000 --> 00:30:46,910
Is dit beter as agt?

567
00:30:46,910 --> 00:30:48,680
Nee, dit beteken nie verander
ons mening glad nie.

568
00:30:48,680 --> 00:30:49,460
Ons kyk na die twee.

569
00:30:49,460 --> 00:30:50,543
Is dit beter as agt?

570
00:30:50,543 --> 00:30:52,580
Nee, dit beteken nie verander
ons mening glad nie.

571
00:30:52,580 --> 00:30:55,480
So nou weet ons ons het uitgeput
al die moontlikhede is daar.

572
00:30:55,480 --> 00:30:58,330
Ons gaan nie om te kry
niks beter as agt.

573
00:30:58,330 --> 00:31:01,310
Ons gaan presies agt kry.

574
00:31:01,310 --> 00:31:03,825
>> En so het ons verander en node
sê, dit is nou 'n sekerheid.

575
00:31:03,825 --> 00:31:07,010

576
00:31:07,010 --> 00:31:10,270
Ons gaan op een vlak bo dit.

577
00:31:10,270 --> 00:31:13,820
En nou weet ons iets
oor daardie minimalisering vlak.

578
00:31:13,820 --> 00:31:18,560
Ons weet dat ons nooit gaan kry
meer as agt punte as ons gaan af

579
00:31:18,560 --> 00:31:20,910
daardie rigting.

580
00:31:20,910 --> 00:31:22,980
Want selfs as diegene
ander twee takke draai uit

581
00:31:22,980 --> 00:31:26,170
te wees en die moeite werd fantastiese
duisende punte elk,

582
00:31:26,170 --> 00:31:31,666
ons opponent sal ons die
minimum, en gee ons die agt.

583
00:31:31,666 --> 00:31:32,790
Alle reg, goed, laat ons sien.

584
00:31:32,790 --> 00:31:35,190
Ons sal aanhou om af te gaan dat die pad.

585
00:31:35,190 --> 00:31:38,490
Ons gaan af na wat middel aan die linkerkant.

586
00:31:38,490 --> 00:31:40,560
Ons kyk af en sien ons daar is 'n nege.

587
00:31:40,560 --> 00:31:45,590
Ons weet dat ons gaan om te kry
minstens nege punte deur te gaan af

588
00:31:45,590 --> 00:31:47,720
dat middeweg.

589
00:31:47,720 --> 00:31:52,110
En op hierdie punt, kan ons net breek.

590
00:31:52,110 --> 00:31:56,910
En ons kan sê, kyk, ek
weet in die vlak bo,

591
00:31:56,910 --> 00:32:01,160
Ek gaan kry nie meer as agt
wys deur af te gaan hierdie rigting.

592
00:32:01,160 --> 00:32:05,670
Maar as ek het in die middel
pad in plaas van die linker pad,

593
00:32:05,670 --> 00:32:08,980
Ek sou kry minstens nege punte.

594
00:32:08,980 --> 00:32:13,590
>> My teenstander is nooit gaan
laat my gaan af dat middeweg.

595
00:32:13,590 --> 00:32:14,650
Hulle kry om van te kies.

596
00:32:14,650 --> 00:32:18,140
En hulle gaan na die kies
pad na die links na die agt,

597
00:32:18,140 --> 00:32:23,650
eerder as in die middel tot
Wat is minstens nege punte.

598
00:32:23,650 --> 00:32:25,334
So op daardie punt, sal ek ophou.

599
00:32:25,334 --> 00:32:26,500
En ek sal sê, jy weet wat?

600
00:32:26,500 --> 00:32:29,990
Ek het nie nodig om enige kyk
meer in daardie rigting.

601
00:32:29,990 --> 00:32:32,270
Omdat ek nooit gaan om daar te kom.

602
00:32:32,270 --> 00:32:36,660
>> Ek kan spring oor daardie een,
en ek kan slaan oor wat ses

603
00:32:36,660 --> 00:32:39,720
want dit is nooit gaan gebeur nie.

604
00:32:39,720 --> 00:32:42,470
So ek sal afgaan en ek sal
oorweeg die volgende moontlikheid.

605
00:32:42,470 --> 00:32:44,830
Ek gaan daar en ek sê, ek sien 'n twee.

606
00:32:44,830 --> 00:32:47,125
Ek weet as ek tot hier, ek is
gaan ten minste twee kry.

607
00:32:47,125 --> 00:32:49,810

608
00:32:49,810 --> 00:32:50,470
OK.

609
00:32:50,470 --> 00:32:51,520
Ek hou.

610
00:32:51,520 --> 00:32:52,440
Ek sien 'n vier.

611
00:32:52,440 --> 00:32:54,920
Ek weet ek gaan ten minste vier te kry.

612
00:32:54,920 --> 00:32:57,200
Daar is nog 'n baie tussen
vier en agt, al is.

613
00:32:57,200 --> 00:32:58,454
So ek gaan hou.

614
00:32:58,454 --> 00:32:59,870
Ek kyk af en ek sien daar is een.

615
00:32:59,870 --> 00:33:01,614
Alle reg, ek weet as
Ek gaan op hierdie pad,

616
00:33:01,614 --> 00:33:03,280
Ek gaan in staat wees om die vier te kies.

617
00:33:03,280 --> 00:33:06,540

618
00:33:06,540 --> 00:33:08,980
Wat my teenstander gaan doen?

619
00:33:08,980 --> 00:33:12,310
Tussen iets wat my gee
agt, iets wat my gee vier

620
00:33:12,310 --> 00:33:14,730
en iets wat
gee my minstens nege,

621
00:33:14,730 --> 00:33:17,550
Wel, hy gaan my die vier gee.

622
00:33:17,550 --> 00:33:20,110
En ek weet nou by die
heel boonste, ek gaan

623
00:33:20,110 --> 00:33:23,145
in staat wees om ten minste kry
vier punte uit hierdie wedstryd.

624
00:33:23,145 --> 00:33:27,030

625
00:33:27,030 --> 00:33:30,900
>> Die hele idee van die alfa-beta
is om dele so afgesny die boom

626
00:33:30,900 --> 00:33:32,530
dat ek nie meer te kyk na hulle.

627
00:33:32,530 --> 00:33:35,964
Maar dit lyk nog steeds soos ek was
op soek na 'n baie van die boom.

628
00:33:35,964 --> 00:33:36,880
Kom ons hou om af te gaan.

629
00:33:36,880 --> 00:33:38,305
Ons sal nou gaan in die volgende een.

630
00:33:38,305 --> 00:33:39,680
Af aan die onderkant, vind ek 'n een.

631
00:33:39,680 --> 00:33:41,030
Ek weet ek gaan ten minste een te kry.

632
00:33:41,030 --> 00:33:41,690
Ek hou soek.

633
00:33:41,690 --> 00:33:42,625
>> Ek vind 'n drie.

634
00:33:42,625 --> 00:33:44,250
Ek weet ek gaan ten minste drie kry.

635
00:33:44,250 --> 00:33:44,840
Ek hou.

636
00:33:44,840 --> 00:33:45,660
Ek vind 'n vyf.

637
00:33:45,660 --> 00:33:49,760
Ek weet ek gaan vyf kry
as ek in daardie pad.

638
00:33:49,760 --> 00:33:52,580
En ek weet ook dan
dat my opponent, as ek

639
00:33:52,580 --> 00:33:55,510
kies die middel van
die drie groot keuses,

640
00:33:55,510 --> 00:34:01,440
hy gaan om my te gee
iets wat vyf of minder.

641
00:34:01,440 --> 00:34:02,150
>> OK.

642
00:34:02,150 --> 00:34:03,400
Ek kan hou gaan daar.

643
00:34:03,400 --> 00:34:06,470
Ek kan kyk af en ek
kan sê, wat gaan ek

644
00:34:06,470 --> 00:34:08,239
te kry as ek gaan in die middel pad?

645
00:34:08,239 --> 00:34:09,909
Ek gaan om daar te kom, goed, drie.

646
00:34:09,909 --> 00:34:12,080
Ek gaan om iets te kry
dit is ten minste drie.

647
00:34:12,080 --> 00:34:16,030
Daar is nog dinge tussen
drie en vyf, so ek hou soek.

648
00:34:16,030 --> 00:34:20,203
O, 'n nege, sal ek beslis
neem dat meer as 'n drie.

649
00:34:20,203 --> 00:34:22,744
Ek gaan minstens nege kry
as ek neerdaal dat middeweg.

650
00:34:22,744 --> 00:34:25,530

651
00:34:25,530 --> 00:34:31,010
>> Stop nou my opponent en sê,
kyk, daar is geen punt nie.

652
00:34:31,010 --> 00:34:33,669
Ek weet dat my
minimalisering teenstander, hy is

653
00:34:33,669 --> 00:34:36,210
gaan my die ding wat ons gee
minder as of gelyk aan vyf

654
00:34:36,210 --> 00:34:39,030
eerder as die ding wat
groter as of gelyk aan nege.

655
00:34:39,030 --> 00:34:39,530
Ek stop.

656
00:34:39,530 --> 00:34:40,779
Ek het nie meer kyk na dit.

657
00:34:40,779 --> 00:34:43,280
Ek hou.

658
00:34:43,280 --> 00:34:44,850
>> Ek kyk af op hierdie een.

659
00:34:44,850 --> 00:34:46,370
Af na die onderkant, vind ek 'n ses.

660
00:34:46,370 --> 00:34:50,040
Ek weet ek gaan minstens ses kry.

661
00:34:50,040 --> 00:34:53,130
En wat kan ek doen?

662
00:34:53,130 --> 00:34:54,877
Ek kan stop.

663
00:34:54,877 --> 00:34:57,460
Want daar is 'n keuse tussen
iets wat ten minste ses

664
00:34:57,460 --> 00:34:59,250
en iets wat
minder as vyf, hy is

665
00:34:59,250 --> 00:35:02,570
gaan my die ding gee
dit is minder as vyf.

666
00:35:02,570 --> 00:35:04,779
En nou, ek weet ek gaan
presies te kry dat die keuse.

667
00:35:04,779 --> 00:35:06,195
Ek gaan dat vyf keuse te kry.

668
00:35:06,195 --> 00:35:08,980

669
00:35:08,980 --> 00:35:10,010
>> Ek gaan terug na die top.

670
00:35:10,010 --> 00:35:11,450
Wat gaan ek
kies tussen iets

671
00:35:11,450 --> 00:35:14,449
dit is groter as of gelyk aan vier,
of iets wat gelyk aan vyf?

672
00:35:14,449 --> 00:35:17,140
Ek gaan iets te neem
dit is ten minste vyf.

673
00:35:17,140 --> 00:35:20,490
Ek gaan in die laaste pad, al
die pad af na die bodem.

674
00:35:20,490 --> 00:35:21,260
Daar is 'n een.

675
00:35:21,260 --> 00:35:23,410
OK, ten minste gaan ek een punt.

676
00:35:23,410 --> 00:35:24,427
Ek hou.

677
00:35:24,427 --> 00:35:25,760
Twee, o, dit is beter as een.

678
00:35:25,760 --> 00:35:27,100
Ek gaan ten minste twee kry.

679
00:35:27,100 --> 00:35:28,610
Ek vind 'n drie.

680
00:35:28,610 --> 00:35:31,450
Ek weet ek gaan drie kry.

681
00:35:31,450 --> 00:35:34,690
>> En die punt bo,
my teenstander gaan

682
00:35:34,690 --> 00:35:38,540
my iets wat om te gee
minder as of gelyk aan drie.

683
00:35:38,540 --> 00:35:40,940
En nou kan ek stop.

684
00:35:40,940 --> 00:35:46,290
Want in die keuse tussen my word
in staat wees om 'n vyf en my opponent te kry

685
00:35:46,290 --> 00:35:52,290
gee my iets minder as drie,
Ek is altyd gaan dat vyf neem.

686
00:35:52,290 --> 00:35:56,810
So ek weet nie wat evalueer
onderste deel van die boom nie.

687
00:35:56,810 --> 00:35:59,470
>> Nou, kan dit lyk minderjarige.

688
00:35:59,470 --> 00:36:03,630
Maar wanneer klein stukkies van rekenkunde,
groter as en minder as,

689
00:36:03,630 --> 00:36:10,640
hele dele van weg kan sny
hierdie eksponensieel groeiende boom,

690
00:36:10,640 --> 00:36:14,280
wat lei tot 'n groot
bedrag van besparings, spaar

691
00:36:14,280 --> 00:36:17,630
wat groot genoeg dat ek is
kan begin speel mededingend

692
00:36:17,630 --> 00:36:21,330
op meer komplekse speletjies.

693
00:36:21,330 --> 00:36:27,030
>> Alle reg, as ons kyk na die grootte
en kompleksiteit van verskillende speletjies,

694
00:36:27,030 --> 00:36:29,470
tic-tac-toe was ons maklike voorbeeld.

695
00:36:29,470 --> 00:36:32,150
Ons het 'n klein raad, drie het deur drie.

696
00:36:32,150 --> 00:36:36,030
Ons kry, op die meeste, 'n gemiddeld van
omtrent vier verskillende keuses

697
00:36:36,030 --> 00:36:38,440
as ons gaan deur die spel.

698
00:36:38,440 --> 00:36:42,720
Ons het êrens rondom 10 tot die
vyfde moontlik verskillende blare.

699
00:36:42,720 --> 00:36:45,200
En die bou van 'n tic-tac-toe
speler, goed, ons het net dit gedoen het.

700
00:36:45,200 --> 00:36:47,460
Dit is maklik.

701
00:36:47,460 --> 00:36:49,890
>> As ons gaan op na iets meer
kompleks, soos Connect Four.

702
00:36:49,890 --> 00:36:53,170
Onthou jy hierdie spel waar
jy die klein tekens daling in?

703
00:36:53,170 --> 00:36:58,490
Dit is 'n ses met sewe raad,
nie veel groter, nog

704
00:36:58,490 --> 00:37:00,770
het ongeveer dieselfde vertakking
faktor soos tic-tac-toe.

705
00:37:00,770 --> 00:37:05,410
Ek het omtrent vier keuses
waar ek dinge in kan sit.

706
00:37:05,410 --> 00:37:10,760
Maar nou, ek het 'n baie meer
lei, 10 tot die 21ste krag.

707
00:37:10,760 --> 00:37:14,440
Dit is iets wat maklik
genoeg dat ons los dit dadelik.

708
00:37:14,440 --> 00:37:17,560
>> Checkers, hoe meer jy complex--
het 'n agt deur agt raad.

709
00:37:17,560 --> 00:37:20,570
Jy is net op die helfte van
hulle te eniger tyd, al is.

710
00:37:20,570 --> 00:37:24,930
Jy het 'n vertakking het
faktor wat gaan oor 2,8.

711
00:37:24,930 --> 00:37:28,160
Wel, ons het 'n paar gekry
beweeg jy kan neem.

712
00:37:28,160 --> 00:37:33,870
Jy het ongeveer 10 het die 31 blare,
groter en groter, en groter ruimtes.

713
00:37:33,870 --> 00:37:37,340
Soos ek het om deur te soek
diegene groter en groter ruimtes,

714
00:37:37,340 --> 00:37:42,220
Dis toe dat dinge soos die alfa-beta en
in staat hele takke weg te sny

715
00:37:42,220 --> 00:37:44,420
word noodsaaklik.

716
00:37:44,420 --> 00:37:47,440
>> Nou, checkers was maklik genoeg in 1992.

717
00:37:47,440 --> 00:37:51,400
'N Rekenaar program genaamd
Chinook klop die wêreld checkers

718
00:37:51,400 --> 00:37:53,590
kampioen, Marion Tinsley.

719
00:37:53,590 --> 00:37:57,260
En sedertdien geen
menslike meester speler het

720
00:37:57,260 --> 00:38:02,290
in staat was om die beste te klop
computational stelsels.

721
00:38:02,290 --> 00:38:06,570
As ons kyk na iets soos skaak, nou
weer, ons het 'n agt deur agt raad.

722
00:38:06,570 --> 00:38:09,870
Maar ons het baie meer kompleks
stukke, baie meer kompleks bewegings.

723
00:38:09,870 --> 00:38:14,610
Ons het 'n vertakking faktor van ongeveer
35, 35 moontlike skuiwe op die gemiddelde

724
00:38:14,610 --> 00:38:20,030
dat ek, en 'n staat kan neem
ruimte, 'n aantal van die blare

725
00:38:20,030 --> 00:38:28,950
dit is gegroei tot 10 123 aan die krag,
enorme getalle moontlikhede.

726
00:38:28,950 --> 00:38:35,570
>> Selfs nog, moderne verwerkers
in staat is om dit suksesvol te doen.

727
00:38:35,570 --> 00:38:43,900
In 1995 en daarna in 1997, 'n rekenaar
program genaamd Deep Blue gebou deur IBM

728
00:38:43,900 --> 00:38:49,601
wat gehardloop op 'n reuse supercomputer
die huidige wêreldkampioen klop,

729
00:38:49,601 --> 00:38:50,225
Garry Kasparov.

730
00:38:50,225 --> 00:38:54,000

731
00:38:54,000 --> 00:38:56,650
Dit was 'n keerpunt.

732
00:38:56,650 --> 00:39:00,620
Vandag, egter dat dieselfde verwerking
krag sit op my MacBook.

733
00:39:00,620 --> 00:39:04,180

734
00:39:04,180 --> 00:39:06,440
>> Verwerking spoed hou
kry vinniger en vinniger.

735
00:39:06,440 --> 00:39:09,500
Ons kan meer en meer te evalueer
borde vinniger en vinniger.

736
00:39:09,500 --> 00:39:14,550
Maar meer belangrik, ons het 'n beter
evaluering funksies en beter snoei

737
00:39:14,550 --> 00:39:15,460
metodes.

738
00:39:15,460 --> 00:39:19,560
Sodat ons kan soek op die
ruimte meer kompleks.

739
00:39:19,560 --> 00:39:22,350
Die grootste van die raad
speletjies wat ons kan dink,

740
00:39:22,350 --> 00:39:26,310
iets soos Go dis
'n 19 met 19 direksie,

741
00:39:26,310 --> 00:39:32,490
nou skielik, ons is verby die punt
waar computational stelsels kan wen.

742
00:39:32,490 --> 00:39:34,530
Daar is geen computational
stelsel daar buite

743
00:39:34,530 --> 00:39:38,880
wat kan klop 'n professionele Go speler.

744
00:39:38,880 --> 00:39:45,000
Die beste stelsels vandag rang dit oor
die soort van goeie amateur vlak.

745
00:39:45,000 --> 00:39:49,285
So is daar steeds 'n bietjie uit te
daar wat jy kan nie nog kry.

746
00:39:49,285 --> 00:39:51,840

747
00:39:51,840 --> 00:39:55,360
>> Alle reg, hierdie
tradisionele bordspeletjies,

748
00:39:55,360 --> 00:39:58,560
hierdie soort stelsels waar ons
bou die minimaks, of dit het

749
00:39:58,560 --> 00:40:06,300
alfa-beta of nie, hierdie algoritmes werk
want daar is sekere beperkings.

750
00:40:06,300 --> 00:40:08,520
Ons het perfekte inligting
oor die hele wêreld.

751
00:40:08,520 --> 00:40:11,690
Ons weet waar al die stukke is.

752
00:40:11,690 --> 00:40:13,570
Die wêreld is staties nie.

753
00:40:13,570 --> 00:40:16,220
Niemand kry om die beweeg
stukke rondom terwyl ek

754
00:40:16,220 --> 00:40:20,640
daar sit dink, neem my beurt.

755
00:40:20,640 --> 00:40:23,140
Daar is 'n aksie ruimte wat diskrete.

756
00:40:23,140 --> 00:40:26,900
Ek kan my pion hier sit,
of ek kan my pion hier sit.

757
00:40:26,900 --> 00:40:30,520
Ek is nie toegelaat om my pion op te sit
die lyn tussen die twee vierkante.

758
00:40:30,520 --> 00:40:34,430

759
00:40:34,430 --> 00:40:36,520
>> En ten slotte, die optrede
is deterministiese.

760
00:40:36,520 --> 00:40:39,790
Ek weet dat as ek sê,
rook Knight drie

761
00:40:39,790 --> 00:40:44,660
my rook gaan eindig by Knight
drie, solank dit 'n geldige beweeg.

762
00:40:44,660 --> 00:40:47,830
Daar is geen onsekerheid oor dat.

763
00:40:47,830 --> 00:40:52,490
Nou, as ek gaan om meer
verskillende soorte speletjies,

764
00:40:52,490 --> 00:40:55,960
ons het na daardie aannames te breek.

765
00:40:55,960 --> 00:41:00,020
>> Wat as ek gaan om iets
soos klassieke video speletjies?

766
00:41:00,020 --> 00:41:04,180
Hier is 'n seleksie van die video
games van die Atari 2600.

767
00:41:04,180 --> 00:41:05,180
Wat moet ek daar?

768
00:41:05,180 --> 00:41:08,440
Ek het Frogger, Space het
Indringers, valkuil, en Pac-Man.

769
00:41:08,440 --> 00:41:11,290

770
00:41:11,290 --> 00:41:14,840
Watter soorte omgewings
moet ek nou hier?

771
00:41:14,840 --> 00:41:16,900
Watter van hierdie aannames
moet ek breek?

772
00:41:16,900 --> 00:41:19,410

773
00:41:19,410 --> 00:41:21,570
>> Wel, dit hang af van die spel.

774
00:41:21,570 --> 00:41:28,170
Ek kon skaak speel op die 2600, en
dit sou wees, net soos dit was voor.

775
00:41:28,170 --> 00:41:33,020
Vir die meeste van hierdie stelsels, is daar
volledige kennis oor die wêreld.

776
00:41:33,020 --> 00:41:36,300
Daar is heeltemal
deterministiese aksies.

777
00:41:36,300 --> 00:41:38,330
Maar gewoonlik, die wêreld se
nie meer staties.

778
00:41:38,330 --> 00:41:41,970
Dit is, terwyl ek daar is sit
wag, is iets wat beweeg.

779
00:41:41,970 --> 00:41:44,320
Die spoke kom om my te kry.

780
00:41:44,320 --> 00:41:46,570
Die skerpioen volg my onder.

781
00:41:46,570 --> 00:41:48,880
Die ruimte indringers is
kom nader en nader.

782
00:41:48,880 --> 00:41:54,020

783
00:41:54,020 --> 00:41:55,510
Hoe goed kan ons doen teen hierdie?

784
00:41:55,510 --> 00:41:58,640

785
00:41:58,640 --> 00:42:02,790
>> 'N Paar jaar gelede, Google
het 'n projek genaamd

786
00:42:02,790 --> 00:42:12,030
DeepMind, waar hulle opgelei 'n rekenaar
program om Atari speel 2600 speletjies.

787
00:42:12,030 --> 00:42:16,120
En as jy dink dit is nie ernstig nie
besigheid, die resultate van hul studie

788
00:42:16,120 --> 00:42:19,920
gepubliseer in Nature, so
net oor so 'n goeie publikasie

789
00:42:19,920 --> 00:42:22,500
as wat jy moontlik kan kry.

790
00:42:22,500 --> 00:42:24,340
En hier is hoe goed hulle presteer.

791
00:42:24,340 --> 00:42:29,220
>> Hulle het 'n algoritme wat sit
en kyk net die skerm insette.

792
00:42:29,220 --> 00:42:34,080
Dit het geen instruksies hoegenaamd
oor die reëls van die spel.

793
00:42:34,080 --> 00:42:42,610
En dit was veronderstel om uit te vind,
grond sy telling, hoe goed dit was om te doen.

794
00:42:42,610 --> 00:42:46,560
Dit was 'n stelsel wat iets gebruik
genoem versterking leer.

795
00:42:46,560 --> 00:42:48,380
Dit is, dit lyk op sy telling.

796
00:42:48,380 --> 00:42:51,620
En as dit 'n goeie telling, het hy gesê,
Ek moet daardie dinge te onthou.

797
00:42:51,620 --> 00:42:53,310
En ek moet die weer te doen.

798
00:42:53,310 --> 00:42:56,450
En as dit het 'n slegte telling, het hy gesê,
Ek moet nie die dinge weer doen.

799
00:42:56,450 --> 00:42:59,750

800
00:42:59,750 --> 00:43:03,430
>> Dit is die prestasie
van diegene wat opgelei stelsels

801
00:43:03,430 --> 00:43:07,490
toegelaat word om te speel vir 'n
paar uur op elke wedstryd,

802
00:43:07,490 --> 00:43:12,490
vergeleke teen professionele gamers.

803
00:43:12,490 --> 00:43:19,670
So vir al die speletjies wat
tot by die linkerkant van die lyn,

804
00:43:19,670 --> 00:43:25,920
hierdie self-opgeleide rekenaarprogram
beter as die professionele spelers.

805
00:43:25,920 --> 00:43:29,690
En vir alles op die
reg, die professionele spelers

806
00:43:29,690 --> 00:43:30,920
was nog steeds die beste.

807
00:43:30,920 --> 00:43:34,040

808
00:43:34,040 --> 00:43:36,850
Vir iets wat geweet
niks oor die reëls, wat

809
00:43:36,850 --> 00:43:43,020
niks geweet van die struktuur van die
speletjies, dit is indrukwekkende vertoning.

810
00:43:43,020 --> 00:43:45,660
En dit is wat ons in staat om te doen vandag.

811
00:43:45,660 --> 00:43:50,239
>> OK, jy sê, maar as ons
dink oor AI in games,

812
00:43:50,239 --> 00:43:52,530
gewoonlik ons ​​dink oor die
dinge wat ons kan eintlik

813
00:43:52,530 --> 00:43:54,180
sit en speel teen.

814
00:43:54,180 --> 00:43:58,760
As ek gaan sit en ek speel
Craft, of ek speel Free sif,

815
00:43:58,760 --> 00:44:01,870
die rekenaar teenstander is die
persoon wat die beheer van die Zerg,

816
00:44:01,870 --> 00:44:06,770
of die beheer van die ander beskawing.

817
00:44:06,770 --> 00:44:11,920
Hoe daardie spelers
eintlik hul bewegings te vind?

818
00:44:11,920 --> 00:44:18,810
>> Wel, is hierdie speletjies gestruktureer
baie dieselfde manier as ons bordspeletjies,

819
00:44:18,810 --> 00:44:22,250
hierdie speletjies wat ons sal
gesamentlik noem vier X games,

820
00:44:22,250 --> 00:44:26,040
verken, expand-- vergeet van die kinders.

821
00:44:26,040 --> 00:44:26,980
Wat is hulle?

822
00:44:26,980 --> 00:44:32,150
Verken, uit te brei, en blus,
Ek dink is die laaste een.

823
00:44:32,150 --> 00:44:36,060
Maar hulle is basies
eksplorasie en verower speletjies.

824
00:44:36,060 --> 00:44:41,020
Tipies, die rekenaar teenstander
daar beperkte inligting.

825
00:44:41,020 --> 00:44:45,486
Hulle weet nie presies wat
aangaan agter die mis van die oorlog.

826
00:44:45,486 --> 00:44:47,735
Hulle kry nie om te sien wat
jy in jou voorraad.

827
00:44:47,735 --> 00:44:50,240

828
00:44:50,240 --> 00:44:52,800
>> Daar is 'n omgewing wat dinamies.

829
00:44:52,800 --> 00:44:56,180
Alles is besig om al die tyd.

830
00:44:56,180 --> 00:45:00,290
Jy kry nie om te sit en
wag om jou skuif te neem.

831
00:45:00,290 --> 00:45:02,810
Maar die meeste dinge is nog steeds diskrete.

832
00:45:02,810 --> 00:45:04,200
Ek moet my stad hier sit.

833
00:45:04,200 --> 00:45:06,750
Of moet ek my stad hier sit.

834
00:45:06,750 --> 00:45:08,950
En alles is deterministiese.

835
00:45:08,950 --> 00:45:14,660
Wanneer ek sê, beweeg my eenheid hier, my eenheid
beweeg hier nie, tensy 'n hindernis skielik

836
00:45:14,660 --> 00:45:17,700
kom in die spel.

837
00:45:17,700 --> 00:45:21,610
Nou, dit is nie al rekenaar
speletjies wat daar vandag.

838
00:45:21,610 --> 00:45:27,320
>> As ek gaan en ek speel 'n eerste tipe persoon
spel, iets soos dief of Fallout

839
00:45:27,320 --> 00:45:33,350
of Skyrim of Halo, nou
Ek het rekenaar teenstanders

840
00:45:33,350 --> 00:45:37,860
dat daar uit wat
'n baie ander situasie.

841
00:45:37,860 --> 00:45:40,020
Hulle het, weer, beperkte inligting.

842
00:45:40,020 --> 00:45:43,420
Hulle kan net 'n kyk
sekere gebied van die oog.

843
00:45:43,420 --> 00:45:45,180
Die omgewing is steeds dinamies.

844
00:45:45,180 --> 00:45:48,280
Dinge verander al die tyd.

845
00:45:48,280 --> 00:45:52,300
>> Maar nou het ek 'n baie meer
deurlopende aksie ruimte.

846
00:45:52,300 --> 00:45:57,170
Ek kan net word loer 'n
bietjie uit die deur.

847
00:45:57,170 --> 00:46:00,650
En 'n paar speletjies, my
optrede is stogastiese.

848
00:46:00,650 --> 00:46:04,590
Ek kry om te probeer om te spring oor die muur,
maar ek het 'n kans om te misluk.

849
00:46:04,590 --> 00:46:08,280

850
00:46:08,280 --> 00:46:14,550
Hierdie tipe van speletjies is om nader
en nader aan die soorte beheerders

851
00:46:14,550 --> 00:46:17,330
dat ons bou in robotika.

852
00:46:17,330 --> 00:46:21,050
>> In robotika, ons het om te aanvaar
dat ons beperkte inligting.

853
00:46:21,050 --> 00:46:23,070
Ons het sensors wat
vertel ons oor die hele wêreld.

854
00:46:23,070 --> 00:46:25,860
Ons het 'n altyd-veranderende,
dinamiese omgewing.

855
00:46:25,860 --> 00:46:30,440
Ons het 'n wêreld waarin ruimte is
deurlopende, eerder as diskrete.

856
00:46:30,440 --> 00:46:36,260
En ons optrede, wanneer ons probeer
hulle het 'n kans om te misluk.

857
00:46:36,260 --> 00:46:40,960
En in die feit, moderne spel
beheerders vir jou Halo teenstander,

858
00:46:40,960 --> 00:46:48,690
of vir diegene NPCs in Skyrim, basies
hardloop klein robotika argitekture.

859
00:46:48,690 --> 00:46:50,380
>> Hulle voel die wêreld.

860
00:46:50,380 --> 00:46:52,910
Hulle bou 'n model van die wêreld.

861
00:46:52,910 --> 00:46:57,950
Hulle bereken gebaseer op 'n stel van
doelwitte wat hulle wil bereik.

862
00:46:57,950 --> 00:47:03,110
Hulle beplan aksies gebaseer
oor wat hulle weet.

863
00:47:03,110 --> 00:47:07,940
En dit is presies dieselfde soort
stelsels wat ons bou in robotika.

864
00:47:07,940 --> 00:47:11,420
So het hierdie argitekture, om
bring dit terug saam,

865
00:47:11,420 --> 00:47:14,500
is dikwels baie dieselfde.

866
00:47:14,500 --> 00:47:16,340
>> So laat ons sien of ons dit kan sien nie.

867
00:47:16,340 --> 00:47:19,210
Kom ons gaan terug na ons
tic-tac-toe voorbeeld.

868
00:47:19,210 --> 00:47:22,690
En ek gaan 'n paar van my vra
post-docs het om te kom help my.

869
00:47:22,690 --> 00:47:26,970
So Chen Ming en Alessandro en
Olivier, as jy ouens sou kom.

870
00:47:26,970 --> 00:47:32,080

871
00:47:32,080 --> 00:47:35,440
En ek gaan nodig
'n paar van die vrywilligers

872
00:47:35,440 --> 00:47:37,590
>> OK, 'n hand het ek reg
daar in die middel.

873
00:47:37,590 --> 00:47:39,965
Laat my toe om 'n meer, iemand
verder in die rug miskien.

874
00:47:39,965 --> 00:47:40,881
Alle reg, daar.

875
00:47:40,881 --> 00:47:41,490
Kom up.

876
00:47:41,490 --> 00:47:44,190

877
00:47:44,190 --> 00:47:45,335
Alles reg.

878
00:47:45,335 --> 00:47:49,490
So laat ons dat dekking af.

879
00:47:49,490 --> 00:48:03,700
En as jy ouens reg sou kom
terug hier rond vir my, fantasties.

880
00:48:03,700 --> 00:48:06,580
>> So dit is 'n robot genoem Baxter.

881
00:48:06,580 --> 00:48:10,880
En Baxter is 'n robot wat is 'n
kommersiële platform, ontwerp

882
00:48:10,880 --> 00:48:13,030
deur 'n maatskappy genaamd Rethink.

883
00:48:13,030 --> 00:48:16,580
En dit robot is ontwerp
vir kleinskaalse vervaardiging.

884
00:48:16,580 --> 00:48:19,265
Maar vandag gaan ons
gebruik dit om tic-tac-toe te speel.

885
00:48:19,265 --> 00:48:21,930

886
00:48:21,930 --> 00:48:27,150
Nou, hierdie robot is ook iets
dit is relatief uniek.

887
00:48:27,150 --> 00:48:32,950
Want as ek nêrens staan
naby aan 'n standaard fabriek automatisering

888
00:48:32,950 --> 00:48:39,580
stelsel, sou ek in 'n baie ernstige wees
gevaar om beseer.

889
00:48:39,580 --> 00:48:45,600
>> Baxter, is egter ontwerp om
relatief veilig om met.

890
00:48:45,600 --> 00:48:48,680
En so kan ek stoot op hierdie robot.

891
00:48:48,680 --> 00:48:52,350
En jy kan sien dit is 'n bietjie
bietjie buigsaam as dit beweeg rond.

892
00:48:52,350 --> 00:48:57,250
En ek kan dit herposisioneer
waar ek wil om dit te gaan.

893
00:48:57,250 --> 00:49:03,410
Nou in 'n normale robot stelsel,
sou ons 'n stel van gewrigte hier

894
00:49:03,410 --> 00:49:07,970
dit sou direk wees
reageer op posisie bevele.

895
00:49:07,970 --> 00:49:13,180
En hulle sal nie noodwendig omgee
as hulle beweeg deur ope lug,

896
00:49:13,180 --> 00:49:15,555
of as hulle beweeg
deur my ribbekas.

897
00:49:15,555 --> 00:49:18,410

898
00:49:18,410 --> 00:49:19,120
>> OK.

899
00:49:19,120 --> 00:49:22,090
En tipies, as jy
hier met 'n industriële stelsel,

900
00:49:22,090 --> 00:49:23,400
sou jy nêrens naby is.

901
00:49:23,400 --> 00:49:26,280
Daar sal geel
veiligheid band rondom dit.

902
00:49:26,280 --> 00:49:28,310
Hierdie stelsel het 'n
effens anders ontwerp

903
00:49:28,310 --> 00:49:32,130
om vriendeliker en makliker wees
vir mense om interaksie met,

904
00:49:32,130 --> 00:49:36,380
in dat elke gewrig, daar is 'n fontein.

905
00:49:36,380 --> 00:49:39,110
En eerder as beheer
'n presiese posisie,

906
00:49:39,110 --> 00:49:43,110
ons beheer 'n sekere bedrag van
wringkrag, 'n sekere bedrag van krag is,

907
00:49:43,110 --> 00:49:45,874
dat ons graag wil wees op daardie lente.

908
00:49:45,874 --> 00:49:47,790
Alle reg, so laat my
neem hier ons vrywilligers.

909
00:49:47,790 --> 00:49:48,540
Hallo, wat is jou naam?

910
00:49:48,540 --> 00:49:49,010
>> GEHOOR: Louis.

911
00:49:49,010 --> 00:49:49,635
>> Spreker: Louis.

912
00:49:49,635 --> 00:49:50,490
Lekker om jou te sien.

913
00:49:50,490 --> 00:49:50,990
En?

914
00:49:50,990 --> 00:49:51,610
>> GEHOOR: David.

915
00:49:51,610 --> 00:49:51,960
>> Spreker: David.

916
00:49:51,960 --> 00:49:52,550
Bly te kenne.

917
00:49:52,550 --> 00:49:54,508
As jy ouens sal wag
hier vir 'n tweede,

918
00:49:54,508 --> 00:49:56,420
Ek gaan om jou te gee
'n kans om dit te doen.

919
00:49:56,420 --> 00:50:00,610
So hierdie robot, as jy kom
en as jy liggies stoot op dit,

920
00:50:00,610 --> 00:50:03,780
jy gaan om te sien dat
dit beweeg 'n bietjie.

921
00:50:03,780 --> 00:50:06,349
En as jy dit reg te gryp
hier op die pols net

922
00:50:06,349 --> 00:50:09,390
bo waar die knoppies is, is dit
lyk soos jy moet gryp die knoppies,

923
00:50:09,390 --> 00:50:13,100
maar gryp reg bo dit plaas, sal jy
in staat wees om baie versigtig te manipuleer dit

924
00:50:13,100 --> 00:50:14,545
deur die ruimte.

925
00:50:14,545 --> 00:50:15,920
Louis, jy wil om dit te probeer?

926
00:50:15,920 --> 00:50:19,465
So gee dit net 'n bietjie
stoot om te begin met.

927
00:50:19,465 --> 00:50:23,190
En dan as jy jou vingers
daar regs en hou op om dit,

928
00:50:23,190 --> 00:50:24,807
want dit sal dan beweeg vir jou.

929
00:50:24,807 --> 00:50:27,824

930
00:50:27,824 --> 00:50:29,365
Alle reg, jy wil om dit te probeer?

931
00:50:29,365 --> 00:50:29,980
Kom up.

932
00:50:29,980 --> 00:50:32,300
So gee dit net 'n sagte
stoot daar te begin.

933
00:50:32,300 --> 00:50:33,820
Jy kan voel hoe dit voel.

934
00:50:33,820 --> 00:50:40,060
En dan as jy dit gryp net daar,
jy sal in staat wees om te maneuver op rond.

935
00:50:40,060 --> 00:50:41,280
>> OK.

936
00:50:41,280 --> 00:50:47,360
So tipies, hierdie soort van 'n robot sou
gebruik word vir kleinskaalse vervaardiging.

937
00:50:47,360 --> 00:50:50,980
En ek gaan na hierdie arm net beweeg
af uit die pad 'n bietjie hier.

938
00:50:50,980 --> 00:50:55,750
Maar vandag, ons gaan die gebruik
dieselfde tic-tac-toe spel stelsel

939
00:50:55,750 --> 00:50:59,520
gebaseer op minimaks dat ons vroeër gebou.

940
00:50:59,520 --> 00:51:00,549
OK?

941
00:51:00,549 --> 00:51:02,340
So, julle is elke
gaan 'n spel te speel.

942
00:51:02,340 --> 00:51:04,210
Louis, jy gaan eerste.

943
00:51:04,210 --> 00:51:05,920
Laat my net te hou hier vir 'n tweede.

944
00:51:05,920 --> 00:51:10,949
Ek gaan om jou regte te staan
hier, net sodat almal kan jy sien.

945
00:51:10,949 --> 00:51:11,990
Is jy ouens opgestel hier?

946
00:51:11,990 --> 00:51:13,120
>> ROBOT: Welkom.

947
00:51:13,120 --> 00:51:15,910
Kom ons speel tic-tac-toe.

948
00:51:15,910 --> 00:51:20,860
Moenie jou teken nie begryp voordat
Ek sê dat dit jou beurt is.

949
00:51:20,860 --> 00:51:22,050
Ek begin die spel.

950
00:51:22,050 --> 00:51:27,900

951
00:51:27,900 --> 00:51:28,750
Dit is my beurt.

952
00:51:28,750 --> 00:51:47,002

953
00:51:47,002 --> 00:51:50,210
Spreker: Nou, as jy kan een van neem
jou stukke en gaan voort en plaas dit.

954
00:51:50,210 --> 00:51:51,446
ROBOT: Dit is jou beurt.

955
00:51:51,446 --> 00:51:53,430
[Gelag]

956
00:51:53,430 --> 00:51:54,836
Dit is my beurt.

957
00:51:54,836 --> 00:51:56,820
[Gelag]

958
00:51:56,820 --> 00:52:12,196

959
00:52:12,196 --> 00:52:15,680
[Gelag]

960
00:52:15,680 --> 00:52:16,570
Dit is jou beurt.

961
00:52:16,570 --> 00:52:21,397

962
00:52:21,397 --> 00:52:23,688
Spreker: Die menslike ras is
reken op u hier, Louis.

963
00:52:23,688 --> 00:52:27,440

964
00:52:27,440 --> 00:52:28,350
>> ROBOT: Dit is my beurt.

965
00:52:28,350 --> 00:52:44,810

966
00:52:44,810 --> 00:52:47,015
>> Spreker: So Baxter
hier suksesvol geblokkeer.

967
00:52:47,015 --> 00:52:49,670

968
00:52:49,670 --> 00:52:52,480
>> ROBOT: Dit is jou beurt.

969
00:52:52,480 --> 00:52:53,360
Dit is my beurt.

970
00:52:53,360 --> 00:53:14,730

971
00:53:14,730 --> 00:53:16,810
Dit is jou beurt.

972
00:53:16,810 --> 00:53:17,760
Dit is my beurt.

973
00:53:17,760 --> 00:53:21,330

974
00:53:21,330 --> 00:53:23,830
Spreker: En ons sal jou laat Baxter
klaar uit sy laaste skuif hier.

975
00:53:23,830 --> 00:53:36,622

976
00:53:36,622 --> 00:53:39,090
>> [Gelag]

977
00:53:39,090 --> 00:53:40,480
>> ROBOT: Dit is 'n das.

978
00:53:40,480 --> 00:53:42,030
Ek sal volgende keer te wen.

979
00:53:42,030 --> 00:53:43,365
>> [Gelag]

980
00:53:43,365 --> 00:53:45,210
>> Spreker: Alle reg,
baie dankie, Louis.

981
00:53:45,210 --> 00:53:46,094
Dankie.

982
00:53:46,094 --> 00:53:46,980
Jy kan op hierdie manier te gaan.

983
00:53:46,980 --> 00:53:49,759
>> ROBOT: Ek begin die spel.

984
00:53:49,759 --> 00:53:51,800
Spreker: So laat ek verduidelik
aan jou een bietjie

985
00:53:51,800 --> 00:53:55,410
bietjie voor ons kry ons herontmoeting hier.

986
00:53:55,410 --> 00:53:57,200
Wat presies gebeur?

987
00:53:57,200 --> 00:53:59,430
So die robot het 'n kamera op top hier.

988
00:53:59,430 --> 00:54:01,330
En dit is kyk neer op die bord.

989
00:54:01,330 --> 00:54:04,470
En dit is om te sien of
Dit het 'n rooi O of 'n blou

990
00:54:04,470 --> 00:54:10,450
en wit X As diegene kry gelê op die
raad, dit is basies dieselfde insette

991
00:54:10,450 --> 00:54:13,890
dat ons sal lees in uit
ons data struktuur van ons skerm.

992
00:54:13,890 --> 00:54:17,290
Dit loop dieselfde
minimaks algoritme te wees

993
00:54:17,290 --> 00:54:21,010
in staat wees om te vind waar om te
plaas 'n goeie teken.

994
00:54:21,010 --> 00:54:24,820
>> En dan is ons gee 'n opdrag oor
waar ons wil graag 'n teken geplaas moet word.

995
00:54:24,820 --> 00:54:26,120
Die arm beweeg nie.

996
00:54:26,120 --> 00:54:31,750
Dit is die gebruik van 'n vakuum grijper om aansoek te doen
sommige suiging om daardie hout stuk,

997
00:54:31,750 --> 00:54:35,240
dit kom haal, skuif dit na die regte
spot, en dan die vrylating suiging

998
00:54:35,240 --> 00:54:36,950
en gooi dit.

999
00:54:36,950 --> 00:54:38,990
Alle reg, ons gaan
om dit te gee 'n meer skoot

1000
00:54:38,990 --> 00:54:40,930
met 'n effens slimmer speler hier.

1001
00:54:40,930 --> 00:54:42,290
Jy gereed?

1002
00:54:42,290 --> 00:54:46,150
Alle reg, as jy wil reg op te staan
hier en gee a-- draai uit hierdie manier

1003
00:54:46,150 --> 00:54:47,955
sodat jy kan sien almal.

1004
00:54:47,955 --> 00:54:48,830
En dan [onhoorbaar].

1005
00:54:48,830 --> 00:54:49,330
>> ROBOT: Dit is my beurt.

1006
00:54:49,330 --> 00:54:50,455
>> Spreker: Baxter sal begin.

1007
00:54:50,455 --> 00:55:10,750

1008
00:55:10,750 --> 00:55:11,730
Dit is jou beurt.

1009
00:55:11,730 --> 00:55:16,490

1010
00:55:16,490 --> 00:55:17,520
Dit is my beurt.

1011
00:55:17,520 --> 00:55:38,740

1012
00:55:38,740 --> 00:55:39,690
Dit is jou beurt.

1013
00:55:39,690 --> 00:55:46,330

1014
00:55:46,330 --> 00:55:47,165
Dit is my beurt.

1015
00:55:47,165 --> 00:56:01,252

1016
00:56:01,252 --> 00:56:06,192
>> [Gelag]

1017
00:56:06,192 --> 00:56:08,542
>> Spreker: [WHISPERING] Net
laat hom voort te gaan en te wen.

1018
00:56:08,542 --> 00:56:09,500
ROBOT: Dit is jou beurt.

1019
00:56:09,500 --> 00:56:15,099

1020
00:56:15,099 --> 00:56:15,890
Spreker: Dit is OK.

1021
00:56:15,890 --> 00:56:20,390

1022
00:56:20,390 --> 00:56:21,360
>> ROBOT: Dit is my beurt.

1023
00:56:21,360 --> 00:56:24,825

1024
00:56:24,825 --> 00:56:26,805
>> [Gelag]

1025
00:56:26,805 --> 00:56:42,650

1026
00:56:42,650 --> 00:56:43,510
>> Ek wen.

1027
00:56:43,510 --> 00:56:45,620
>> [Gelag]

1028
00:56:45,620 --> 00:56:46,595
>> Ek begin die spel.

1029
00:56:46,595 --> 00:56:48,261
>> Spreker: Alle reg, baie dankie.

1030
00:56:48,261 --> 00:56:50,180

1031
00:56:50,180 --> 00:56:55,590
Alle reg, ek dink ons ​​het die tyd het vir
een uitstekende tic-tac-toe-speler,

1032
00:56:55,590 --> 00:57:00,490
iemand wat hierdie ding kan sit om
pas, wat weet wat hulle doen.

1033
00:57:00,490 --> 00:57:03,010
>> [Gelag]

1034
00:57:03,010 --> 00:57:05,560
>> Wie gaan ons kampioen hier wees?

1035
00:57:05,560 --> 00:57:08,110
Alle reg, jou vriende vrywillig jou.

1036
00:57:08,110 --> 00:57:11,190
Dit is goed genoeg vir my.

1037
00:57:11,190 --> 00:57:12,194
Vertel my weer jou naam.

1038
00:57:12,194 --> 00:57:12,860
GEHOOR: Tamir.

1039
00:57:12,860 --> 00:57:14,193
Spreker: Tamir, lekker om jou te sien.

1040
00:57:14,193 --> 00:57:19,270
Alle reg, weer, ons gaan sit jy
reg hier sodat almal kan jy sien.

1041
00:57:19,270 --> 00:57:22,070
Jy is ons verteenwoordiger
in hierdie wedstryd nou.

1042
00:57:22,070 --> 00:57:24,540
Baxter is een en oh en oh.

1043
00:57:24,540 --> 00:57:26,300
Of jammer, een oh en een.

1044
00:57:26,300 --> 00:57:27,490
En dit is aan jou hier.

1045
00:57:27,490 --> 00:57:29,340
Baxter sal kry om die eerste skuif, al is.

1046
00:57:29,340 --> 00:57:30,435
Doen.

1047
00:57:30,435 --> 00:57:31,310
ROBOT: Dit is my beurt.

1048
00:57:31,310 --> 00:57:45,226

1049
00:57:45,226 --> 00:57:48,208
>> [Gelag]

1050
00:57:48,208 --> 00:57:52,720

1051
00:57:52,720 --> 00:57:55,780
>> Dit is jou beurt.

1052
00:57:55,780 --> 00:57:56,845
Dit is my beurt.

1053
00:57:56,845 --> 00:58:18,130

1054
00:58:18,130 --> 00:58:18,965
Dit is jou beurt.

1055
00:58:18,965 --> 00:58:28,751

1056
00:58:28,751 --> 00:58:30,248
Dit is my beurt.

1057
00:58:30,248 --> 00:58:51,210

1058
00:58:51,210 --> 00:58:52,160
Dit is jou beurt.

1059
00:58:52,160 --> 00:59:00,854

1060
00:59:00,854 --> 00:59:03,365
>> [Gelag]

1061
00:59:03,365 --> 00:59:04,240
ROBOT: Dit is my beurt.

1062
00:59:04,240 --> 00:59:06,930
Spreker: Dit is 'n baie harder wanneer
jy staan ​​hier op, mense.

1063
00:59:06,930 --> 00:59:19,400

1064
00:59:19,400 --> 00:59:21,840
[Gelag]

1065
00:59:21,840 --> 00:59:26,730

1066
00:59:26,730 --> 00:59:29,054
ROBOT: Jy is mense so maklik om te klop.

1067
00:59:29,054 --> 00:59:30,803
[Gelag en applous]

1068
00:59:30,803 --> 00:59:31,886
Spreker: Baie dankie.

1069
00:59:31,886 --> 00:59:34,692
ROBOT: ek wen.

1070
00:59:34,692 --> 00:59:35,400
Ek begin die spel.

1071
00:59:35,400 --> 00:59:39,500
>> Spreker: Alle reg, so dankie baie
veel om te Olivier en Alessandro,

1072
00:59:39,500 --> 00:59:41,616
en Chen Ming.

1073
00:59:41,616 --> 00:59:45,600
>> [Applous]

1074
00:59:45,600 --> 00:59:47,040
>> Ek wil 'n laaste punt te maak.

1075
00:59:47,040 --> 00:59:51,630
So Baxter op die heel
eindig daar, verneuk.

1076
00:59:51,630 --> 00:59:54,160

1077
00:59:54,160 --> 00:59:56,310
En dit was onverwags.

1078
00:59:56,310 --> 01:00:00,440
Een van die fantastiese
dinge oor AI is dat ons

1079
01:00:00,440 --> 01:00:05,070
werk te doen in AI sodat ons kan bou
baie interessant en intelligente

1080
01:00:05,070 --> 01:00:06,930
toestelle.

1081
01:00:06,930 --> 01:00:10,130
Maar ons het ook werk in AI
want dit vertel ons iets

1082
01:00:10,130 --> 01:00:13,940
oor hoe die mens is intelligent.

1083
01:00:13,940 --> 01:00:17,280
>> Een van die gunsteling
studies van my lab is

1084
01:00:17,280 --> 01:00:23,660
kyk na wat gebeur wanneer
masjiene onverwags kul.

1085
01:00:23,660 --> 01:00:27,070
Ons het dit aanvanklik nie met
Baxter speel tic-tac-toe,

1086
01:00:27,070 --> 01:00:30,340
maar met 'n kleiner robot genoem Nao,
wat rock-papier-skêr gespeel.

1087
01:00:30,340 --> 01:00:33,010

1088
01:00:33,010 --> 01:00:35,800
En soms na
speel baie, baie

1089
01:00:35,800 --> 01:00:41,580
verveel rock-papier-skêr games,
die robot sal gooi 'n gebaar,

1090
01:00:41,580 --> 01:00:48,616
verloor nie, en dan skielik verander
sy gebaar en sê ek wen.

1091
01:00:48,616 --> 01:00:50,480
>> [Gelag]

1092
01:00:50,480 --> 01:00:56,090
>> Nou, soms wil ons ook die robot,
net soos 'n beheer, gooi 'n gebaar,

1093
01:00:56,090 --> 01:01:01,270
wen, en verander sy gebaar
om te verloor, gooi die wedstryd,

1094
01:01:01,270 --> 01:01:04,070
oneerlik om te verloor.

1095
01:01:04,070 --> 01:01:07,540
En dit is nie naastenby so oortuigend.

1096
01:01:07,540 --> 01:01:09,890
Die robot wat cheats
om mense te wen

1097
01:01:09,890 --> 01:01:14,660
reageer asof dit
uit om hulle te kry, soos dit

1098
01:01:14,660 --> 01:01:17,690
is aktief op soek na hul ondergang.

1099
01:01:17,690 --> 01:01:19,210
>> [Gelag]

1100
01:01:19,210 --> 01:01:20,990
>> Dit word 'n agent.

1101
01:01:20,990 --> 01:01:21,840
Dit is soos 'n persoon.

1102
01:01:21,840 --> 01:01:23,970
Dit het geloof en voorneme.

1103
01:01:23,970 --> 01:01:27,470
En dit is nie goeie bedoeling.

1104
01:01:27,470 --> 01:01:33,790
En die robot wat gooi die
spel is net onklaar.

1105
01:01:33,790 --> 01:01:36,990
Dis net 'n gebreekte toestel.

1106
01:01:36,990 --> 01:01:41,405
Laat my jou wys 'n paar voorbeelde
van daardie van 'n paar van ons deelnemers.

1107
01:01:41,405 --> 01:01:43,990

1108
01:01:43,990 --> 01:01:45,600
So hier is verneuk om te verloor.

1109
01:01:45,600 --> 01:01:46,266
>> [Video speel]

1110
01:01:46,266 --> 01:01:47,010
- [Onhoorbaar] wen.

1111
01:01:47,010 --> 01:01:49,550
Kom ons speel.

1112
01:01:49,550 --> 01:01:50,538
>> -Wag wat?

1113
01:01:50,538 --> 01:01:54,490

1114
01:01:54,490 --> 01:01:55,352
>> - [Onhoorbaar] wen.

1115
01:01:55,352 --> 01:01:58,280
Kom ons speel.

1116
01:01:58,280 --> 01:01:59,400
>> [Onhoorbaar] wen.

1117
01:01:59,400 --> 01:02:02,290
Kom ons speel.

1118
01:02:02,290 --> 01:02:05,490
>> Spreker: En hier is verneuk om te wen.

1119
01:02:05,490 --> 01:02:06,438
>> -Ja, Ek wen.

1120
01:02:06,438 --> 01:02:07,394
Kom ons speel.

1121
01:02:07,394 --> 01:02:08,828
>> -Jy Kan dit nie doen nie.

1122
01:02:08,828 --> 01:02:10,740
>> [Gelag]

1123
01:02:10,740 --> 01:02:12,174

1124
01:02:12,174 --> 01:02:13,979
>> -Ja, Ek wen.

1125
01:02:13,979 --> 01:02:14,520
-Jy Bedrieg.

1126
01:02:14,520 --> 01:02:17,990

1127
01:02:17,990 --> 01:02:20,010
Jy verneuk nou.

1128
01:02:20,010 --> 01:02:21,140
>> -Ja, Ek wen.

1129
01:02:21,140 --> 01:02:22,940
>> Hey, jy cheater.

1130
01:02:22,940 --> 01:02:26,670
Jy oneerlik, super oneerlik.

1131
01:02:26,670 --> 01:02:27,650
>> [Einde afspeel]

1132
01:02:27,650 --> 01:02:31,130
>> Spreker: Hierdie verskillende
reaksies vinnig

1133
01:02:31,130 --> 01:02:34,890
verander ons persepsie van die toestel.

1134
01:02:34,890 --> 01:02:36,780
Beteken dit dat
ons doelbewus bou

1135
01:02:36,780 --> 01:02:40,370
masjiene wat oneerlik, want dit is
die beste ingenieurswese wat ons kan doen?

1136
01:02:40,370 --> 01:02:44,680
Nee, maar dit vertel ons iets
baie interessant oor mense.

1137
01:02:44,680 --> 01:02:49,710
Daardie ding wat jy en cheats
steel jou oorwinning, dit is

1138
01:02:49,710 --> 01:02:53,660
iets wat lewendig, dis
animeer, dit is uit om jou te kry.

1139
01:02:53,660 --> 01:02:54,680
Dit het geestelike toestand.

1140
01:02:54,680 --> 01:02:55,400
Dit het geloof.

1141
01:02:55,400 --> 01:02:57,170
Dit het voorneme.

1142
01:02:57,170 --> 01:03:01,540
>> Daardie ding wat die hande van die
spel vir jou, dit is nie.

1143
01:03:01,540 --> 01:03:04,670
Dit is net onklaar.

1144
01:03:04,670 --> 01:03:08,900
Dit is in baie maniere hoekom dit
maklik om die spel te gooi met kinders.

1145
01:03:08,900 --> 01:03:12,050
Maar as jy probeer om hulle te kul
en soort eis oorwinning

1146
01:03:12,050 --> 01:03:15,200
wanneer, jy weet, net om die verkort
spel, sal hulle jou vang dadelik.

1147
01:03:15,200 --> 01:03:19,040

1148
01:03:19,040 --> 01:03:23,140
Hierdie soort effekte wat
ons sien uit te kom van AI,

1149
01:03:23,140 --> 01:03:26,490
Dit leer ons baie oor onsself.

1150
01:03:26,490 --> 01:03:28,076
>> Alle reg, dit is dit vir vandag.

1151
01:03:28,076 --> 01:03:30,450
Baie dankie aan Dawid en
die Harvard produksie span

1152
01:03:30,450 --> 01:03:32,350
vir afkom.

1153
01:03:32,350 --> 01:03:33,820
>> [Applous]

1154
01:03:33,820 --> 01:03:36,760

1155
01:03:36,760 --> 01:03:41,840
>> Ons sal sien dat jy vir quiz een
en dan vir 'n laaste lesing.

1156
01:03:41,840 --> 01:03:43,025
Lekker dag.

1157
01:03:43,025 --> 01:03:44,965
>> [Applous]

1158
01:03:44,965 --> 01:03:48,360

1159
01:03:48,360 --> 01:03:51,825
>> [Speel van musiek]

1160
01:03:51,825 --> 01:03:54,950
DAVID J MALAN: Wel, waarskynlik moet ons
om 'n soort stel van enkripsie,

1161
01:03:54,950 --> 01:03:55,450
reg?

1162
01:03:55,450 --> 01:03:58,650
Want dan is die kop van
hierdie HTTP versoeke sal wees

1163
01:03:58,650 --> 01:04:01,530
roer sodat almal
probeer om jou verkeer te snuffel

1164
01:04:01,530 --> 01:04:03,400
sal eintlik nie in staat wees om hulle te sien.

1165
01:04:03,400 --> 01:04:05,254
So, wat is die oplossing vir hierdie probleem?

1166
01:04:05,254 --> 01:04:07,920
Wel, ons moet eintlik stel
enkripsie in die formule,

1167
01:04:07,920 --> 01:04:11,010
sodat wanneer daardie persoon
oordrag van data vanaf A na B,

1168
01:04:11,010 --> 01:04:12,390
ons kan veilig send--

1169
01:04:12,390 --> 01:04:14,590
>> [Gelag]

1170
01:04:14,590 --> 01:04:19,530
>> Die inligting in 'n manier dat die
teenstander kan nie, in werklikheid, dit sien.