1
00:00:00,000 --> 00:00:01,924
>> [Musik spiller]

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

3
00:00:10,600 --> 00:00:13,280
>> SPEAKER: Velkommen tilbage, alle.

4
00:00:13,280 --> 00:00:15,440
Det er CS50.

5
00:00:15,440 --> 00:00:21,040
Og i dag har vi en masse
interessante ting at tale om.

6
00:00:21,040 --> 00:00:25,500
Men først jeg nødt til at minde
dig om et par administrative ting.

7
00:00:25,500 --> 00:00:30,160
I denne uge er quiz én, onsdag
eller til Yale afsnittet

8
00:00:30,160 --> 00:00:32,940
på tirsdage og torsdage, på torsdag.

9
00:00:32,940 --> 00:00:38,170
Der er quiz anmeldelser
i aften på Yale, 5:30 til 07:00.

10
00:00:38,170 --> 00:00:40,030
På Harvard, indspillede de en i går.

11
00:00:40,030 --> 00:00:43,000
Og alle kan se, at online.

12
00:00:43,000 --> 00:00:49,406
>> Også denne uge eller begyndelsen af ​​næste uge,
vi har vores sidste CS50 foredrag.

13
00:00:49,406 --> 00:00:51,450
[Stønner] jeg kender.

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

15
00:00:54,140 --> 00:00:57,820
Yale studerende vil have en live
foredrag her i jura

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

17
00:00:59,920 --> 00:01:01,140
Der vil være kage.

18
00:01:01,140 --> 00:01:05,570
Harvard studerende vil have den
sidste foredrag i Sanders på mandag.

19
00:01:05,570 --> 00:01:08,050
Der vil også være kage.

20
00:01:08,050 --> 00:01:14,000
>> Også i denne uge på fredag, for dem
af jer, der kommer til 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 mere end 30
forskellige grupper registreret

23
00:01:18,850 --> 00:01:22,530
at vise dig alt
fra autonome sejlbåde,

24
00:01:22,530 --> 00:01:27,170
til systemer, der genkender
digitale portrætter, til computeren

25
00:01:27,170 --> 00:01:32,100
musik og computer-produceret musik.

26
00:01:32,100 --> 00:01:33,610
Så vær venlig slutte sig til os.

27
00:01:33,610 --> 00:01:36,460
Jeg tror, ​​det kommer til at være et godt tidspunkt.

28
00:01:36,460 --> 00:01:40,320
>> I dag, selv om, vi kommer til at
fortsætte med at tale om AI,

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

30
00:01:43,150 --> 00:01:46,070
Og en af ​​de ting,
vi vil komme til i dag

31
00:01:46,070 --> 00:01:51,750
er ideen om, hvordan man
bruge AI til at løse problemer.

32
00:01:51,750 --> 00:01:54,690
Nu, som altid, lad os starte
med noget simpelt.

33
00:01:54,690 --> 00:01:57,120
Og vi kommer til at starte
med en simpel idé.

34
00:01:57,120 --> 00:01:59,920
Og det er ved hjælp af søgning.

35
00:01:59,920 --> 00:02:06,990
>> Så forestil dig et øjeblik, at jeg
har en opgave, som jeg har brug for at udføre.

36
00:02:06,990 --> 00:02:11,970
Og jeg vil gerne have, at opgaven
automatiseret af nogle software agent.

37
00:02:11,970 --> 00:02:17,100
Forestil dig, at jeg forsøger at bestille et sæt
på fly fra, lad os sige, Boston

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

39
00:02:20,040 --> 00:02:24,230
Jeg kunne gå igennem og jeg kunne bruge
en af ​​de vidunderlige online-søgning

40
00:02:24,230 --> 00:02:28,790
værktøjer, der vil gøre
dybest set den samme proces, som vi er

41
00:02:28,790 --> 00:02:30,030
kommer til at gå gennem i dag.

42
00:02:30,030 --> 00:02:34,100
Men hvis du ikke har det
værktøj, hvad ville du gøre?

43
00:02:34,100 --> 00:02:37,570
>> Nå, kunne du se og
se og sige, jeg er i Boston.

44
00:02:37,570 --> 00:02:41,520
Hvilke flyvninger er tilgængelige for mig?

45
00:02:41,520 --> 00:02:44,390
Nu, måske jeg har tre
mulige flyvninger ud af Boston

46
00:02:44,390 --> 00:02:47,180
der vil passe tiden
når jeg har brug for at forlade.

47
00:02:47,180 --> 00:02:48,830
Jeg kunne flyve til Chicago.

48
00:02:48,830 --> 00:02:50,130
Eller jeg kunne flyve til Miami.

49
00:02:50,130 --> 00:02:53,340
Eller jeg kunne flyve til New York.

50
00:02:53,340 --> 00:02:56,980
Jeg kunne derefter se fra hver
en af ​​disse destination byer

51
00:02:56,980 --> 00:03:00,650
og tænke over, hvad steder
Jeg kunne muligvis nå

52
00:03:00,650 --> 00:03:03,020
fra hver af disse individuelle byer.

53
00:03:03,020 --> 00:03:07,390
>> Så måske fra Chicago, kan jeg få
et direkte fly til San Francisco.

54
00:03:07,390 --> 00:03:09,550
Det er fremragende.

55
00:03:09,550 --> 00:03:12,360
Eller jeg kunne få et fly til Denver.

56
00:03:12,360 --> 00:03:16,970
Nu, måske det flyvning til San Francisco
er den perfekte løsning for mig,

57
00:03:16,970 --> 00:03:19,530
men måske ikke.

58
00:03:19,530 --> 00:03:22,180
Måske jeg leder efter noget
det er en lille smule billigere

59
00:03:22,180 --> 00:03:24,920
eller en lille smule bedre for min tidsplan.

60
00:03:24,920 --> 00:03:29,197
Og så kunne jeg se efter, hvad andre
muligheder kan være derude.

61
00:03:29,197 --> 00:03:30,280
Så jeg kunne se på Denver.

62
00:03:30,280 --> 00:03:33,870
Og fra Denver, godt, måske
Jeg kan få en flyvning til Austin.

63
00:03:33,870 --> 00:03:37,080
Og fra Austin, måske jeg kan få en
flyvning til Phoenix, og fra Phoenix

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

65
00:03:40,190 --> 00:03:42,730
Nu er jeg ikke færdig endnu.

66
00:03:42,730 --> 00:03:45,640
Fordi måske er der en
direkte flyvning fra New York

67
00:03:45,640 --> 00:03:47,850
til San Francisco, der er perfekt for mig.

68
00:03:47,850 --> 00:03:53,354
Eller måske er der en flyvning fra Miami
gennem Denver, som er meget billigere.

69
00:03:53,354 --> 00:03:54,270
Så jeg stadig nødt til at gå.

70
00:03:54,270 --> 00:03:58,200
Og jeg stadig nødt til at se på alle dem,
byer, som jeg ikke har undersøgt endnu.

71
00:03:58,200 --> 00:04:04,220
Jeg er nødt til udtømmende kontrollere alle
de muligheder, jeg måtte have.

72
00:04:04,220 --> 00:04:09,610
>> Så fra New York, måske kan jeg få en
flyvning til Nashville, og fra Nashville

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

74
00:04:10,336 --> 00:04:11,460
Og så ved jeg, hvor jeg er.

75
00:04:11,460 --> 00:04:14,252
Og så ved jeg fra Austin, kan jeg
flyve til Phoenix, og fra Phoenix

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

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

78
00:04:18,240 --> 00:04:22,830
Hvis jeg flyver først til Miami, selv om,
måske jeg kan få en flyvning fra Miami

79
00:04:22,830 --> 00:04:25,080
til Nashville, eller fra Miami til Austin.

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

81
00:04:27,950 --> 00:04:30,860
>> Og nu har jeg prøvet alt
af mulighederne.

82
00:04:30,860 --> 00:04:36,310
Jeg har opbygget denne graf,
viser mig alle de mulige ruter

83
00:04:36,310 --> 00:04:37,790
at jeg kunne være i stand til at tage.

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

85
00:04:40,510 --> 00:04:43,640
Når vi repræsenterer disse
former for problemer,

86
00:04:43,640 --> 00:04:47,870
Vi kommer ikke til at repræsentere
dem eksplicit som denne graf,

87
00:04:47,870 --> 00:04:51,590
fordi det grafen ikke repræsenterer
historien om, hvor vi har gået.

88
00:04:51,590 --> 00:04:55,260
Vel vidende, at jeg fløj fra
Phoenix til San Francisco

89
00:04:55,260 --> 00:05:01,690
ikke fortælle mig, om jeg kom via
Nashville, eller via Denver, eller via Miami.

90
00:05:01,690 --> 00:05:06,430
>> Så hvad jeg vil gøre i stedet er
Jeg tager det samme problem,

91
00:05:06,430 --> 00:05:09,140
og jeg vil repræsentere det som et træ.

92
00:05:09,140 --> 00:05:14,300
Og ved roden af ​​træet, på
top, jeg vil sætte det sted, jeg startede,

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

94
00:05:16,590 --> 00:05:19,310
Og fra Boston, vil jeg se på
alle de mulige placeringer

95
00:05:19,310 --> 00:05:20,380
at jeg kan rejse til.

96
00:05:20,380 --> 00:05:25,480
Tja, i dette tilfælde havde jeg tre,
Chicago, New York, og Miami.

97
00:05:25,480 --> 00:05:29,850
Og så vil jeg udforske hver af
disse børn i træet.

98
00:05:29,850 --> 00:05:32,690
>> Fra Chicago, så jeg
at jeg havde to flyvninger.

99
00:05:32,690 --> 00:05:35,940
Jeg kunne flyve direkte til
San Francisco eller til Denver.

100
00:05:35,940 --> 00:05:37,740
Nu San Francisco, det er mit mål.

101
00:05:37,740 --> 00:05:39,790
Det er min destination.

102
00:05:39,790 --> 00:05:42,220
Det kommer til at være et blad af dette træ.

103
00:05:42,220 --> 00:05:45,340
Det vil sige, jeg aldrig kommer til at gå
et eller andet sted efter San Francisco.

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

105
00:05:47,850 --> 00:05:50,340
Fra Denver, selv om,
Jeg kan flyve fra Denver

106
00:05:50,340 --> 00:05:54,220
til Austin, fra Austin til Phoenix,
og fra Phoenix til San Francisco.

107
00:05:54,220 --> 00:05:56,050
Og nu igen, har jeg nået et blad.

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

109
00:05:59,470 --> 00:06:03,980
>> Jeg kunne derefter gå tilbage til den næste
by, som jeg ikke har fuldt udforsket.

110
00:06:03,980 --> 00:06:07,440
Det ville være New York, gå
tilbage til toppen af ​​mit træ,

111
00:06:07,440 --> 00:06:09,160
komme ned til New York.

112
00:06:09,160 --> 00:06:12,700
Fra New York, kan jeg flyve til
Nashville, fra Nashville til Austin,

113
00:06:12,700 --> 00:06:17,290
fra Austin til Phoenix, og
fra Phoenix til San Francisco.

114
00:06:17,290 --> 00:06:20,170
Og endelig, en by, jeg
har ikke kigget på endnu, Miami.

115
00:06:20,170 --> 00:06:24,600
>> Nå, fra Miami jeg sagde, jeg havde to
muligheder, Nashville eller Austin.

116
00:06:24,600 --> 00:06:28,810
Hvis jeg flyver til Nashville, ja så flyver jeg
fra Nashville til Austin, til Phoenix,

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

118
00:06:29,640 --> 00:06:33,600
Hvis jeg flyver til Austin, jeg flyver Austin,
til Phoenix, til San Francisco.

119
00:06:33,600 --> 00:06:36,340
Og nu har jeg et træ.

120
00:06:36,340 --> 00:06:37,230
Det er en komplet træ.

121
00:06:37,230 --> 00:06:41,890
Det er alle de muligheder og
alle de stier, som jeg kunne tage.

122
00:06:41,890 --> 00:06:44,310
Det vil sige, hvis jeg begynder på
roden af ​​træet øverst

123
00:06:44,310 --> 00:06:47,860
og jeg gå ned til en af ​​de
blade, det fortæller mig ikke alene

124
00:06:47,860 --> 00:06:50,480
hvor jeg har tænkt mig at
ender, San Francisco,

125
00:06:50,480 --> 00:06:53,670
men det fortæller mig den rute, som
Jeg har brug for at tage for at komme dertil.

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

127
00:06:56,400 --> 00:06:59,690
>> Nu, hvor en af ​​disse er den bedste?

128
00:06:59,690 --> 00:07:02,430
Nå, ikke noget om dette
problem endnu fortæller mig

129
00:07:02,430 --> 00:07:04,710
hvilken af ​​dem er den bedste løsning.

130
00:07:04,710 --> 00:07:09,270
Måske jeg bekymrer mest om
hvor meget tid jeg er i luften,

131
00:07:09,270 --> 00:07:12,350
eller den afstand, jeg flyver.

132
00:07:12,350 --> 00:07:16,410
I så fald Chicago til San
Francisco kan være den korteste antal

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

134
00:07:18,910 --> 00:07:20,860
>> Måske jeg mig om omkostninger.

135
00:07:20,860 --> 00:07:23,680
Og vi ved alle, direkte flyvninger
er normalt dyrere.

136
00:07:23,680 --> 00:07:26,610
Så måske hvis jeg tager denne
slags baglæns rute

137
00:07:26,610 --> 00:07:30,650
gennem Miami, Nashville,
Austin, Phoenix, måske derefter

138
00:07:30,650 --> 00:07:34,070
Jeg får en lavere pris.

139
00:07:34,070 --> 00:07:36,440
Men jeg kunne optimere på enhver
kriterier, som jeg holder af.

140
00:07:36,440 --> 00:07:39,790
Hvem har det bedste i
fly Wi-Fi, eller som

141
00:07:39,790 --> 00:07:43,110
lufthavne har den bedste mad til rådighed.

142
00:07:43,110 --> 00:07:47,280
Og hver af dem, måske
give mig en anden løsning

143
00:07:47,280 --> 00:07:49,215
at jeg ser som værende den bedste.

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

145
00:07:51,990 --> 00:07:54,400
>> Disse former for problemer,
hvor vi skal hen

146
00:07:54,400 --> 00:07:58,480
at opbygge denne træ
muligheder, og derefter

147
00:07:58,480 --> 00:08:02,100
se på hver af dem,
individuelle stier, og undersøge

148
00:08:02,100 --> 00:08:05,270
hvilke af disse honorerer
et kriterium for os,

149
00:08:05,270 --> 00:08:08,790
vi kommer til at kalde
disse søgning problemer.

150
00:08:08,790 --> 00:08:11,280
Og vi har masser af
algoritmer, hvoraf nogle

151
00:08:11,280 --> 00:08:15,270
vi har set allerede, til at gå
og udforske disse træer.

152
00:08:15,270 --> 00:08:19,270
Vi kunne gøre det på den måde, at jeg
lige gjorde, en dybde-først søgning,

153
00:08:19,270 --> 00:08:22,900
gå ned så langt som vi kan, indtil vi
ramte et blad, og så kommer tilbage,

154
00:08:22,900 --> 00:08:24,787
og gå tilbage ned.

155
00:08:24,787 --> 00:08:26,870
Eller vi kunne gøre, hvad der er
kaldet bredde-først søgning.

156
00:08:26,870 --> 00:08:29,675
Vi kunne udvide alt
foroven, og derefter

157
00:08:29,675 --> 00:08:31,550
alt én linje
nedenunder, og derefter

158
00:08:31,550 --> 00:08:35,240
alt én linje under det.

159
00:08:35,240 --> 00:08:41,250
Disse søgetræer
er grundlæggende for AI.

160
00:08:41,250 --> 00:08:46,570
Men de har ikke helt få
det rigtigt hele tiden.

161
00:08:46,570 --> 00:08:51,600
I virkeligheden, i en masse af tilfældene
at vi virkelig bekymrer sig om,

162
00:08:51,600 --> 00:08:54,430
vi ønsker at opbygge et træ,
men vi gør faktisk ikke

163
00:08:54,430 --> 00:08:57,140
komme til at gøre alle de beslutninger.

164
00:08:57,140 --> 00:09:00,940
>> Det er situationer kaldes
kontradiktorisk søgning, også kendt

165
00:09:00,940 --> 00:09:05,390
som, hvordan man skriver spil at spille
systemer og blive betalt for det.

166
00:09:05,390 --> 00:09:07,940
Men disse er den slags
af systemer, hvor jeg

167
00:09:07,940 --> 00:09:12,920
kan komme til at vælge, når jeg går fra
Boston, hvilken by jeg går til næste.

168
00:09:12,920 --> 00:09:19,990
Men efter det, kan en anden får
til at gøre beslutningen om, hvor jeg flyver.

169
00:09:19,990 --> 00:09:24,040
Så for at bygge disse
slags strukturer, vi er

170
00:09:24,040 --> 00:09:28,510
nødt til at tage en lidt
anderledes tilgang til det.

171
00:09:28,510 --> 00:09:31,060
Vi kommer ikke til at være i stand til
bare søge gennem træet

172
00:09:31,060 --> 00:09:35,000
længere, fordi vi ikke er
den, der er i kontrol

173
00:09:35,000 --> 00:09:38,180
hver af disse beslutningspunkter.

174
00:09:38,180 --> 00:09:42,590
>> Så lad os forestille os en simpel
spil som Kryds og bolle.

175
00:09:42,590 --> 00:09:46,730
Jeg kunne starte med en
helt blank board.

176
00:09:46,730 --> 00:09:49,580
Og i tic-tac-toe,
X kommer til at spille først.

177
00:09:49,580 --> 00:09:53,890
Og så jeg kunne tænke på alle de
mulige træk, at X kunne gøre.

178
00:09:53,890 --> 00:09:57,420
Og hvis jeg er den ene spiller
X, det er fantastisk.

179
00:09:57,420 --> 00:10:01,020
Jeg har ni mulige
bevæger sig, at jeg kan gøre.

180
00:10:01,020 --> 00:10:05,000
Jeg kunne sætte et X i et
af disse ni positioner.

181
00:10:05,000 --> 00:10:10,710
>> Og derefter fra hver af dem, I
kunne forestille sig, hvad der sker næste.

182
00:10:10,710 --> 00:10:14,130
Tja, i dette tilfælde, den anden
spiller ville komme til at tage en tur.

183
00:10:14,130 --> 00:10:15,660
O ville komme til at tage en tur.

184
00:10:15,660 --> 00:10:19,510
Og fra hver af disse, der
ville være otte forskellige steder

185
00:10:19,510 --> 00:10:22,980
at O kunne placere deres markering.

186
00:10:22,980 --> 00:10:25,790
>> Lad os sige, at jeg besluttede, at jeg var
kommer til at sætte et X i midten.

187
00:10:25,790 --> 00:10:28,810
Der altid ser ud som
en god åbning flytte.

188
00:10:28,810 --> 00:10:34,870
Jeg kunne se på under det, den
otte mulige træk som O gør.

189
00:10:34,870 --> 00:10:37,320
Nu, hvis jeg spiller X, det er vidunderligt.

190
00:10:37,320 --> 00:10:41,740
Jeg får at vælge, hvilken en jeg
gå til, den ene i midten.

191
00:10:41,740 --> 00:10:45,000
Men nu O får lov til at vælge.

192
00:10:45,000 --> 00:10:48,750
Og jeg har ikke kontrol
i løbet af denne afgørelse.

193
00:10:48,750 --> 00:10:51,670
>> Men fra hver af disse
mulige bestyrelsesposter,

194
00:10:51,670 --> 00:10:54,020
Der er så en anden
sæt af muligheder.

195
00:10:54,020 --> 00:10:56,700
Når det kommer til at være
Min vende igen, ville jeg

196
00:10:56,700 --> 00:11:01,500
komme til at vælge og sige, ja,
hvis O bevæger sig ind i, ja,

197
00:11:01,500 --> 00:11:06,110
den midterste plet på venstre, derefter
Jeg har et sæt af muligheder

198
00:11:06,110 --> 00:11:09,740
hvor jeg kan tage mit næste træk.

199
00:11:09,740 --> 00:11:14,140
Fra dem, kunne jeg overveje alle
mulighederne under dem.

200
00:11:14,140 --> 00:11:18,030
Og så O ville få
at vælge mellem disse.

201
00:11:18,030 --> 00:11:22,290
>> Og jeg kunne holde bygning denne
træet ud, indtil jeg kom til det punkt,

202
00:11:22,290 --> 00:11:26,960
hvor enten en person
vinder game--, der er

203
00:11:26,960 --> 00:11:31,070
fik at blive betragtet som en blad node--
eller bestyrelsen er helt fyldt

204
00:11:31,070 --> 00:11:32,704
og ingen har vundet.

205
00:11:32,704 --> 00:11:34,370
Og der er også kommer til at være et blad node.

206
00:11:34,370 --> 00:11:35,411
Det kommer til at være en uafgjort.

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

208
00:11:37,820 --> 00:11:41,680
>> Men det tricky ting med dette er
hvis dette var blot en regelmæssig søgning

209
00:11:41,680 --> 00:11:44,269
problem, ville jeg være i stand til
siger, godt, bør X gå her.

210
00:11:44,269 --> 00:11:45,560
Og O skal gå vejen derovre.

211
00:11:45,560 --> 00:11:46,770
Og så X skal gå over her.

212
00:11:46,770 --> 00:11:48,269
Og så O skal gå vejen derovre.

213
00:11:48,269 --> 00:11:51,860
Og så X kan få tre
i træk, og jeg vinder.

214
00:11:51,860 --> 00:11:54,870
Og spillet ville være over
i fem bevæger sig, tre for mig,

215
00:11:54,870 --> 00:11:57,710
to for min modstander.

216
00:11:57,710 --> 00:12:01,300
Men jeg tror ikke altid får at vælge det.

217
00:12:01,300 --> 00:12:03,720
>> Så i stedet, hvad vi er
nødt til at gøre

218
00:12:03,720 --> 00:12:06,270
er vi vil have
at have en ny strategi.

219
00:12:06,270 --> 00:12:09,350
Og den strategi, som
spil-playing algoritmer ofte bruger

220
00:12:09,350 --> 00:12:12,000
er det, der hedder minimax.

221
00:12:12,000 --> 00:12:15,500
Den centrale idé i
Minimax er, at vi er

222
00:12:15,500 --> 00:12:21,365
kommer til at vælge den bevægelse, der giver
vores modstander den værst tænkelige sæt

223
00:12:21,365 --> 00:12:22,790
af bevæger sig, at de kan gøre.

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

225
00:12:25,570 --> 00:12:28,870
Det gør ikke mig noget godt
til at vælge et træk, hvor

226
00:12:28,870 --> 00:12:31,952
Jeg kan være i stand til at vinde efter
at fordi min modstander ikke er

227
00:12:31,952 --> 00:12:33,160
vil give mig den chance.

228
00:12:33,160 --> 00:12:37,770
De kommer til at vælge nogle
frygtelige resultat for mig.

229
00:12:37,770 --> 00:12:42,010
Så jeg har tænkt mig at gøre
flytte der tvinger min modstander

230
00:12:42,010 --> 00:12:45,760
at gøre noget bedre for mig.

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

232
00:12:46,260 --> 00:12:48,410
Lad os se, hvordan det udspiller sig.

233
00:12:48,410 --> 00:12:51,640
Så her er vores algoritme i pseudokode.

234
00:12:51,640 --> 00:12:54,450
Vi kommer til at generere
hele spillet træ.

235
00:12:54,450 --> 00:12:56,757
Vi kommer til at bygge
hele strukturen.

236
00:12:56,757 --> 00:12:57,840
Og så vil vi gå igennem.

237
00:12:57,840 --> 00:13:02,100
Og i bunden ved hver af de
terminal noder, på hvert af de blade,

238
00:13:02,100 --> 00:13:07,850
vi vil vurdere, hvordan
værdifulde er, at for mig?

239
00:13:07,850 --> 00:13:11,690
Og vi vil værdi ting,
er godt for mig at være positiv.

240
00:13:11,690 --> 00:13:14,460
Ting, der ikke godt for mig
vil være mindre positiv eller nul,

241
00:13:14,460 --> 00:13:16,480
eller endog negativ.

242
00:13:16,480 --> 00:13:19,240
>> Så i tic-tac-toe, måske
en sejr for mig er god.

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

244
00:13:20,290 --> 00:13:22,400
Og et slips er nul.

245
00:13:22,400 --> 00:13:26,230
Og noget, der er et tab for
mig, måske det er en negativ.

246
00:13:26,230 --> 00:13:29,620
Alle, der betyder noget, er, at jo bedre
det er for mig, jo højere score

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

248
00:13:32,160 --> 00:13:36,690
Fra disse muligheder på
bund, så vil vi filtrere opad.

249
00:13:36,690 --> 00:13:40,650
Og når det er min chance for at vælge
blandt et sæt af alternativer,

250
00:13:40,650 --> 00:13:44,460
Jeg vil vælge den, der er
fik den højeste score.

251
00:13:44,460 --> 00:13:47,200
>> Og når det er min
modstandere tur til at vælge,

252
00:13:47,200 --> 00:13:52,350
Jeg vil antage, at de vil
vælge den med den laveste score.

253
00:13:52,350 --> 00:13:56,090
Og hvis jeg gør det hele vejen
op til toppen af ​​træet,

254
00:13:56,090 --> 00:14:03,150
Jeg har valgt en vej, der giver
mig det bedste resultat, som jeg kan få,

255
00:14:03,150 --> 00:14:09,110
under forudsætning af, at min modstander
gør alle de rigtige træk.

256
00:14:09,110 --> 00:14:11,940
>> Okay, så lad os se
dette i aktion først.

257
00:14:11,940 --> 00:14:14,980
Og så vil vi faktisk
se på koden til det.

258
00:14:14,980 --> 00:14:16,780
Så forestil jeg har denne store træ.

259
00:14:16,780 --> 00:14:18,280
Og nu er jeg ikke spiller Kryds og bolle.

260
00:14:18,280 --> 00:14:20,405
Jeg ønskede at give dig
noget lidt rigere.

261
00:14:20,405 --> 00:14:23,560
Så jeg har fået nogle spil, hvor
der er mange forskellige scoringer

262
00:14:23,560 --> 00:14:26,390
at jeg kunne have i slutningen.

263
00:14:26,390 --> 00:14:27,980
Og så jeg bygge denne komplette træ.

264
00:14:27,980 --> 00:14:29,070
Og jeg kommer til at bevæge sig først.

265
00:14:29,070 --> 00:14:31,290
Jeg er ved roden af ​​træet.

266
00:14:31,290 --> 00:14:36,150
>> Og jeg får at vælge at-- så jeg får
at maksimere tværs af denne første knudepunkt.

267
00:14:36,150 --> 00:14:38,410
Og så min modstander får lov til at gå.

268
00:14:38,410 --> 00:14:41,910
Og så får jeg at gå en gang mere.

269
00:14:41,910 --> 00:14:46,830
Så ned på bunden, jeg har et sæt af
muligheder, som jeg kan vælge fra,

270
00:14:46,830 --> 00:14:50,570
forskellige terminal tilstande af spillet.

271
00:14:50,570 --> 00:14:54,980
Hvis jeg er fastsat i nævnte
yderste venstre hjørne,

272
00:14:54,980 --> 00:14:58,867
og jeg kan se, at jeg har fået et valg
mellem en otte, syv og en to,

273
00:14:58,867 --> 00:15:00,450
godt, jeg er den, der får lov til at vælge.

274
00:15:00,450 --> 00:15:02,910
Så jeg har tænkt mig at vælge
den bedste af dem.

275
00:15:02,910 --> 00:15:05,650
Jeg har tænkt mig at vælge de otte.

276
00:15:05,650 --> 00:15:10,090
>> Så jeg ved, at hvis jeg nogensinde
komme ned til det punkt,

277
00:15:10,090 --> 00:15:13,890
Jeg vil være i stand til at få det otte point.

278
00:15:13,890 --> 00:15:17,410
Hvis jeg ender på det næste punkt
bliver den næste node i,

279
00:15:17,410 --> 00:15:20,760
en ni, en en eller en seks, ja, jeg er
kommer til at vælge den bedste af dem.

280
00:15:20,760 --> 00:15:21,950
Jeg vil vælge de ni.

281
00:15:21,950 --> 00:15:24,880
Hvis jeg har et valg mellem
to og fire, og en,

282
00:15:24,880 --> 00:15:28,240
Jeg vil vælge de fire, det højeste.

283
00:15:28,240 --> 00:15:31,990
>> Nu, hvis jeg ser på det niveau,
ovenstående, min modstander

284
00:15:31,990 --> 00:15:34,440
er den man får til at træffe dette valg.

285
00:15:34,440 --> 00:15:37,040
Så min modstander får til
vælger, ønsker jeg at give ham

286
00:15:37,040 --> 00:15:39,250
de ting, der sker
at få ham otte point,

287
00:15:39,250 --> 00:15:41,916
eller skal jeg give ham det, som er
vil give ham ni punkter,

288
00:15:41,916 --> 00:15:45,240
eller de ting, der sker
at give ham fire point?

289
00:15:45,240 --> 00:15:49,130
Og min modstander, bliver
rationel, går

290
00:15:49,130 --> 00:15:53,470
at vælge den mindste af disse,
kommer til at vælge de fire.

291
00:15:53,470 --> 00:15:56,020
>> Og jeg kan gøre dette
gennem hele træet.

292
00:15:56,020 --> 00:15:59,110
Jeg kan gå ned til det
midterste sæt af tre.

293
00:15:59,110 --> 00:16:01,517
Og jeg kan vælge mellem
en, tre og fem.

294
00:16:01,517 --> 00:16:02,350
Og jeg får at vælge.

295
00:16:02,350 --> 00:16:03,810
Så jeg vælger en fem.

296
00:16:03,810 --> 00:16:05,340
Jeg kan vælge tre, ni eller to.

297
00:16:05,340 --> 00:16:07,570
Jeg får at vælge, så jeg vælger ni.

298
00:16:07,570 --> 00:16:09,290
Seks, fem, eller to, vælger jeg.

299
00:16:09,290 --> 00:16:11,539
Jeg får at vælge de seks.

300
00:16:11,539 --> 00:16:13,080
Niveau over det, som sætter til at vælge?

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

302
00:16:16,280 --> 00:16:18,140
Hvem får til at vælge?

303
00:16:18,140 --> 00:16:20,000
Den anden fyr, min modstander.

304
00:16:20,000 --> 00:16:22,583
Så de vælger fem,
ni eller seks, hvilken?

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

306
00:16:23,410 --> 00:16:25,250
>> SPEAKER: De vælger de fem.

307
00:16:25,250 --> 00:16:27,400
De får at vælge den mindste.

308
00:16:27,400 --> 00:16:29,690
Og derefter den sidste,
vælge en, to eller tre.

309
00:16:29,690 --> 00:16:31,720
Jeg får at vælge, så jeg vælger tre.

310
00:16:31,720 --> 00:16:34,370
Ni, syv, eller to, jeg vælger ni.

311
00:16:34,370 --> 00:16:37,070
Og 11, seks eller fire, jeg vælger 11.

312
00:16:37,070 --> 00:16:41,190
Min modstander derefter vælger tre,
ni eller 11, vælger minimum.

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

314
00:16:43,290 --> 00:16:47,780
Og så endelig på toppen af
træet, jeg får at vælge igen.

315
00:16:47,780 --> 00:16:51,190
Og jeg kommer til at vælge mellem
en fire, fem eller tre.

316
00:16:51,190 --> 00:16:52,270
Så jeg tager fem.

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

318
00:16:55,070 --> 00:17:00,891
>> Hvis jeg kom til at styre alt, jeg havde
tage den vej, der førte til 11.

319
00:17:00,891 --> 00:17:02,390
Men jeg kan ikke komme til at træffe dette valg.

320
00:17:02,390 --> 00:17:04,220
Hvis jeg går den vej.

321
00:17:04,220 --> 00:17:10,710
Min modstander vil tvinge mig ind
valget, der fører til en tre.

322
00:17:10,710 --> 00:17:14,530
Så det bedste, jeg kan gøre, er
at tage det midterste gren,

323
00:17:14,530 --> 00:17:19,859
træffe dette valg, der er i sidste ende
kommer til at føre mig til fem point.

324
00:17:19,859 --> 00:17:23,230
Det er, hvad minimax gør.

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

326
00:17:23,807 --> 00:17:24,890
Lad os tage et kig på det.

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

328
00:17:27,480 --> 00:17:32,330
Så her i CS50
IDE er et program,

329
00:17:32,330 --> 00:17:36,540
implementerer minimax at spille tic-tac-toe.

330
00:17:36,540 --> 00:17:40,100
Vi kommer til at bygge
en repræsentation.

331
00:17:40,100 --> 00:17:44,390
Vi kommer til at have to opponent--
eller to spillere, vores computer

332
00:17:44,390 --> 00:17:46,090
afspiller og en menneskelig spiller.

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

334
00:17:48,980 --> 00:17:53,090
Spiller nummer et vil spille
den O. Det bliver maskinen afspilleren.

335
00:17:53,090 --> 00:17:55,747
De får at flytte sekund.

336
00:17:55,747 --> 00:17:57,830
Og den anden spiller, vores
menneskelig spiller, vil være X.

337
00:17:57,830 --> 00:17:59,880
>> Og for at gøre mit liv en
lidt simpel, jeg har tænkt mig

338
00:17:59,880 --> 00:18:03,060
til at mærke, at spilleren negativ.

339
00:18:03,060 --> 00:18:05,026
Så jeg kan bare formere
af negativ at bytte

340
00:18:05,026 --> 00:18:06,400
mellem en spiller og den anden.

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

342
00:18:09,030 --> 00:18:12,250
Okay, så lad os tage et kig på
hvad vi egentlig vil gøre.

343
00:18:12,250 --> 00:18:15,840
Vi kommer til at definere vores bord.

344
00:18:15,840 --> 00:18:19,060
Det kommer til at være, godt, vi kommer
at lade det være tre gange tre,

345
00:18:19,060 --> 00:18:21,580
eller vi kan endda spille
fem med fem eller syv

346
00:18:21,580 --> 00:18:28,870
af syv Kryds og bolle, hvis du ville
lignende, baseret på nogle dimension D.

347
00:18:28,870 --> 00:18:31,260
>> Og vi vil have et par
af hjælpefunktioner

348
00:18:31,260 --> 00:18:34,360
der vil gøre ting som
initialisere screen-- eller ked af det,

349
00:18:34,360 --> 00:18:38,900
initialisere vores variabler, rydde
skærmen, tegne brættet på skærmen,

350
00:18:38,900 --> 00:18:41,060
en, der kontrollerer en bestyrelse
at se, hvorvidt

351
00:18:41,060 --> 00:18:44,520
der er en vinder, en,
analyserer gennem kommandolinjen,

352
00:18:44,520 --> 00:18:50,670
bare for at hjælpe, en, der læser i
input, og en funktion kaldet minimax.

353
00:18:50,670 --> 00:18:52,746
Og det er den ene
vi interesserer mest om.

354
00:18:52,746 --> 00:18:54,120
Men lad os først se på de vigtigste.

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

356
00:18:57,490 --> 00:18:58,510
>> Hvad gør vi?

357
00:18:58,510 --> 00:19:00,570
Nå, vi kommer til at
parse vores kommandolinjen,

358
00:19:00,570 --> 00:19:04,300
lige læst ind og se, hvad
dimension bord vi gerne vil have.

359
00:19:04,300 --> 00:19:07,330
Vi vil initialisere vores bord.

360
00:19:07,330 --> 00:19:10,360
Og så vil vi indtaste én
store vilde loop, gentagne gange

361
00:19:10,360 --> 00:19:16,630
acceptere flytter indtil spillet er
vandt, eller der er ingen træk tilbage.

362
00:19:16,630 --> 00:19:20,560
Hver gang vi går gennem denne
loop, vil vi rydde skærmen.

363
00:19:20,560 --> 00:19:23,290
Vi vil trække brættet på skærmen.

364
00:19:23,290 --> 00:19:28,750
Og vi er bevidst slags
abstrahere disse væk som subrutiner,

365
00:19:28,750 --> 00:19:32,030
således at vi ikke behøver at bekymre dig for meget
om detaljerne i, hvordan de sker.

366
00:19:32,030 --> 00:19:33,480
>> Du får koden senere i dag.

367
00:19:33,480 --> 00:19:37,970
Og hvis du ønsker at se gennem
og finde ud af, du kan se dem alle.

368
00:19:37,970 --> 00:19:39,890
Men vi vil trække en bestyrelse på skærmen.

369
00:19:39,890 --> 00:19:43,620
Og så vil vi kontrollere og
se, har vi en vinder?

370
00:19:43,620 --> 00:19:46,290
Har nogen vundet dette spil?

371
00:19:46,290 --> 00:19:49,260
Hvis de har, vil vi udskrive
ud en sejr budskab.

372
00:19:49,260 --> 00:19:51,680
Og vi vil afslutte spillet.

373
00:19:51,680 --> 00:19:54,510
>> Vi vil også kontrollere og
se, om der er en uafgjort.

374
00:19:54,510 --> 00:19:56,620
Det vil være let at se, om der er en uafgjort.

375
00:19:56,620 --> 00:20:00,700
Det betyder, at alle rum er fuld,
men der har ikke været en vinder endnu.

376
00:20:00,700 --> 00:20:03,580
Vi kan erklære en uafgjort og være færdig.

377
00:20:03,580 --> 00:20:10,530
Så den virkelige meat-- hvis
Det er en maskine-afspiller,

378
00:20:10,530 --> 00:20:14,120
vi vil tillade, at
Maskinen afspiller for at søge

379
00:20:14,120 --> 00:20:19,500
ved at bruge denne minimax algoritme,
for at finde det bedste spil, at det kan.

380
00:20:19,500 --> 00:20:22,310
Og så vil vi sætte det træk op.

381
00:20:22,310 --> 00:20:27,640
>> Ellers, hvis det er en menneskelig spiller,
vi vil læse nogle input fra menneske.

382
00:20:27,640 --> 00:20:30,800
Og så om det er den menneskelige
afspiller eller maskinen spiller

383
00:20:30,800 --> 00:20:32,800
vi vil gøre et par lidt
stumper af fejlkontrol,

384
00:20:32,800 --> 00:20:36,910
sørg for at det holder sig inden for grænserne
af de faktiske dimensioner af bestyrelsen

385
00:20:36,910 --> 00:20:40,040
at vi har, skal du sørge for
at denne plads er tom,

386
00:20:40,040 --> 00:20:43,570
at ingen os sætte en
brik i der allerede.

387
00:20:43,570 --> 00:20:45,810
Og så vil vi bare sætte
en brik på brættet,

388
00:20:45,810 --> 00:20:51,550
ændre afspilleren til næste lag, og
tilvækst, hvor mange flytter være sket.

389
00:20:51,550 --> 00:20:54,090
>> Det er den vigtigste loop for
vores Kryds og bolle spil.

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

391
00:20:57,000 --> 00:21:02,340
Minimax er altså præcis
algoritmen, som vi før.

392
00:21:02,340 --> 00:21:04,710
Det eneste tilpasning,
vi har gjort, så vi

393
00:21:04,710 --> 00:21:07,290
kan spille højere
dimensionelle brædder er vi har

394
00:21:07,290 --> 00:21:11,070
holdt denne ekstra parameter kaldet dybde.

395
00:21:11,070 --> 00:21:14,870
Og dybde bare siger, hvis jeg
søger nedad gennem det træ

396
00:21:14,870 --> 00:21:19,022
og jeg får så langt ned
ud over en vis grad dybde

397
00:21:19,022 --> 00:21:20,730
at jeg bare ikke ønsker
til at gå videre,

398
00:21:20,730 --> 00:21:25,630
Jeg har tænkt mig at stoppe og bare
evaluere bestyrelsen på det tidspunkt.

399
00:21:25,630 --> 00:21:27,310
Jeg vil kontrollere og se, om der er en vinder.

400
00:21:27,310 --> 00:21:29,240
Hvis der er en vinder, jeg returnere dem.

401
00:21:29,240 --> 00:21:31,720
Ellers vil jeg gå gennem en løkke.

402
00:21:31,720 --> 00:21:34,380
Og jeg vil sige, for alle
De mulige placeringer

403
00:21:34,380 --> 00:21:38,080
at jeg kunne eventuelt
tage som min flytte, vil jeg

404
00:21:38,080 --> 00:21:43,760
opbygge en hypotetisk bestyrelse,
omfatter min Flyt på denne bord,

405
00:21:43,760 --> 00:21:45,960
og derefter kalder rekursivt minimax.

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

407
00:21:49,360 --> 00:21:53,900
>> Hvis det er min flytte, får jeg at finde den
en, der har fået den største score.

408
00:21:53,900 --> 00:21:58,710
Hvis det er min modstanders træk, vi finder
den, der har fået den mindste score.

409
00:21:58,710 --> 00:22:02,240
Og alt andet er
bare journalføring.

410
00:22:02,240 --> 00:22:04,789
Okay, så lad os se denne kørsel.

411
00:22:04,789 --> 00:22:06,830
Faktisk, måske vi kan
få et par frivillige

412
00:22:06,830 --> 00:22:09,930
til at komme op og spille Kryds og bolle.

413
00:22:09,930 --> 00:22:12,780
[Uhørligt] en, og én
mere, to, lige der.

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

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

416
00:22:19,290 --> 00:22:23,650
>> Så lad os gå videre og
genstarte dette fuldstændigt.

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

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

419
00:22:24,920 --> 00:22:25,420
>> SPEAKER: Hvad er dit navn?

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

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

422
00:22:26,840 --> 00:22:27,800
>> PUBLIKUM: Jeg er Layla.

423
00:22:27,800 --> 00:22:29,490
>> SPEAKER: Og Layla, og Layla, undskyld.

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

425
00:22:30,384 --> 00:22:32,050
Gorav, vi vil have dig gå først.

426
00:22:32,050 --> 00:22:37,710
Og jeg har tænkt mig at bede dig om at være en ikke
frygtelig god Kryds og bolle-afspiller.

427
00:22:37,710 --> 00:22:40,130
OK, så alt presset er slukket på dig.

428
00:22:40,130 --> 00:22:44,660
Lad os se, selv om, at vores maskine
Spilleren kan faktisk gøre noget smart.

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

430
00:22:45,310 --> 00:22:49,830
Du kommer til at skrive, hvor koordinere
du gerne vil sætte dit X i.

431
00:22:49,830 --> 00:22:55,170
A0, OK, og maskinen er gået
højre væk og sætte sit præg i A1.

432
00:22:55,170 --> 00:22:56,640
>> Sæt O på brættet.

433
00:22:56,640 --> 00:22:58,970
Okay, nu gå videre.

434
00:22:58,970 --> 00:23:00,193
Hvor vil du gerne hen?

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
Vores maskine spiller har taget
den midterste firkant, blokeret dig.

438
00:23:08,430 --> 00:23:10,320
Så det var en god,
smart ting for den at gøre.

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

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

441
00:23:14,250 --> 00:23:15,210
Det er fremragende.

442
00:23:15,210 --> 00:23:16,390
Det tager om hjørnet er der.

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

444
00:23:23,890 --> 00:23:30,430
>> Og det kommer til at tvinge dig til
tage en sidste plads, B0.

445
00:23:30,430 --> 00:23:32,220
Og spillet ender i en uafgjort.

446
00:23:32,220 --> 00:23:35,030
Men det spillede en rimelig
spil mod dig, ikke?

447
00:23:35,030 --> 00:23:36,956
Okay, tak meget, Gorav.

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

449
00:23:40,860 --> 00:23:44,723
>> Okay, Layla, vi vil
op spillet på dig her.

450
00:23:44,723 --> 00:23:46,940
>> PUBLIKUM: Åh, stor.

451
00:23:46,940 --> 00:23:49,950
>> SPEAKER: Vi vil give
du fire af fire Kryds og bolle.

452
00:23:49,950 --> 00:23:54,760
Nu, i fire af fire, er du nødt til at vinde
med fire i træk, ikke tre i træk.

453
00:23:54,760 --> 00:23:56,135
Og det er alle dine.

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 vil nu følge
vores computer spiller her.

457
00:24:11,730 --> 00:24:16,910
Tre af tre Kryds og bolle er den slags
af ting, der er nemt for os alle.

458
00:24:16,910 --> 00:24:21,960
Men det er stadig rart at se
computer spiller gøre smart træk.

459
00:24:21,960 --> 00:24:23,725
Fire af fire bliver til
være lidt tricky.

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

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

462
00:24:44,230 --> 00:24:46,210
Okay, så Layla er færdig fra.

463
00:24:46,210 --> 00:24:48,270
Åh, og vi bør være endt der.

464
00:24:48,270 --> 00:24:51,870
Men lad os gøre én mere op her.

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

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

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

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

469
00:25:00,410 --> 00:25:04,750
>> Så vores Kryds og bolle spiller går
igennem og finder steder,

470
00:25:04,750 --> 00:25:07,040
løser dem ved hjælp af denne minimax.

471
00:25:07,040 --> 00:25:08,990
Og jeg havde en dybde indstilling
på det, så det

472
00:25:08,990 --> 00:25:11,010
ikke ville løbe for hurtigt,
som sandsynligvis er hvorfor

473
00:25:11,010 --> 00:25:16,790
Layla var i stand til at gå pænt i god
som hun gjorde, og gjorde meget godt.

474
00:25:16,790 --> 00:25:20,450
Men disse systemer, der bare
gå igennem og brute force

475
00:25:20,450 --> 00:25:23,870
gå dybere, og dybere, og dybere,
og holde finde en løsning

476
00:25:23,870 --> 00:25:29,890
at de har brug for, den slags systemer
er ganske vellykket på disse, godt,

477
00:25:29,890 --> 00:25:32,700
standard brætspil.

478
00:25:32,700 --> 00:25:37,060
>> Og i virkeligheden, hvis vi ser på et
tre med tre Kryds og bolle spil,

479
00:25:37,060 --> 00:25:40,040
dette er dybest set et løst problem.

480
00:25:40,040 --> 00:25:45,430
Og det er en vidunderlig diagram
fra Randall Munroe på XKCD,

481
00:25:45,430 --> 00:25:52,130
viser hvilke flytter du bør
tage, givet din modstanders træk.

482
00:25:52,130 --> 00:25:56,420
Det er noget, vi kunne
nemt angive forvejen.

483
00:25:56,420 --> 00:26:00,180
Men hvad sker der, når vi kommer til mere
komplekse spil, mere komplicerede spil,

484
00:26:00,180 --> 00:26:05,690
hvor der er større boards, mere
muligheder, dybere strategi?

485
00:26:05,690 --> 00:26:09,660
>> Det viser sig, at denne
brute force søger stadig

486
00:26:09,660 --> 00:26:14,150
gør rimeligt godt, bortset fra
når du kommer til det punkt

487
00:26:14,150 --> 00:26:19,230
hvor det træ er så stort
at du ikke kan repræsentere det hele.

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

489
00:26:22,370 --> 00:26:28,280
Når du ikke kan beregne hele træet,
når du ikke kan gå fremad og skub

490
00:26:28,280 --> 00:26:32,204
dig selv til det punkt, hvor du har
fået hele træet i hukommelsen,

491
00:26:32,204 --> 00:26:34,370
eller om du kan få det
i hukommelsen og det vil bare

492
00:26:34,370 --> 00:26:39,200
tage dig alt for lang tid at søge igennem
det, er du nødt til at gøre noget smartere.

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

494
00:26:42,620 --> 00:26:46,450
>> For at gøre det, du
nødt til at gøre to ting.

495
00:26:46,450 --> 00:26:49,030
Først skal du nødt til at finde nogle
måde at begrænse din dybde.

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

497
00:26:50,370 --> 00:26:55,740
Vi kan finde nogle nice, minimum
og sige, du kan kun gå så dybt.

498
00:26:55,740 --> 00:27:00,890
Men når du gør det, det betyder at du
har disse delvist ufuldstændige boards.

499
00:27:00,890 --> 00:27:04,770
Og du skal vælge, kan jeg godt lide
dette delvist ufuldstændige bord,

500
00:27:04,770 --> 00:27:08,600
eller det delvist ufuldstændige board?

501
00:27:08,600 --> 00:27:11,910
>> Og på vores fire af
fire Kryds og bolle spil,

502
00:27:11,910 --> 00:27:15,240
vores computer-spiller kom ned
til bunden, og det sagde,

503
00:27:15,240 --> 00:27:16,800
Jeg har to forskellige bestyrelser.

504
00:27:16,800 --> 00:27:17,940
Hverken det ene er en win.

505
00:27:17,940 --> 00:27:19,120
Hverken det ene er et tab.

506
00:27:19,120 --> 00:27:22,070
Hverken den ene er en uafgjort.

507
00:27:22,070 --> 00:27:24,100
Hvordan vælger jeg imellem dem?

508
00:27:24,100 --> 00:27:26,200
Og det havde ikke en
smart måde at gøre det på.

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

510
00:27:28,910 --> 00:27:32,850
>> Vi ser denne form for
evaluering sker hele tiden

511
00:27:32,850 --> 00:27:35,290
som vi får i mere komplekse spil.

512
00:27:35,290 --> 00:27:37,600
Skak er et godt eksempel.

513
00:27:37,600 --> 00:27:41,550
I skak, vi har, først
og fremmest et større bord.

514
00:27:41,550 --> 00:27:43,370
Vi har langt flere stykker.

515
00:27:43,370 --> 00:27:47,930
Og placeringen af ​​disse stykker
og den måde, disse stykker bevæger

516
00:27:47,930 --> 00:27:50,370
er kritisk vigtigt.

517
00:27:50,370 --> 00:27:53,700
Så hvis jeg vil bruge minimax,
Jeg har brug for at være i stand til at specificere

518
00:27:53,700 --> 00:27:58,240
og sige, dette board, hvor
ingen har vundet eller tabt endnu,

519
00:27:58,240 --> 00:28:04,310
er på en måde bedre end dette andet
bord, hvor ingen har vundet eller tabt.

520
00:28:04,310 --> 00:28:06,740
>> For at gøre det, kan jeg gøre
ting som jeg måske bare

521
00:28:06,740 --> 00:28:10,787
tælle, hvor mange stykker har jeg
og hvor mange stykker har du?

522
00:28:10,787 --> 00:28:12,870
Eller jeg kan give forskellige
stykker forskellige punkter.

523
00:28:12,870 --> 00:28:14,420
Min dronning er værd 20 point.

524
00:28:14,420 --> 00:28:16,500
Din bonde er værd ét punkt.

525
00:28:16,500 --> 00:28:18,920
Hvem har flere point i alt?

526
00:28:18,920 --> 00:28:22,300
Eller jeg kunne overveje tingene lide,
hvem der fik bedre bestyrelsen stilling?

527
00:28:22,300 --> 00:28:26,820
Hvis tur er det næste,
noget, jeg kan

528
00:28:26,820 --> 00:28:31,220
behøver at vurdere mere præcist
hvilke af disse muligheder

529
00:28:31,220 --> 00:28:34,660
er bedre uden
udtømmende overvejer

530
00:28:34,660 --> 00:28:36,565
enhver bevægelse, der kunne komme efter det.

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

532
00:28:39,740 --> 00:28:45,130
>> Nu for at gøre dette arbejde,
en af ​​de ting, der er

533
00:28:45,130 --> 00:28:48,680
kommer til at blive virkelig vigtigt
for os er ikke bare bevæger sig lige

534
00:28:48,680 --> 00:28:53,720
ned til en bestemt dybde
grænse, men at kunne sige,

535
00:28:53,720 --> 00:28:59,380
en af ​​disse ideer, som jeg
har, er så dårlig, at det er

536
00:28:59,380 --> 00:29:02,280
ikke værd at overveje
alle de mulige måder

537
00:29:02,280 --> 00:29:06,680
at tingene kan gå fra slemt til værre.

538
00:29:06,680 --> 00:29:12,760
For at gøre dette, vil vi tilføje i minimax
et princip kaldes Alph-beta.

539
00:29:12,760 --> 00:29:16,340
Og alfa-beta siger,
hvis du har en dårlig idé,

540
00:29:16,340 --> 00:29:22,840
ikke spilde din tid forsøger at
finde ud af, præcis hvor slemt det er.

541
00:29:22,840 --> 00:29:24,990
>> Så her er, hvad vi vil gøre.

542
00:29:24,990 --> 00:29:28,620
Vi kommer til at tage det samme
principper, som vi havde før,

543
00:29:28,620 --> 00:29:32,200
den samme minimax typen
søgning, kun er vi

544
00:29:32,200 --> 00:29:37,570
vil holde styr, ikke blot for
faktiske værdier, som vi har, men vi vil

545
00:29:37,570 --> 00:29:41,440
holde styr på den bedst mulige
værdi, som jeg kunne få,

546
00:29:41,440 --> 00:29:45,700
og det værst tænkelige
resultat jeg kunne have.

547
00:29:45,700 --> 00:29:50,470
Og helst det værst tænkelige
ting ser sandsynligt,

548
00:29:50,470 --> 00:29:52,694
Jeg vil opgive den del af træet.

549
00:29:52,694 --> 00:29:54,610
Og jeg vil ikke engang gider
ser på det længere.

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

551
00:29:57,680 --> 00:30:02,600
>> Okay, så forestille sig, at vi starter
med samme nøjagtige spil træ.

552
00:30:02,600 --> 00:30:05,200
Og nu vi kommer til at gå
ned igen, hele vejen ned

553
00:30:05,200 --> 00:30:07,200
til den nederste venstre hjørne.

554
00:30:07,200 --> 00:30:11,180
Og i den nederste venstre hjørne, vi
ser, og vi vurderer dette board.

555
00:30:11,180 --> 00:30:15,700
Måske er det en fire af fire Kryds og bolle
bord, eller måske er det et skakbræt.

556
00:30:15,700 --> 00:30:18,620
Men vi ser på det, og vi evaluerer
det, og vi får en værdi på otte.

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

558
00:30:22,290 --> 00:30:28,030
>> På det tidspunkt ved vi, at
vi kommer til at få mindst

559
00:30:28,030 --> 00:30:32,380
otte point fra denne nederste beslutning.

560
00:30:32,380 --> 00:30:36,620
Det er ligegyldigt, hvad den anden
to er, at syv og to.

561
00:30:36,620 --> 00:30:38,580
De kunne være nogen værdier
de ønskede at være.

562
00:30:38,580 --> 00:30:41,279
Vi kommer til at få på
mindst otte point.

563
00:30:41,279 --> 00:30:43,070
Okay, men vi kunne
gå videre og kontrollere.

564
00:30:43,070 --> 00:30:45,080
Måske er en af ​​dem bedre end otte.

565
00:30:45,080 --> 00:30:46,000
>> Vi ser på de syv.

566
00:30:46,000 --> 00:30:46,910
Er det bedre end otte?

567
00:30:46,910 --> 00:30:48,680
Nej, det ikke ændre
vores mening overhovedet.

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

569
00:30:49,460 --> 00:30:50,543
Er det bedre end otte?

570
00:30:50,543 --> 00:30:52,580
Nej, det ikke ændre
vores mening overhovedet.

571
00:30:52,580 --> 00:30:55,480
Så nu ved vi, at vi har opbrugt
alle de muligheder der.

572
00:30:55,480 --> 00:30:58,330
Vi kommer ikke til at få
noget bedre end otte.

573
00:30:58,330 --> 00:31:01,310
Vi kommer til at få præcis otte.

574
00:31:01,310 --> 00:31:03,825
>> Og så vi ændre det node og
sige, der nu er en sikkerhed.

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

576
00:31:07,010 --> 00:31:10,270
Vi går et niveau op over det.

577
00:31:10,270 --> 00:31:13,820
Og nu ved vi noget
om det minimering niveau.

578
00:31:13,820 --> 00:31:18,560
Vi ved, at vi aldrig kommer til at få
mere end otte point, hvis vi går ned

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

580
00:31:20,910 --> 00:31:22,980
For selv om de,
to andre grene vise sig

581
00:31:22,980 --> 00:31:26,170
at være fantastisk og værd
tusindvis af point hver,

582
00:31:26,170 --> 00:31:31,666
vores modstander vil give os den
minimum og give os de otte.

583
00:31:31,666 --> 00:31:32,790
Okay, godt, lad os se.

584
00:31:32,790 --> 00:31:35,190
Vi vil holde gå den vej.

585
00:31:35,190 --> 00:31:38,490
Vi går ned til midten til venstre.

586
00:31:38,490 --> 00:31:40,560
Vi ser ned, og vi se, at der er en ni.

587
00:31:40,560 --> 00:31:45,590
Vi ved, at vi vil få
mindst ni punkter ved at gå ned

588
00:31:45,590 --> 00:31:47,720
at midterste vej.

589
00:31:47,720 --> 00:31:52,110
Og på dette tidspunkt, kan vi bare holde pause.

590
00:31:52,110 --> 00:31:56,910
Og vi kan sige, se, jeg
ved i niveauet ovenfor,

591
00:31:56,910 --> 00:32:01,160
Jeg har tænkt mig at få mere end otte
peger ved at gå ned denne retning.

592
00:32:01,160 --> 00:32:05,670
Men hvis jeg gik ned midt
vej i stedet for venstre bane,

593
00:32:05,670 --> 00:32:08,980
Jeg ville få mindst ni point.

594
00:32:08,980 --> 00:32:13,590
>> Min modstander er aldrig vil
lad mig gå den midterste sti.

595
00:32:13,590 --> 00:32:14,650
De får at vælge.

596
00:32:14,650 --> 00:32:18,140
Og de kommer til at vælge den
vej til venstre mod otte,

597
00:32:18,140 --> 00:32:23,650
snarere end på midten mod
hvad der er mindst ni point.

598
00:32:23,650 --> 00:32:25,334
Så på det tidspunkt, vil jeg stoppe.

599
00:32:25,334 --> 00:32:26,500
Og jeg vil sige, ved du hvad?

600
00:32:26,500 --> 00:32:29,990
Jeg behøver ikke at se nogen
mere ned i den retning.

601
00:32:29,990 --> 00:32:32,270
Fordi jeg aldrig kommer til at blive der.

602
00:32:32,270 --> 00:32:36,660
>> Jeg kan springe over, at man,
og jeg kan springe over, at seks,

603
00:32:36,660 --> 00:32:39,720
fordi der er aldrig kommer til at ske.

604
00:32:39,720 --> 00:32:42,470
Så jeg vil gå ned, og jeg vil
overveje næste mulighed.

605
00:32:42,470 --> 00:32:44,830
Jeg går ned der, og jeg siger, jeg ser en to.

606
00:32:44,830 --> 00:32:47,125
Jeg ved, hvis jeg får til her, er jeg
kommer til at få mindst to.

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
Jeg holde ud.

610
00:32:51,520 --> 00:32:52,440
Jeg ser en fire.

611
00:32:52,440 --> 00:32:54,920
Jeg ved, jeg har tænkt mig at få mindst fire.

612
00:32:54,920 --> 00:32:57,200
Der er stadig en masse mellem
fire og otte, selv om.

613
00:32:57,200 --> 00:32:58,454
Så jeg holde ud.

614
00:32:58,454 --> 00:32:59,870
Jeg ser ned og jeg ser der er én.

615
00:32:59,870 --> 00:33:01,614
Okay, jeg vide, om
Jeg gå denne vej,

616
00:33:01,614 --> 00:33:03,280
Jeg har tænkt mig at være i stand til at vælge de fire.

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

618
00:33:06,540 --> 00:33:08,980
Hvad er min modstander kommer til at gøre?

619
00:33:08,980 --> 00:33:12,310
Mellem noget, der giver mig
otte, noget, der giver mig fire,

620
00:33:12,310 --> 00:33:14,730
og noget,
giver mig mindst ni,

621
00:33:14,730 --> 00:33:17,550
godt, han vil give mig de fire.

622
00:33:17,550 --> 00:33:20,110
Og jeg ved nu på
helt i top, jeg har tænkt mig

623
00:33:20,110 --> 00:33:23,145
at kunne få mindst
fire point ud af dette spil.

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

625
00:33:27,030 --> 00:33:30,900
>> Hele ideen med alfa-beta
er at afskære dele træet, så

626
00:33:30,900 --> 00:33:32,530
at jeg ikke se på dem længere.

627
00:33:32,530 --> 00:33:35,964
Men det ligner stadig jeg har været
ser på en masse af træet.

628
00:33:35,964 --> 00:33:36,880
Lad os holde gå ned.

629
00:33:36,880 --> 00:33:38,305
Vi vil gå ned i næste nu.

630
00:33:38,305 --> 00:33:39,680
Nede i bunden, jeg finder en en.

631
00:33:39,680 --> 00:33:41,030
Jeg ved, jeg har tænkt mig at få mindst én.

632
00:33:41,030 --> 00:33:41,690
Jeg holde søger.

633
00:33:41,690 --> 00:33:42,625
>> Jeg finder en tre.

634
00:33:42,625 --> 00:33:44,250
Jeg ved, jeg har tænkt mig at få mindst tre.

635
00:33:44,250 --> 00:33:44,840
Jeg holde ud.

636
00:33:44,840 --> 00:33:45,660
Jeg finder en fem.

637
00:33:45,660 --> 00:33:49,760
Jeg ved, jeg har tænkt mig at få fem
hvis jeg får ned i den vej.

638
00:33:49,760 --> 00:33:52,580
Og jeg ved også, så
at min modstander, hvis jeg

639
00:33:52,580 --> 00:33:55,510
vælge midten af
de tre store valg,

640
00:33:55,510 --> 00:34:01,440
han vil give mig
noget, der er fem eller mindre.

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

642
00:34:02,150 --> 00:34:03,400
Jeg kan holde vil der.

643
00:34:03,400 --> 00:34:06,470
Jeg kan kigge ned og jeg
kan sige, hvad jeg vil

644
00:34:06,470 --> 00:34:08,239
at få, hvis jeg går ned midt vej?

645
00:34:08,239 --> 00:34:09,909
Jeg har tænkt mig at få, ja, tre der.

646
00:34:09,909 --> 00:34:12,080
Jeg har tænkt mig at få noget
der er mindst tre.

647
00:34:12,080 --> 00:34:16,030
Der er stadig ting mellem
tre og fem, så jeg holde søger.

648
00:34:16,030 --> 00:34:20,203
Åh, en ni, jeg vil helt sikkert
tage det over en tre.

649
00:34:20,203 --> 00:34:22,744
Jeg har tænkt mig at få mindst ni
hvis jeg går ned, at midterste sti.

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

651
00:34:25,530 --> 00:34:31,010
>> Nu er min modstander stopper og siger,
se, der er ingen mening længere.

652
00:34:31,010 --> 00:34:33,669
Jeg ved, at min
minimering modstander, han er

653
00:34:33,669 --> 00:34:36,210
kommer til at give mig de ting, der er
mindre end eller lig med fem,

654
00:34:36,210 --> 00:34:39,030
snarere end de ting, der er
større end eller lig med ni.

655
00:34:39,030 --> 00:34:39,530
Jeg stoppe.

656
00:34:39,530 --> 00:34:40,779
Jeg ser ikke nogen mere ved det.

657
00:34:40,779 --> 00:34:43,280
Jeg holde ud.

658
00:34:43,280 --> 00:34:44,850
>> Jeg ser ned på denne ene.

659
00:34:44,850 --> 00:34:46,370
Ned til bunden, finder jeg en seks.

660
00:34:46,370 --> 00:34:50,040
Jeg ved, jeg har tænkt mig at få mindst seks.

661
00:34:50,040 --> 00:34:53,130
Og hvad kan jeg gøre?

662
00:34:53,130 --> 00:34:54,877
Jeg kan stoppe.

663
00:34:54,877 --> 00:34:57,460
Fordi der er et valg mellem
noget, der er mindst seks

664
00:34:57,460 --> 00:34:59,250
og noget, der er
mindre end fem, han er

665
00:34:59,250 --> 00:35:02,570
kommer til at give mig de ting
der er mindre end fem.

666
00:35:02,570 --> 00:35:04,779
Og nu ved jeg, jeg har tænkt mig
at få præcis dette valg.

667
00:35:04,779 --> 00:35:06,195
Jeg har tænkt mig at få at fem valg.

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

669
00:35:08,980 --> 00:35:10,010
>> Jeg går tilbage op til toppen.

670
00:35:10,010 --> 00:35:11,450
Som jeg vil
vælge mellem noget

671
00:35:11,450 --> 00:35:14,449
der er større end eller lig med fire,
eller noget, der er lig med fem?

672
00:35:14,449 --> 00:35:17,140
Jeg har tænkt mig at tage noget
der er mindst fem.

673
00:35:17,140 --> 00:35:20,490
Jeg gå ned den sidste vej, alt
vejen ned til bunden.

674
00:35:20,490 --> 00:35:21,260
Der er en en.

675
00:35:21,260 --> 00:35:23,410
OK, i det mindste jeg har tænkt mig at få et point.

676
00:35:23,410 --> 00:35:24,427
Jeg holde ud.

677
00:35:24,427 --> 00:35:25,760
To, åh, det er bedre end en.

678
00:35:25,760 --> 00:35:27,100
Jeg har tænkt mig at få mindst to.

679
00:35:27,100 --> 00:35:28,610
Jeg finder en tre.

680
00:35:28,610 --> 00:35:31,450
Jeg ved, jeg har tænkt mig at få tre.

681
00:35:31,450 --> 00:35:34,690
>> Og det punkt ovenstående,
min modstander går

682
00:35:34,690 --> 00:35:38,540
at give mig noget, der er
mindre end eller lig med tre.

683
00:35:38,540 --> 00:35:40,940
Og nu kan jeg stoppe.

684
00:35:40,940 --> 00:35:46,290
Fordi i valget mellem mig bliver
kunne få en fem og min modstander

685
00:35:46,290 --> 00:35:52,290
giver mig noget mindre end tre,
Jeg er altid kommer til at tage, at fem.

686
00:35:52,290 --> 00:35:56,810
Så jeg ikke vurdere, at
nederste del af træet overhovedet.

687
00:35:56,810 --> 00:35:59,470
>> Nu kan det virke mindre.

688
00:35:59,470 --> 00:36:03,630
Men når små stumper af aritmetik,
større end og mindre end,

689
00:36:03,630 --> 00:36:10,640
kan skæres væk hele dele af
denne eksponentielt voksende træ,

690
00:36:10,640 --> 00:36:14,280
der fører til en enorm
mængde af opsparing, opsparing

691
00:36:14,280 --> 00:36:17,630
der er store nok, at jeg
kan begynde at spille konkurrencedygtige

692
00:36:17,630 --> 00:36:21,330
ved mere komplekse spil.

693
00:36:21,330 --> 00:36:27,030
>> Okay, hvis vi ser på størrelsen
og kompleksiteten af ​​de forskellige spil,

694
00:36:27,030 --> 00:36:29,470
Kryds og bolle var vores nemme eksempel.

695
00:36:29,470 --> 00:36:32,150
Vi har fået et lille bord, tre med tre.

696
00:36:32,150 --> 00:36:36,030
Vi får højst et gennemsnit på
omkring fire forskellige valg

697
00:36:36,030 --> 00:36:38,440
som vi går igennem spillet.

698
00:36:38,440 --> 00:36:42,720
Vi har et sted omkring 10 til
femte mulige forskellige blade.

699
00:36:42,720 --> 00:36:45,200
Og opbygge en tic-tac-toe
afspiller, godt, vi bare gjorde det.

700
00:36:45,200 --> 00:36:47,460
Det er nemt.

701
00:36:47,460 --> 00:36:49,890
>> Hvis vi går op til noget mere
kompleks, som Connect Four.

702
00:36:49,890 --> 00:36:53,170
Kan du huske dette spil, hvor
du taber de små tokens i?

703
00:36:53,170 --> 00:36:58,490
Det er en seks af syv bord,
ikke så meget større, stadig

704
00:36:58,490 --> 00:37:00,770
har omtrent samme forgrening
faktor som Kryds og bolle.

705
00:37:00,770 --> 00:37:05,410
Jeg har omkring fire valgmuligheder
hvor jeg kan sætte tingene i.

706
00:37:05,410 --> 00:37:10,760
Men nu, jeg har fået en masse mere
fører, 10 til 21. magt.

707
00:37:10,760 --> 00:37:14,440
Det er noget, der er nemt
nok, at vi løser det med det samme.

708
00:37:14,440 --> 00:37:17,560
>> Brikker, mere complex-- dig
fik en otte med otte bord.

709
00:37:17,560 --> 00:37:20,570
Du er kun på halvdelen af
dem når som helst, selv om.

710
00:37:20,570 --> 00:37:24,930
Du har fået en forgrening
faktor, der er ca. 2,8.

711
00:37:24,930 --> 00:37:28,160
Tja, vi har fået et par
bevæger du kan tage.

712
00:37:28,160 --> 00:37:33,870
Du har fået omkring 10 til 31. blade,
større, og større, og større rum.

713
00:37:33,870 --> 00:37:37,340
Som jeg er nødt til at søge gennem
disse større og større rum,

714
00:37:37,340 --> 00:37:42,220
det er, når ting som alfa-beta og
at kunne skåret væk hele brancher

715
00:37:42,220 --> 00:37:44,420
bliver afgørende.

716
00:37:44,420 --> 00:37:47,440
>> Nu var let nok i 1992 brikker.

717
00:37:47,440 --> 00:37:51,400
Et edb-program kaldet
Chinook slog verdens brikker

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

719
00:37:53,590 --> 00:37:57,260
Og siden da, nej
menneskelig mester spiller har

720
00:37:57,260 --> 00:38:02,290
været i stand til at slå de bedste
beregningsmæssige systemer.

721
00:38:02,290 --> 00:38:06,570
Hvis vi ser på noget som skak, nu
igen, har vi en otte med otte bord.

722
00:38:06,570 --> 00:38:09,870
Men vi har meget mere kompleks
stykker, meget mere komplekse bevægelser.

723
00:38:09,870 --> 00:38:14,610
Vi har en forgrening faktor på ca.
35, 35 mulige træk i gennemsnit

724
00:38:14,610 --> 00:38:20,030
at jeg kan tage, og en stat
rum, et antal blade,

725
00:38:20,030 --> 00:38:28,950
der er vokset til 10 til 123. strøm,
enorme antal af muligheder.

726
00:38:28,950 --> 00:38:35,570
>> Selv stadig moderne processorer
er i stand til at gøre dette med succes.

727
00:38:35,570 --> 00:38:43,900
I 1995 og derefter i 1997, en computer
program kaldet Deep Blue bygget af IBM

728
00:38:43,900 --> 00:38:49,601
der kørte på en kæmpe supercomputer
slå den nuværende verdensmester,

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
Det var et vendepunkt.

732
00:38:56,650 --> 00:39:00,620
I dag er dog, at samme behandling
magt sidder på min MacBook.

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

734
00:39:04,180 --> 00:39:06,440
>> Behandling hastighed holder
bliver hurtigere og hurtigere.

735
00:39:06,440 --> 00:39:09,500
Vi kan evaluere mere og mere
bestyrelser hurtigere og hurtigere.

736
00:39:09,500 --> 00:39:14,550
Men mere vigtigt, har vi bedre
evaluering funktioner og bedre beskæring

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

738
00:39:15,460 --> 00:39:19,560
Så vi kan søge i
plads mere komplekst.

739
00:39:19,560 --> 00:39:22,350
Den største af bestyrelsen
spil, som vi kan tænke på,

740
00:39:22,350 --> 00:39:26,310
noget lignende Go, der er
fik en 19 med 19 bord,

741
00:39:26,310 --> 00:39:32,490
nu pludselig er vi forbi det punkt
hvor beregningsmæssige systemer kan vinde.

742
00:39:32,490 --> 00:39:34,530
Der er ingen beregningsmæssige
systemet derude

743
00:39:34,530 --> 00:39:38,880
der kan slå en professionel Go-afspiller.

744
00:39:38,880 --> 00:39:45,000
Det bedste systemer i dag rang det om
slags god amatørniveau.

745
00:39:45,000 --> 00:39:49,285
Så der er stadig ganske lidt ud
der, at du ikke kan komme til endnu.

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

747
00:39:51,840 --> 00:39:55,360
>> Okay, disse
traditionelle brætspil,

748
00:39:55,360 --> 00:39:58,560
disse typer af systemer, hvor vi
bygge denne minimax, uanset om det har fået

749
00:39:58,560 --> 00:40:06,300
alpha-beta eller ikke, disse algoritmer arbejder
fordi der er visse begrænsninger.

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

751
00:40:08,520 --> 00:40:11,690
Vi ved, hvor alle brikkerne er.

752
00:40:11,690 --> 00:40:13,570
Verden er statisk.

753
00:40:13,570 --> 00:40:16,220
Ingen får at flytte
stykker rundt mens jeg er

754
00:40:16,220 --> 00:40:20,640
sidder der tænker, at tage min tur.

755
00:40:20,640 --> 00:40:23,140
Der er en handling plads, der er diskret.

756
00:40:23,140 --> 00:40:26,900
Jeg kan sætte min bonde her,
eller jeg kan sætte min bonde her.

757
00:40:26,900 --> 00:40:30,520
Jeg er ikke tilladt at sætte min bonde på
linien mellem de to felter.

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

759
00:40:34,430 --> 00:40:36,520
>> Og endelig de handlinger,
er deterministisk.

760
00:40:36,520 --> 00:40:39,790
Jeg ved, at hvis jeg siger,
tårn til ridder tre,

761
00:40:39,790 --> 00:40:44,660
mit tårn kommer til at ende på ridder
tre, så længe det er et gyldigt træk.

762
00:40:44,660 --> 00:40:47,830
Der er ingen usikkerhed om.

763
00:40:47,830 --> 00:40:52,490
Nu, da jeg går til mere
forskellige former for spil,

764
00:40:52,490 --> 00:40:55,960
vi nødt til at bryde disse antagelser.

765
00:40:55,960 --> 00:41:00,020
>> Hvad hvis jeg går til noget
Ligesom klassiske videospil?

766
00:41:00,020 --> 00:41:04,180
Her er et udvalg af video
spil fra Atari 2600.

767
00:41:04,180 --> 00:41:05,180
Hvad har jeg deroppe?

768
00:41:05,180 --> 00:41:08,440
Jeg har Frogger, Space
Invaders, faldgrube, og Pac-Man.

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

770
00:41:11,290 --> 00:41:14,840
Hvilke typer af miljøer
har jeg her nu?

771
00:41:14,840 --> 00:41:16,900
Hvilke af disse antagelser
skal jeg nødt til at bryde?

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

773
00:41:19,410 --> 00:41:21,570
>> Tja, det afhænger af spillet.

774
00:41:21,570 --> 00:41:28,170
Jeg kunne spille skak på 2600, og
det ville være ligesom det var før.

775
00:41:28,170 --> 00:41:33,020
For de fleste af disse systemer, der er
fuldstændig viden om verden.

776
00:41:33,020 --> 00:41:36,300
Der er helt
deterministiske handlinger.

777
00:41:36,300 --> 00:41:38,330
Men som regel, verdens
ikke længere statisk.

778
00:41:38,330 --> 00:41:41,970
Det vil sige, mens jeg sidder der
venter, er noget bevæger sig.

779
00:41:41,970 --> 00:41:44,320
De spøgelser kommer til at få mig.

780
00:41:44,320 --> 00:41:46,570
Skorpionen følger mig nedenunder.

781
00:41:46,570 --> 00:41:48,880
Space Invaders er
kommer tættere og tættere.

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

783
00:41:54,020 --> 00:41:55,510
Hvor godt kan vi gøre mod disse?

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

785
00:41:58,640 --> 00:42:02,790
>> For et par år siden, Google
havde et projekt kaldet

786
00:42:02,790 --> 00:42:12,030
DeepMind, hvor de trænede en computer
program at spille Atari 2600 spil.

787
00:42:12,030 --> 00:42:16,120
Og hvis du tror, ​​det er ikke alvorligt
virksomhed, resultaterne af deres undersøgelse

788
00:42:16,120 --> 00:42:19,920
blev offentliggjort i Nature, så
kun om så god en publikation

789
00:42:19,920 --> 00:42:22,500
som du overhovedet kan få.

790
00:42:22,500 --> 00:42:24,340
Og her er, hvor godt de udføres.

791
00:42:24,340 --> 00:42:29,220
>> De har en algoritme, der sad
og så bare skærmen indgange.

792
00:42:29,220 --> 00:42:34,080
Det fik ingen instrukser overhovedet
om reglerne i spillet.

793
00:42:34,080 --> 00:42:42,610
Og det var meningen at regne ud,
baseret sin score, hvor godt det gjorde.

794
00:42:42,610 --> 00:42:46,560
Det var et system, der brugte noget
kaldes forstærkning læring.

795
00:42:46,560 --> 00:42:48,380
Det vil sige, det så på sin score.

796
00:42:48,380 --> 00:42:51,620
Og hvis det fik en god score, er det sagt,
Jeg skal huske disse ting.

797
00:42:51,620 --> 00:42:53,310
Og jeg skal gøre dem igen.

798
00:42:53,310 --> 00:42:56,450
Og hvis det fik en dårlig score, er det sagt,
Jeg skal ikke gøre disse ting igen.

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

800
00:42:59,750 --> 00:43:03,430
>> Dette er den ydelse,
af disse uddannede systemer

801
00:43:03,430 --> 00:43:07,490
lov til at spille for en
par timer på hvert spil,

802
00:43:07,490 --> 00:43:12,490
sammenlignes med professionelle gamere.

803
00:43:12,490 --> 00:43:19,670
Så for alle de spil, der er
til venstre side af denne linje,

804
00:43:19,670 --> 00:43:25,920
denne selv-uddannede computerprogram
udkonkurrerede de professionelle gamere.

805
00:43:25,920 --> 00:43:29,690
Og for alt til
rigtige, professionelle gamere

806
00:43:29,690 --> 00:43:30,920
var stadig bedst.

807
00:43:30,920 --> 00:43:34,040

808
00:43:34,040 --> 00:43:36,850
For noget, der vidste
intet om reglerne, at

809
00:43:36,850 --> 00:43:43,020
vidste intet om strukturen af
spil, det er imponerende præstation.

810
00:43:43,020 --> 00:43:45,660
Og det er det, vi er i stand til at gøre i dag.

811
00:43:45,660 --> 00:43:50,239
>> OK, du siger, men hvis vi
tænke over AI i spil,

812
00:43:50,239 --> 00:43:52,530
normalt vi tænker på
ting, vi kan faktisk

813
00:43:52,530 --> 00:43:54,180
sætte sig ned og spille mod.

814
00:43:54,180 --> 00:43:58,760
Hvis jeg sætter mig ned, og jeg spiller
StarCraft, eller jeg spiller gratis Sieve,

815
00:43:58,760 --> 00:44:01,870
computerens modstander er den
person, der kontrollerer Zerg,

816
00:44:01,870 --> 00:44:06,770
eller styring af en anden kultur.

817
00:44:06,770 --> 00:44:11,920
Hvordan disse spillere
faktisk finde deres bevægelser?

818
00:44:11,920 --> 00:44:18,810
>> Nå, er disse spil struktureret
meget på samme måde som vores brætspil,

819
00:44:18,810 --> 00:44:22,250
disse spil, at vi vil
kollektivt kalder fire X Games,

820
00:44:22,250 --> 00:44:26,040
udforske, expand-- glemmer dem.

821
00:44:26,040 --> 00:44:26,980
Hvad er de?

822
00:44:26,980 --> 00:44:32,150
Udforsk, udvide, og slukke,
Jeg mener, er den sidste.

823
00:44:32,150 --> 00:44:36,060
Men de er dybest set
udforskning og erobre spil.

824
00:44:36,060 --> 00:44:41,020
Typisk computer modstander
der har begrænsede oplysninger.

825
00:44:41,020 --> 00:44:45,486
De ved ikke præcis, hvad der er
foregår bag den tåge af krig.

826
00:44:45,486 --> 00:44:47,735
De får ikke at se, hvad
du har i din beholdning.

827
00:44:47,735 --> 00:44:50,240

828
00:44:50,240 --> 00:44:52,800
>> Der er et miljø, der er dynamisk.

829
00:44:52,800 --> 00:44:56,180
Alt ændrer sig hele tiden.

830
00:44:56,180 --> 00:45:00,290
Du får ikke at sidde og
vente med at tage din flytning.

831
00:45:00,290 --> 00:45:02,810
Men de fleste ting er stadig diskrete.

832
00:45:02,810 --> 00:45:04,200
Jeg nødt til at sætte min by her.

833
00:45:04,200 --> 00:45:06,750
Eller jeg nødt til at sætte min by her.

834
00:45:06,750 --> 00:45:08,950
Og alt er deterministisk.

835
00:45:08,950 --> 00:45:14,660
Når jeg siger, flytte min enhed her, min enhed
bevæger sig her, medmindre en hindring pludselig

836
00:45:14,660 --> 00:45:17,700
kommer i spil.

837
00:45:17,700 --> 00:45:21,610
Nu, det er ikke alle computer
spil, der er derude i dag.

838
00:45:21,610 --> 00:45:27,320
>> Hvis jeg går og jeg spiller en første person typen
spil, noget som Thief eller Fallout

839
00:45:27,320 --> 00:45:33,350
eller Skyrim eller halogen, nu
Jeg har computer modstandere

840
00:45:33,350 --> 00:45:37,860
der er derude, der har
en helt anden situation.

841
00:45:37,860 --> 00:45:40,020
De har igen begrænset information.

842
00:45:40,020 --> 00:45:43,420
De kan kun se en
visse synsfelt.

843
00:45:43,420 --> 00:45:45,180
Miljøet er stadig dynamisk.

844
00:45:45,180 --> 00:45:48,280
Tingene ændrer sig hele tiden.

845
00:45:48,280 --> 00:45:52,300
>> Men nu har jeg en meget mere
kontinuerlig indsats plads.

846
00:45:52,300 --> 00:45:57,170
Jeg kan bare kigger en
lidt ud af døråbningen.

847
00:45:57,170 --> 00:46:00,650
Og nogle spil, min
handlinger er stokastisk.

848
00:46:00,650 --> 00:46:04,590
Jeg kommer til at forsøge at hoppe over muren,
men jeg har fået en chance for at fejle.

849
00:46:04,590 --> 00:46:08,280

850
00:46:08,280 --> 00:46:14,550
Disse typer af spil er at komme tættere
og tættere på den slags controllere

851
00:46:14,550 --> 00:46:17,330
at vi bygger i robotteknologi.

852
00:46:17,330 --> 00:46:21,050
>> I robotteknologi, vi er nødt til at påtage sig
at vi har begrænset information.

853
00:46:21,050 --> 00:46:23,070
Vi har sensorer,
fortælle os om verden.

854
00:46:23,070 --> 00:46:25,860
Vi har en altid skiftende,
dynamisk miljø.

855
00:46:25,860 --> 00:46:30,440
Vi har en verden, hvor pladsen er
kontinuerlig snarere end diskret.

856
00:46:30,440 --> 00:46:36,260
Og vores handlinger, når vi forsøger
dem, har en chance for at fejle.

857
00:46:36,260 --> 00:46:40,960
Og i virkeligheden, moderne spil
controllere til din Halo modstander,

858
00:46:40,960 --> 00:46:48,690
eller for de NPC'ere i Skyrim, dybest set
køre små robotteknologi arkitekturer.

859
00:46:48,690 --> 00:46:50,380
>> De fornemme verden.

860
00:46:50,380 --> 00:46:52,910
De bygge en model af verden.

861
00:46:52,910 --> 00:46:57,950
De beregne baseret på et sæt af
mål, som de gerne vil udrette.

862
00:46:57,950 --> 00:47:03,110
De planlægger foranstaltninger baseret
om, hvad de ved.

863
00:47:03,110 --> 00:47:07,940
Og dem er nøjagtig de samme typer
af systemer, som vi bygger i robotteknologi.

864
00:47:07,940 --> 00:47:11,420
Så disse arkitekturer, til
samle dette tilbage,

865
00:47:11,420 --> 00:47:14,500
er ofte helt den samme.

866
00:47:14,500 --> 00:47:16,340
>> Så lad os se, om vi kan se, at.

867
00:47:16,340 --> 00:47:19,210
Lad os gå tilbage til vores
Kryds og bolle eksempel.

868
00:47:19,210 --> 00:47:22,690
Og jeg har tænkt mig at stille et par min
post-docs for at komme op og hjælpe mig.

869
00:47:22,690 --> 00:47:26,970
Så Chen Ming, og Alessandro, og
Olivier, hvis du fyre ville komme op.

870
00:47:26,970 --> 00:47:32,080

871
00:47:32,080 --> 00:47:35,440
Og jeg har tænkt mig at brug
et par frivillige

872
00:47:35,440 --> 00:47:37,590
>> OK, så jeg en hånd op til højre
der i midten.

873
00:47:37,590 --> 00:47:39,965
Lad mig tage en mere, nogen
yderligere i ryggen måske.

874
00:47:39,965 --> 00:47:40,881
Okay, derovre.

875
00:47:40,881 --> 00:47:41,490
Kom op.

876
00:47:41,490 --> 00:47:44,190

877
00:47:44,190 --> 00:47:45,335
Okay.

878
00:47:45,335 --> 00:47:49,490
Så lad os tage den dækning ned.

879
00:47:49,490 --> 00:48:03,700
Og hvis du fyre ville komme ret
tilbage omkring her for mig, fantastisk.

880
00:48:03,700 --> 00:48:06,580
>> Så dette er en robot kaldet Baxter.

881
00:48:06,580 --> 00:48:10,880
Og Baxter er en robot, der er en
kommerciel platform, designet

882
00:48:10,880 --> 00:48:13,030
af et selskab kaldet Rethink.

883
00:48:13,030 --> 00:48:16,580
Og denne robot er konstrueret
til mindre produktion.

884
00:48:16,580 --> 00:48:19,265
Men i dag vil vi
bruge den til at spille tic-tac-toe.

885
00:48:19,265 --> 00:48:21,930

886
00:48:21,930 --> 00:48:27,150
Nu, denne robot er også noget
det er relativt enestående.

887
00:48:27,150 --> 00:48:32,950
Fordi hvis jeg stod overalt
tæt på en standard fabrik automatisering

888
00:48:32,950 --> 00:48:39,580
systemet, ville jeg være i meget alvorlig
fare for at blive skadet.

889
00:48:39,580 --> 00:48:45,600
>> Baxter er imidlertid designet til at være
relativt sikkert at interagere med.

890
00:48:45,600 --> 00:48:48,680
Og så jeg kan skubbe på denne robot.

891
00:48:48,680 --> 00:48:52,350
Og du kan se det er lidt
bit fleksibelt som den bevæger sig rundt.

892
00:48:52,350 --> 00:48:57,250
Og jeg kan flytte det
hvor jeg gerne vil have det til at gå.

893
00:48:57,250 --> 00:49:03,410
Nu i en normal robotsystem,
vi ville have en sæt sammenføjninger her

894
00:49:03,410 --> 00:49:07,970
der ville være direkte
reagerer på position kommandoer.

895
00:49:07,970 --> 00:49:13,180
Og de ville ikke nødvendigvis pleje
hvis de bevæger sig gennem fri luft,

896
00:49:13,180 --> 00:49:15,555
eller hvis de var på vej
gennem min brystkasse.

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
Og typisk, hvis du var
her med et industrielt system

900
00:49:22,090 --> 00:49:23,400
du ville gå langtfra det.

901
00:49:23,400 --> 00:49:26,280
Der ville være gul
sikkerhed tape hele vejen rundt.

902
00:49:26,280 --> 00:49:28,310
Dette system har en
lidt anderledes design

903
00:49:28,310 --> 00:49:32,130
at være mere brugervenlige og lettere
for folk til at interagere med,

904
00:49:32,130 --> 00:49:36,380
i, at der i hver samling, er der en fjeder.

905
00:49:36,380 --> 00:49:39,110
Og i stedet for at styre
en nøjagtig position,

906
00:49:39,110 --> 00:49:43,110
vi kontrollerer en vis mængde
drejningsmoment, en vis mængde kraft,

907
00:49:43,110 --> 00:49:45,874
at vi gerne vil være på, at foråret.

908
00:49:45,874 --> 00:49:47,790
Okay, så lad mig
tage vores frivillige her.

909
00:49:47,790 --> 00:49:48,540
Hej hvad hedder du?

910
00:49:48,540 --> 00:49:49,010
>> PUBLIKUM: Louis.

911
00:49:49,010 --> 00:49:49,635
>> SPEAKER: Louis.

912
00:49:49,635 --> 00:49:50,490
Dejligt at se dig.

913
00:49:50,490 --> 00:49:50,990
Og?

914
00:49:50,990 --> 00:49:51,610
>> PUBLIKUM: David.

915
00:49:51,610 --> 00:49:51,960
>> SPEAKER: David.

916
00:49:51,960 --> 00:49:52,550
Dejligt at møde dig.

917
00:49:52,550 --> 00:49:54,508
Hvis du fyre ville vente
lige her for en anden,

918
00:49:54,508 --> 00:49:56,420
Jeg har tænkt mig at give dig
en chance for at gøre dette.

919
00:49:56,420 --> 00:50:00,610
Så denne robot, hvis du kommer op
og hvis du skubber forsigtigt på det,

920
00:50:00,610 --> 00:50:03,780
du kommer til at se, at
den bevæger sig en lille smule.

921
00:50:03,780 --> 00:50:06,349
Og hvis du har fat i det rigtige
her på håndleddet lige

922
00:50:06,349 --> 00:50:09,390
ovenfor, hvor disse knapper er det
ser ud som du skal få fat i knapperne,

923
00:50:09,390 --> 00:50:13,100
men få fat i lige over det i stedet, vil du
være i stand til meget forsigtigt manipulere den

924
00:50:13,100 --> 00:50:14,545
gennem rummet.

925
00:50:14,545 --> 00:50:15,920
Louis, du ønsker at give det en chance?

926
00:50:15,920 --> 00:50:19,465
Så giv det bare en lille smule
skubbe til at starte med.

927
00:50:19,465 --> 00:50:23,190
Og så hvis du lægger dine fingre
lige der, og holde fast til det,

928
00:50:23,190 --> 00:50:24,807
fordi det vil bevæge sig for dig så.

929
00:50:24,807 --> 00:50:27,824

930
00:50:27,824 --> 00:50:29,365
Okay, du ønsker at give det en chance?

931
00:50:29,365 --> 00:50:29,980
Kom op.

932
00:50:29,980 --> 00:50:32,300
Så giver det bare en blid
skubbe der til at starte.

933
00:50:32,300 --> 00:50:33,820
Du kan føle, hvordan det er.

934
00:50:33,820 --> 00:50:40,060
Og derefter, hvis du har fat i det rigtige der,
vil du være i stand til at manøvrere på omkring.

935
00:50:40,060 --> 00:50:41,280
>> OK.

936
00:50:41,280 --> 00:50:47,360
Så typisk denne form for en robot ville
anvendes til fremstilling i lille skala.

937
00:50:47,360 --> 00:50:50,980
Og jeg har tænkt mig at flytte denne arm bare
ned af vejen lidt her.

938
00:50:50,980 --> 00:50:55,750
Men i dag, vi kommer til at bruge
samme Kryds og bolle spille systemet

939
00:50:55,750 --> 00:50:59,520
baseret på Minimax at vi bygget tidligere.

940
00:50:59,520 --> 00:51:00,549
OK?

941
00:51:00,549 --> 00:51:02,340
Så du fyre er hver
kommer til at spille et spil.

942
00:51:02,340 --> 00:51:04,210
Louis, er du nødt til at være først.

943
00:51:04,210 --> 00:51:05,920
Lad mig bare holde op her for en anden.

944
00:51:05,920 --> 00:51:10,949
Jeg har tænkt mig at have du står ret
her, bare så alle kan se dig.

945
00:51:10,949 --> 00:51:11,990
Er du fyre oprettet her?

946
00:51:11,990 --> 00:51:13,120
>> ROBOT: Velkommen.

947
00:51:13,120 --> 00:51:15,910
Lad os spille Kryds og bolle.

948
00:51:15,910 --> 00:51:20,860
Du må ikke forstå din token før
Jeg siger, at det er din tur.

949
00:51:20,860 --> 00:51:22,050
Jeg starter spillet.

950
00:51:22,050 --> 00:51:27,900

951
00:51:27,900 --> 00:51:28,750
Det er min tur.

952
00:51:28,750 --> 00:51:47,002

953
00:51:47,002 --> 00:51:50,210
SPEAKER: Nu, hvis du kunne tage en af
dine brikker og gå videre og placere den.

954
00:51:50,210 --> 00:51:51,446
ROBOT: Det er din tur.

955
00:51:51,446 --> 00:51:53,430
[LATTER]

956
00:51:53,430 --> 00:51:54,836
Det er min tur.

957
00:51:54,836 --> 00:51:56,820
[LATTER]

958
00:51:56,820 --> 00:52:12,196

959
00:52:12,196 --> 00:52:15,680
[LATTER]

960
00:52:15,680 --> 00:52:16,570
Det er din tur.

961
00:52:16,570 --> 00:52:21,397

962
00:52:21,397 --> 00:52:23,688
SPEAKER: Den menneskelige race er
regner med dig her, Louis.

963
00:52:23,688 --> 00:52:27,440

964
00:52:27,440 --> 00:52:28,350
>> ROBOT: Det er min tur.

965
00:52:28,350 --> 00:52:44,810

966
00:52:44,810 --> 00:52:47,015
>> SPEAKER: Så Baxter
held blokeret her.

967
00:52:47,015 --> 00:52:49,670

968
00:52:49,670 --> 00:52:52,480
>> ROBOT: Det er din tur.

969
00:52:52,480 --> 00:52:53,360
Det er min tur.

970
00:52:53,360 --> 00:53:14,730

971
00:53:14,730 --> 00:53:16,810
Det er din tur.

972
00:53:16,810 --> 00:53:17,760
Det er min tur.

973
00:53:17,760 --> 00:53:21,330

974
00:53:21,330 --> 00:53:23,830
SPEAKER: Og vi vil lade Baxter
afslutte sin sidste træk her.

975
00:53:23,830 --> 00:53:36,622

976
00:53:36,622 --> 00:53:39,090
>> [LATTER]

977
00:53:39,090 --> 00:53:40,480
>> ROBOT: Det er en uafgjort.

978
00:53:40,480 --> 00:53:42,030
Jeg vil vinde næste gang.

979
00:53:42,030 --> 00:53:43,365
>> [LATTER]

980
00:53:43,365 --> 00:53:45,210
>> SPEAKER: Okay,
tak meget, Louis.

981
00:53:45,210 --> 00:53:46,094
Tak.

982
00:53:46,094 --> 00:53:46,980
Du kan gå på denne måde.

983
00:53:46,980 --> 00:53:49,759
>> ROBOT: Jeg starter spillet.

984
00:53:49,759 --> 00:53:51,800
SPEAKER: Så lad mig forklare
til dig endnu en lille

985
00:53:51,800 --> 00:53:55,410
lidt, før vi får vores omkamp her.

986
00:53:55,410 --> 00:53:57,200
Hvad der præcist sker der?

987
00:53:57,200 --> 00:53:59,430
Så robotten har et kamera op øverst her.

988
00:53:59,430 --> 00:54:01,330
Og det ser ned på brættet.

989
00:54:01,330 --> 00:54:04,470
Og det er at se, om
det har fået en rød O eller en blå

990
00:54:04,470 --> 00:54:10,450
og hvid X. Som dem, bliver placeret på
bord, det er dybest set den samme indgang

991
00:54:10,450 --> 00:54:13,890
at vi ville være at læse ind fra
vores datastruktur fra skærmen.

992
00:54:13,890 --> 00:54:17,290
Det kører det samme
Minimax algoritme til at være

993
00:54:17,290 --> 00:54:21,010
stand til at finde, hvor at
placere en god token.

994
00:54:21,010 --> 00:54:24,820
>> Og så giver vi en kommando om
hvor vi gerne et token, der skal placeres.

995
00:54:24,820 --> 00:54:26,120
Armen bevæger sig ud.

996
00:54:26,120 --> 00:54:31,750
Det er ved hjælp af et vakuum griber til at anvende
nogle sugning til det stykke træ,

997
00:54:31,750 --> 00:54:35,240
samle den op, flytte den til højre
stedet, og slip derefter suge

998
00:54:35,240 --> 00:54:36,950
og slip det.

999
00:54:36,950 --> 00:54:38,990
Okay, vi kommer
at give det en mere skudt

1000
00:54:38,990 --> 00:54:40,930
med en lidt smartere spiller her.

1001
00:54:40,930 --> 00:54:42,290
Er du klar?

1002
00:54:42,290 --> 00:54:46,150
Okay, hvis du vil stå lige op
her og give en-- vise sig på denne måde

1003
00:54:46,150 --> 00:54:47,955
så du kan se alle.

1004
00:54:47,955 --> 00:54:48,830
Og derefter [uhørligt].

1005
00:54:48,830 --> 00:54:49,330
>> ROBOT: Det er min tur.

1006
00:54:49,330 --> 00:54:50,455
>> SPEAKER: Baxter starter.

1007
00:54:50,455 --> 00:55:10,750

1008
00:55:10,750 --> 00:55:11,730
Det er din tur.

1009
00:55:11,730 --> 00:55:16,490

1010
00:55:16,490 --> 00:55:17,520
Det er min tur.

1011
00:55:17,520 --> 00:55:38,740

1012
00:55:38,740 --> 00:55:39,690
Det er din tur.

1013
00:55:39,690 --> 00:55:46,330

1014
00:55:46,330 --> 00:55:47,165
Det er min tur.

1015
00:55:47,165 --> 00:56:01,252

1016
00:56:01,252 --> 00:56:06,192
>> [LATTER]

1017
00:56:06,192 --> 00:56:08,542
>> SPEAKER: [WHISPERING] Just
lad ham gå videre og vinde.

1018
00:56:08,542 --> 00:56:09,500
ROBOT: Det er din tur.

1019
00:56:09,500 --> 00:56:15,099

1020
00:56:15,099 --> 00:56:15,890
SPEAKER: Det er OK.

1021
00:56:15,890 --> 00:56:20,390

1022
00:56:20,390 --> 00:56:21,360
>> ROBOT: Det er min tur.

1023
00:56:21,360 --> 00:56:24,825

1024
00:56:24,825 --> 00:56:26,805
>> [LATTER]

1025
00:56:26,805 --> 00:56:42,650

1026
00:56:42,650 --> 00:56:43,510
>> Jeg vinder.

1027
00:56:43,510 --> 00:56:45,620
>> [LATTER]

1028
00:56:45,620 --> 00:56:46,595
>> Jeg starter spillet.

1029
00:56:46,595 --> 00:56:48,261
>> SPEAKER: Okay, tak.

1030
00:56:48,261 --> 00:56:50,180

1031
00:56:50,180 --> 00:56:55,590
Okay, jeg tror, ​​vi har fået tid til
endnu en fremragende Kryds og bolle-afspiller,

1032
00:56:55,590 --> 00:57:00,490
nogen, der kan sætte denne ting til
matche, der ved, hvad de laver.

1033
00:57:00,490 --> 00:57:03,010
>> [LATTER]

1034
00:57:03,010 --> 00:57:05,560
>> Hvem kommer til at være vores mester her?

1035
00:57:05,560 --> 00:57:08,110
Okay, dine venner meldte dig.

1036
00:57:08,110 --> 00:57:11,190
Det er godt nok for mig.

1037
00:57:11,190 --> 00:57:12,194
Fortæl mig dit navn igen.

1038
00:57:12,194 --> 00:57:12,860
PUBLIKUM: Tamir.

1039
00:57:12,860 --> 00:57:14,193
SPEAKER: Tamir, rart at se dig.

1040
00:57:14,193 --> 00:57:19,270
Okay, igen, vi kommer til at sætte dig
lige op her, så alle kan se dig.

1041
00:57:19,270 --> 00:57:22,070
Du er vores repræsentant
i denne kamp nu.

1042
00:57:22,070 --> 00:57:24,540
Baxter er én og åh og åh.

1043
00:57:24,540 --> 00:57:26,300
Eller ked af det, man oh og én.

1044
00:57:26,300 --> 00:57:27,490
Og det er op til dig her.

1045
00:57:27,490 --> 00:57:29,340
Baxter vil komme til at bevæge sig først, selv om.

1046
00:57:29,340 --> 00:57:30,435
Så.

1047
00:57:30,435 --> 00:57:31,310
ROBOT: Det er min tur.

1048
00:57:31,310 --> 00:57:45,226

1049
00:57:45,226 --> 00:57:48,208
>> [LATTER]

1050
00:57:48,208 --> 00:57:52,720

1051
00:57:52,720 --> 00:57:55,780
>> Det er din tur.

1052
00:57:55,780 --> 00:57:56,845
Det er min tur.

1053
00:57:56,845 --> 00:58:18,130

1054
00:58:18,130 --> 00:58:18,965
Det er din tur.

1055
00:58:18,965 --> 00:58:28,751

1056
00:58:28,751 --> 00:58:30,248
Det er min tur.

1057
00:58:30,248 --> 00:58:51,210

1058
00:58:51,210 --> 00:58:52,160
Det er din tur.

1059
00:58:52,160 --> 00:59:00,854

1060
00:59:00,854 --> 00:59:03,365
>> [LATTER]

1061
00:59:03,365 --> 00:59:04,240
ROBOT: Det er min tur.

1062
00:59:04,240 --> 00:59:06,930
SPEAKER: Det er meget sværere, når
du står op her, folkens.

1063
00:59:06,930 --> 00:59:19,400

1064
00:59:19,400 --> 00:59:21,840
[LATTER]

1065
00:59:21,840 --> 00:59:26,730

1066
00:59:26,730 --> 00:59:29,054
ROBOT: Du mennesker er så nemme at slå.

1067
00:59:29,054 --> 00:59:30,803
[Latter og bifald]

1068
00:59:30,803 --> 00:59:31,886
SPEAKER: tak.

1069
00:59:31,886 --> 00:59:34,692
ROBOT: Jeg vinder.

1070
00:59:34,692 --> 00:59:35,400
Jeg starter spillet.

1071
00:59:35,400 --> 00:59:39,500
>> SPEAKER: Okay, tak meget
meget til Olivier, og Alessandro,

1072
00:59:39,500 --> 00:59:41,616
og Chen Ming.

1073
00:59:41,616 --> 00:59:45,600
>> [BIFALD]

1074
00:59:45,600 --> 00:59:47,040
>> Jeg vil gerne gøre et sidste punkt.

1075
00:59:47,040 --> 00:59:51,630
Så Baxter ved meget
ende der, snydt.

1076
00:59:51,630 --> 00:59:54,160

1077
00:59:54,160 --> 00:59:56,310
Og det var uventet.

1078
00:59:56,310 --> 01:00:00,440
En af de fantastiske
ting om AI er, at vi

1079
01:00:00,440 --> 01:00:05,070
udføre arbejde i AI, så vi kan bygge
virkelig interessant og intelligent

1080
01:00:05,070 --> 01:00:06,930
enheder.

1081
01:00:06,930 --> 01:00:10,130
Men vi også gøre arbejdet i AI
fordi det fortæller os noget

1082
01:00:10,130 --> 01:00:13,940
om, hvordan mennesker er intelligente.

1083
01:00:13,940 --> 01:00:17,280
>> En af de foretrukne
undersøgelser fra mit laboratorium er

1084
01:00:17,280 --> 01:00:23,660
se på, hvad der sker, når
maskiner uventet snyde.

1085
01:00:23,660 --> 01:00:27,070
Vi gjorde dette oprindeligt ikke med
Baxter spiller Kryds og bolle,

1086
01:00:27,070 --> 01:00:30,340
men med en mindre robot ved navn Nao,
der spillede rock papir-saks.

1087
01:00:30,340 --> 01:00:33,010

1088
01:00:33,010 --> 01:00:35,800
Og nogle gange efter
spille masser og masser

1089
01:00:35,800 --> 01:00:41,580
af kedelige sten-papir-saks spil,
robotten ville kaste en gestus,

1090
01:00:41,580 --> 01:00:48,616
taber, og så pludselig ændrer
sin gestus og siger, jeg vinder.

1091
01:00:48,616 --> 01:00:50,480
>> [LATTER]

1092
01:00:50,480 --> 01:00:56,090
>> Nu, nogle gange ville vi også have robotten,
lige som en kontrol, smide en gestus,

1093
01:00:56,090 --> 01:01:01,270
vinde, og ændre sin gestus
at tabe, smide kampen,

1094
01:01:01,270 --> 01:01:04,070
snyde for at tabe.

1095
01:01:04,070 --> 01:01:07,540
Og det er ikke nær så overbevisende.

1096
01:01:07,540 --> 01:01:09,890
Robotten, der snyder
med henblik på at vinde folk

1097
01:01:09,890 --> 01:01:14,660
svare som om det er
ud for at få dem, ligesom det

1098
01:01:14,660 --> 01:01:17,690
søger aktivt deres ødelæggelse.

1099
01:01:17,690 --> 01:01:19,210
>> [LATTER]

1100
01:01:19,210 --> 01:01:20,990
>> Det bliver en agent.

1101
01:01:20,990 --> 01:01:21,840
Det er ligesom en person.

1102
01:01:21,840 --> 01:01:23,970
Det har tro og hensigt.

1103
01:01:23,970 --> 01:01:27,470
Og det er ikke godt hensigt.

1104
01:01:27,470 --> 01:01:33,790
Og robotten, der kaster
Spillet er bare funktionsfejl.

1105
01:01:33,790 --> 01:01:36,990
Det er bare en ødelagt enhed.

1106
01:01:36,990 --> 01:01:41,405
Lad mig vise dig et par eksempler
af, at der fra et par af vores deltagere.

1107
01:01:41,405 --> 01:01:43,990

1108
01:01:43,990 --> 01:01:45,600
Så her er snyd for at tabe.

1109
01:01:45,600 --> 01:01:46,266
>> [VIDEO PLAYBACK]

1110
01:01:46,266 --> 01:01:47,010
- [Uhørligt] vinde.

1111
01:01:47,010 --> 01:01:49,550
Lad os lege.

1112
01:01:49,550 --> 01:01:50,538
>> -Vent, hvad?

1113
01:01:50,538 --> 01:01:54,490

1114
01:01:54,490 --> 01:01:55,352
>> - [Uhørligt] vinde.

1115
01:01:55,352 --> 01:01:58,280
Lad os lege.

1116
01:01:58,280 --> 01:01:59,400
>> [Uhørligt] vinde.

1117
01:01:59,400 --> 01:02:02,290
Lad os lege.

1118
01:02:02,290 --> 01:02:05,490
>> SPEAKER: Og her er snyd at vinde.

1119
01:02:05,490 --> 01:02:06,438
>> -Ja, Vinder jeg.

1120
01:02:06,438 --> 01:02:07,394
Lad os lege.

1121
01:02:07,394 --> 01:02:08,828
>> -Du Kan ikke gøre det.

1122
01:02:08,828 --> 01:02:10,740
>> [LATTER]

1123
01:02:10,740 --> 01:02:12,174

1124
01:02:12,174 --> 01:02:13,979
>> -Ja, Vinder jeg.

1125
01:02:13,979 --> 01:02:14,520
-Du Snydt.

1126
01:02:14,520 --> 01:02:17,990

1127
01:02:17,990 --> 01:02:20,010
Du snydt nu.

1128
01:02:20,010 --> 01:02:21,140
>> -Ja, Vinder jeg.

1129
01:02:21,140 --> 01:02:22,940
>> -Hey, Du snyder.

1130
01:02:22,940 --> 01:02:26,670
Du snyder, super snyde.

1131
01:02:26,670 --> 01:02:27,650
>> [END AFSPIL]

1132
01:02:27,650 --> 01:02:31,130
>> SPEAKER: Disse forskellige
reaktioner hurtigt

1133
01:02:31,130 --> 01:02:34,890
ændre vores opfattelse af enheden.

1134
01:02:34,890 --> 01:02:36,780
Betyder det, at
vi bevidst bygger

1135
01:02:36,780 --> 01:02:40,370
maskiner, der snyder, fordi det er
den bedste teknik, som vi kan gøre?

1136
01:02:40,370 --> 01:02:44,680
Nej, men det fortæller os noget
virkelig interessant om mennesker.

1137
01:02:44,680 --> 01:02:49,710
Den ting, der snyder dig og
stjæler din sejr, det er

1138
01:02:49,710 --> 01:02:53,660
noget, der er i live, det er
animere, der er ude for at få dig.

1139
01:02:53,660 --> 01:02:54,680
Det har mentale tilstand.

1140
01:02:54,680 --> 01:02:55,400
Det har tro.

1141
01:02:55,400 --> 01:02:57,170
Det har til hensigt.

1142
01:02:57,170 --> 01:03:01,540
>> Den ting, der hænder
spil til dig, det er ikke.

1143
01:03:01,540 --> 01:03:04,670
Det er bare funktionsfejl.

1144
01:03:04,670 --> 01:03:08,900
Det er på mange måder, hvorfor det er
let at kaste spil med børnene.

1145
01:03:08,900 --> 01:03:12,050
Men hvis du prøver at snyde dem
og sortering af krav på sejren

1146
01:03:12,050 --> 01:03:15,200
når, du ved, bare for at forkorte
spil, vil de fanger dig med det samme.

1147
01:03:15,200 --> 01:03:19,040

1148
01:03:19,040 --> 01:03:23,140
Disse former for effekter,
vi ser kommer ud af AI,

1149
01:03:23,140 --> 01:03:26,490
de underviser os en masse om os selv.

1150
01:03:26,490 --> 01:03:28,076
>> Okay, det er det for i dag.

1151
01:03:28,076 --> 01:03:30,450
Tak meget til David og
Harvard produktion teamet

1152
01:03:30,450 --> 01:03:32,350
for at komme ned.

1153
01:03:32,350 --> 01:03:33,820
>> [BIFALD]

1154
01:03:33,820 --> 01:03:36,760

1155
01:03:36,760 --> 01:03:41,840
>> Vi vil se dig for quiz én,
og derefter til en sidste forelæsning.

1156
01:03:41,840 --> 01:03:43,025
Hav en god dag.

1157
01:03:43,025 --> 01:03:44,965
>> [BIFALD]

1158
01:03:44,965 --> 01:03:48,360

1159
01:03:48,360 --> 01:03:51,825
>> [Musik spiller]

1160
01:03:51,825 --> 01:03:54,950
David J MALAN: Nå, vi sandsynligvis har brug for
at indføre en form for kryptering,

1161
01:03:54,950 --> 01:03:55,450
højre?

1162
01:03:55,450 --> 01:03:58,650
Fordi så overskrifterne i
disse HTTP-anmodninger vil være

1163
01:03:58,650 --> 01:04:01,530
scrambled så alle
forsøger at snuse din trafik

1164
01:04:01,530 --> 01:04:03,400
vil faktisk ikke kunne se dem.

1165
01:04:03,400 --> 01:04:05,254
Så hvad er løsningen på dette problem?

1166
01:04:05,254 --> 01:04:07,920
Nå, vi er nødt til rent faktisk at indføre
kryptering i formlen,

1167
01:04:07,920 --> 01:04:11,010
så når denne person er
at overføre data fra A til B,

1168
01:04:11,010 --> 01:04:12,390
vi kan sikkert send--

1169
01:04:12,390 --> 01:04:14,590
>> [LATTER]

1170
01:04:14,590 --> 01:04:19,530
>> De oplysninger på en måde, at den
modstander kan ikke, i virkeligheden, se det.