1
00:00:00,000 --> 00:00:01,924
>> [MUSIK SPELA]

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

3
00:00:10,600 --> 00:00:13,280
>> Speak: Välkommen tillbaka, alla.

4
00:00:13,280 --> 00:00:15,440
Detta är CS50.

5
00:00:15,440 --> 00:00:21,040
Och i dag har vi en hel del
intressanta saker att prata om.

6
00:00:21,040 --> 00:00:25,500
Men först måste jag påminna
dig om några administrativa saker.

7
00:00:25,500 --> 00:00:30,160
Den här veckan är quiz en, onsdag
eller för Yale sektionen

8
00:00:30,160 --> 00:00:32,940
på tisdagar och torsdagar, på torsdag.

9
00:00:32,940 --> 00:00:38,170
Det finns frågesport omdömen
ikväll på Yale, från 5:30 till 7:00.

10
00:00:38,170 --> 00:00:40,030
Vid Harvard, spelade de en igår.

11
00:00:40,030 --> 00:00:43,000
Och alla kan titta på det på nätet.

12
00:00:43,000 --> 00:00:49,406
>> Även denna vecka eller i början av nästa vecka,
vi har vår sista CS50 föreläsning.

13
00:00:49,406 --> 00:00:51,450
[Groans] Jag vet.

14
00:00:51,450 --> 00:00:54,140
Det kom så snart.

15
00:00:54,140 --> 00:00:57,820
Yale studenter kommer att ha en levande
föreläsa här i juridisk fakultet

16
00:00:57,820 --> 00:00:59,920
auditorium på fredag.

17
00:00:59,920 --> 00:01:01,140
Det kommer att bli tårta.

18
00:01:01,140 --> 00:01:05,570
Harvard studenter kommer att ha
sista föreläsning i Sanders på måndagen.

19
00:01:05,570 --> 00:01:08,050
Det kommer också att kakan.

20
00:01:08,050 --> 00:01:14,000
>> Även denna vecka på fredag, för dem
av er som kommer till New Haven,

21
00:01:14,000 --> 00:01:15,740
Vi har CS50 Expo.

22
00:01:15,740 --> 00:01:18,850
Vi har mer än 30
olika grupper registrerade

23
00:01:18,850 --> 00:01:22,530
att visa dig allt
från autonoma segelbåtar,

24
00:01:22,530 --> 00:01:27,170
till system som känner igen
digitala porträtt, till datorn

25
00:01:27,170 --> 00:01:32,100
musik och datorproducerade musik.

26
00:01:32,100 --> 00:01:33,610
Så snälla gå med oss.

27
00:01:33,610 --> 00:01:36,460
Jag tror att det kommer att vara en bra tid.

28
00:01:36,460 --> 00:01:40,320
>> Idag, men vi får
fortsätta prata om AI,

29
00:01:40,320 --> 00:01:43,150
om artificiell intelligens.

30
00:01:43,150 --> 00:01:46,070
Och en av de saker som
vi kommer att komma till idag

31
00:01:46,070 --> 00:01:51,750
är idén om hur man
använda AI att lösa problem.

32
00:01:51,750 --> 00:01:54,690
Nu, som alltid, låt oss börja
med något enkelt.

33
00:01:54,690 --> 00:01:57,120
Och vi kommer att börja
med en enkel idé.

34
00:01:57,120 --> 00:01:59,920
Och det är med sökord.

35
00:01:59,920 --> 00:02:06,990
>> Så tänk för ett ögonblick att jag
har en uppgift som jag behöver för att utföra.

36
00:02:06,990 --> 00:02:11,970
Och jag skulle vilja ha denna uppgift
automatiseras av vissa program agent.

37
00:02:11,970 --> 00:02:17,100
Föreställ dig att jag försöker boka en uppsättning
på flyg från, låt oss säga, Boston

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

39
00:02:20,040 --> 00:02:24,230
Jag kunde gå igenom och jag kunde använda
en av de underbara online-sökning

40
00:02:24,230 --> 00:02:28,790
verktyg, som kommer att göra
princip samma process som vi är

41
00:02:28,790 --> 00:02:30,030
kommer att gå igenom i dag.

42
00:02:30,030 --> 00:02:34,100
Men om du inte har det
verktyg, vad skulle du göra?

43
00:02:34,100 --> 00:02:37,570
>> Tja, kan du titta och
se och säga, jag är i Boston.

44
00:02:37,570 --> 00:02:41,520
Vilka flygningar är tillgängliga för mig?

45
00:02:41,520 --> 00:02:44,390
Nu kanske jag har tre
eventuella flygningar av Boston

46
00:02:44,390 --> 00:02:47,180
som passar den tid
när jag måste lämna.

47
00:02:47,180 --> 00:02:48,830
Jag kunde flyga till Chicago.

48
00:02:48,830 --> 00:02:50,130
Eller jag kunde flyga till Miami.

49
00:02:50,130 --> 00:02:53,340
Eller jag kunde flyga till New York.

50
00:02:53,340 --> 00:02:56,980
Jag kunde då se från varje
en av dessa destinationen städer

51
00:02:56,980 --> 00:03:00,650
och tänka på vad platser
Jag skulle kunna nå

52
00:03:00,650 --> 00:03:03,020
från var och en av dessa enskilda städerna.

53
00:03:03,020 --> 00:03:07,390
>> Så kanske från Chicago, kan jag få
ett direktflyg till San Francisco.

54
00:03:07,390 --> 00:03:09,550
Det är utmärkt.

55
00:03:09,550 --> 00:03:12,360
Eller jag kunde få en flygning till Denver.

56
00:03:12,360 --> 00:03:16,970
Nu kanske det flyg till San Francisco
är den perfekta lösningen för mig,

57
00:03:16,970 --> 00:03:19,530
men kanske inte.

58
00:03:19,530 --> 00:03:22,180
Kanske jag letar efter något
det är lite billigare

59
00:03:22,180 --> 00:03:24,920
eller lite bättre för mitt schema.

60
00:03:24,920 --> 00:03:29,197
Och så jag kunde leta efter vad andra
möjligheter kan vara ute.

61
00:03:29,197 --> 00:03:30,280
Så jag kunde titta på Denver.

62
00:03:30,280 --> 00:03:33,870
Och från Denver, ja, kanske
Jag kan få en flygning till Austin.

63
00:03:33,870 --> 00:03:37,080
Och från Austin, kanske jag kan få en
flyg till Phoenix, och från Phoenix

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

65
00:03:40,190 --> 00:03:42,730
Nu, jag är inte klar än.

66
00:03:42,730 --> 00:03:45,640
Eftersom kanske det finns en
direktflyg från New York

67
00:03:45,640 --> 00:03:47,850
San Francisco som är perfekt för mig.

68
00:03:47,850 --> 00:03:53,354
Eller kanske det finns en flygning från Miami
genom Denver som är mycket billigare.

69
00:03:53,354 --> 00:03:54,270
Så jag har fortfarande att gå.

70
00:03:54,270 --> 00:03:58,200
Och jag har fortfarande att titta på alla de
städer som jag inte har undersökt ännu.

71
00:03:58,200 --> 00:04:04,220
Jag måste uttömmande kontrollera alla
de möjligheter som jag kan ha.

72
00:04:04,220 --> 00:04:09,610
>> Så från New York, kanske jag kan få en
flyg till Nashville, och från Nashville

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

74
00:04:10,336 --> 00:04:11,460
Och då jag vet var jag är.

75
00:04:11,460 --> 00:04:14,252
Och då jag vet från Austin, jag kan
flyga till Phoenix, och från Phoenix

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

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

78
00:04:18,240 --> 00:04:22,830
Om jag flyger först till Miami, men,
kanske jag kan få en flygning från Miami

79
00:04:22,830 --> 00:04:25,080
till Nashville, eller från Miami till Austin.

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

81
00:04:27,950 --> 00:04:30,860
>> Och nu har jag provat alla
av möjligheterna.

82
00:04:30,860 --> 00:04:36,310
Jag har byggt upp denna graf som
visar mig alla möjliga vägar

83
00:04:36,310 --> 00:04:37,790
att jag skulle kunna ta.

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

85
00:04:40,510 --> 00:04:43,640
När vi representerar dessa
typer av problem,

86
00:04:43,640 --> 00:04:47,870
Vi kommer inte att representera
dem uttryckligen som denna graf,

87
00:04:47,870 --> 00:04:51,590
eftersom den grafen representerar inte
historia där vi har gått.

88
00:04:51,590 --> 00:04:55,260
Att veta att jag flög från
Phoenix till San Francisco

89
00:04:55,260 --> 00:05:01,690
inte tala om för mig om jag kom via
Nashville, eller via Denver, eller via Miami.

90
00:05:01,690 --> 00:05:06,430
>> Så vad jag ska göra i stället är
Jag tar samma problem,

91
00:05:06,430 --> 00:05:09,140
och jag ska representera det som ett träd.

92
00:05:09,140 --> 00:05:14,300
Och vid roten av trädet, vid
top, ska jag lägga den plats som jag började,

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

94
00:05:16,590 --> 00:05:19,310
Och från Boston, kommer jag att titta på
alla möjliga platser

95
00:05:19,310 --> 00:05:20,380
att jag kan resa till.

96
00:05:20,380 --> 00:05:25,480
Tja, i det här fallet, hade jag tre,
Chicago, New York och Miami.

97
00:05:25,480 --> 00:05:29,850
Och då ska jag undersöka var och en av
dessa barn i trädet.

98
00:05:29,850 --> 00:05:32,690
>> Från Chicago, jag såg
att jag hade två flygningar.

99
00:05:32,690 --> 00:05:35,940
Jag kunde flyga direkt till
San Francisco eller Denver.

100
00:05:35,940 --> 00:05:37,740
Nu San Francisco, det är mitt mål.

101
00:05:37,740 --> 00:05:39,790
Det är mitt mål.

102
00:05:39,790 --> 00:05:42,220
Det kommer att bli ett löv av det här trädet.

103
00:05:42,220 --> 00:05:45,340
Det vill säga, jag kommer aldrig att gå
någonstans efter San Francisco.

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

105
00:05:47,850 --> 00:05:50,340
Från Denver, dock,
Jag kan flyga från Denver

106
00:05:50,340 --> 00:05:54,220
Austin, från Austin till Phoenix,
och från Phoenix till San Francisco.

107
00:05:54,220 --> 00:05:56,050
Och nu igen, har jag nått ett löv.

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

109
00:05:59,470 --> 00:06:03,980
>> Jag kunde sedan gå tillbaka till nästa
stad som jag inte till fullo har utforskat.

110
00:06:03,980 --> 00:06:07,440
Det skulle vara New York, gå
tillbaka upp till toppen av mitt träd,

111
00:06:07,440 --> 00:06:09,160
komma ner till New York.

112
00:06:09,160 --> 00:06:12,700
Från New York, kan jag flyga till
Nashville, från Nashville till Austin,

113
00:06:12,700 --> 00:06:17,290
från Austin till Phoenix, och
från Phoenix till San Francisco.

114
00:06:17,290 --> 00:06:20,170
Och slutligen, en stad jag
har inte tittat på ännu, Miami.

115
00:06:20,170 --> 00:06:24,600
>> Tja, från Miami jag sa att jag hade två
möjligheter, Nashville eller Austin.

116
00:06:24,600 --> 00:06:28,810
Om jag flyger till Nashville, ja då flyger jag
från Nashville till Austin till Phoenix,

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

118
00:06:29,640 --> 00:06:33,600
Om jag flyger till Austin, jag flyger Austin,
till Phoenix, San Francisco.

119
00:06:33,600 --> 00:06:36,340
Och nu har jag ett träd.

120
00:06:36,340 --> 00:06:37,230
Det är en komplett träd.

121
00:06:37,230 --> 00:06:41,890
Det är alla de möjligheter och
alla de banor som jag kunde ta.

122
00:06:41,890 --> 00:06:44,310
Det är, om jag börjar på
roten av trädet på toppen

123
00:06:44,310 --> 00:06:47,860
och jag gå ner till en av de
blad, det säger mig inte bara

124
00:06:47,860 --> 00:06:50,480
där jag ska
hamnar, San Francisco,

125
00:06:50,480 --> 00:06:53,670
men det säger mig den väg som
Jag behöver ta för att komma dit.

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

127
00:06:56,400 --> 00:06:59,690
>> Nu är som en av dessa bäst?

128
00:06:59,690 --> 00:07:02,430
Tja, ingenting om detta
Problemet berättar ännu

129
00:07:02,430 --> 00:07:04,710
vilka av dessa är den bästa lösningen.

130
00:07:04,710 --> 00:07:09,270
Kanske jag bryr mest om
hur mycket tid jag är i luften,

131
00:07:09,270 --> 00:07:12,350
eller avståndet som jag flyger.

132
00:07:12,350 --> 00:07:16,410
I så fall, Chicago till San
Francisco kan vara den kortaste nummer

133
00:07:16,410 --> 00:07:18,910
av miles i luften.

134
00:07:18,910 --> 00:07:20,860
>> Jag kanske bryr sig om kostnaden.

135
00:07:20,860 --> 00:07:23,680
Och vi vet alla direktflyg
är oftast dyrare.

136
00:07:23,680 --> 00:07:26,610
Så kanske om jag tar detta
typ av bakåt rutt

137
00:07:26,610 --> 00:07:30,650
genom Miami, Nashville,
Austin, Phoenix, kanske sedan

138
00:07:30,650 --> 00:07:34,070
Jag får ett lägre pris.

139
00:07:34,070 --> 00:07:36,440
Men jag kunde optimera på någon
kriterier som jag bryr mig om.

140
00:07:36,440 --> 00:07:39,790
Vem har bäst i
flyg Wi-Fi, eller som

141
00:07:39,790 --> 00:07:43,110
flygplatserna har den bästa mat tillgänglig.

142
00:07:43,110 --> 00:07:47,280
Och vart och ett av de kanske
ge mig en annan lösning

143
00:07:47,280 --> 00:07:49,215
som jag ser som den bästa.

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

145
00:07:51,990 --> 00:07:54,400
>> Dessa typer av problem,
där vi ska

146
00:07:54,400 --> 00:07:58,480
att bygga ut detta träd av
möjligheter, och sedan

147
00:07:58,480 --> 00:08:02,100
titta på var och en av dem
enskilda vägar, och undersöka

148
00:08:02,100 --> 00:08:05,270
vilken av dessa uppfyller
ett kriterium för oss,

149
00:08:05,270 --> 00:08:08,790
vi ska ringa
dessa sökproblem.

150
00:08:08,790 --> 00:08:11,280
Och vi har massor av
algoritmer, av vilka

151
00:08:11,280 --> 00:08:15,270
Vi har redan sett, att gå
och utforska dessa träd.

152
00:08:15,270 --> 00:08:19,270
Vi kan göra det på det sätt som jag
bara gjorde en djup första sökning,

153
00:08:19,270 --> 00:08:22,900
gå ner så långt som vi kan tills vi
slå ett löv, och sedan komma tillbaka,

154
00:08:22,900 --> 00:08:24,787
och gå tillbaka ner.

155
00:08:24,787 --> 00:08:26,870
Eller vi kunde göra vad som är
kallas bredden-först sökning.

156
00:08:26,870 --> 00:08:29,675
Vi kunde expandera allt
vid toppen, och sedan

157
00:08:29,675 --> 00:08:31,550
allt en rad
därunder, och sedan

158
00:08:31,550 --> 00:08:35,240
allt en rad under det.

159
00:08:35,240 --> 00:08:41,250
Dessa sökträd
är grundläggande för AI.

160
00:08:41,250 --> 00:08:46,570
Men de vet inte riktigt får
det rätt hela tiden.

161
00:08:46,570 --> 00:08:51,600
I själva verket, i många av fallen
att vi verkligen bryr oss om,

162
00:08:51,600 --> 00:08:54,430
vi vill bygga ett träd,
men vi egentligen inte

163
00:08:54,430 --> 00:08:57,140
få göra alla beslut.

164
00:08:57,140 --> 00:09:00,940
>> Dessa är situationer som kallas
kontradiktoriskt sökning, även känd

165
00:09:00,940 --> 00:09:05,390
som hur man skriver spelande
system och få betalt för det.

166
00:09:05,390 --> 00:09:07,940
Men det är dessa typer
system där jag

167
00:09:07,940 --> 00:09:12,920
kanske får välja när jag går från
Boston, vilken stad jag gå vidare till nästa.

168
00:09:12,920 --> 00:09:19,990
Men efter det, skulle någon annan få
att fatta beslut om var jag flyga.

169
00:09:19,990 --> 00:09:24,040
Så för att bygga dessa
typer strukturer, vi är

170
00:09:24,040 --> 00:09:28,510
kommer att behöva ta en något
olika förhållningssätt till det.

171
00:09:28,510 --> 00:09:31,060
Vi kommer inte att kunna
bara söka igenom trädet

172
00:09:31,060 --> 00:09:35,000
längre, eftersom vi inte
den som är i kontroll

173
00:09:35,000 --> 00:09:38,180
var och en av dessa beslutspunkter.

174
00:09:38,180 --> 00:09:42,590
>> Så låt oss föreställa oss en enkel
spel som Tre i rad.

175
00:09:42,590 --> 00:09:46,730
Jag kan börja med en
helt tom kartong.

176
00:09:46,730 --> 00:09:49,580
Och i Tre i rad,
X får spela först.

177
00:09:49,580 --> 00:09:53,890
Och så jag kunde tänka på alla
möjliga drag att X skulle kunna göra.

178
00:09:53,890 --> 00:09:57,420
Och om jag är en spel
X, det är bra.

179
00:09:57,420 --> 00:10:01,020
Jag har nio möjliga
flyttar jag kan göra.

180
00:10:01,020 --> 00:10:05,000
Jag skulle kunna sätta ett kryss i någon
av dessa nio positioner.

181
00:10:05,000 --> 00:10:10,710
>> Och sedan från vart och ett av dem, jag
kunde föreställa sig vad som händer härnäst.

182
00:10:10,710 --> 00:10:14,130
Jo, i detta fall, den andra
spelare skulle få ta en sväng.

183
00:10:14,130 --> 00:10:15,660
O skulle få ta en sväng.

184
00:10:15,660 --> 00:10:19,510
Och från vart och ett av dem, det
skulle vara åtta olika platser

185
00:10:19,510 --> 00:10:22,980
att O kan placera sin markör.

186
00:10:22,980 --> 00:10:25,790
>> Låt oss säga att jag bestämde att jag var
kommer att sätta ett kryss i mitten.

187
00:10:25,790 --> 00:10:28,810
Det verkar alltid som
en bra öppning drag.

188
00:10:28,810 --> 00:10:34,870
Jag kan titta på undersidan att den
åtta möjliga drag att O gör.

189
00:10:34,870 --> 00:10:37,320
Nu, om jag spelar X, det är underbart.

190
00:10:37,320 --> 00:10:41,740
Jag får välja vilka jag
gå till, en i mitten.

191
00:10:41,740 --> 00:10:45,000
Men nu O får välja.

192
00:10:45,000 --> 00:10:48,750
Och jag har inte kontroll
över detta beslut.

193
00:10:48,750 --> 00:10:51,670
>> Men från var och en av dem
möjliga styrelseuppdrag,

194
00:10:51,670 --> 00:10:54,020
det finns sedan en annan
uppsättning av möjligheter.

195
00:10:54,020 --> 00:10:56,700
När det kommer att vara
Min tur igen, skulle jag

196
00:10:56,700 --> 00:11:01,500
får välja och säga, ja,
om O flyttar in, ja,

197
00:11:01,500 --> 00:11:06,110
mitten plats på vänster, sedan
Jag har en uppsättning av möjligheter

198
00:11:06,110 --> 00:11:09,740
där jag kan ta min nästa drag.

199
00:11:09,740 --> 00:11:14,140
Från dem, skulle jag överväga alla
möjligheterna under dem.

200
00:11:14,140 --> 00:11:18,030
Och sedan O skulle få
att välja bland dem.

201
00:11:18,030 --> 00:11:22,290
>> Och jag kunde hålla bygga denna
träd tills jag kom till en punkt

202
00:11:22,290 --> 00:11:26,960
där antingen någon
vinner game-- som är

203
00:11:26,960 --> 00:11:31,070
fick betraktas som en leaf node--
eller styrelsen är helt full

204
00:11:31,070 --> 00:11:32,704
och ingen har vunnit.

205
00:11:32,704 --> 00:11:34,370
Och det kommer också att bli en lövnod.

206
00:11:34,370 --> 00:11:35,411
Det kommer att bli en slips.

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

208
00:11:37,820 --> 00:11:41,680
>> Men knepig sak med detta är
om detta var bara en vanlig sökning

209
00:11:41,680 --> 00:11:44,269
problem, skulle jag kunna
säga, ja, X bör gå hit.

210
00:11:44,269 --> 00:11:45,560
Och O skulle gå vägen dit.

211
00:11:45,560 --> 00:11:46,770
Och sedan X bör gå hit.

212
00:11:46,770 --> 00:11:48,269
Och sedan O bör gå vägen dit.

213
00:11:48,269 --> 00:11:51,860
Och sedan X kan få tre
i rad, och jag vinner.

214
00:11:51,860 --> 00:11:54,870
Och spelet skulle vara över
i fem drag, tre för mig,

215
00:11:54,870 --> 00:11:57,710
två för min motståndare.

216
00:11:57,710 --> 00:12:01,300
Men jag vet inte alltid får välja det.

217
00:12:01,300 --> 00:12:03,720
>> Så istället, vad vi är
kommer att behöva göra

218
00:12:03,720 --> 00:12:06,270
är vi kommer att ha
att ha en ny strategi.

219
00:12:06,270 --> 00:12:09,350
Och den strategi som
spel-playing algoritmer använder ofta

220
00:12:09,350 --> 00:12:12,000
är vad som kallas minimax.

221
00:12:12,000 --> 00:12:15,500
Den centrala idén om
Minimax är att vi är

222
00:12:15,500 --> 00:12:21,365
kommer att plocka drag som ger
våra motståndare värsta möjliga mängd

223
00:12:21,365 --> 00:12:22,790
drag att de kan göra.

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

225
00:12:25,570 --> 00:12:28,870
Det gör inte mig något bra
att välja ett drag där

226
00:12:28,870 --> 00:12:31,952
Jag skulle kunna vinna efter
det, eftersom min motståndare är inte

227
00:12:31,952 --> 00:12:33,160
kommer att ge mig den chansen.

228
00:12:33,160 --> 00:12:37,770
De kommer att välja några
fruktansvärda utfall för mig.

229
00:12:37,770 --> 00:12:42,010
Så jag kommer att göra
flytta som tvingar min motståndare

230
00:12:42,010 --> 00:12:45,760
att göra något bättre för mig.

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

232
00:12:46,260 --> 00:12:48,410
Låt oss se hur det utspelar sig.

233
00:12:48,410 --> 00:12:51,640
Så här är vår algoritm i pseudokod.

234
00:12:51,640 --> 00:12:54,450
Vi kommer att generera
hela spelträdet.

235
00:12:54,450 --> 00:12:56,757
Vi kommer att bygga
hela strukturen.

236
00:12:56,757 --> 00:12:57,840
Och sedan ska vi gå igenom.

237
00:12:57,840 --> 00:13:02,100
Och längst ner vid var och en av
terminalnoder, vid var och en av bladen,

238
00:13:02,100 --> 00:13:07,850
Vi ska utvärdera hur
värdefullt är det för mig?

239
00:13:07,850 --> 00:13:11,690
Och vi kommer att värdera saker som
är bra för mig som positivt.

240
00:13:11,690 --> 00:13:14,460
Saker som inte är bra för mig
kommer att vara mindre positiv, eller noll,

241
00:13:14,460 --> 00:13:16,480
eller till och med negativ.

242
00:13:16,480 --> 00:13:19,240
>> Så i Tre i rad, kanske
en vinst för mig är bra.

243
00:13:19,240 --> 00:13:20,290
Det är en en.

244
00:13:20,290 --> 00:13:22,400
Och en slips är noll.

245
00:13:22,400 --> 00:13:26,230
Och något som är en förlust för
mig, kanske det är en negativ.

246
00:13:26,230 --> 00:13:29,620
Allt som räknas är att ju bättre
Det är för mig, desto högre poäng

247
00:13:29,620 --> 00:13:32,160
den tar emot.

248
00:13:32,160 --> 00:13:36,690
Från dessa möjligheter på
botten, sedan kommer vi filtrera uppåt.

249
00:13:36,690 --> 00:13:40,650
Och när det är min chans att välja
bland ett antal alternativ,

250
00:13:40,650 --> 00:13:44,460
Jag ska välja det som är
fick den högsta poängen.

251
00:13:44,460 --> 00:13:47,200
>> Och när det är min
motståndare vända sig till välja,

252
00:13:47,200 --> 00:13:52,350
Jag antar att de kommer att
välj en med den lägsta poängen.

253
00:13:52,350 --> 00:13:56,090
Och om jag gör det hela vägen
upp till toppen av trädet,

254
00:13:56,090 --> 00:14:03,150
Jag har valt en väg som ger
mig det bästa resultatet som jag kan få,

255
00:14:03,150 --> 00:14:09,110
förutsatt att min motståndare
gör alla rätt drag.

256
00:14:09,110 --> 00:14:11,940
>> Okej, så låt oss se
detta i aktion först.

257
00:14:11,940 --> 00:14:14,980
Och sedan ska vi faktiskt
titta på koden för den.

258
00:14:14,980 --> 00:14:16,780
Så tänk Jag har denna stora träd.

259
00:14:16,780 --> 00:14:18,280
Och nu jag inte spelar Tre i rad.

260
00:14:18,280 --> 00:14:20,405
Jag ville ge dig
något lite rikare.

261
00:14:20,405 --> 00:14:23,560
Så jag har lite spel där
det finns många olika poäng

262
00:14:23,560 --> 00:14:26,390
att jag kunde ha i slutet.

263
00:14:26,390 --> 00:14:27,980
Och så jag bygga denna kompletta träd.

264
00:14:27,980 --> 00:14:29,070
Och jag får gå först.

265
00:14:29,070 --> 00:14:31,290
Jag är vid roten av trädet.

266
00:14:31,290 --> 00:14:36,150
>> Och jag får välja that-- så får jag
att maximera över denna första noden.

267
00:14:36,150 --> 00:14:38,410
Och sedan min motståndare får gå.

268
00:14:38,410 --> 00:14:41,910
Och då får jag gå en gång.

269
00:14:41,910 --> 00:14:46,830
Så nere på botten, jag har en uppsättning av
möjligheter som jag kan välja mellan,

270
00:14:46,830 --> 00:14:50,570
olika terminal tillstånd av spelet.

271
00:14:50,570 --> 00:14:54,980
Om jag i det
långt vänstra hörnet,

272
00:14:54,980 --> 00:14:58,867
och jag ser att jag har ett val
mellan en åtta, en sju, och en två,

273
00:14:58,867 --> 00:15:00,450
Tja, jag är den som får välja.

274
00:15:00,450 --> 00:15:02,910
Så jag kommer att välja
den bästa av dem.

275
00:15:02,910 --> 00:15:05,650
Jag kommer att välja åtta.

276
00:15:05,650 --> 00:15:10,090
>> Så jag vet att om jag någonsin
komma ner till den punkten,

277
00:15:10,090 --> 00:15:13,890
Jag kommer att kunna få det åtta poäng.

278
00:15:13,890 --> 00:15:17,410
Om jag hamnar på nästa punkt
över, nästa nod över,

279
00:15:17,410 --> 00:15:20,760
en nio, en, eller en sex, ja, jag är
kommer att välja den bästa av dem.

280
00:15:20,760 --> 00:15:21,950
Jag ska välja nio.

281
00:15:21,950 --> 00:15:24,880
Om jag har ett val mellan
två och fyra och en,

282
00:15:24,880 --> 00:15:28,240
Jag ska välja fyra, den högsta.

283
00:15:28,240 --> 00:15:31,990
>> Nu, om jag tittar på den nivå
ovanför det, min motståndare

284
00:15:31,990 --> 00:15:34,440
är man får göra det valet.

285
00:15:34,440 --> 00:15:37,040
Så min motståndare får
välja, vill jag ge honom

286
00:15:37,040 --> 00:15:39,250
det som händer
att få honom åtta poäng,

287
00:15:39,250 --> 00:15:41,916
eller måste jag ge honom det som är
kommer att ge honom nio poäng,

288
00:15:41,916 --> 00:15:45,240
eller det som händer
att ge honom fyra poäng?

289
00:15:45,240 --> 00:15:49,130
Och min motståndare, är
rationell, går

290
00:15:49,130 --> 00:15:53,470
att välja ett minimum av dem,
kommer att välja fyra.

291
00:15:53,470 --> 00:15:56,020
>> Och jag kan göra detta
genom hela trädet.

292
00:15:56,020 --> 00:15:59,110
Jag kan gå ner till den
mitten uppsättning av tre.

293
00:15:59,110 --> 00:16:01,517
Och jag kan välja mellan
en, tre och fem.

294
00:16:01,517 --> 00:16:02,350
Och jag får välja.

295
00:16:02,350 --> 00:16:03,810
Så jag väljer en fem.

296
00:16:03,810 --> 00:16:05,340
Jag kan välja tre, nio, eller två.

297
00:16:05,340 --> 00:16:07,570
Jag får välja, så väljer jag nio.

298
00:16:07,570 --> 00:16:09,290
Sex, fem, eller två, jag väljer.

299
00:16:09,290 --> 00:16:11,539
Jag får välja sex.

300
00:16:11,539 --> 00:16:13,080
Nivå över det, vem som får välja?

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

302
00:16:16,280 --> 00:16:18,140
Vem får välja?

303
00:16:18,140 --> 00:16:20,000
Den andra killen, min motståndare.

304
00:16:20,000 --> 00:16:22,583
Så de väljer fem,
nio eller sex, som en?

305
00:16:22,583 --> 00:16:23,410
>> PUBLIK: De fem.

306
00:16:23,410 --> 00:16:25,250
>> Speak: De väljer de fem.

307
00:16:25,250 --> 00:16:27,400
De får välja ett minimum.

308
00:16:27,400 --> 00:16:29,690
Och sedan sist,
välja en, två, eller tre.

309
00:16:29,690 --> 00:16:31,720
Jag får välja, så jag väljer tre.

310
00:16:31,720 --> 00:16:34,370
Nio, sju, eller två, jag väljer nio.

311
00:16:34,370 --> 00:16:37,070
Och 11, sex eller fyra, jag väljer 11.

312
00:16:37,070 --> 00:16:41,190
Min motståndare väljer sedan tre,
nio, eller 11, väljer ett minimum.

313
00:16:41,190 --> 00:16:43,290
Han ger mig en tre.

314
00:16:43,290 --> 00:16:47,780
Och sedan slutligen på toppen av
trädet, jag får välja igen.

315
00:16:47,780 --> 00:16:51,190
Och jag får välja mellan
en fyra, fem eller tre.

316
00:16:51,190 --> 00:16:52,270
Så jag tar fem.

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

318
00:16:55,070 --> 00:17:00,891
>> Om jag fick styra allt, skulle jag
ta stigen som ledde till 11.

319
00:17:00,891 --> 00:17:02,390
Men jag får inte göra det valet.

320
00:17:02,390 --> 00:17:04,220
Om jag går ner den vägen.

321
00:17:04,220 --> 00:17:10,710
Min motståndare kommer att tvinga mig in
det val som leder till en tre.

322
00:17:10,710 --> 00:17:14,530
Så det bästa som jag kan göra är
att ta den mellersta grenen,

323
00:17:14,530 --> 00:17:19,859
göra det val som är till slut
kommer att leda mig till fem poäng.

324
00:17:19,859 --> 00:17:23,230
Det är vad minimax gör.

325
00:17:23,230 --> 00:17:23,807
>> Okej.

326
00:17:23,807 --> 00:17:24,890
Låt oss ta en titt på det.

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

328
00:17:27,480 --> 00:17:32,330
Så här i CS50
IDE är ett program som

329
00:17:32,330 --> 00:17:36,540
implementerar Minimax att spela Tre i rad.

330
00:17:36,540 --> 00:17:40,100
Vi kommer att bygga
upp en representation.

331
00:17:40,100 --> 00:17:44,390
Vi kommer att ha två opponent--
eller två spelare, vår dator

332
00:17:44,390 --> 00:17:46,090
spelare och en mänsklig spelare.

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

334
00:17:48,980 --> 00:17:53,090
Spelar nummer ett kommer att spela
O. Det ska vara maskin spelaren.

335
00:17:53,090 --> 00:17:55,747
De får flytta andra.

336
00:17:55,747 --> 00:17:57,830
Och den andra spelaren, vår
mänsklig spelare, blir X.

337
00:17:57,830 --> 00:17:59,880
>> Och för att göra mitt liv
liten enkel, jag kommer

338
00:17:59,880 --> 00:18:03,060
för att märka den spelaren negativa ett.

339
00:18:03,060 --> 00:18:05,026
Så jag kan bara föröka
genom negativ en att byta

340
00:18:05,026 --> 00:18:06,400
mellan en spelare och den andra.

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

342
00:18:09,030 --> 00:18:12,250
Okej, så låt oss ta en titt på
vad vi egentligen ska göra.

343
00:18:12,250 --> 00:18:15,840
Vi kommer att definiera vår styrelse.

344
00:18:15,840 --> 00:18:19,060
Det kommer att vara bra, vi kommer
att låta det vara tre av tre,

345
00:18:19,060 --> 00:18:21,580
eller vi kan även spela
fem av fem eller sju

346
00:18:21,580 --> 00:18:28,870
med sju Tre i rad om du skulle
som, baserat på några dimension D.

347
00:18:28,870 --> 00:18:31,260
>> Och vi kommer att ha ett par
av hjälparfunktioner

348
00:18:31,260 --> 00:18:34,360
som kommer att göra saker som
initiera Screen-- eller ledsen,

349
00:18:34,360 --> 00:18:38,900
initiera våra variabler, rensa
skärm, rita styrelsen på skärmen,

350
00:18:38,900 --> 00:18:41,060
en som kontrollerar en styrelse
för att se huruvida

351
00:18:41,060 --> 00:18:44,520
det finns en vinnare, en som
tolkar via kommandoraden,

352
00:18:44,520 --> 00:18:50,670
bara för att hjälpa till, en som läser in
input, och en funktion som kallas minimax.

353
00:18:50,670 --> 00:18:52,746
Och det är en
vi bryr oss mest om.

354
00:18:52,746 --> 00:18:54,120
Men låt oss först titta på de viktigaste.

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

356
00:18:57,490 --> 00:18:58,510
>> Vad gör vi?

357
00:18:58,510 --> 00:19:00,570
Tja, ska vi
tolka vår kommandorad,

358
00:19:00,570 --> 00:19:04,300
bara läsa in och se vad
dimension pension vi skulle vilja ha.

359
00:19:04,300 --> 00:19:07,330
Vi kommer att initiera vår styrelse.

360
00:19:07,330 --> 00:19:10,360
Och då kommer vi in ​​ett
stora vilda slingan, vid upprepade tillfällen

361
00:19:10,360 --> 00:19:16,630
acceptera flyttas tills spelet är
vann, eller det finns några drag kvar.

362
00:19:16,630 --> 00:19:20,560
Varje gång vi går igenom det
loop, kommer vi rensa skärmen.

363
00:19:20,560 --> 00:19:23,290
Vi kommer att dra ombord på skärmen.

364
00:19:23,290 --> 00:19:28,750
Och vi är medvetet sorts
abstrahera bort dessa som subrutiner,

365
00:19:28,750 --> 00:19:32,030
så att vi inte behöver oroa sig alltför mycket
om detaljerna i hur de inträffar.

366
00:19:32,030 --> 00:19:33,480
>> Du har koden senare i dag.

367
00:19:33,480 --> 00:19:37,970
Och om du vill titta igenom
och ta reda på, du kan se dem alla.

368
00:19:37,970 --> 00:19:39,890
Men vi ska dra en styrelse på skärmen.

369
00:19:39,890 --> 00:19:43,620
Och sedan ska vi kontrollera och
se, vi har en vinnare?

370
00:19:43,620 --> 00:19:46,290
Har någon vunnit det här spelet?

371
00:19:46,290 --> 00:19:49,260
Om de har, kommer vi att skriva ut
en seger meddelande.

372
00:19:49,260 --> 00:19:51,680
Och vi kommer att avsluta spelet.

373
00:19:51,680 --> 00:19:54,510
>> Vi kommer även att kontrollera och
se om det finns en slips.

374
00:19:54,510 --> 00:19:56,620
Det ska vara lätt att se om det finns en slips.

375
00:19:56,620 --> 00:20:00,700
Det betyder att alla områden är fulla,
men det har inte varit en vinnare än.

376
00:20:00,700 --> 00:20:03,580
Vi kan förklara en slips och göras.

377
00:20:03,580 --> 00:20:10,530
Då den verkliga meat-- om
Det är en maskin spelare,

378
00:20:10,530 --> 00:20:14,120
Vi kommer att göra det möjligt att
maskin spelare att söka

379
00:20:14,120 --> 00:20:19,500
genom att använda denna minimax algoritm,
att hitta det bästa draget att det kan.

380
00:20:19,500 --> 00:20:22,310
Och sedan ska vi sätta som rör sig upp.

381
00:20:22,310 --> 00:20:27,640
>> Annars om det är en mänsklig spelare,
Vi ska läsa lite input från människa.

382
00:20:27,640 --> 00:20:30,800
Och därefter om det är den mänskliga
spelare eller maskinen spelare,

383
00:20:30,800 --> 00:20:32,800
Vi kommer att göra ett par lite
bitar av felkontroll,

384
00:20:32,800 --> 00:20:36,910
se till att det håller sig inom gränserna
av de faktiska dimensionerna hos brädan

385
00:20:36,910 --> 00:20:40,040
att vi har, se till
att det utrymmet är tomt,

386
00:20:40,040 --> 00:20:43,570
att ingen ens sätta en
bit i det redan.

387
00:20:43,570 --> 00:20:45,810
Och sedan kommer vi bara sätta
en pjäs på brädet,

388
00:20:45,810 --> 00:20:51,550
ändra spelaren till nästa lager, och
öka hur många flyttar har hänt.

389
00:20:51,550 --> 00:20:54,090
>> Det är huvudslingan för
vår Tre i rad spel.

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

391
00:20:57,000 --> 00:21:02,340
Minimax är då exakt
den algoritm som vi tidigare.

392
00:21:02,340 --> 00:21:04,710
Den enda justering som
Vi har gjort så att vi

393
00:21:04,710 --> 00:21:07,290
kan spela högre
dimensionella styrelser är vi har

394
00:21:07,290 --> 00:21:11,070
hålls denna extra parameter som kallas djup.

395
00:21:11,070 --> 00:21:14,870
Och djup bara säger, om jag
söka nedåt genom det trädet

396
00:21:14,870 --> 00:21:19,022
och jag får så långt ner
utöver en viss nivå djup

397
00:21:19,022 --> 00:21:20,730
att jag bara inte vill
att gå vidare,

398
00:21:20,730 --> 00:21:25,630
Jag kommer att stanna upp och bara
utvärdera styrelsen vid den punkten.

399
00:21:25,630 --> 00:21:27,310
Jag ska kolla och se om det finns en vinnare.

400
00:21:27,310 --> 00:21:29,240
Om det finns en vinnare, jag tillbaka dem.

401
00:21:29,240 --> 00:21:31,720
Annars kommer jag att gå igenom en slinga.

402
00:21:31,720 --> 00:21:34,380
Och jag ska säga, för alla
möjliga platser

403
00:21:34,380 --> 00:21:38,080
att jag kunde möjligen
ta så min flytt, jag

404
00:21:38,080 --> 00:21:43,760
bygga en hypotetisk bräda som
innehåller min flytt på kortet,

405
00:21:43,760 --> 00:21:45,960
och sedan rekursivt anropar minimax.

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

407
00:21:49,360 --> 00:21:53,900
>> Om det är min flytt, jag får hitta
en som har fått den största poängen.

408
00:21:53,900 --> 00:21:58,710
Om det är min motståndares drag, finner vi
den som har fått den lägsta poäng.

409
00:21:58,710 --> 00:22:02,240
Och allt annat är
bara bokföring.

410
00:22:02,240 --> 00:22:04,789
Okej, så låt oss se denna körning.

411
00:22:04,789 --> 00:22:06,830
Egentligen kanske vi kan
få ett par frivilliga

412
00:22:06,830 --> 00:22:09,930
att komma upp och spela Tre i rad.

413
00:22:09,930 --> 00:22:12,780
[OHÖRBAR] en och en
mer, två, precis där.

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

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

416
00:22:19,290 --> 00:22:23,650
>> Så låt oss gå vidare och
starta om helt.

417
00:22:23,650 --> 00:22:24,150
Så, hej.

418
00:22:24,150 --> 00:22:24,920
>> PUBLIK: Hej.

419
00:22:24,920 --> 00:22:25,420
>> Speak: Vad heter du?

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

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

422
00:22:26,840 --> 00:22:27,800
>> PUBLIK: Jag är Layla.

423
00:22:27,800 --> 00:22:29,490
>> Speak: Och Layla och Layla, sorry.

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

425
00:22:30,384 --> 00:22:32,050
Gorav, vi kommer att ha dig gå först.

426
00:22:32,050 --> 00:22:37,710
Och jag kommer att be er att vara en icke
fruktansvärt bra Tre i rad spelare.

427
00:22:37,710 --> 00:22:40,130
OK, så all press är avstängd på dig.

428
00:22:40,130 --> 00:22:44,660
Låt oss se, men att vår maskin
spelare kan faktiskt göra något smart.

429
00:22:44,660 --> 00:22:45,310
Så gå vidare.

430
00:22:45,310 --> 00:22:49,830
Du kommer att skriva in som samordnar
du vill sätta din X.

431
00:22:49,830 --> 00:22:55,170
A0, OK, och maskinen har gått
direkt och sätter sin prägel på A1.

432
00:22:55,170 --> 00:22:56,640
>> Placera O på tavlan.

433
00:22:56,640 --> 00:22:58,970
Okej, nu gå vidare.

434
00:22:58,970 --> 00:23:00,193
Vart skulle du vilja gå?

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
Vår maskin spelare har tagit
i mitten torget, blockerat dig.

438
00:23:08,430 --> 00:23:10,320
Så det var en bra,
smart sak för att det ska göra.

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

440
00:23:13,430 --> 00:23:14,250
Du har blockerat det.

441
00:23:14,250 --> 00:23:15,210
Det är utmärkt.

442
00:23:15,210 --> 00:23:16,390
Det tar hörnet där.

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

444
00:23:23,890 --> 00:23:30,430
>> Och det kommer att tvinga dig att
ta en sista plats, B0.

445
00:23:30,430 --> 00:23:32,220
Och matchen slutar oavgjort.

446
00:23:32,220 --> 00:23:35,030
Men det spelade en rimlig
match mot dig, eller hur?

447
00:23:35,030 --> 00:23:36,956
Okej, tack så mycket, Gorav.

448
00:23:36,956 --> 00:23:40,860
>> [APPLÅDER]

449
00:23:40,860 --> 00:23:44,723
>> Okej, Layla, vi kommer
upp spelet på dig här.

450
00:23:44,723 --> 00:23:46,940
>> Målgrupp: Åh, bra.

451
00:23:46,940 --> 00:23:49,950
>> Speak: Vi kommer att ge
du fyra av fyra Tre i rad.

452
00:23:49,950 --> 00:23:54,760
Nu, i fyra av fyra, måste du vinna
med fyra i rad, inte tre i rad.

453
00:23:54,760 --> 00:23:56,135
Och det är din.

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

455
00:24:02,180 --> 00:24:04,420
Så Layla tog D1.

456
00:24:04,420 --> 00:24:11,730
Vi bevakar nu kommer att följa
vår dator spelare här.

457
00:24:11,730 --> 00:24:16,910
Tre av tre tic-tac-toe är den typ
saker som är lätt för oss alla.

458
00:24:16,910 --> 00:24:21,960
Men det är ändå trevligt att se
datorspelare att göra smarta drag.

459
00:24:21,960 --> 00:24:23,725
Fyra av fyra får
vara lite svårare.

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

461
00:24:42,960 --> 00:24:44,230
>> Snyggt gjort.

462
00:24:44,230 --> 00:24:46,210
Okej, så Layla är avslutade.

463
00:24:46,210 --> 00:24:48,270
Åh, och vi borde ha tagit slut där.

464
00:24:48,270 --> 00:24:51,870
Men låt oss göra ett mer här uppe.

465
00:24:51,870 --> 00:24:53,480
Så Layla, tack.

466
00:24:53,480 --> 00:24:55,112
Snyggt gjort.

467
00:24:55,112 --> 00:24:57,517
>> [APPLÅDER]

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

469
00:25:00,410 --> 00:25:04,750
>> Så vår Tre i rad spelare går
genom och finner platser,

470
00:25:04,750 --> 00:25:07,040
löser dem med denna minimax.

471
00:25:07,040 --> 00:25:08,990
Och jag hade en djupinställning
på den, så att den

472
00:25:08,990 --> 00:25:11,010
skulle inte köra för fort,
vilket förmodligen är anledningen

473
00:25:11,010 --> 00:25:16,790
Layla kunde gå fint i förväg
som hon gjorde, och gjorde mycket bra.

474
00:25:16,790 --> 00:25:20,450
Men dessa system som bara
gå igenom och råstyrka

475
00:25:20,450 --> 00:25:23,870
gå djupare och djupare, och djupare,
och hålla hitta lösningen

476
00:25:23,870 --> 00:25:29,890
att de behöver dessa typer av system
är ganska framgångsrika på dessa, ja,

477
00:25:29,890 --> 00:25:32,700
vanliga brädspel.

478
00:25:32,700 --> 00:25:37,060
>> Och i själva verket, om vi tittar på en
tre med tre Tre i rad spel,

479
00:25:37,060 --> 00:25:40,040
detta är i grunden en löst problem.

480
00:25:40,040 --> 00:25:45,430
Och detta är en underbar diagram
från Randall Munroe på XKCD,

481
00:25:45,430 --> 00:25:52,130
visar vilka flyttar du bör
ta, med tanke på din motståndares drag.

482
00:25:52,130 --> 00:25:56,420
Detta är något som vi kunde
enkelt ange i förväg.

483
00:25:56,420 --> 00:26:00,180
Men vad som händer när vi får mer
komplexa spel, mer intrikata spel,

484
00:26:00,180 --> 00:26:05,690
där det finns större styrelser, mer
möjligheter, djupare strategi?

485
00:26:05,690 --> 00:26:09,660
>> Det visar sig att detta
brute force söka fortfarande

486
00:26:09,660 --> 00:26:14,150
gör ganska bra, utom
när du kommer till den punkt

487
00:26:14,150 --> 00:26:19,230
där trädet är så stort
att du inte kan representera allt.

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

489
00:26:22,370 --> 00:26:28,280
När du inte kan beräkna hela trädet,
när du inte kan gå framåt och tryck

490
00:26:28,280 --> 00:26:32,204
själv till den punkt där du har
fått hela trädet i minnet,

491
00:26:32,204 --> 00:26:34,370
eller om du kan få det
i minnet och det kommer bara

492
00:26:34,370 --> 00:26:39,200
ta dig alldeles för lång tid att söka igenom
det, måste du göra något smartare.

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

494
00:26:42,620 --> 00:26:46,450
>> För att göra det, du
måste göra två saker.

495
00:26:46,450 --> 00:26:49,030
Först måste du hitta några
sätt att begränsa din djup.

496
00:26:49,030 --> 00:26:50,370
Tja, det är OK.

497
00:26:50,370 --> 00:26:55,740
Vi kan hitta några trevliga, minimum
och säga, du kan bara gå så djupt.

498
00:26:55,740 --> 00:27:00,890
Men när du gör det, betyder att du
har dessa delvis ofullständiga styrelser.

499
00:27:00,890 --> 00:27:04,770
Och du måste välja, jag gillar
detta delvis ofullständig styrelse,

500
00:27:04,770 --> 00:27:08,600
eller detta delvis ofullständiga ombord?

501
00:27:08,600 --> 00:27:11,910
>> Och på våra fyra av
fyra Tre i rad spel,

502
00:27:11,910 --> 00:27:15,240
vår dator spelare kom ner
till botten och det sa,

503
00:27:15,240 --> 00:27:16,800
Jag har två olika styrelser.

504
00:27:16,800 --> 00:27:17,940
Varken ett är en seger.

505
00:27:17,940 --> 00:27:19,120
Varken ett är en förlust.

506
00:27:19,120 --> 00:27:22,070
Varken ett är en slips.

507
00:27:22,070 --> 00:27:24,100
Hur väljer jag mellan dem?

508
00:27:24,100 --> 00:27:26,200
Och det inte har en
smart sätt att göra det.

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

510
00:27:28,910 --> 00:27:32,850
>> Vi ser den här typen av
utvärderingen sker hela tiden

511
00:27:32,850 --> 00:27:35,290
som vi får in mer komplexa spel.

512
00:27:35,290 --> 00:27:37,600
Chess är ett bra exempel.

513
00:27:37,600 --> 00:27:41,550
I schack, vi har, först
av allt, en större bräda.

514
00:27:41,550 --> 00:27:43,370
Vi har betydligt fler bitar.

515
00:27:43,370 --> 00:27:47,930
Och placeringen av dessa bitar
och det sätt som dessa bitar flytta

516
00:27:47,930 --> 00:27:50,370
är mycket viktigt.

517
00:27:50,370 --> 00:27:53,700
Så om jag vill använda minimax,
Jag måste kunna ange

518
00:27:53,700 --> 00:27:58,240
och säga, detta forum, där
ingen har vunnit eller förlorat ännu,

519
00:27:58,240 --> 00:28:04,310
är något bättre än denna andra
styrelse, där ingen har vunnit eller förlorat.

520
00:28:04,310 --> 00:28:06,740
>> För att göra det, kan jag göra
saker som jag kanske bara

521
00:28:06,740 --> 00:28:10,787
räkna hur många bitar har jag
och hur många bitar har du?

522
00:28:10,787 --> 00:28:12,870
Eller jag kan ge olika
pieces olika punkter.

523
00:28:12,870 --> 00:28:14,420
Min drottning är värd 20 poäng.

524
00:28:14,420 --> 00:28:16,500
Din bonde är värda en poäng.

525
00:28:16,500 --> 00:28:18,920
Vem har fler poäng totalt?

526
00:28:18,920 --> 00:28:22,300
Eller jag kanske överväga saker som,
som har fått bättre styrelsen position?

527
00:28:22,300 --> 00:28:26,820
Vems tur är det nästa,
något som jag kan

528
00:28:26,820 --> 00:28:31,220
göra för att mer exakt utvärdera
vilken av dessa möjligheter

529
00:28:31,220 --> 00:28:34,660
är bättre utan
uttömmande väger

530
00:28:34,660 --> 00:28:36,565
varje rörelse som kan komma efter det.

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

532
00:28:39,740 --> 00:28:45,130
>> Nu för att göra detta arbete,
en av de saker som är

533
00:28:45,130 --> 00:28:48,680
kommer att bli mycket viktigt
för oss är inte bara flytta rakt

534
00:28:48,680 --> 00:28:53,720
ned till ett visst djup
gräns, men att kunna säga,

535
00:28:53,720 --> 00:28:59,380
en av dessa idéer som jag
har är så dåligt att det är

536
00:28:59,380 --> 00:29:02,280
inte värt att överväga
alla möjliga sätt

537
00:29:02,280 --> 00:29:06,680
att saker och ting kan gå från dåligt till värre.

538
00:29:06,680 --> 00:29:12,760
För att göra det, kommer vi att lägga in minimax
en princip som kallas alph-beta.

539
00:29:12,760 --> 00:29:16,340
Och alfa-beta säger,
om du har en dålig idé,

540
00:29:16,340 --> 00:29:22,840
slösa inte din tid på att försöka
ta reda på exakt hur illa det är.

541
00:29:22,840 --> 00:29:24,990
>> Så här är vad vi ska göra.

542
00:29:24,990 --> 00:29:28,620
Vi kommer att ta samma
principer som vi hade tidigare,

543
00:29:28,620 --> 00:29:32,200
samma minimax typ
av sök, bara vi är

544
00:29:32,200 --> 00:29:37,570
kommer hålla koll, inte bara i förhållande
faktiska värden som vi har, men vi ska

545
00:29:37,570 --> 00:29:41,440
hålla reda på den bästa möjliga
värde som jag kunde få,

546
00:29:41,440 --> 00:29:45,700
och sämsta möjliga
utfall jag kunde ha.

547
00:29:45,700 --> 00:29:50,470
Och varje gång det värsta möjliga
sak ser sannolikt,

548
00:29:50,470 --> 00:29:52,694
Jag ska överge denna del av trädet.

549
00:29:52,694 --> 00:29:54,610
Och jag kommer inte ens bry
titta på det längre.

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

551
00:29:57,680 --> 00:30:02,600
>> Okej, så föreställa sig att vi börjar
med samma exakta spelträdet.

552
00:30:02,600 --> 00:30:05,200
Och nu ska vi gå
ner igen, hela vägen ner

553
00:30:05,200 --> 00:30:07,200
till det nedre vänstra hörnet.

554
00:30:07,200 --> 00:30:11,180
Och i det nedre vänstra hörnet, vi
titta och vi utvärderar detta forum.

555
00:30:11,180 --> 00:30:15,700
Kanske är det en fyra av fyra Tre i rad
ombord, eller kanske är det ett schackbräde.

556
00:30:15,700 --> 00:30:18,620
Men vi ser på det, och vi utvärderar
det, och vi får ett värde på åtta.

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

558
00:30:22,290 --> 00:30:28,030
>> Vid den tidpunkten, vi vet att
Vi kommer att få åtminstone

559
00:30:28,030 --> 00:30:32,380
åtta poäng från denna botten beslut.

560
00:30:32,380 --> 00:30:36,620
Det spelar ingen roll vad den andra
två är att sju och att två.

561
00:30:36,620 --> 00:30:38,580
De kan vara några värden
de ville vara.

562
00:30:38,580 --> 00:30:41,279
Vi kommer att komma åt
minst åtta poäng.

563
00:30:41,279 --> 00:30:43,070
Okej, men vi kunde
gå vidare och kolla.

564
00:30:43,070 --> 00:30:45,080
Kanske en av dem är bättre än åtta.

565
00:30:45,080 --> 00:30:46,000
>> Vi tittar på sju.

566
00:30:46,000 --> 00:30:46,910
Är det bättre än åtta?

567
00:30:46,910 --> 00:30:48,680
Nej, det ändrar
vår åsikt alls.

568
00:30:48,680 --> 00:30:49,460
Vi tittar på de två.

569
00:30:49,460 --> 00:30:50,543
Är det bättre än åtta?

570
00:30:50,543 --> 00:30:52,580
Nej, det ändrar
vår åsikt alls.

571
00:30:52,580 --> 00:30:55,480
Så nu vet vi att vi har uttömt
alla möjligheter där.

572
00:30:55,480 --> 00:30:58,330
Vi kommer inte att få
något bättre än åtta.

573
00:30:58,330 --> 00:31:01,310
Vi kommer att få exakt åtta.

574
00:31:01,310 --> 00:31:03,825
>> Och så vi ändra på det nod och
säg, är det nu en visshet.

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

576
00:31:07,010 --> 00:31:10,270
Vi går upp en nivå ovanför det.

577
00:31:10,270 --> 00:31:13,820
Och nu vet vi något
om det minimering nivå.

578
00:31:13,820 --> 00:31:18,560
Vi vet att vi aldrig kommer att få
mer än åtta poäng om vi går ner

579
00:31:18,560 --> 00:31:20,910
den riktningen.

580
00:31:20,910 --> 00:31:22,980
För även om de
två andra grenar sig

581
00:31:22,980 --> 00:31:26,170
att vara fantastiskt och värt
tusentals poäng vardera,

582
00:31:26,170 --> 00:31:31,666
vår motståndare kommer att ge oss
minimum, och ge oss åtta.

583
00:31:31,666 --> 00:31:32,790
Okej, låt oss se.

584
00:31:32,790 --> 00:31:35,190
Vi kommer att fortsätta på den inslagna vägen.

585
00:31:35,190 --> 00:31:38,490
Vi går ner till den mitten till vänster.

586
00:31:38,490 --> 00:31:40,560
Vi tittar ner och vi ser att det finns en nio.

587
00:31:40,560 --> 00:31:45,590
Vi vet att vi kommer att få
åtminstone nio poäng genom att gå ned

588
00:31:45,590 --> 00:31:47,720
den mellersta vägen.

589
00:31:47,720 --> 00:31:52,110
Och på denna punkt, kan vi bara pausa.

590
00:31:52,110 --> 00:31:56,910
Och vi kan säga, titta, jag
har nivån ovanför,

591
00:31:56,910 --> 00:32:01,160
Jag kommer att få mer än åtta
pekar genom att gå ned denna riktning.

592
00:32:01,160 --> 00:32:05,670
Men om jag gick i mitten
bana i stället för vänster väg,

593
00:32:05,670 --> 00:32:08,980
Jag skulle få minst nio poäng.

594
00:32:08,980 --> 00:32:13,590
>> Min motståndare aldrig kommer att
Låt mig gå den medelväg.

595
00:32:13,590 --> 00:32:14,650
De får välja.

596
00:32:14,650 --> 00:32:18,140
Och de kommer att välja
sökväg till vänster mot åtta,

597
00:32:18,140 --> 00:32:23,650
snarare än i mitten mot
vad är minst nio poäng.

598
00:32:23,650 --> 00:32:25,334
Så på den punkten, ska jag sluta.

599
00:32:25,334 --> 00:32:26,500
Och jag ska säga, vet du vad?

600
00:32:26,500 --> 00:32:29,990
Jag behöver inte se någon
mer ner i den riktningen.

601
00:32:29,990 --> 00:32:32,270
Eftersom jag aldrig kommer att komma dit.

602
00:32:32,270 --> 00:32:36,660
>> Jag kan hoppa över att man,
och jag kan hoppa över att sex,

603
00:32:36,660 --> 00:32:39,720
eftersom det aldrig kommer att hända.

604
00:32:39,720 --> 00:32:42,470
Så jag ska gå ner och jag ska
överväga nästa möjlighet.

605
00:32:42,470 --> 00:32:44,830
Jag åker dit ner och jag säger, jag ser en två.

606
00:32:44,830 --> 00:32:47,125
Jag vet inte om jag får här, jag är
kommer att få åtminstone två.

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
Jag fortsätta.

610
00:32:51,520 --> 00:32:52,440
Jag ser en fyra.

611
00:32:52,440 --> 00:32:54,920
Jag vet att jag kommer att få minst fyra.

612
00:32:54,920 --> 00:32:57,200
Det finns fortfarande en hel del mellan
fyra och åtta, men.

613
00:32:57,200 --> 00:32:58,454
Så jag fortsätta.

614
00:32:58,454 --> 00:32:59,870
Jag tittar ner och jag ser det finns en.

615
00:32:59,870 --> 00:33:01,614
Okej, jag vet om
Jag går denna väg,

616
00:33:01,614 --> 00:33:03,280
Jag kommer att kunna välja fyra.

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

618
00:33:06,540 --> 00:33:08,980
Vad är min motståndare kommer att göra?

619
00:33:08,980 --> 00:33:12,310
Mellan något som ger mig
åtta, något som ger mig fyra,

620
00:33:12,310 --> 00:33:14,730
och något som
ger mig åtminstone nio,

621
00:33:14,730 --> 00:33:17,550
Tja, han kommer att ge mig fyra.

622
00:33:17,550 --> 00:33:20,110
Och jag vet nu på
högst upp, jag ska

623
00:33:20,110 --> 00:33:23,145
att kunna få åtminstone
fyra poäng av detta spel.

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

625
00:33:27,030 --> 00:33:30,900
>> Hela idén med alfa-beta
är att skära av delar trädet så

626
00:33:30,900 --> 00:33:32,530
att jag inte titta på dem längre.

627
00:33:32,530 --> 00:33:35,964
Men det fortfarande ser ut som jag har varit
tittar på en hel del av trädet.

628
00:33:35,964 --> 00:33:36,880
Låt oss hålla gå ned.

629
00:33:36,880 --> 00:33:38,305
Vi ska gå ner nästa nu.

630
00:33:38,305 --> 00:33:39,680
Nere på botten, jag hittar en.

631
00:33:39,680 --> 00:33:41,030
Jag vet att jag kommer att få åtminstone en.

632
00:33:41,030 --> 00:33:41,690
Jag hålla ute.

633
00:33:41,690 --> 00:33:42,625
>> Jag hittar en tre.

634
00:33:42,625 --> 00:33:44,250
Jag vet att jag kommer att få minst tre.

635
00:33:44,250 --> 00:33:44,840
Jag fortsätta.

636
00:33:44,840 --> 00:33:45,660
Jag hittar en fem.

637
00:33:45,660 --> 00:33:49,760
Jag vet att jag kommer att få fem
om jag får ner i den vägen.

638
00:33:49,760 --> 00:33:52,580
Och jag vet också sedan
att min motståndare, om jag

639
00:33:52,580 --> 00:33:55,510
välja mitten av
de tre stora val,

640
00:33:55,510 --> 00:34:01,440
han kommer att ge mig
något som är fem eller mindre.

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

642
00:34:02,150 --> 00:34:03,400
Jag kan fortsätta där.

643
00:34:03,400 --> 00:34:06,470
Jag kan titta ner och jag
kan säga, vad ska jag

644
00:34:06,470 --> 00:34:08,239
att få om jag går ner i medelväg?

645
00:34:08,239 --> 00:34:09,909
Jag kommer att få, väl, tre där.

646
00:34:09,909 --> 00:34:12,080
Jag kommer att få något
som är minst tre.

647
00:34:12,080 --> 00:34:16,030
Det finns fortfarande saker mellan
tre och fem, så jag hålla ute.

648
00:34:16,030 --> 00:34:20,203
Åh, en nio, jag ska definitivt
ta det över en tre.

649
00:34:20,203 --> 00:34:22,744
Jag kommer att få minst nio
om jag går ner den medelväg.

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

651
00:34:25,530 --> 00:34:31,010
>> Nu stannar och säger min motståndare,
titta, det är ingen idé längre.

652
00:34:31,010 --> 00:34:33,669
Jag vet att min
minimering motståndare, han

653
00:34:33,669 --> 00:34:36,210
kommer att ge mig det som är
mindre än eller lika med fem,

654
00:34:36,210 --> 00:34:39,030
snarare än det som är
större än eller lika med nio.

655
00:34:39,030 --> 00:34:39,530
Jag stannar.

656
00:34:39,530 --> 00:34:40,779
Jag ser inte något mer på det.

657
00:34:40,779 --> 00:34:43,280
Jag fortsätta.

658
00:34:43,280 --> 00:34:44,850
>> Jag tittar ner på detta.

659
00:34:44,850 --> 00:34:46,370
Ner till botten, jag hittar en sex.

660
00:34:46,370 --> 00:34:50,040
Jag vet att jag kommer att få minst sex.

661
00:34:50,040 --> 00:34:53,130
Och vad kan jag göra?

662
00:34:53,130 --> 00:34:54,877
Jag kan sluta.

663
00:34:54,877 --> 00:34:57,460
Eftersom det är ett val mellan
något som är minst sex

664
00:34:57,460 --> 00:34:59,250
och något som är
mindre än fem, han

665
00:34:59,250 --> 00:35:02,570
kommer att ge mig saken
som är mindre än fem.

666
00:35:02,570 --> 00:35:04,779
Och nu vet jag att jag kommer
att få exakt det valet.

667
00:35:04,779 --> 00:35:06,195
Jag kommer att få det fem val.

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

669
00:35:08,980 --> 00:35:10,010
>> Jag går tillbaka upp till toppen.

670
00:35:10,010 --> 00:35:11,450
Som jag kommer att
välja mellan något

671
00:35:11,450 --> 00:35:14,449
det är större än eller lika med fyra,
eller något som är lika med fem?

672
00:35:14,449 --> 00:35:17,140
Jag kommer att ta något
som är minst fem.

673
00:35:17,140 --> 00:35:20,490
Jag går ner den sista banan, alla
vägen ner till botten.

674
00:35:20,490 --> 00:35:21,260
Det finns en en.

675
00:35:21,260 --> 00:35:23,410
OK, åtminstone jag kommer att få en poäng.

676
00:35:23,410 --> 00:35:24,427
Jag fortsätta.

677
00:35:24,427 --> 00:35:25,760
Två, åh, det är bättre än en.

678
00:35:25,760 --> 00:35:27,100
Jag kommer att få åtminstone två.

679
00:35:27,100 --> 00:35:28,610
Jag hittar en tre.

680
00:35:28,610 --> 00:35:31,450
Jag vet att jag kommer att få tre.

681
00:35:31,450 --> 00:35:34,690
>> Och punkten ovan att
min motståndare kommer

682
00:35:34,690 --> 00:35:38,540
ge mig något som är
mindre än eller lika med tre.

683
00:35:38,540 --> 00:35:40,940
Och nu kan jag sluta.

684
00:35:40,940 --> 00:35:46,290
På grund i valet mellan att jag är
kunna få en fem och min motståndare

685
00:35:46,290 --> 00:35:52,290
ge mig något mindre än tre,
Jag kommer alltid att ta det fem.

686
00:35:52,290 --> 00:35:56,810
Så jag inte bedöma det
nedre delen av trädet alls.

687
00:35:56,810 --> 00:35:59,470
>> Nu kan detta verka mindre.

688
00:35:59,470 --> 00:36:03,630
Men när små bitar av aritmetik,
större än och mindre än,

689
00:36:03,630 --> 00:36:10,640
kan skära bort hela delar av
detta exponentiellt växande träd,

690
00:36:10,640 --> 00:36:14,280
som leder till en enorm
mängd besparingar, besparingar

691
00:36:14,280 --> 00:36:17,630
som är stora nog att jag
kan börja spela konkurrenskraftigt

692
00:36:17,630 --> 00:36:21,330
fler komplexa spel.

693
00:36:21,330 --> 00:36:27,030
>> Okej, om vi tittar på storleken
och komplexitet olika spel,

694
00:36:27,030 --> 00:36:29,470
Tre i rad var vår enkla exempel.

695
00:36:29,470 --> 00:36:32,150
Vi har en liten styrelse, tre och tre.

696
00:36:32,150 --> 00:36:36,030
Vi får på sin höjd, i genomsnitt
cirka fyra olika val

697
00:36:36,030 --> 00:36:38,440
när vi går igenom spelet.

698
00:36:38,440 --> 00:36:42,720
Vi har någonstans runt 10 till
femte möjliga olika blad.

699
00:36:42,720 --> 00:36:45,200
Och bygga en Tre i rad
spelare, ja, bara vi gjorde det.

700
00:36:45,200 --> 00:36:47,460
Det är lätt.

701
00:36:47,460 --> 00:36:49,890
>> Om vi ​​går upp till något mer
komplex, som Connect Four.

702
00:36:49,890 --> 00:36:53,170
Minns du det här spelet där
du tappar de små polletter i?

703
00:36:53,170 --> 00:36:58,490
Det är en sex av sju ombord,
inte så mycket större, fortfarande

704
00:36:58,490 --> 00:37:00,770
har ungefär samma förgrening
faktor som Tre i rad.

705
00:37:00,770 --> 00:37:05,410
Jag har ungefär fyra val
där jag kan lägga saker i.

706
00:37:05,410 --> 00:37:10,760
Men nu har jag fått en hel del mer
leder, 10 till den 21: strömmen.

707
00:37:10,760 --> 00:37:14,440
Det är något som är lätt
nog att vi lösa det direkt.

708
00:37:14,440 --> 00:37:17,560
>> Pjäser, mer complex-- du
fick en åtta med åtta styrelse.

709
00:37:17,560 --> 00:37:20,570
Du är bara hälften av
dem när som helst, dock.

710
00:37:20,570 --> 00:37:24,930
Du har en förgrening
faktor som är ca 2,8.

711
00:37:24,930 --> 00:37:28,160
Tja, vi har ett par
flyttar du kan ta.

712
00:37:28,160 --> 00:37:33,870
Du har cirka 10 till 31 blad,
större och större, och större utrymmen.

713
00:37:33,870 --> 00:37:37,340
Som jag måste söka igenom
de större och större utrymmen,

714
00:37:37,340 --> 00:37:42,220
det är då saker som alfa-beta och
att kunna skära bort hela grenar

715
00:37:42,220 --> 00:37:44,420
blir avgörande.

716
00:37:44,420 --> 00:37:47,440
>> Nu, pjäser var lätt nog 1992.

717
00:37:47,440 --> 00:37:51,400
Ett datorprogram som kallas
Chinook slå världs pjäser

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

719
00:37:53,590 --> 00:37:57,260
Och sedan dess, ingen
mänsklig mästare spelare har

720
00:37:57,260 --> 00:38:02,290
kunnat slå de bästa
beräkningssystem.

721
00:38:02,290 --> 00:38:06,570
Om vi ​​tittar på något som schack, nu
igen, har vi en åtta med åtta styrelse.

722
00:38:06,570 --> 00:38:09,870
Men vi har mycket mer komplex
bitar, mycket mer komplexa rörelser.

723
00:38:09,870 --> 00:38:14,610
Vi har en förgreningsfaktor av ca
35, 35 möjliga drag i genomsnitt

724
00:38:14,610 --> 00:38:20,030
att jag kan ta, och en stat
utrymme, ett antal blad

725
00:38:20,030 --> 00:38:28,950
som har vuxit till 10 till 123. makt,
enormt antal möjligheter.

726
00:38:28,950 --> 00:38:35,570
>> Även fortfarande moderna processorer
har möjlighet att göra detta framgångsrikt.

727
00:38:35,570 --> 00:38:43,900
Under 1995 och sedan 1997, en dator
program som heter Deep Blue byggdes av IBM

728
00:38:43,900 --> 00:38:49,601
som körde på en gigantisk superdator
slå den nuvarande världsmästare,

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

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

731
00:38:54,000 --> 00:38:56,650
Detta var en vändpunkt.

732
00:38:56,650 --> 00:39:00,620
Men i dag, samma behandling
makt sitter på min MacBook.

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

734
00:39:04,180 --> 00:39:06,440
>> Behandlingshastigheten håller
blir snabbare och snabbare.

735
00:39:06,440 --> 00:39:09,500
Vi kan utvärdera mer och mer
styrelser snabbare och snabbare.

736
00:39:09,500 --> 00:39:14,550
Men ännu viktigare, har vi bättre
utvärderingsfunktioner och bättre beskärning

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

738
00:39:15,460 --> 00:39:19,560
Så vi kan söka
utrymmet mer komplext.

739
00:39:19,560 --> 00:39:22,350
Den största av styrelsen
spel som vi kan tänka på,

740
00:39:22,350 --> 00:39:26,310
något liknande Go som är
fick en 19 med 19 ombord,

741
00:39:26,310 --> 00:39:32,490
nu plötsligt är vi förbi den punkt
där beräkningssystem kan vinna.

742
00:39:32,490 --> 00:39:34,530
Det finns ingen beräknings
systemet där ute

743
00:39:34,530 --> 00:39:38,880
som kan slå en professionell Go spelare.

744
00:39:38,880 --> 00:39:45,000
Det bästa system idag rang det om
den typ av god amatörnivå.

745
00:39:45,000 --> 00:39:49,285
Så det finns fortfarande en hel del ut
det att du inte kan få ännu.

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

747
00:39:51,840 --> 00:39:55,360
>> Okej, dessa
traditionella brädspel,

748
00:39:55,360 --> 00:39:58,560
dessa typer av system där vi
bygga denna minimax, oavsett om det har fått

749
00:39:58,560 --> 00:40:06,300
alfa-beta eller ej, dessa algoritmer fungerar
eftersom det finns vissa begränsningar.

750
00:40:06,300 --> 00:40:08,520
Vi har perfekt information
om världen.

751
00:40:08,520 --> 00:40:11,690
Vi vet var alla bitar är.

752
00:40:11,690 --> 00:40:13,570
Världen är statisk.

753
00:40:13,570 --> 00:40:16,220
Ingen får flytta
delar runt medan jag är

754
00:40:16,220 --> 00:40:20,640
sitter där och tänkte, tar min tur.

755
00:40:20,640 --> 00:40:23,140
Det finns en åtgärd utrymme som är diskret.

756
00:40:23,140 --> 00:40:26,900
Jag kan sätta min bonde här,
eller jag kan sätta min bonde här.

757
00:40:26,900 --> 00:40:30,520
Jag är inte tillåtet att sätta min bonde på
linjen mellan de två rutorna.

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

759
00:40:34,430 --> 00:40:36,520
>> Och slutligen, de åtgärder
är deterministisk.

760
00:40:36,520 --> 00:40:39,790
Jag vet att om jag säger,
torn till riddare tre,

761
00:40:39,790 --> 00:40:44,660
min torn kommer att hamna på riddare
tre, så länge det är ett giltigt drag.

762
00:40:44,660 --> 00:40:47,830
Det finns ingen osäkerhet om det.

763
00:40:47,830 --> 00:40:52,490
Nu, när jag går till mer
olika typer av spel,

764
00:40:52,490 --> 00:40:55,960
Vi måste bryta dessa antaganden.

765
00:40:55,960 --> 00:41:00,020
>> Vad händer om jag går till något
som klassiska videospel?

766
00:41:00,020 --> 00:41:04,180
Här är ett urval av video
spel från Atari 2600.

767
00:41:04,180 --> 00:41:05,180
Vad har jag där uppe?

768
00:41:05,180 --> 00:41:08,440
Jag har Frogger, Space
Invaders, Fallgrop, och Pac-Man.

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

770
00:41:11,290 --> 00:41:14,840
Vilka typer av miljöer
har jag här nu?

771
00:41:14,840 --> 00:41:16,900
Vilken av dessa antaganden
måste jag bryta?

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

773
00:41:19,410 --> 00:41:21,570
>> Tja, det beror på spelet.

774
00:41:21,570 --> 00:41:28,170
Jag kunde spela schack på 2600, och
det skulle vara precis som det var innan.

775
00:41:28,170 --> 00:41:33,020
För de flesta av dessa system, det finns
fullständig kunskap om världen.

776
00:41:33,020 --> 00:41:36,300
Det är helt
deterministiska åtgärder.

777
00:41:36,300 --> 00:41:38,330
Men oftast, världens
inte längre statisk.

778
00:41:38,330 --> 00:41:41,970
Det är, medan jag sitter där
väntar, är något som rör sig.

779
00:41:41,970 --> 00:41:44,320
De spöken kommer att få mig.

780
00:41:44,320 --> 00:41:46,570
Skorpionen följer mig under.

781
00:41:46,570 --> 00:41:48,880
Space Invaders är
kommer närmare och närmare.

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

783
00:41:54,020 --> 00:41:55,510
Hur väl kan vi göra mot dessa?

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

785
00:41:58,640 --> 00:42:02,790
>> För några år sedan, Google
hade ett projekt som kallas

786
00:42:02,790 --> 00:42:12,030
DeepMind, där de utbildade en dator
program för att spela Atari 2600 spel.

787
00:42:12,030 --> 00:42:16,120
Och om du tror att detta är inte seriöst
affärer, resultaten av sin studie

788
00:42:16,120 --> 00:42:19,920
publicerades i Nature, så
nästan lika bra en publikation

789
00:42:19,920 --> 00:42:22,500
som man kan komma.

790
00:42:22,500 --> 00:42:24,340
Och här är hur väl de utfört.

791
00:42:24,340 --> 00:42:29,220
>> De har en algoritm som satt
och tittade bara på skärmen ingångarna.

792
00:42:29,220 --> 00:42:34,080
Det fick inga instruktioner som helst
om spelreglerna.

793
00:42:34,080 --> 00:42:42,610
Och det var tänkt att räkna ut,
grundat sin värdering, hur bra det gjorde.

794
00:42:42,610 --> 00:42:46,560
Detta var ett system som används något
kallas förstärkning lärande.

795
00:42:46,560 --> 00:42:48,380
Det vill säga, det såg ut på sin poäng.

796
00:42:48,380 --> 00:42:51,620
Och om det blev en bra poäng, sa det,
Jag bör komma ihåg dessa saker.

797
00:42:51,620 --> 00:42:53,310
Och jag skulle göra dem igen.

798
00:42:53,310 --> 00:42:56,450
Och om det blev ett lågt betyg, sade det,
Jag ska inte göra dessa saker igen.

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

800
00:42:59,750 --> 00:43:03,430
>> Detta är resultatet
av dessa utbildade system

801
00:43:03,430 --> 00:43:07,490
tillåtet att spela för en
några timmar på varje spel,

802
00:43:07,490 --> 00:43:12,490
jämförs med professionella spelare.

803
00:43:12,490 --> 00:43:19,670
Så för alla de spel som finns
till den vänstra sidan av denna linje,

804
00:43:19,670 --> 00:43:25,920
denna själv utbildad datorprogram
överträffade professionella spelare.

805
00:43:25,920 --> 00:43:29,690
Och för allt till
höger, de professionella spelare

806
00:43:29,690 --> 00:43:30,920
fortfarande var bäst.

807
00:43:30,920 --> 00:43:34,040

808
00:43:34,040 --> 00:43:36,850
För något som visste
ingenting om reglerna, att

809
00:43:36,850 --> 00:43:43,020
visste ingenting om struktur
spel, är detta imponerande prestanda.

810
00:43:43,020 --> 00:43:45,660
Och detta är vad vi kan göra i dag.

811
00:43:45,660 --> 00:43:50,239
>> OK, säger du, men om vi
tänka AI i spel,

812
00:43:50,239 --> 00:43:52,530
normalt tror att vi om
saker som vi kan faktiskt

813
00:43:52,530 --> 00:43:54,180
sitta ner och spela mot.

814
00:43:54,180 --> 00:43:58,760
Om jag sitta ner och jag spelar
Starcraft, eller jag spelar gratis Sieve,

815
00:43:58,760 --> 00:44:01,870
datorn motståndare är
person som kontrollerar Zerg,

816
00:44:01,870 --> 00:44:06,770
eller styra andra civilisationen.

817
00:44:06,770 --> 00:44:11,920
Hur gör de spelare
faktiskt hitta sina drag?

818
00:44:11,920 --> 00:44:18,810
>> Tja, är dessa spel strukturerade
ungefär på samma sätt som våra brädspel,

819
00:44:18,810 --> 00:44:22,250
dessa spel som vi kommer
kollektivt kalla fyra X Games,

820
00:44:22,250 --> 00:44:26,040
utforska, expand-- glömma de.

821
00:44:26,040 --> 00:44:26,980
Vad är de?

822
00:44:26,980 --> 00:44:32,150
Utforska, expandera, och släcka,
Jag tror är den sista.

823
00:44:32,150 --> 00:44:36,060
Men de är i grund och botten
prospektering och erövra spel.

824
00:44:36,060 --> 00:44:41,020
Typiskt dator motståndare
Det har begränsad information.

825
00:44:41,020 --> 00:44:45,486
De vet inte exakt vad som är
pågår bakom dimma av krig.

826
00:44:45,486 --> 00:44:47,735
De får inte se vad
du har i ditt lager.

827
00:44:47,735 --> 00:44:50,240

828
00:44:50,240 --> 00:44:52,800
>> Det finns en miljö som är dynamisk.

829
00:44:52,800 --> 00:44:56,180
Allt förändras hela tiden.

830
00:44:56,180 --> 00:45:00,290
Du får inte sitta och
vänta med att ta ditt drag.

831
00:45:00,290 --> 00:45:02,810
Men det mesta är fortfarande diskret.

832
00:45:02,810 --> 00:45:04,200
Jag måste sätta min stad här.

833
00:45:04,200 --> 00:45:06,750
Eller jag måste sätta min stad här.

834
00:45:06,750 --> 00:45:08,950
Och allt är deterministisk.

835
00:45:08,950 --> 00:45:14,660
När jag säger, flytta min enhet här, min enhet
flyttar här, såvida inte ett hinder plötsligt

836
00:45:14,660 --> 00:45:17,700
kommer in i bilden.

837
00:45:17,700 --> 00:45:21,610
Nu, det är inte alla datorer
spel som finns där ute idag.

838
00:45:21,610 --> 00:45:27,320
>> Om jag går och jag spelar en förstapersons typ
spel, något som tjuv eller Fallout

839
00:45:27,320 --> 00:45:33,350
eller Skyrim eller halo, nu
Jag har datormotståndare

840
00:45:33,350 --> 00:45:37,860
som är där ute som har
en helt annan situation.

841
00:45:37,860 --> 00:45:40,020
De har återigen begränsad information.

842
00:45:40,020 --> 00:45:43,420
De kan bara se en
vissa synfält.

843
00:45:43,420 --> 00:45:45,180
Miljön är fortfarande dynamisk.

844
00:45:45,180 --> 00:45:48,280
Saker förändras hela tiden.

845
00:45:48,280 --> 00:45:52,300
>> Men nu har jag en mycket mer
kontinuerliga åtgärder utrymme.

846
00:45:52,300 --> 00:45:57,170
Jag kan bara kikar en
lite av dörröppningen.

847
00:45:57,170 --> 00:46:00,650
Och vissa spel, min
åtgärder är stokastiska.

848
00:46:00,650 --> 00:46:04,590
Jag får försöka hoppa över den där väggen,
men jag har en chans att misslyckas.

849
00:46:04,590 --> 00:46:08,280

850
00:46:08,280 --> 00:46:14,550
Dessa typer av spel närmar
och närmare de typer av regulatorer

851
00:46:14,550 --> 00:46:17,330
att vi bygger inom robotik.

852
00:46:17,330 --> 00:46:21,050
>> Inom robotik, måste vi anta
att vi har begränsad information.

853
00:46:21,050 --> 00:46:23,070
Vi har sensorer som
berätta om världen.

854
00:46:23,070 --> 00:46:25,860
Vi har en ständigt föränderlig,
dynamisk miljö.

855
00:46:25,860 --> 00:46:30,440
Vi har en värld där utrymmet är
kontinuerlig, snarare än diskret.

856
00:46:30,440 --> 00:46:36,260
Och våra handlingar, när vi försöker
dem, har en chans att misslyckas.

857
00:46:36,260 --> 00:46:40,960
Och faktiskt, moderna spel
styrenheter för din Halo motståndare,

858
00:46:40,960 --> 00:46:48,690
eller för de NPC i Skyrim, i princip
köra små robot arkitekturer.

859
00:46:48,690 --> 00:46:50,380
>> De känner världen.

860
00:46:50,380 --> 00:46:52,910
De bygger en modell av världen.

861
00:46:52,910 --> 00:46:57,950
De beräknar baserat på en uppsättning av
mål som de skulle vilja genomföra.

862
00:46:57,950 --> 00:47:03,110
De planerar åtgärder baserade
om vad de vet.

863
00:47:03,110 --> 00:47:07,940
Och de är exakt samma slag
av system som vi bygger inom robotik.

864
00:47:07,940 --> 00:47:11,420
Så dessa arkitekturer, till
föra samman den tillbaka,

865
00:47:11,420 --> 00:47:14,500
är ofta ganska lika.

866
00:47:14,500 --> 00:47:16,340
>> Så låt oss se om vi kan se det.

867
00:47:16,340 --> 00:47:19,210
Låt oss gå tillbaka till vår
Tre i rad exempel.

868
00:47:19,210 --> 00:47:22,690
Och jag kommer att ställa ett par av mina
postdocs att komma och hjälpa mig.

869
00:47:22,690 --> 00:47:26,970
Så Chen Ming, och Alessandro, och
Olivier, om ni skulle komma.

870
00:47:26,970 --> 00:47:32,080

871
00:47:32,080 --> 00:47:35,440
Och jag kommer att behöva
ett par frivilliga

872
00:47:35,440 --> 00:47:37,590
>> OK, jag såg en hand upp till höger
där i mitten.

873
00:47:37,590 --> 00:47:39,965
Låt mig ta ett ytterligare, någon
vidare i ryggen kanske.

874
00:47:39,965 --> 00:47:40,881
Okej, där borta.

875
00:47:40,881 --> 00:47:41,490
Kom upp.

876
00:47:41,490 --> 00:47:44,190

877
00:47:44,190 --> 00:47:45,335
Okej.

878
00:47:45,335 --> 00:47:49,490
Så låt oss ta ner som täcker.

879
00:47:49,490 --> 00:48:03,700
Och om ni skulle komma rätt
tillbaka runt här för mig, fantastiskt.

880
00:48:03,700 --> 00:48:06,580
>> Så det här är en robot som heter Baxter.

881
00:48:06,580 --> 00:48:10,880
Och Baxter är en robot som är en
kommersiell plattform, utformad

882
00:48:10,880 --> 00:48:13,030
av ett företag som heter Rethink.

883
00:48:13,030 --> 00:48:16,580
Och denna robot är utformad
för småskalig tillverkning.

884
00:48:16,580 --> 00:48:19,265
Men idag ska vi
använda den för att spela tic-tac-toe.

885
00:48:19,265 --> 00:48:21,930

886
00:48:21,930 --> 00:48:27,150
Nu är denna robot också något
det är relativt unikt.

887
00:48:27,150 --> 00:48:32,950
För om jag stod någonstans
nära en standardfabriksautomation

888
00:48:32,950 --> 00:48:39,580
systemet, skulle jag vara mycket grav
riskerar att skadas.

889
00:48:39,580 --> 00:48:45,600
>> Baxter, är emellertid avsedd att vara
relativt säkert att interagera med.

890
00:48:45,600 --> 00:48:48,680
Och så jag kan driva på denna robot.

891
00:48:48,680 --> 00:48:52,350
Och du kan se att det är en liten
bit flexibel som den rör sig runt.

892
00:48:52,350 --> 00:48:57,250
Och jag kan flytta det
där jag skulle vilja att det ska gå.

893
00:48:57,250 --> 00:49:03,410
Nu i ett normalt robotsystem,
vi skulle ha en uppsättning av lederna här

894
00:49:03,410 --> 00:49:07,970
som skulle vara direkt
svara på positionskommandon.

895
00:49:07,970 --> 00:49:13,180
Och de skulle inte nödvändigtvis bryr
om de rör sig genom open air,

896
00:49:13,180 --> 00:49:15,555
eller om de rörde sig
genom min bröstkorg.

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
Och typiskt, om du var
här med ett industriellt system,

900
00:49:22,090 --> 00:49:23,400
du skulle gå någonstans nära den.

901
00:49:23,400 --> 00:49:26,280
Det skulle vara gul
säkerhet tejp runt den.

902
00:49:26,280 --> 00:49:28,310
Detta system har en
något annorlunda konstruktion

903
00:49:28,310 --> 00:49:32,130
att vara vänligare och enklare
för människor att interagera med,

904
00:49:32,130 --> 00:49:36,380
att i varje led, det finns en fjäder.

905
00:49:36,380 --> 00:49:39,110
Och snarare än att styra
en exakt position,

906
00:49:39,110 --> 00:49:43,110
vi kontrollerar en viss mängd
vridmoment, en viss mängd kraft,

907
00:49:43,110 --> 00:49:45,874
att vi vill vara på den våren.

908
00:49:45,874 --> 00:49:47,790
Okej, så låt mig
ta våra volontärer här.

909
00:49:47,790 --> 00:49:48,540
Hej vad heter du?

910
00:49:48,540 --> 00:49:49,010
>> PUBLIK: Louis.

911
00:49:49,010 --> 00:49:49,635
>> Speak: Louis.

912
00:49:49,635 --> 00:49:50,490
Trevligt att träffas.

913
00:49:50,490 --> 00:49:50,990
Och?

914
00:49:50,990 --> 00:49:51,610
>> PUBLIK: David.

915
00:49:51,610 --> 00:49:51,960
>> Speak: David.

916
00:49:51,960 --> 00:49:52,550
Trevligt att träffas.

917
00:49:52,550 --> 00:49:54,508
Om ni skulle vänta
för en sekund här,

918
00:49:54,508 --> 00:49:56,420
Jag kommer att ge dig
en chans att göra detta.

919
00:49:56,420 --> 00:50:00,610
Så denna robot, om du kommer upp
och om du trycker lätt på det,

920
00:50:00,610 --> 00:50:03,780
du kommer att se att
den rör sig lite.

921
00:50:03,780 --> 00:50:06,349
Och om du ta tag i den rätt
här på handleden bara

922
00:50:06,349 --> 00:50:09,390
ovan där dessa knappar är det
ser ut som du borde ta knapparna,

923
00:50:09,390 --> 00:50:13,100
men ta precis ovanför det i stället, kommer du
kunna mycket försiktigt manipulera det

924
00:50:13,100 --> 00:50:14,545
genom rymden.

925
00:50:14,545 --> 00:50:15,920
Louis, du vill ge det ett försök?

926
00:50:15,920 --> 00:50:19,465
Så ge det bara lite
tryck för att börja med.

927
00:50:19,465 --> 00:50:23,190
Och sedan om du lägger fingrarna
just där och hålla fast vid det,

928
00:50:23,190 --> 00:50:24,807
eftersom det kommer att flytta för dig då.

929
00:50:24,807 --> 00:50:27,824

930
00:50:27,824 --> 00:50:29,365
Okej, vill du ge det ett försök?

931
00:50:29,365 --> 00:50:29,980
Kom upp.

932
00:50:29,980 --> 00:50:32,300
Så ge det bara en mild
Tryck där för att starta.

933
00:50:32,300 --> 00:50:33,820
Du kan känna hur det är.

934
00:50:33,820 --> 00:50:40,060
Och sedan om du ta tag i det där,
du kommer att kunna manövrera på runt.

935
00:50:40,060 --> 00:50:41,280
>> OK.

936
00:50:41,280 --> 00:50:47,360
Så typiskt, denna typ av en robot skulle
användas för småskalig tillverkning.

937
00:50:47,360 --> 00:50:50,980
Och jag kommer att flytta denna arm bara
ned ur vägen lite här.

938
00:50:50,980 --> 00:50:55,750
Men i dag, kommer vi att använda
Samma Tre i rad spela system

939
00:50:55,750 --> 00:50:59,520
baserat på Minimax som vi byggt tidigare.

940
00:50:59,520 --> 00:51:00,549
OK?

941
00:51:00,549 --> 00:51:02,340
Så, ni är varje
kommer att spela ett spel.

942
00:51:02,340 --> 00:51:04,210
Louis, du kommer att vara först.

943
00:51:04,210 --> 00:51:05,920
Låt mig bara hålla dig här för en sekund.

944
00:51:05,920 --> 00:51:10,949
Jag kommer att ha du står rätt
här, bara så att alla kan se dig.

945
00:51:10,949 --> 00:51:11,990
Är ni inrättas här?

946
00:51:11,990 --> 00:51:13,120
>> ROBOT: Välkommen.

947
00:51:13,120 --> 00:51:15,910
Låt oss leka Tre i rad.

948
00:51:15,910 --> 00:51:20,860
Hittar du inte förstå din token innan
Jag säger att det är din tur.

949
00:51:20,860 --> 00:51:22,050
Jag startar spelet.

950
00:51:22,050 --> 00:51:27,900

951
00:51:27,900 --> 00:51:28,750
Det är min tur.

952
00:51:28,750 --> 00:51:47,002

953
00:51:47,002 --> 00:51:50,210
Speak: Nu, om du kunde ta en av
dina pjäser och gå vidare och placera den.

954
00:51:50,210 --> 00:51:51,446
ROBOT: Det är din tur.

955
00:51:51,446 --> 00:51:53,430
[SKRATT]

956
00:51:53,430 --> 00:51:54,836
Det är min tur.

957
00:51:54,836 --> 00:51:56,820
[SKRATT]

958
00:51:56,820 --> 00:52:12,196

959
00:52:12,196 --> 00:52:15,680
[SKRATT]

960
00:52:15,680 --> 00:52:16,570
Det är din tur.

961
00:52:16,570 --> 00:52:21,397

962
00:52:21,397 --> 00:52:23,688
Speak: Den mänskliga rasen är
räknar med att ni här, Louis.

963
00:52:23,688 --> 00:52:27,440

964
00:52:27,440 --> 00:52:28,350
>> ROBOT: Det är min tur.

965
00:52:28,350 --> 00:52:44,810

966
00:52:44,810 --> 00:52:47,015
>> Speak: Så Baxter
framgångsrikt blockerade här.

967
00:52:47,015 --> 00:52:49,670

968
00:52:49,670 --> 00:52:52,480
>> ROBOT: Det är din tur.

969
00:52:52,480 --> 00:52:53,360
Det är min tur.

970
00:52:53,360 --> 00:53:14,730

971
00:53:14,730 --> 00:53:16,810
Det är din tur.

972
00:53:16,810 --> 00:53:17,760
Det är min tur.

973
00:53:17,760 --> 00:53:21,330

974
00:53:21,330 --> 00:53:23,830
Speak: Och vi ska låta Baxter
avsluta sin senaste draget här.

975
00:53:23,830 --> 00:53:36,622

976
00:53:36,622 --> 00:53:39,090
>> [SKRATT]

977
00:53:39,090 --> 00:53:40,480
>> ROBOT: Det är en slips.

978
00:53:40,480 --> 00:53:42,030
Jag kommer att vinna nästa gång.

979
00:53:42,030 --> 00:53:43,365
>> [SKRATT]

980
00:53:43,365 --> 00:53:45,210
>> Speak: Okej,
tack så mycket, Louis.

981
00:53:45,210 --> 00:53:46,094
Tack.

982
00:53:46,094 --> 00:53:46,980
Du kan gå denna väg.

983
00:53:46,980 --> 00:53:49,759
>> ROBOT: Jag startar spelet.

984
00:53:49,759 --> 00:53:51,800
Speak: Så låt mig förklara
till er en liten

985
00:53:51,800 --> 00:53:55,410
bit innan vi får vår returmatch här.

986
00:53:55,410 --> 00:53:57,200
Vad händer?

987
00:53:57,200 --> 00:53:59,430
Så roboten har en kamera där uppe här.

988
00:53:59,430 --> 00:54:01,330
Och det ser ner på tavlan.

989
00:54:01,330 --> 00:54:04,470
Och det är att se om
det har fått en röd O eller en blå

990
00:54:04,470 --> 00:54:10,450
och vit X. Som de får släppas ut på
ombord, det är i stort sett samma ingång

991
00:54:10,450 --> 00:54:13,890
att vi skulle läsa in från
vår datastruktur från vår skärmen.

992
00:54:13,890 --> 00:54:17,290
Det kör samma
Minimax algoritm för att vara

993
00:54:17,290 --> 00:54:21,010
kunna hitta var att
Placera en bra token.

994
00:54:21,010 --> 00:54:24,820
>> Och sedan ger vi ett kommando om
där vi vill ha en token ska placeras.

995
00:54:24,820 --> 00:54:26,120
Armen rör sig ut.

996
00:54:26,120 --> 00:54:31,750
Det är med hjälp av en vakuumgrip att tillämpa
vissa sug till den träbit,

997
00:54:31,750 --> 00:54:35,240
plocka upp, flytta den åt höger
plats, och släpp sedan sug

998
00:54:35,240 --> 00:54:36,950
och släpp den.

999
00:54:36,950 --> 00:54:38,990
Okej, vi kommer
för att ge det en mer skott

1000
00:54:38,990 --> 00:54:40,930
med en något smartare spelare här.

1001
00:54:40,930 --> 00:54:42,290
Är du redo?

1002
00:54:42,290 --> 00:54:46,150
Okej, om du skulle stå rätt upp
här och ge en-- vända på detta sätt

1003
00:54:46,150 --> 00:54:47,955
så att du kan se alla.

1004
00:54:47,955 --> 00:54:48,830
Och sedan [OHÖRBAR].

1005
00:54:48,830 --> 00:54:49,330
>> ROBOT: Det är min tur.

1006
00:54:49,330 --> 00:54:50,455
>> Speak: Baxter startar.

1007
00:54:50,455 --> 00:55:10,750

1008
00:55:10,750 --> 00:55:11,730
Det är din tur.

1009
00:55:11,730 --> 00:55:16,490

1010
00:55:16,490 --> 00:55:17,520
Det är min tur.

1011
00:55:17,520 --> 00:55:38,740

1012
00:55:38,740 --> 00:55:39,690
Det är din tur.

1013
00:55:39,690 --> 00:55:46,330

1014
00:55:46,330 --> 00:55:47,165
Det är min tur.

1015
00:55:47,165 --> 00:56:01,252

1016
00:56:01,252 --> 00:56:06,192
>> [SKRATT]

1017
00:56:06,192 --> 00:56:08,542
>> Speak: [WHISPERING] Just
låt honom gå vidare och vinna.

1018
00:56:08,542 --> 00:56:09,500
ROBOT: Det är din tur.

1019
00:56:09,500 --> 00:56:15,099

1020
00:56:15,099 --> 00:56:15,890
Speak: Det är OK.

1021
00:56:15,890 --> 00:56:20,390

1022
00:56:20,390 --> 00:56:21,360
>> ROBOT: Det är min tur.

1023
00:56:21,360 --> 00:56:24,825

1024
00:56:24,825 --> 00:56:26,805
>> [SKRATT]

1025
00:56:26,805 --> 00:56:42,650

1026
00:56:42,650 --> 00:56:43,510
>> Jag vinner.

1027
00:56:43,510 --> 00:56:45,620
>> [SKRATT]

1028
00:56:45,620 --> 00:56:46,595
>> Jag startar spelet.

1029
00:56:46,595 --> 00:56:48,261
>> Speak: Okej, tack så mycket.

1030
00:56:48,261 --> 00:56:50,180

1031
00:56:50,180 --> 00:56:55,590
Okej, jag tror att vi har tid för
ytterligare en utmärkt Tre i rad spelare,

1032
00:56:55,590 --> 00:57:00,490
någon som kan sätta denna sak att
matcha, som vet vad de ska göra.

1033
00:57:00,490 --> 00:57:03,010
>> [SKRATT]

1034
00:57:03,010 --> 00:57:05,560
>> Vem ska vara vår mästare här?

1035
00:57:05,560 --> 00:57:08,110
Okej, dina vänner frivilligt dig.

1036
00:57:08,110 --> 00:57:11,190
Det är bra nog för mig.

1037
00:57:11,190 --> 00:57:12,194
Berätta ditt namn igen.

1038
00:57:12,194 --> 00:57:12,860
PUBLIK: Tamir.

1039
00:57:12,860 --> 00:57:14,193
Speak: Tamir, trevligt att se dig.

1040
00:57:14,193 --> 00:57:19,270
Okej, återigen, vi kommer att sätta dig
ända fram här så att alla kan se dig.

1041
00:57:19,270 --> 00:57:22,070
Du är vår representant
i denna match nu.

1042
00:57:22,070 --> 00:57:24,540
Baxter är en och oh och oh.

1043
00:57:24,540 --> 00:57:26,300
Eller förlåt, en oh och en.

1044
00:57:26,300 --> 00:57:27,490
Och det är upp till dig här.

1045
00:57:27,490 --> 00:57:29,340
Baxter kommer att få flytta först, men.

1046
00:57:29,340 --> 00:57:30,435
Så.

1047
00:57:30,435 --> 00:57:31,310
ROBOT: Det är min tur.

1048
00:57:31,310 --> 00:57:45,226

1049
00:57:45,226 --> 00:57:48,208
>> [SKRATT]

1050
00:57:48,208 --> 00:57:52,720

1051
00:57:52,720 --> 00:57:55,780
>> Det är din tur.

1052
00:57:55,780 --> 00:57:56,845
Det är min tur.

1053
00:57:56,845 --> 00:58:18,130

1054
00:58:18,130 --> 00:58:18,965
Det är din tur.

1055
00:58:18,965 --> 00:58:28,751

1056
00:58:28,751 --> 00:58:30,248
Det är min tur.

1057
00:58:30,248 --> 00:58:51,210

1058
00:58:51,210 --> 00:58:52,160
Det är din tur.

1059
00:58:52,160 --> 00:59:00,854

1060
00:59:00,854 --> 00:59:03,365
>> [SKRATT]

1061
00:59:03,365 --> 00:59:04,240
ROBOT: Det är min tur.

1062
00:59:04,240 --> 00:59:06,930
Speak: Det är mycket svårare när
du står upp här, folks.

1063
00:59:06,930 --> 00:59:19,400

1064
00:59:19,400 --> 00:59:21,840
[SKRATT]

1065
00:59:21,840 --> 00:59:26,730

1066
00:59:26,730 --> 00:59:29,054
ROBOT: Du människor är så lätt att slå.

1067
00:59:29,054 --> 00:59:30,803
[Skratt och applåder]

1068
00:59:30,803 --> 00:59:31,886
Speak: Tack så mycket.

1069
00:59:31,886 --> 00:59:34,692
ROBOT: Jag vinner.

1070
00:59:34,692 --> 00:59:35,400
Jag startar spelet.

1071
00:59:35,400 --> 00:59:39,500
>> SPEAKER: Okej, så tack så
mycket till Olivier, och Alessandro,

1072
00:59:39,500 --> 00:59:41,616
och Chen Ming.

1073
00:59:41,616 --> 00:59:45,600
>> [APPLÅDER]

1074
00:59:45,600 --> 00:59:47,040
>> Jag vill göra en sista punkt.

1075
00:59:47,040 --> 00:59:51,630
Så Baxter vid mycket
slut där, lurade.

1076
00:59:51,630 --> 00:59:54,160

1077
00:59:54,160 --> 00:59:56,310
Och det var oväntat.

1078
00:59:56,310 --> 01:00:00,440
En av de fantastiska
saker om AI är att vi

1079
01:00:00,440 --> 01:00:05,070
göra arbete i AI så att vi kan bygga
riktigt intressant och intelligent

1080
01:00:05,070 --> 01:00:06,930
enheter.

1081
01:00:06,930 --> 01:00:10,130
Men vi också göra arbete i AI
eftersom det säger oss något

1082
01:00:10,130 --> 01:00:13,940
om hur människan är intelligenta.

1083
01:00:13,940 --> 01:00:17,280
>> En av favorit
studier från mitt labb är

1084
01:00:17,280 --> 01:00:23,660
titta på vad som händer när
maskiner oväntat fuska.

1085
01:00:23,660 --> 01:00:27,070
Vi gjorde detta ursprungligen inte med
Baxter spelar Tre i rad,

1086
01:00:27,070 --> 01:00:30,340
men med en mindre robot som heter Nao,
som spelade Sten, sax, påse.

1087
01:00:30,340 --> 01:00:33,010

1088
01:00:33,010 --> 01:00:35,800
Och ibland efter
spela massor

1089
01:00:35,800 --> 01:00:41,580
av tråkiga Sten, sax, påse spel,
roboten skulle kasta en gest,

1090
01:00:41,580 --> 01:00:48,616
förlora, och sedan plötsligt förändras
dess gest och säger, jag vinner.

1091
01:00:48,616 --> 01:00:50,480
>> [SKRATT]

1092
01:00:50,480 --> 01:00:56,090
>> Nu, ibland skulle vi också ha robot,
bara som en kontroll, kasta en gest,

1093
01:00:56,090 --> 01:01:01,270
vinna, och ändra dess gest
att förlora, kasta matchen,

1094
01:01:01,270 --> 01:01:04,070
fuska för att förlora.

1095
01:01:04,070 --> 01:01:07,540
Och det är inte alls lika övertygande.

1096
01:01:07,540 --> 01:01:09,890
Roboten som fusk
för att vinna människor

1097
01:01:09,890 --> 01:01:14,660
svara på som om det är
ut för att få dem, som det

1098
01:01:14,660 --> 01:01:17,690
aktivt söker deras undergång.

1099
01:01:17,690 --> 01:01:19,210
>> [SKRATT]

1100
01:01:19,210 --> 01:01:20,990
>> Det blir en agent.

1101
01:01:20,990 --> 01:01:21,840
Det är som en person.

1102
01:01:21,840 --> 01:01:23,970
Den har tro och avsikt.

1103
01:01:23,970 --> 01:01:27,470
Och det är inte goda avsikter.

1104
01:01:27,470 --> 01:01:33,790
Och robot som kastar
Spelet är bara inte fungerar.

1105
01:01:33,790 --> 01:01:36,990
Det är bara en trasig enhet.

1106
01:01:36,990 --> 01:01:41,405
Låt mig visa dig ett par exempel
av det från några av våra deltagare.

1107
01:01:41,405 --> 01:01:43,990

1108
01:01:43,990 --> 01:01:45,600
Så här är fusk för att förlora.

1109
01:01:45,600 --> 01:01:46,266
>> [VIDEOAVSPELNING]

1110
01:01:46,266 --> 01:01:47,010
- [OHÖRBAR] vinna.

1111
01:01:47,010 --> 01:01:49,550
Låt oss leka.

1112
01:01:49,550 --> 01:01:50,538
>> -Vänta, va?

1113
01:01:50,538 --> 01:01:54,490

1114
01:01:54,490 --> 01:01:55,352
>> - [OHÖRBAR] vinna.

1115
01:01:55,352 --> 01:01:58,280
Låt oss leka.

1116
01:01:58,280 --> 01:01:59,400
>> [OHÖRBAR] vinna.

1117
01:01:59,400 --> 01:02:02,290
Låt oss leka.

1118
01:02:02,290 --> 01:02:05,490
>> Speak: Och här är fusk att vinna.

1119
01:02:05,490 --> 01:02:06,438
>> -Ja, Jag vinner.

1120
01:02:06,438 --> 01:02:07,394
Låt oss leka.

1121
01:02:07,394 --> 01:02:08,828
>> -Du Kan inte göra det.

1122
01:02:08,828 --> 01:02:10,740
>> [SKRATT]

1123
01:02:10,740 --> 01:02:12,174

1124
01:02:12,174 --> 01:02:13,979
>> -Ja, Jag vinner.

1125
01:02:13,979 --> 01:02:14,520
-Du Lurade.

1126
01:02:14,520 --> 01:02:17,990

1127
01:02:17,990 --> 01:02:20,010
Du lurade nu.

1128
01:02:20,010 --> 01:02:21,140
>> -Ja, Jag vinner.

1129
01:02:21,140 --> 01:02:22,940
>> -Hej, Du fuskare.

1130
01:02:22,940 --> 01:02:26,670
Du fuskar, super fuska.

1131
01:02:26,670 --> 01:02:27,650
>> [END SPELA]

1132
01:02:27,650 --> 01:02:31,130
>> Speak: Dessa olika
reaktioner snabbt

1133
01:02:31,130 --> 01:02:34,890
förändra vår uppfattning av enheten.

1134
01:02:34,890 --> 01:02:36,780
Betyder det att
vi medvetet bygga

1135
01:02:36,780 --> 01:02:40,370
maskiner som fuskar eftersom det är
den bästa teknik som vi kan göra?

1136
01:02:40,370 --> 01:02:44,680
Nej, men det säger oss något
riktigt intressant om människor.

1137
01:02:44,680 --> 01:02:49,710
Denna sak som fusk dig och
stjäl din seger, det är

1138
01:02:49,710 --> 01:02:53,660
något som är levande, det är
animera, det är ute efter dig.

1139
01:02:53,660 --> 01:02:54,680
Det har mentala tillstånd.

1140
01:02:54,680 --> 01:02:55,400
Det har tro.

1141
01:02:55,400 --> 01:02:57,170
Det har avsikt.

1142
01:02:57,170 --> 01:03:01,540
>> Denna sak som händer den
spel för dig, det är inte.

1143
01:03:01,540 --> 01:03:04,670
Det är bara inte fungerar.

1144
01:03:04,670 --> 01:03:08,900
Detta är på många sätt varför det är
lätt att kasta spelet med barnen.

1145
01:03:08,900 --> 01:03:12,050
Men om du försöker lura dem
och typ av anspråk på seger

1146
01:03:12,050 --> 01:03:15,200
när, du vet, bara för att förkorta
spelet kommer de fångar dig direkt.

1147
01:03:15,200 --> 01:03:19,040

1148
01:03:19,040 --> 01:03:23,140
Dessa typer av effekter som
ser vi kommer ut ur AI,

1149
01:03:23,140 --> 01:03:26,490
de lära oss en hel del om oss själva.

1150
01:03:26,490 --> 01:03:28,076
>> Okej, det är det för dag.

1151
01:03:28,076 --> 01:03:30,450
Tack så mycket till David och
Harvard produktionsteam

1152
01:03:30,450 --> 01:03:32,350
för att ni kom ner.

1153
01:03:32,350 --> 01:03:33,820
>> [APPLÅDER]

1154
01:03:33,820 --> 01:03:36,760

1155
01:03:36,760 --> 01:03:41,840
>> Vi får se dig för frågesport en,
och sedan för en sista föreläsning.

1156
01:03:41,840 --> 01:03:43,025
Ha en bra dag.

1157
01:03:43,025 --> 01:03:44,965
>> [APPLÅDER]

1158
01:03:44,965 --> 01:03:48,360

1159
01:03:48,360 --> 01:03:51,825
>> [MUSIK SPELA]

1160
01:03:51,825 --> 01:03:54,950
DAVID J MALAN: Tja, förmodligen behöver vi
att införa någon form av kryptering,

1161
01:03:54,950 --> 01:03:55,450
höger?

1162
01:03:55,450 --> 01:03:58,650
För då rubrikerna i
dessa HTTP-förfrågningar kommer att vara

1163
01:03:58,650 --> 01:04:01,530
oordning så att alla
försöker sniffa trafiken

1164
01:04:01,530 --> 01:04:03,400
kommer faktiskt inte att kunna se dem.

1165
01:04:03,400 --> 01:04:05,254
Så vad är lösningen på detta problem?

1166
01:04:05,254 --> 01:04:07,920
Tja, måste vi faktiskt införa
kryptering i formeln,

1167
01:04:07,920 --> 01:04:11,010
så att när den personen är
överföring av data från A till B,

1168
01:04:11,010 --> 01:04:12,390
vi kan säkert send--

1169
01:04:12,390 --> 01:04:14,590
>> [SKRATT]

1170
01:04:14,590 --> 01:04:19,530
>> Den information på ett sätt att den
motståndare inte i själva verket se den.