1
00:00:00,000 --> 00:00:01,924
>> [RIPRODUZIONE DI BRANI MUSICALI]

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

3
00:00:10,600 --> 00:00:13,280
>> SPEAKER: Bentornato, tutti.

4
00:00:13,280 --> 00:00:15,440
Questo è CS50.

5
00:00:15,440 --> 00:00:21,040
E oggi, abbiamo un sacco di
cose interessanti di cui parlare.

6
00:00:21,040 --> 00:00:25,500
Prima, però, devo ricordare
si di un paio di cose amministrative.

7
00:00:25,500 --> 00:00:30,160
Questa settimana è un quiz, Mercoledì
o per la sezione Yale

8
00:00:30,160 --> 00:00:32,940
il martedì e il giovedì, il Giovedi.

9
00:00:32,940 --> 00:00:38,170
Non ci sono recensioni quiz
stasera a Yale, 5:30-07:00.

10
00:00:38,170 --> 00:00:40,030
Ad Harvard, hanno registrato uno ieri.

11
00:00:40,030 --> 00:00:43,000
E tutti possono vedere che on-line.

12
00:00:43,000 --> 00:00:49,406
>> Inoltre, questa settimana o all'inizio della prossima settimana,
abbiamo la nostra ultima lezione CS50.

13
00:00:49,406 --> 00:00:51,450
[Geme] Lo so.

14
00:00:51,450 --> 00:00:54,140
E 'venuto così presto.

15
00:00:54,140 --> 00:00:57,820
Studenti di Yale avranno un live
conferenza qui in scuola di legge

16
00:00:57,820 --> 00:00:59,920
auditorium il Venerdì.

17
00:00:59,920 --> 00:01:01,140
Ci saranno torta.

18
00:01:01,140 --> 00:01:05,570
Studenti di Harvard avranno la
ultima conferenza in Sanders il Lunedi.

19
00:01:05,570 --> 00:01:08,050
Ci sarà anche la torta.

20
00:01:08,050 --> 00:01:14,000
>> Inoltre, questa settimana il Venerdì, per chi
di voi che stanno venendo a New Haven,

21
00:01:14,000 --> 00:01:15,740
abbiamo il CS50 Expo.

22
00:01:15,740 --> 00:01:18,850
Abbiamo più di 30
diversi gruppi registrati

23
00:01:18,850 --> 00:01:22,530
per mostrare tutto
da barche a vela autonomi,

24
00:01:22,530 --> 00:01:27,170
a sistemi che riconoscono
ritratti digitali, al calcolatore

25
00:01:27,170 --> 00:01:32,100
musica e computer music-prodotta.

26
00:01:32,100 --> 00:01:33,610
Quindi, unitevi a noi.

27
00:01:33,610 --> 00:01:36,460
Penso che sarà un grande momento.

28
00:01:36,460 --> 00:01:40,320
>> Oggi, però, si arriva a
continuare a parlare di intelligenza artificiale,

29
00:01:40,320 --> 00:01:43,150
sull'intelligenza artificiale.

30
00:01:43,150 --> 00:01:46,070
E una delle cose che
stiamo andando a raggiungere oggi

31
00:01:46,070 --> 00:01:51,750
è l'idea di come
utilizzare AI per risolvere i problemi.

32
00:01:51,750 --> 00:01:54,690
Ora, come sempre, cominciamo
con qualcosa di semplice.

33
00:01:54,690 --> 00:01:57,120
E stiamo per iniziare
con una semplice idea.

34
00:01:57,120 --> 00:01:59,920
E questo è utilizzando la ricerca.

35
00:01:59,920 --> 00:02:06,990
>> Quindi immaginate per un momento che io
hanno un compito che ho bisogno di eseguire.

36
00:02:06,990 --> 00:02:11,970
E mi piacerebbe avere questo compito
automatizzato da un agente software.

37
00:02:11,970 --> 00:02:17,100
Immaginate che io sto cercando di prenotare un set
di voli da, diciamo, Boston

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

39
00:02:20,040 --> 00:02:24,230
Potrei andare attraverso e ho potuto usare
uno della meravigliosa ricerca online

40
00:02:24,230 --> 00:02:28,790
strumenti, che sta per fare
fondamentalmente lo stesso processo che siamo

41
00:02:28,790 --> 00:02:30,030
andando a piedi fino ad oggi.

42
00:02:30,030 --> 00:02:34,100
Ma se non si dispone di tale
strumento, cosa faresti?

43
00:02:34,100 --> 00:02:37,570
>> Beh, si potrebbe guardare e
vedo e dico, io sono a Boston.

44
00:02:37,570 --> 00:02:41,520
Quali voli sono disponibili per me?

45
00:02:41,520 --> 00:02:44,390
Ora, forse ho tre
voli possibili su Boston

46
00:02:44,390 --> 00:02:47,180
che si adatta il tempo
quando ho bisogno di lasciare.

47
00:02:47,180 --> 00:02:48,830
Potrei volare a Chicago.

48
00:02:48,830 --> 00:02:50,130
Oppure potrei volare a Miami.

49
00:02:50,130 --> 00:02:53,340
Oppure potrei volare a New York.

50
00:02:53,340 --> 00:02:56,980
Potrei poi guardare da ogni
una di quelle città di destinazione

51
00:02:56,980 --> 00:03:00,650
e pensare a ciò che posizioni
Avrei potuto raggiungere

52
00:03:00,650 --> 00:03:03,020
da ciascuno di tali singole città.

53
00:03:03,020 --> 00:03:07,390
>> Così forse da Chicago, posso ottenere
un volo diretto a San Francisco.

54
00:03:07,390 --> 00:03:09,550
Questo è eccellente.

55
00:03:09,550 --> 00:03:12,360
Oppure avrei potuto ottenere un volo per Denver.

56
00:03:12,360 --> 00:03:16,970
Ora, forse questo volo per San Francisco
è la soluzione perfetta per me,

57
00:03:16,970 --> 00:03:19,530
ma forse no.

58
00:03:19,530 --> 00:03:22,180
Forse sto cercando qualcosa
che è un po 'meno

59
00:03:22,180 --> 00:03:24,920
o un po 'meglio per la mia pianificazione.

60
00:03:24,920 --> 00:03:29,197
E così ho potuto guardare per quello che altri
possibilità potrebbero essere là fuori.

61
00:03:29,197 --> 00:03:30,280
Così ho potuto guardare a Denver.

62
00:03:30,280 --> 00:03:33,870
E da Denver, beh, forse
Posso ottenere un volo per Austin.

63
00:03:33,870 --> 00:03:37,080
E da Austin, forse posso ottenere un
volo a Phoenix, e da Phoenix

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

65
00:03:40,190 --> 00:03:42,730
Ora, io non ho ancora finito.

66
00:03:42,730 --> 00:03:45,640
Perché forse c'è un
volo diretto da New York

67
00:03:45,640 --> 00:03:47,850
a San Francisco che è perfetto per me.

68
00:03:47,850 --> 00:03:53,354
O forse c'è un volo da Miami
attraverso Denver che è molto più economico.

69
00:03:53,354 --> 00:03:54,270
Quindi devo ancora andare.

70
00:03:54,270 --> 00:03:58,200
E ho ancora di guardare a tutti coloro
le città che non ho ancora indagati.

71
00:03:58,200 --> 00:04:04,220
Devo controllare esaustivamente tutti
le possibilità che io possa avere.

72
00:04:04,220 --> 00:04:09,610
>> Così da New York, forse posso ottenere un
volo a Nashville, e da Nashville

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

74
00:04:10,336 --> 00:04:11,460
E poi io so dove mi trovo.

75
00:04:11,460 --> 00:04:14,252
E poi so da Austin, posso
volare a Phoenix, e da Phoenix

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

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

78
00:04:18,240 --> 00:04:22,830
Se io volo prima a Miami, però,
forse posso prendere un volo da Miami

79
00:04:22,830 --> 00:04:25,080
a Nashville, o da Miami a Austin.

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

81
00:04:27,950 --> 00:04:30,860
>> E ora che ho provato tutto
delle possibilità.

82
00:04:30,860 --> 00:04:36,310
Ho costruito questa grafico che
mi mostra tutti i possibili percorsi

83
00:04:36,310 --> 00:04:37,790
che potrei essere in grado di prendere.

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

85
00:04:40,510 --> 00:04:43,640
Quando noi rappresentiamo questi
tipi di problemi,

86
00:04:43,640 --> 00:04:47,870
non stiamo andando a rappresentare
esplicitamente come questo grafico,

87
00:04:47,870 --> 00:04:51,590
perché tale grafico non rappresenta
la storia di dove siamo andati.

88
00:04:51,590 --> 00:04:55,260
Sapendo che ho volato da
Phoenix a San Francisco

89
00:04:55,260 --> 00:05:01,690
non mi dire se sono venuto via
Nashville, o tramite Denver, o via Miami.

90
00:05:01,690 --> 00:05:06,430
>> Così che cosa farò invece è
Prendo questo stesso problema,

91
00:05:06,430 --> 00:05:09,140
e io rappresento come un albero.

92
00:05:09,140 --> 00:05:14,300
E alla radice dell'albero, al
top, io metterò il luogo che ho iniziato,

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

94
00:05:16,590 --> 00:05:19,310
E da Boston, guarderò
tutte le possibili posizioni

95
00:05:19,310 --> 00:05:20,380
che posso viaggiare.

96
00:05:20,380 --> 00:05:25,480
Beh, in questo caso, ho avuto tre,
Chicago, New York e Miami.

97
00:05:25,480 --> 00:05:29,850
E poi mi esplorare ciascuno di
questi bambini nella struttura.

98
00:05:29,850 --> 00:05:32,690
>> Da Chicago, ho visto
che ho avuto due voli.

99
00:05:32,690 --> 00:05:35,940
Ho potuto volare direttamente a
San Francisco o a Denver.

100
00:05:35,940 --> 00:05:37,740
Ora San Francisco, che è il mio obiettivo.

101
00:05:37,740 --> 00:05:39,790
Questa è la mia destinazione.

102
00:05:39,790 --> 00:05:42,220
Che sta per essere una foglia di questo albero.

103
00:05:42,220 --> 00:05:45,340
Cioè, io non intenzione di andare
da qualche parte dopo San Francisco.

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

105
00:05:47,850 --> 00:05:50,340
Da Denver, però,
Posso volare da Denver

106
00:05:50,340 --> 00:05:54,220
a Austin, da Austin a Phoenix,
e da Phoenix a San Francisco.

107
00:05:54,220 --> 00:05:56,050
E ora di nuovo, ho raggiunto una foglia.

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

109
00:05:59,470 --> 00:06:03,980
>> Potrei poi tornare a quello successivo
città che non ho completamente esplorata.

110
00:06:03,980 --> 00:06:07,440
Sarebbe New York, andare
indietro fino alla cima del mio albero,

111
00:06:07,440 --> 00:06:09,160
scendere a New York.

112
00:06:09,160 --> 00:06:12,700
Da New York, posso volare a
Nashville, da Nashville a Austin,

113
00:06:12,700 --> 00:06:17,290
da Austin a Phoenix, e
da Phoenix a San Francisco.

114
00:06:17,290 --> 00:06:20,170
E, infine, una città che ho
non sono ancora guardato, Miami.

115
00:06:20,170 --> 00:06:24,600
>> Beh, da Miami ho detto che avevo due
possibilità, Nashville o Austin.

116
00:06:24,600 --> 00:06:28,810
Se io volo a Nashville, beh, allora io volo
da Nashville, a Austin, a Phoenix,

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

118
00:06:29,640 --> 00:06:33,600
Se io volo a Austin, io volo Austin,
a Phoenix, a San Francisco.

119
00:06:33,600 --> 00:06:36,340
E ora ho un albero.

120
00:06:36,340 --> 00:06:37,230
Si tratta di un albero completo.

121
00:06:37,230 --> 00:06:41,890
E 'tutte le possibilità e
tutti i percorsi che ho potuto prendere.

122
00:06:41,890 --> 00:06:44,310
Cioè, se comincio a
radice dell'albero in alto

123
00:06:44,310 --> 00:06:47,860
e scendo ad una delle
lascia, mi dice non solo

124
00:06:47,860 --> 00:06:50,480
dove sto andando a
finire, San Francisco,

125
00:06:50,480 --> 00:06:53,670
ma mi dice che il percorso che
Ho bisogno di prendere per arrivarci.

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

127
00:06:56,400 --> 00:06:59,690
>> Ora, che uno di questi è il migliore?

128
00:06:59,690 --> 00:07:02,430
Beh, niente di questo
problema ma mi dice

129
00:07:02,430 --> 00:07:04,710
quali di questi è la soluzione migliore.

130
00:07:04,710 --> 00:07:09,270
Forse mi interessa di più di
quanto tempo sono in aria,

131
00:07:09,270 --> 00:07:12,350
o la distanza che sto volando.

132
00:07:12,350 --> 00:07:16,410
In tal caso, Chicago a San
Francisco potrebbe essere il minor numero

133
00:07:16,410 --> 00:07:18,910
di miglia in aria.

134
00:07:18,910 --> 00:07:20,860
>> Forse mi interessa costo.

135
00:07:20,860 --> 00:07:23,680
E tutti sappiamo voli diretti
sono generalmente più costosi.

136
00:07:23,680 --> 00:07:26,610
Quindi forse se prendo questo
tipo di percorso a ritroso

137
00:07:26,610 --> 00:07:30,650
attraverso Miami, Nashville,
Austin, Phoenix, forse allora

138
00:07:30,650 --> 00:07:34,070
Ottengo un prezzo più basso.

139
00:07:34,070 --> 00:07:36,440
Ma potrei ottimizzare su qualsiasi
criteri che mi preoccupo.

140
00:07:36,440 --> 00:07:39,790
Chi ha il migliore
volo connessione Wi-Fi, o che

141
00:07:39,790 --> 00:07:43,110
aeroporti hanno il miglior cibo disponibile.

142
00:07:43,110 --> 00:07:47,280
E ciascuno di questi potrebbe
darmi una soluzione diversa

143
00:07:47,280 --> 00:07:49,215
che vedo come il migliore.

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

145
00:07:51,990 --> 00:07:54,400
>> Questi tipi di problemi,
dove stiamo andando

146
00:07:54,400 --> 00:07:58,480
per costruire questo albero di
possibilità, e poi

147
00:07:58,480 --> 00:08:02,100
guardare ciascuno di questi
percorsi individuali, ed esaminare

148
00:08:02,100 --> 00:08:05,270
quale di questi soddisfa
un criterio per noi,

149
00:08:05,270 --> 00:08:08,790
stiamo andando a chiamare
questi problemi di ricerca.

150
00:08:08,790 --> 00:08:11,280
E abbiamo un sacco di
algoritmi, alcuni dei quali

151
00:08:11,280 --> 00:08:15,270
abbiamo visto già, ad andare
ed esplorare quegli alberi.

152
00:08:15,270 --> 00:08:19,270
Potremmo farlo nel modo in cui io
appena fatto, una ricerca in profondità,

153
00:08:19,270 --> 00:08:22,900
scendendo per quanto possibile fino a quando non
ha colpito una foglia, e poi tornare su,

154
00:08:22,900 --> 00:08:24,787
e andando a destra indietro.

155
00:08:24,787 --> 00:08:26,870
Oppure potremmo fare ciò che è
chiamato ricerca in ampiezza.

156
00:08:26,870 --> 00:08:29,675
Potremmo ampliare tutto
in alto, e quindi

157
00:08:29,675 --> 00:08:31,550
tutto una riga
sotto quella, e poi

158
00:08:31,550 --> 00:08:35,240
tutto una riga sotto quella.

159
00:08:35,240 --> 00:08:41,250
Quegli alberi di ricerca
sono fondamentali per AI.

160
00:08:41,250 --> 00:08:46,570
Ma essi non riesce quasi mai
bene tutto il tempo.

161
00:08:46,570 --> 00:08:51,600
Infatti, in molti casi
che abbiamo davvero a cuore,

162
00:08:51,600 --> 00:08:54,430
vogliamo costruire un albero,
ma non lo facciamo davvero

163
00:08:54,430 --> 00:08:57,140
arrivare a fare tutte le decisioni.

164
00:08:57,140 --> 00:09:00,940
>> Si tratta di situazioni chiamati
Ricerca contraddittorio, noto anche

165
00:09:00,940 --> 00:09:05,390
come come scrivere gioco giocare
sistemi e pagati per farlo.

166
00:09:05,390 --> 00:09:07,940
Ma questi sono i tipi
di sistemi in cui mi

167
00:09:07,940 --> 00:09:12,920
potrebbe arrivare a scegliere quando vado da
Boston, quale città vado a successivo.

168
00:09:12,920 --> 00:09:19,990
Ma dopo che, qualcun altro potrebbe arrivare
prendere la decisione su dove io volo.

169
00:09:19,990 --> 00:09:24,040
Quindi, per costruire questi
strutture generi, siamo

170
00:09:24,040 --> 00:09:28,510
andando a prendere leggermente
approccio diverso ad esso.

171
00:09:28,510 --> 00:09:31,060
Non stiamo andando per essere in grado di
basta cercare attraverso l'albero

172
00:09:31,060 --> 00:09:35,000
più, perché non siamo
quello che è in controllo

173
00:09:35,000 --> 00:09:38,180
di ciascuno di tali punti di decisione.

174
00:09:38,180 --> 00:09:42,590
>> Quindi cerchiamo di immaginare una semplice
gioco come tic-tac-toe.

175
00:09:42,590 --> 00:09:46,730
Potrei iniziare con un
bordo completamente vuoto.

176
00:09:46,730 --> 00:09:49,580
E nel tic-tac-toe,
X arriva a giocare per primo.

177
00:09:49,580 --> 00:09:53,890
E così ho potuto pensare a tutto il
possibili mosse che X potrebbe fare.

178
00:09:53,890 --> 00:09:57,420
E se sono io quella di gioco
X, che è grande.

179
00:09:57,420 --> 00:10:01,020
Ho nove possibile
mosse che posso fare.

180
00:10:01,020 --> 00:10:05,000
Potrei mettere una X in uno qualunque
di questi nove posizioni.

181
00:10:05,000 --> 00:10:10,710
>> E poi da ciascuno di questi, I
poteva immaginare cosa succede dopo.

182
00:10:10,710 --> 00:10:14,130
Ebbene, in questo caso, l'altra
giocatore dovrebbe arrivare a prendere una piega.

183
00:10:14,130 --> 00:10:15,660
O sarebbe arrivare a prendere una piega.

184
00:10:15,660 --> 00:10:19,510
E da ciascuno di questi, ci
sarebbe otto luoghi diversi

185
00:10:19,510 --> 00:10:22,980
O che potrebbe mettere il proprio segnalino.

186
00:10:22,980 --> 00:10:25,790
>> Diciamo che ho deciso che ero
andando a mettere una X al centro.

187
00:10:25,790 --> 00:10:28,810
Che sembra sempre come
una buona mossa di apertura.

188
00:10:28,810 --> 00:10:34,870
Potevo guardare sotto quella, la
otto possibili mosse che O fa.

189
00:10:34,870 --> 00:10:37,320
Ora, se sto giocando X, è meraviglioso.

190
00:10:37,320 --> 00:10:41,740
Mi capita di scegliere quale io
andare, quella nel mezzo.

191
00:10:41,740 --> 00:10:45,000
Ma ora O deve scegliere.

192
00:10:45,000 --> 00:10:48,750
E io non ho il controllo
su tale decisione.

193
00:10:48,750 --> 00:10:51,670
>> Ma a ciascuno di tali
possibili posizioni di bordo,

194
00:10:51,670 --> 00:10:54,020
c'è poi un altro
set di possibilità.

195
00:10:54,020 --> 00:10:56,700
Quando si tratta di essere
Il mio turno di nuovo, vorrei

196
00:10:56,700 --> 00:11:01,500
arrivare a scegliere e dire, beh,
se O si sposta nella, beh,

197
00:11:01,500 --> 00:11:06,110
il punto centrale sulla sinistra, poi
Ho una serie di possibilità

198
00:11:06,110 --> 00:11:09,740
dove posso prendere la mia prossima mossa.

199
00:11:09,740 --> 00:11:14,140
Da quelli, ho potuto prendere in considerazione tutti
le possibilità sotto di loro.

200
00:11:14,140 --> 00:11:18,030
E poi O otterrebbe
di scegliere tra quelli.

201
00:11:18,030 --> 00:11:22,290
>> E potrei continuare a costruire questo
albero fuori fino a quando ho avuto modo di punto

202
00:11:22,290 --> 00:11:26,960
dove sia qualcuno
vince la game-- che è

203
00:11:26,960 --> 00:11:31,070
Deve essere considerata una foglia node--
o la scheda è completamente pieno

204
00:11:31,070 --> 00:11:32,704
e nessuno ha vinto.

205
00:11:32,704 --> 00:11:34,370
E questo anche sarà un nodo foglia.

206
00:11:34,370 --> 00:11:35,411
Che sta per essere un pareggio.

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

208
00:11:37,820 --> 00:11:41,680
>> Ma la cosa difficile di questo è
se questo fosse solo una ricerca normale

209
00:11:41,680 --> 00:11:44,269
problema, sarei in grado di
per esempio, beh, X dovrebbe andare qui.

210
00:11:44,269 --> 00:11:45,560
E O dovrebbe andare laggiù.

211
00:11:45,560 --> 00:11:46,770
E allora X dovrebbe andare qui.

212
00:11:46,770 --> 00:11:48,269
E poi O dovrebbe andare laggiù.

213
00:11:48,269 --> 00:11:51,860
E allora X può ottenere tre
in fila, e vinco.

214
00:11:51,860 --> 00:11:54,870
E il gioco sarebbe finito
in cinque mosse, tre per me,

215
00:11:54,870 --> 00:11:57,710
due per il mio avversario.

216
00:11:57,710 --> 00:12:01,300
Ma non sempre arrivare alla scelta che.

217
00:12:01,300 --> 00:12:03,720
>> Così, invece, ciò che siamo
andando ad avere a che fare

218
00:12:03,720 --> 00:12:06,270
è che stiamo andando ad avere
avere una nuova strategia.

219
00:12:06,270 --> 00:12:09,350
E la strategia che
Algoritmi di gioco-gioco utilizzano spesso

220
00:12:09,350 --> 00:12:12,000
è ciò che è chiamato minimax.

221
00:12:12,000 --> 00:12:15,500
L'idea centrale
Minimax è che siamo

222
00:12:15,500 --> 00:12:21,365
andando a scegliere la mossa che dà
il nostro avversario peggiore possibile

223
00:12:21,365 --> 00:12:22,790
di mosse che si può fare.

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

225
00:12:25,570 --> 00:12:28,870
Non fa nulla di buono mi
di scegliere una mossa in cui

226
00:12:28,870 --> 00:12:31,952
Potrei essere in grado di vincere dopo
che, perché il mio avversario non è

227
00:12:31,952 --> 00:12:33,160
andando a darmi questa possibilità.

228
00:12:33,160 --> 00:12:37,770
Stanno andando a scegliere alcuni
esito terribile per me.

229
00:12:37,770 --> 00:12:42,010
Quindi ho intenzione di fare il
mossa che costringe il mio avversario

230
00:12:42,010 --> 00:12:45,760
di fare qualcosa di meglio per me.

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

232
00:12:46,260 --> 00:12:48,410
Vediamo come che gioca fuori.

233
00:12:48,410 --> 00:12:51,640
Quindi, ecco il nostro algoritmo in pseudocodice.

234
00:12:51,640 --> 00:12:54,450
Stiamo andando a generare
l'intero albero gioco.

235
00:12:54,450 --> 00:12:56,757
Stiamo andando a costruire
l'intera struttura.

236
00:12:56,757 --> 00:12:57,840
E poi andremo attraverso.

237
00:12:57,840 --> 00:13:02,100
E in fondo a ciascuno dei
nodi terminali, a ciascuna delle foglie,

238
00:13:02,100 --> 00:13:07,850
noi valuteremo come
prezioso è che a me?

239
00:13:07,850 --> 00:13:11,690
E stiamo andando a cose di valore che
sono buoni per me come essere positivo.

240
00:13:11,690 --> 00:13:14,460
Le cose che non sono buone per me
sarà meno positivo, o zero,

241
00:13:14,460 --> 00:13:16,480
o addirittura negativo.

242
00:13:16,480 --> 00:13:19,240
>> Così nel tic-tac-toe, forse
una vittoria per me è buona.

243
00:13:19,240 --> 00:13:20,290
Questo è uno.

244
00:13:20,290 --> 00:13:22,400
E una cravatta è zero.

245
00:13:22,400 --> 00:13:26,230
E qualcosa che è una perdita per
me, forse è uno negativo.

246
00:13:26,230 --> 00:13:29,620
Tutto ciò che conta è che il meglio
è per me, più alto è il punteggio

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

248
00:13:32,160 --> 00:13:36,690
Da queste possibilità al
fondo, poi ci filtriamo verso l'alto.

249
00:13:36,690 --> 00:13:40,650
E quando è il mio possibilità di scegliere
tra un insieme di alternative,

250
00:13:40,650 --> 00:13:44,460
Io sceglierò quello che è
ha ottenuto il punteggio più alto.

251
00:13:44,460 --> 00:13:47,200
>> E ogni volta è il mio
avversari rivolgono a scegliere,

252
00:13:47,200 --> 00:13:52,350
Darò per scontato che andranno a
scegliere quello con il punteggio più basso.

253
00:13:52,350 --> 00:13:56,090
E se faccio questo tutto il senso
fino alla cima dell'albero,

254
00:13:56,090 --> 00:14:03,150
Io ho scelto un percorso che dà
me il miglior risultato che posso ottenere,

255
00:14:03,150 --> 00:14:09,110
partendo dal presupposto che il mio avversario
rende tutte le mosse giuste.

256
00:14:09,110 --> 00:14:11,940
>> Va bene, vediamo
questo in azione prima.

257
00:14:11,940 --> 00:14:14,980
E poi ci troveremo a
guardare il codice per esso.

258
00:14:14,980 --> 00:14:16,780
Quindi immaginate ho questo grande albero.

259
00:14:16,780 --> 00:14:18,280
E ora non sto giocando tic-tac-toe.

260
00:14:18,280 --> 00:14:20,405
Volevo darvi
qualcosa di un po 'più ricco.

261
00:14:20,405 --> 00:14:23,560
Così ho avuto qualche gioco in cui
ci sono molti diversi punteggi

262
00:14:23,560 --> 00:14:26,390
che avrei potuto alla fine.

263
00:14:26,390 --> 00:14:27,980
E così ho costruito questo albero completo.

264
00:14:27,980 --> 00:14:29,070
E mi capita di passare per primo.

265
00:14:29,070 --> 00:14:31,290
Sono alla radice dell'albero.

266
00:14:31,290 --> 00:14:36,150
>> E posso scegliere che-- così ottengo
per massimizzare attraverso quel primo nodo.

267
00:14:36,150 --> 00:14:38,410
E poi il mio avversario arriva a andare.

268
00:14:38,410 --> 00:14:41,910
E poi mi capita di andare ancora una volta.

269
00:14:41,910 --> 00:14:46,830
Quindi giù in fondo, ho un gruppo di
possibilità che posso scegliere,

270
00:14:46,830 --> 00:14:50,570
diversi stati terminali del gioco.

271
00:14:50,570 --> 00:14:54,980
Se sono in tale
all'estrema sinistra angolo mano,

272
00:14:54,980 --> 00:14:58,867
e vedo che ho un scelta
tra un otto, un sette, e due,

273
00:14:58,867 --> 00:15:00,450
bene, sono io quello che deve scegliere.

274
00:15:00,450 --> 00:15:02,910
Quindi ho intenzione di scegliere
il migliore di quelli.

275
00:15:02,910 --> 00:15:05,650
Ho intenzione di scegliere il otto.

276
00:15:05,650 --> 00:15:10,090
>> Quindi so che se avessi mai
scendere a quel punto,

277
00:15:10,090 --> 00:15:13,890
Sarò in grado di ottenere che le otto punti.

278
00:15:13,890 --> 00:15:17,410
Se finisco al punto successivo
sopra, il nodo successivo sopra,

279
00:15:17,410 --> 00:15:20,760
un nove, uno, o un sei, bene, sono
andando a scegliere il migliore di quelli.

280
00:15:20,760 --> 00:15:21,950
Scelgo nove.

281
00:15:21,950 --> 00:15:24,880
Se ho una scelta tra
due e quattro, e uno,

282
00:15:24,880 --> 00:15:28,240
Scelgo il quattro, il più alto.

283
00:15:28,240 --> 00:15:31,990
>> Ora, se guardo a livello
superiore a quello, il mio avversario

284
00:15:31,990 --> 00:15:34,440
è quello arriva a fare questa scelta.

285
00:15:34,440 --> 00:15:37,040
Quindi il mio avversario ha a
Scelgo, voglio dargli

286
00:15:37,040 --> 00:15:39,250
la cosa che sta succedendo
per ottenere gli otto punti,

287
00:15:39,250 --> 00:15:41,916
o ne gli do la cosa che è
intenzione di dargli nove punti,

288
00:15:41,916 --> 00:15:45,240
o la cosa che sta andando
per dargli quattro punti?

289
00:15:45,240 --> 00:15:49,130
E il mio avversario, essendo
razionale, sta andando

290
00:15:49,130 --> 00:15:53,470
scegliere il minimo di questi,
sta per scegliere il quattro.

291
00:15:53,470 --> 00:15:56,020
>> E posso fare questo
attraverso l'intero albero.

292
00:15:56,020 --> 00:15:59,110
Posso andare fino a quel
insieme mezzo di tre.

293
00:15:59,110 --> 00:16:01,517
E posso scegliere tra
uno, tre e cinque.

294
00:16:01,517 --> 00:16:02,350
E posso scegliere.

295
00:16:02,350 --> 00:16:03,810
Così ho scelto un cinque.

296
00:16:03,810 --> 00:16:05,340
Posso scegliere tre, nove, o due.

297
00:16:05,340 --> 00:16:07,570
Posso scegliere, così ho scelto il nove.

298
00:16:07,570 --> 00:16:09,290
Sei, cinque, o due, ho scelto.

299
00:16:09,290 --> 00:16:11,539
Mi capita di scegliere il sei.

300
00:16:11,539 --> 00:16:13,080
Livello superiore a quello, chi può scegliere?

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

302
00:16:16,280 --> 00:16:18,140
Chi arriva a scegliere?

303
00:16:18,140 --> 00:16:20,000
L'altro ragazzo, il mio avversario.

304
00:16:20,000 --> 00:16:22,583
Così hanno scelto cinque,
nove, o sei, quale?

305
00:16:22,583 --> 00:16:23,410
>> PUBBLICO: I cinque.

306
00:16:23,410 --> 00:16:25,250
>> SPEAKER: Scelgono il cinque.

307
00:16:25,250 --> 00:16:27,400
Si arriva a scegliere il minimo.

308
00:16:27,400 --> 00:16:29,690
E poi l'ultimo,
scegliere una, due, o tre.

309
00:16:29,690 --> 00:16:31,720
Posso scegliere, così ho scelto tre.

310
00:16:31,720 --> 00:16:34,370
Nove, sette, o due, scelgo nove.

311
00:16:34,370 --> 00:16:37,070
E 11, sei, o quattro, scelgo 11.

312
00:16:37,070 --> 00:16:41,190
Il mio avversario sceglie poi di tre,
nove, o 11, sceglie il minimo.

313
00:16:41,190 --> 00:16:43,290
Mi dà un tre.

314
00:16:43,290 --> 00:16:47,780
E infine in cima
l'albero, mi arriva a scegliere di nuovo.

315
00:16:47,780 --> 00:16:51,190
E mi capita di scegliere tra
quattro, cinque, o tre.

316
00:16:51,190 --> 00:16:52,270
Così prendo il cinque.

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

318
00:16:55,070 --> 00:17:00,891
>> Se ho avuto modo di controllare tutto, mi piacerebbe
prendere il sentiero che portava al 11.

319
00:17:00,891 --> 00:17:02,390
Ma io non arrivare a fare quella scelta.

320
00:17:02,390 --> 00:17:04,220
Se vado su questa strada.

321
00:17:04,220 --> 00:17:10,710
Il mio avversario mi costringerà in
la scelta che porta a tre.

322
00:17:10,710 --> 00:17:14,530
Quindi la cosa migliore che posso fare è
a prendere quel ramo di mezzo,

323
00:17:14,530 --> 00:17:19,859
fare questa scelta che è alla fine
andando a mi portano a cinque punti.

324
00:17:19,859 --> 00:17:23,230
Questo è ciò che fa minimax.

325
00:17:23,230 --> 00:17:23,807
>> Tutto ok.

326
00:17:23,807 --> 00:17:24,890
Diamo uno sguardo a questo.

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

328
00:17:27,480 --> 00:17:32,330
Così qui in CS50
IDE è un programma che

329
00:17:32,330 --> 00:17:36,540
implementa minimax a giocare tic-tac-toe.

330
00:17:36,540 --> 00:17:40,100
Stiamo andando a costruire
su una rappresentazione.

331
00:17:40,100 --> 00:17:44,390
Stiamo per avere due opponent--
o due giocatori, il nostro computer

332
00:17:44,390 --> 00:17:46,090
giocatore e un giocatore umano.

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

334
00:17:48,980 --> 00:17:53,090
Giocatore numero uno ci sarà
O. che sarà il giocatore della macchina.

335
00:17:53,090 --> 00:17:55,747
Ottengono di muoversi secondo.

336
00:17:55,747 --> 00:17:57,830
E l'altro giocatore, il nostro
giocatore umano, sarà X.

337
00:17:57,830 --> 00:17:59,880
>> E per rendere la mia vita un
poco semplice, io vado

338
00:17:59,880 --> 00:18:03,060
etichettare quella lettore uno negativo.

339
00:18:03,060 --> 00:18:05,026
Quindi posso solo moltiplicare
da un negativo di scambiare

340
00:18:05,026 --> 00:18:06,400
tra un giocatore e l'altra.

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

342
00:18:09,030 --> 00:18:12,250
Va bene, quindi cerchiamo di dare un'occhiata a
quello che stiamo effettivamente andando a fare.

343
00:18:12,250 --> 00:18:15,840
Stiamo andando a definire la nostra tavola.

344
00:18:15,840 --> 00:18:19,060
Sta andando per essere, beh, stiamo andando
per permettere che sia tre per tre,

345
00:18:19,060 --> 00:18:21,580
o possiamo anche giocare
cinque da cinque o sette

346
00:18:21,580 --> 00:18:28,870
per sette tic-tac-toe Se desideri
come, sulla base di una dimensione D.

347
00:18:28,870 --> 00:18:31,260
>> E avremo una coppia
di funzioni di supporto

348
00:18:31,260 --> 00:18:34,360
basta così le cose come
inizializzare il screen-- o dispiaciuto,

349
00:18:34,360 --> 00:18:38,900
inizializzare le nostre variabili, deselezionare la
schermo, disegnare il bordo dello schermo,

350
00:18:38,900 --> 00:18:41,060
uno che controlla un consiglio
per vedere se non

351
00:18:41,060 --> 00:18:44,520
c'è un vincitore, che
analizza attraverso la riga di comando,

352
00:18:44,520 --> 00:18:50,670
solo per dare una mano, uno che legge
ingresso, e una funzione chiamata minimax.

353
00:18:50,670 --> 00:18:52,746
E questo è quello
ci preoccupa di più di.

354
00:18:52,746 --> 00:18:54,120
Ma diamo un'occhiata prima al principale.

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

356
00:18:57,490 --> 00:18:58,510
>> Cosa facciamo?

357
00:18:58,510 --> 00:19:00,570
Beh, stiamo andando a
analizzare la nostra linea di comando,

358
00:19:00,570 --> 00:19:04,300
appena letto e vedere cosa
bordo dimensione ci piacerebbe avere.

359
00:19:04,300 --> 00:19:07,330
Ti Inizializziamo nostra tavola.

360
00:19:07,330 --> 00:19:10,360
E poi ci entreremo uno
grande anello selvaggio, ripetutamente

361
00:19:10,360 --> 00:19:16,630
accetta si muove fino a quando il gioco è
ha vinto, o non ci sono movimenti di sinistra.

362
00:19:16,630 --> 00:19:20,560
Ogni volta che andiamo attraverso quella
cappio, faremo cancellare lo schermo.

363
00:19:20,560 --> 00:19:23,290
Noi disegneremo la scheda sullo schermo.

364
00:19:23,290 --> 00:19:28,750
E siamo deliberatamente sorta di
astraendo questi via come subroutine,

365
00:19:28,750 --> 00:19:32,030
in modo che noi non dobbiamo preoccuparci troppo
circa i dettagli di come accadono.

366
00:19:32,030 --> 00:19:33,480
>> Avrete il codice più tardi oggi.

367
00:19:33,480 --> 00:19:37,970
E se si vuole guardare attraverso
e scoprire, è possibile vederli tutti.

368
00:19:37,970 --> 00:19:39,890
Ma noi disegniamo una scheda sullo schermo.

369
00:19:39,890 --> 00:19:43,620
E poi controlleremo e
vedere, abbiamo un vincitore?

370
00:19:43,620 --> 00:19:46,290
Qualcuno ha vinto questo gioco?

371
00:19:46,290 --> 00:19:49,260
Se hanno, faremo stampare
un messaggio di vittoria.

372
00:19:49,260 --> 00:19:51,680
E finiremo il gioco.

373
00:19:51,680 --> 00:19:54,510
>> Ci sarà anche il check e
vedere se c'è un pareggio.

374
00:19:54,510 --> 00:19:56,620
Sarà facile per vedere se c'è un pareggio.

375
00:19:56,620 --> 00:20:00,700
Ciò significa che tutti gli spazi sono pieni,
ma non è stato ancora un vincitore.

376
00:20:00,700 --> 00:20:03,580
Siamo in grado di dichiarare un pareggio e da fare.

377
00:20:03,580 --> 00:20:10,530
Poi il vero meat-- se
si tratta di un giocatore della macchina,

378
00:20:10,530 --> 00:20:14,120
ci permettiamo che
giocatore della macchina per la ricerca

379
00:20:14,120 --> 00:20:19,500
attraverso l'utilizzo di questo algoritmo Minimax,
per trovare la migliore mossa che può.

380
00:20:19,500 --> 00:20:22,310
E poi ci metteremo quella mossa su.

381
00:20:22,310 --> 00:20:27,640
>> In caso contrario, se si tratta di un giocatore umano,
leggeremo qualche input da quella umana.

382
00:20:27,640 --> 00:20:30,800
E poi se è l'uomo
giocatore o il giocatore della macchina,

383
00:20:30,800 --> 00:20:32,800
faremo un paio po '
bit di controllo degli errori,

384
00:20:32,800 --> 00:20:36,910
assicurarsi che rimanga entro i confini
delle dimensioni effettive del consiglio

385
00:20:36,910 --> 00:20:40,040
che abbiamo, fare in modo
che tale spazio è vuoto,

386
00:20:40,040 --> 00:20:43,570
che nessuno ha messo un
pezzo in là già.

387
00:20:43,570 --> 00:20:45,810
E poi ci appena messo
un pezzo sulla scacchiera,

388
00:20:45,810 --> 00:20:51,550
cambiare il giocatore al livello successivo, e
incrementare il numero di mosse accaduto.

389
00:20:51,550 --> 00:20:54,090
>> Questo è il ciclo principale per
il nostro gioco tic-tac-toe.

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

391
00:20:57,000 --> 00:21:02,340
Minimax, allora, è proprio
l'algoritmo che prima.

392
00:21:02,340 --> 00:21:04,710
L'unica regolazione che
abbiamo fatto in modo che si

393
00:21:04,710 --> 00:21:07,290
può giocare più alto
tavole dimensionali è che abbiamo

394
00:21:07,290 --> 00:21:11,070
mantenuto questo parametro extra chiamato profondità.

395
00:21:11,070 --> 00:21:14,870
E profondità dice solo, se sono
la ricerca verso il basso attraverso quell'albero

396
00:21:14,870 --> 00:21:19,022
e ho così in basso
al di là di un certo livello di profondità

397
00:21:19,022 --> 00:21:20,730
che io non voglio
di andare oltre,

398
00:21:20,730 --> 00:21:25,630
Ho intenzione di fermarsi e solo
valutare il bordo in quel punto.

399
00:21:25,630 --> 00:21:27,310
Vado a controllare e vedere se c'è un vincitore.

400
00:21:27,310 --> 00:21:29,240
Se c'è un vincitore, li torno.

401
00:21:29,240 --> 00:21:31,720
In caso contrario, vado attraverso un ciclo.

402
00:21:31,720 --> 00:21:34,380
E io dico, per tutti
le posizioni possibili

403
00:21:34,380 --> 00:21:38,080
che avrei potuto forse
prendere come la mia mossa, io ti

404
00:21:38,080 --> 00:21:43,760
costruire una scheda ipotetico che
include la mia mossa su quel bordo,

405
00:21:43,760 --> 00:21:45,960
e poi chiama ricorsivamente minimax.

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

407
00:21:49,360 --> 00:21:53,900
>> Se è la mia mossa, riesco a trovare il
uno che ha ottenuto il maggior punteggio.

408
00:21:53,900 --> 00:21:58,710
Se si tratta di mossa del mio avversario, troviamo
quello che ha ottenuto il punteggio minimo.

409
00:21:58,710 --> 00:22:02,240
E tutto il resto è
tenuta proprio record.

410
00:22:02,240 --> 00:22:04,789
Va bene, vediamo questa corsa.

411
00:22:04,789 --> 00:22:06,830
A dire il vero, forse possiamo
ottenere un paio di volontari

412
00:22:06,830 --> 00:22:09,930
a venire e giocare a tic-tac-toe.

413
00:22:09,930 --> 00:22:12,780
[Incomprensibile] uno, e uno
di più, due, proprio lì.

414
00:22:12,780 --> 00:22:13,550
Vieni su.

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

416
00:22:19,290 --> 00:22:23,650
>> Quindi cerchiamo di andare avanti e
riavviare questo completamente.

417
00:22:23,650 --> 00:22:24,150
Quindi, ciao.

418
00:22:24,150 --> 00:22:24,920
>> PUBBLICO: Ciao.

419
00:22:24,920 --> 00:22:25,420
>> SPEAKER: Qual è il tuo nome?

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

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

422
00:22:26,840 --> 00:22:27,800
>> PUBBLICO: Io sono Layla.

423
00:22:27,800 --> 00:22:29,490
>> SPEAKER: E Layla, e Layla, mi dispiace.

424
00:22:29,490 --> 00:22:30,384
Vieni su.

425
00:22:30,384 --> 00:22:32,050
Gorav, stiamo per avere di andare prima.

426
00:22:32,050 --> 00:22:37,710
E ho intenzione di chiedere di essere un non
terribilmente buon giocatore tic-tac-toe.

427
00:22:37,710 --> 00:22:40,130
OK, così tutta la pressione è su di voi.

428
00:22:40,130 --> 00:22:44,660
Vediamo, però, che la nostra macchina
giocatore può realmente fare qualcosa di intelligente.

429
00:22:44,660 --> 00:22:45,310
Quindi, andare avanti.

430
00:22:45,310 --> 00:22:49,830
Stai andando a digitare il quale coordinare
volete mettere il vostro X.

431
00:22:49,830 --> 00:22:55,170
A0, OK, e la macchina è andata
subito e mettere il suo marchio in A1.

432
00:22:55,170 --> 00:22:56,640
>> Mettere la O sulla scheda.

433
00:22:56,640 --> 00:22:58,970
Va bene, ora andare avanti.

434
00:22:58,970 --> 00:23:00,193
Dove vorresti andare?

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
Il nostro giocatore ha preso la macchina
la piazza centrale, è bloccato.

438
00:23:08,430 --> 00:23:10,320
Così che era un bene,
cosa intelligente per poter fare.

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

440
00:23:13,430 --> 00:23:14,250
Hai bloccato esso.

441
00:23:14,250 --> 00:23:15,210
Questo è eccellente.

442
00:23:15,210 --> 00:23:16,390
Si batte il corner lì.

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

444
00:23:23,890 --> 00:23:30,430
>> E sta andando a costringere a
prendere un ultimo spazio, B0.

445
00:23:30,430 --> 00:23:32,220
E la partita finisce in parità.

446
00:23:32,220 --> 00:23:35,030
Ma ha giocato un ragionevole
gioco contro di te, giusto?

447
00:23:35,030 --> 00:23:36,956
Va bene, grazie mille, Gorav.

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

449
00:23:40,860 --> 00:23:44,723
>> Va bene, Layla, stiamo andando
il gioco su di voi qui.

450
00:23:44,723 --> 00:23:46,940
>> PUBBLICO: Oh, grande.

451
00:23:46,940 --> 00:23:49,950
>> SPEAKER: Stiamo andando a dare
voi quattro da quattro tic-tac-toe.

452
00:23:49,950 --> 00:23:54,760
Ora, a quattro a quattro, devi vincere
con quattro di fila, non tre di fila.

453
00:23:54,760 --> 00:23:56,135
Ed è tutto tuo.

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

455
00:24:02,180 --> 00:24:04,420
Così Layla ha preso D1.

456
00:24:04,420 --> 00:24:11,730
Stiamo andando a seguire
il nostro giocatore di computer qui.

457
00:24:11,730 --> 00:24:16,910
Tre per tre tic-tac-toe è il tipo
di cosa che è facile per tutti noi.

458
00:24:16,910 --> 00:24:21,960
Ma è ancora bello vedere la
giocatore del calcolatore fare mosse intelligenti.

459
00:24:21,960 --> 00:24:23,725
Quattro per quattro arriva a
essere un po 'più complicato.

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

461
00:24:42,960 --> 00:24:44,230
>> Ben fatto.

462
00:24:44,230 --> 00:24:46,210
Va bene, così Layla di finito fuori.

463
00:24:46,210 --> 00:24:48,270
Oh, e avremmo dovuto finita lì.

464
00:24:48,270 --> 00:24:51,870
Ma facciamo un altro qui.

465
00:24:51,870 --> 00:24:53,480
Così Layla, grazie.

466
00:24:53,480 --> 00:24:55,112
Ben fatto.

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

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

469
00:25:00,410 --> 00:25:04,750
>> Così il nostro giocatore tic-tac-toe va
attraverso e trova luoghi,

470
00:25:04,750 --> 00:25:07,040
risolve utilizzando questo minimax.

471
00:25:07,040 --> 00:25:08,990
E ho avuto una regolazione della profondità
in tale modo che

472
00:25:08,990 --> 00:25:11,010
non avrebbe eseguito troppo veloce,
che è probabilmente il motivo

473
00:25:11,010 --> 00:25:16,790
Layla è stato in grado di andare ben prima
come ha fatto, e ha fatto molto bene.

474
00:25:16,790 --> 00:25:20,450
Ma questi sistemi che solo
passare attraverso e forza bruta

475
00:25:20,450 --> 00:25:23,870
andare più a fondo, e più profondo, e più in profondità,
e continuare a trovare la soluzione

476
00:25:23,870 --> 00:25:29,890
che hanno bisogno, questo tipo di sistemi
sono molto successo a questi, beh,

477
00:25:29,890 --> 00:25:32,700
giochi da tavolo standard.

478
00:25:32,700 --> 00:25:37,060
>> E infatti, se guardiamo un
tre per tre gioco tic-tac-toe,

479
00:25:37,060 --> 00:25:40,040
questo è fondamentalmente un problema risolto.

480
00:25:40,040 --> 00:25:45,430
E questo è un diagramma meraviglioso
da Randall Munroe a XKCD,

481
00:25:45,430 --> 00:25:52,130
mostra che si muovono si dovrebbe
prendere, dato le mosse dell'avversario.

482
00:25:52,130 --> 00:25:56,420
Questo è qualcosa che potremmo
facilmente specificare prima del tempo.

483
00:25:56,420 --> 00:26:00,180
Ma cosa succede quando si arriva a più
giochi complessi, i giochi più complessi,

484
00:26:00,180 --> 00:26:05,690
dove ci sono grandi tavole, più
possibilità, la strategia più profondo?

485
00:26:05,690 --> 00:26:09,660
>> Si scopre che questo
forza bruta alla ricerca ancora

486
00:26:09,660 --> 00:26:14,150
fa abbastanza bene, tranne
quando si arriva al punto

487
00:26:14,150 --> 00:26:19,230
qualora tale albero è così grande
che non si può rappresentare tutto.

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

489
00:26:22,370 --> 00:26:28,280
Quando non è possibile calcolare l'intero albero,
quando non si può andare avanti e spingere

490
00:26:28,280 --> 00:26:32,204
voi stessi al punto in cui hai
ottenuto l'intero albero in memoria,

491
00:26:32,204 --> 00:26:34,370
o se si può ottenere
in memoria e sarà solo

492
00:26:34,370 --> 00:26:39,200
prendere troppo tempo per la ricerca in
esso, devi fare qualcosa di più intelligente.

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

494
00:26:42,620 --> 00:26:46,450
>> Per fare questo, si
hanno a che fare due cose.

495
00:26:46,450 --> 00:26:49,030
In primo luogo, è necessario trovare qualche
modo di limitare la profondità.

496
00:26:49,030 --> 00:26:50,370
Beh, questo è OK.

497
00:26:50,370 --> 00:26:55,740
Possiamo trovare qualche bella, minimo
e dire, si può solo andare così in profondità.

498
00:26:55,740 --> 00:27:00,890
Ma quando lo fate, che significa
avere queste schede parzialmente incomplete.

499
00:27:00,890 --> 00:27:04,770
E devi scegliere, mi piace fare
questa scheda parzialmente incomplete,

500
00:27:04,770 --> 00:27:08,600
o questo forum parzialmente incompleto?

501
00:27:08,600 --> 00:27:11,910
>> E sul nostro quattro da
quattro gioco tic-tac-toe,

502
00:27:11,910 --> 00:27:15,240
il nostro giocatore di computer scese
al fondo e detto,

503
00:27:15,240 --> 00:27:16,800
Ho due schede diverse.

504
00:27:16,800 --> 00:27:17,940
Nessuno dei due è una vittoria.

505
00:27:17,940 --> 00:27:19,120
Nessuno dei due è una perdita.

506
00:27:19,120 --> 00:27:22,070
Nessuno dei due è un pareggio.

507
00:27:22,070 --> 00:27:24,100
Come faccio a scegliere tra di loro?

508
00:27:24,100 --> 00:27:26,200
E non ha avuto un
modo intelligente di farlo.

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

510
00:27:28,910 --> 00:27:32,850
>> Vediamo questo tipo di
Valutazione accade tutto il tempo

511
00:27:32,850 --> 00:27:35,290
come otteniamo in giochi più complessi.

512
00:27:35,290 --> 00:27:37,600
Gli scacchi sono un grande esempio.

513
00:27:37,600 --> 00:27:41,550
Negli scacchi, abbiamo, prima
di tutto, una tavola più grande.

514
00:27:41,550 --> 00:27:43,370
Abbiamo molti più pezzi.

515
00:27:43,370 --> 00:27:47,930
E il posizionamento di questi pezzi
e il modo in cui questi pezzi muovono

516
00:27:47,930 --> 00:27:50,370
è di fondamentale importanza.

517
00:27:50,370 --> 00:27:53,700
Quindi, se voglio usare Minimax,
Ho bisogno di essere in grado di specificare

518
00:27:53,700 --> 00:27:58,240
e dire, questa tavola, dove
nessuno ha vinto o perso ancora,

519
00:27:58,240 --> 00:28:04,310
è in qualche modo meglio di questo altro
bordo, dove nessuno ha vinto o perso.

520
00:28:04,310 --> 00:28:06,740
>> Per fare questo, potrei fare
cose come potrei solo

521
00:28:06,740 --> 00:28:10,787
contare quanti pezzi devo
e quanti pezzi avete?

522
00:28:10,787 --> 00:28:12,870
Oppure potrei dare diverso
pezzi diversi punti.

523
00:28:12,870 --> 00:28:14,420
Mia regina vale 20 punti.

524
00:28:14,420 --> 00:28:16,500
La vostra pedina vale un punto.

525
00:28:16,500 --> 00:28:18,920
Chi ha il totale più punti?

526
00:28:18,920 --> 00:28:22,300
Oppure potrei considerare le cose come,
chi è che ha avuto la meglio posizione di bordo?

527
00:28:22,300 --> 00:28:26,820
A chi tocca il prossimo,
tutto ciò che posso

528
00:28:26,820 --> 00:28:31,220
non per valutare con maggiore precisione
quale di queste possibilità

529
00:28:31,220 --> 00:28:34,660
è meglio senza
esaustivamente in considerazione

530
00:28:34,660 --> 00:28:36,565
ogni mossa che potrebbe venire dopo.

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

532
00:28:39,740 --> 00:28:45,130
>> Ora, per fare quel lavoro,
una delle cose che è

533
00:28:45,130 --> 00:28:48,680
sta per diventare veramente importante
per noi non è solo muovendo dritto

534
00:28:48,680 --> 00:28:53,720
fino ad una profondità particolare
limite, ma essere in grado di dire,

535
00:28:53,720 --> 00:28:59,380
una di queste idee che
avere è così male che è

536
00:28:59,380 --> 00:29:02,280
Non vale la pena considerare
tutti i modi possibili

537
00:29:02,280 --> 00:29:06,680
che le cose possono andare di male in peggio.

538
00:29:06,680 --> 00:29:12,760
Per fare questo, si aggiungerà in minimax
un principio chiamato alph-beta.

539
00:29:12,760 --> 00:29:16,340
E alfa-beta dice:
se si dispone di una cattiva idea,

540
00:29:16,340 --> 00:29:22,840
non perdete il vostro tempo cercando di
scoprire esattamente quanto è fatto male.

541
00:29:22,840 --> 00:29:24,990
>> Così qui è quello che andremo a fare.

542
00:29:24,990 --> 00:29:28,620
Stiamo andando a prendere la stessa
principi che avevamo prima,

543
00:29:28,620 --> 00:29:32,200
lo stesso tipo minimax
di ricerca, solo noi siamo

544
00:29:32,200 --> 00:29:37,570
andando tenere traccia, non solo della
valori reali che abbiamo, ma ce la faremo

545
00:29:37,570 --> 00:29:41,440
tenere traccia dei migliori possibili
valore che ho potuto ottenere,

546
00:29:41,440 --> 00:29:45,700
e la peggiore possibile
esito avrei potuto.

547
00:29:45,700 --> 00:29:50,470
E ogni volta che il peggiore possibile
cosa sta cercando probabile,

548
00:29:50,470 --> 00:29:52,694
Io abbandonare quella parte dell'albero.

549
00:29:52,694 --> 00:29:54,610
E non voglio nemmeno
guardando più.

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

551
00:29:57,680 --> 00:30:02,600
>> Va bene, quindi immaginiamo che cominciamo
con questo stesso albero esatto gioco.

552
00:30:02,600 --> 00:30:05,200
E ora stiamo per andare
giù di nuovo, fino in fondo

553
00:30:05,200 --> 00:30:07,200
a quello in basso a sinistra.

554
00:30:07,200 --> 00:30:11,180
E in quella in basso a sinistra angolo, ci
guardiamo e valutiamo questa scheda.

555
00:30:11,180 --> 00:30:15,700
Forse è un quattro per quattro tic-tac-toe
bordo, o forse è una scacchiera.

556
00:30:15,700 --> 00:30:18,620
Ma noi guardiamo, e valutiamo
esso, e si ottiene un valore di otto.

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

558
00:30:22,290 --> 00:30:28,030
>> A quel punto, sappiamo che
ci accingiamo a ottenere almeno

559
00:30:28,030 --> 00:30:32,380
otto punti di questa decisione di fondo.

560
00:30:32,380 --> 00:30:36,620
Non importa ciò che l'altro
due sono, che sette e che due.

561
00:30:36,620 --> 00:30:38,580
Potrebbero essere i valori
volevano essere.

562
00:30:38,580 --> 00:30:41,279
Stiamo per arrivare a
almeno otto punti.

563
00:30:41,279 --> 00:30:43,070
Va bene, ma abbiamo potuto
andare avanti e controllare.

564
00:30:43,070 --> 00:30:45,080
Forse uno di loro è meglio di otto.

565
00:30:45,080 --> 00:30:46,000
>> Guardiamo il sette.

566
00:30:46,000 --> 00:30:46,910
Va meglio di otto?

567
00:30:46,910 --> 00:30:48,680
No, questo non cambia
nostro parere affatto.

568
00:30:48,680 --> 00:30:49,460
Guardiamo i due.

569
00:30:49,460 --> 00:30:50,543
Va meglio di otto?

570
00:30:50,543 --> 00:30:52,580
No, questo non cambia
nostro parere affatto.

571
00:30:52,580 --> 00:30:55,480
Così ora sappiamo abbiamo esaurito
tutte le possibilità lì.

572
00:30:55,480 --> 00:30:58,330
Non abbiamo intenzione di ottenere
niente di meglio di otto.

573
00:30:58,330 --> 00:31:01,310
Stiamo per ottenere esattamente otto.

574
00:31:01,310 --> 00:31:03,825
>> E così cambiamo quel nodo e
per esempio, che è ormai una certezza.

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

576
00:31:07,010 --> 00:31:10,270
Saliamo di un livello superiore a quello.

577
00:31:10,270 --> 00:31:13,820
E ora sappiamo qualcosa
su quel livello di minimizzazione.

578
00:31:13,820 --> 00:31:18,560
Sappiamo che non riusciremo mai a ottenere
più di otto punti se ci vanno giù

579
00:31:18,560 --> 00:31:20,910
quella direzione.

580
00:31:20,910 --> 00:31:22,980
Perché anche se quelli
altri due rami risultano

581
00:31:22,980 --> 00:31:26,170
ad essere fantastico e vale la pena
migliaia di punti ciascuno,

582
00:31:26,170 --> 00:31:31,666
il nostro avversario ci darà il
minima, e ci danno l'otto.

583
00:31:31,666 --> 00:31:32,790
D'accordo, beh, vediamo.

584
00:31:32,790 --> 00:31:35,190
Vi terremo andando su questa strada.

585
00:31:35,190 --> 00:31:38,490
Scendiamo a quella centrale sulla sinistra.

586
00:31:38,490 --> 00:31:40,560
Guardiamo verso il basso e si vede c'è un nove.

587
00:31:40,560 --> 00:31:45,590
Sappiamo che stiamo andando a ottenere
almeno nove punti scendendo

588
00:31:45,590 --> 00:31:47,720
quella strada di mezzo.

589
00:31:47,720 --> 00:31:52,110
E a questo punto, possiamo semplicemente mettere in pausa.

590
00:31:52,110 --> 00:31:56,910
E possiamo dire, guarda, io
conoscere nel livello superiore,

591
00:31:56,910 --> 00:32:01,160
Ho intenzione di ottenere non più di otto
punti scendendo questa direzione.

592
00:32:01,160 --> 00:32:05,670
Ma se sono andato giù la metà
percorso anziché il percorso di sinistra,

593
00:32:05,670 --> 00:32:08,980
Vorrei avere almeno nove punti.

594
00:32:08,980 --> 00:32:13,590
>> Il mio avversario non sta andando mai
fammi andare su questa strada di mezzo.

595
00:32:13,590 --> 00:32:14,650
Ottengono di scegliere.

596
00:32:14,650 --> 00:32:18,140
E che stanno andando a scegliere il
percorso a sinistra verso le otto,

597
00:32:18,140 --> 00:32:23,650
piuttosto che giù la metà verso
ciò che è di almeno nove punti.

598
00:32:23,650 --> 00:32:25,334
A quel punto, mi fermerò.

599
00:32:25,334 --> 00:32:26,500
E io dico, sai una cosa?

600
00:32:26,500 --> 00:32:29,990
Non devo guardare qualsiasi
più in tale direzione.

601
00:32:29,990 --> 00:32:32,270
Perché sto andando mai arrivarci.

602
00:32:32,270 --> 00:32:36,660
>> Posso saltare quello,
e posso saltare che sei,

603
00:32:36,660 --> 00:32:39,720
Perché questo è mai succederà.

604
00:32:39,720 --> 00:32:42,470
Quindi vado giù e ti
considerare la possibilità successiva.

605
00:32:42,470 --> 00:32:44,830
Vado lì e dico, vedo due.

606
00:32:44,830 --> 00:32:47,125
So che se mi a qui, io sono
andando ad ottenere almeno due.

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
Continuo ad andarci.

610
00:32:51,520 --> 00:32:52,440
Vedo un quattro.

611
00:32:52,440 --> 00:32:54,920
So che sto andando ottenere almeno quattro.

612
00:32:54,920 --> 00:32:57,200
C'è ancora molto tra
quattro e otto, però.

613
00:32:57,200 --> 00:32:58,454
Quindi continuo ad andarci.

614
00:32:58,454 --> 00:32:59,870
Abbasso lo sguardo e vedo che c'è uno.

615
00:32:59,870 --> 00:33:01,614
Va bene, so che se
Vado su questa strada,

616
00:33:01,614 --> 00:33:03,280
Ho intenzione di essere in grado di scegliere i quattro.

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

618
00:33:06,540 --> 00:33:08,980
Che cosa il mio avversario sta per fare?

619
00:33:08,980 --> 00:33:12,310
Tra una cosa che mi dà
otto, qualcosa che mi dà quattro,

620
00:33:12,310 --> 00:33:14,730
e qualcosa che
mi dà almeno nove,

621
00:33:14,730 --> 00:33:17,550
bene, ha intenzione di darmi il quattro.

622
00:33:17,550 --> 00:33:20,110
E so che ora al
molto alto, ho intenzione

623
00:33:20,110 --> 00:33:23,145
per poter ottenere almeno
quattro punti su questo gioco.

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

625
00:33:27,030 --> 00:33:30,900
>> L'intera idea di alfa-beta
è quello di tagliare le parti l'albero in modo

626
00:33:30,900 --> 00:33:32,530
che io non li guardo più.

627
00:33:32,530 --> 00:33:35,964
Ma sembra ancora come se fossi stato
guardando un sacco di albero.

628
00:33:35,964 --> 00:33:36,880
Andiamo avanti verso il basso.

629
00:33:36,880 --> 00:33:38,305
Andremo giù il prossimo ora.

630
00:33:38,305 --> 00:33:39,680
Nel fondo, ho trovato uno.

631
00:33:39,680 --> 00:33:41,030
So che sto andando ottenere almeno uno.

632
00:33:41,030 --> 00:33:41,690
Continuo a guardare.

633
00:33:41,690 --> 00:33:42,625
>> Trovo un tre.

634
00:33:42,625 --> 00:33:44,250
So che sto andando ottenere almeno tre.

635
00:33:44,250 --> 00:33:44,840
Continuo ad andarci.

636
00:33:44,840 --> 00:33:45,660
Trovo un cinque.

637
00:33:45,660 --> 00:33:49,760
So che sto andando ottenere cinque
se Scendo in quel percorso.

638
00:33:49,760 --> 00:33:52,580
E so anche allora
che il mio avversario, se io

639
00:33:52,580 --> 00:33:55,510
scegliere mezzo
le tre grandi scelte,

640
00:33:55,510 --> 00:34:01,440
ha intenzione di darmi
qualcosa che è cinque o meno.

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

642
00:34:02,150 --> 00:34:03,400
Posso andare avanti lì.

643
00:34:03,400 --> 00:34:06,470
Posso guardare giù e io
può dire, che cosa sono io che vado

644
00:34:06,470 --> 00:34:08,239
per ottenere, se vado giù la via di mezzo?

645
00:34:08,239 --> 00:34:09,909
Io vado a prendere, beh, tre lì.

646
00:34:09,909 --> 00:34:12,080
Ho intenzione di ottenere qualcosa
che è almeno tre.

647
00:34:12,080 --> 00:34:16,030
Ci sono ancora cose tra
tre e cinque, in modo da continuare a cercare.

648
00:34:16,030 --> 00:34:20,203
Oh, un nove, ci tornerò sicuramente
prendere che nel corso di un tre.

649
00:34:20,203 --> 00:34:22,744
Ho intenzione di ottenere almeno nove
se vado su questa strada di mezzo.

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

651
00:34:25,530 --> 00:34:31,010
>> Ora il mio avversario si ferma e dice:
guarda, non c'è più nessun punto.

652
00:34:31,010 --> 00:34:33,669
So che il mio
minimizzazione avversario, lui è

653
00:34:33,669 --> 00:34:36,210
andando a darmi la cosa che è
minore o uguale a cinque,

654
00:34:36,210 --> 00:34:39,030
piuttosto che la cosa che è
maggiore o uguale a nove.

655
00:34:39,030 --> 00:34:39,530
Mi fermo.

656
00:34:39,530 --> 00:34:40,779
Io non guardo più a questo.

657
00:34:40,779 --> 00:34:43,280
Continuo ad andarci.

658
00:34:43,280 --> 00:34:44,850
>> Abbasso lo sguardo su questo.

659
00:34:44,850 --> 00:34:46,370
Fino in fondo, trovo un sei.

660
00:34:46,370 --> 00:34:50,040
So che sto andando ottenere almeno sei.

661
00:34:50,040 --> 00:34:53,130
E che cosa posso fare?

662
00:34:53,130 --> 00:34:54,877
Posso smettere.

663
00:34:54,877 --> 00:34:57,460
Perché c'è una scelta tra
qualcosa che è almeno sei

664
00:34:57,460 --> 00:34:59,250
e qualcosa che è
inferiore a cinque, lui è

665
00:34:59,250 --> 00:35:02,570
andando a darmi la cosa
che è inferiore a cinque.

666
00:35:02,570 --> 00:35:04,779
E adesso so che sto andando
per ottenere esattamente quella scelta.

667
00:35:04,779 --> 00:35:06,195
Ho intenzione di ottenere che cinque scelta.

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

669
00:35:08,980 --> 00:35:10,010
>> Vado indietro fino alla cima.

670
00:35:10,010 --> 00:35:11,450
Quali sono io che vado a
scegliere tra qualcosa

671
00:35:11,450 --> 00:35:14,449
che è maggiore o uguale a quattro,
o qualcosa che è pari a cinque?

672
00:35:14,449 --> 00:35:17,140
Vado a prendere qualcosa
che sono almeno cinque.

673
00:35:17,140 --> 00:35:20,490
Scendo l'ultimo percorso, tutto
la via verso il fondo.

674
00:35:20,490 --> 00:35:21,260
C'è un uno.

675
00:35:21,260 --> 00:35:23,410
OK, almeno io vado a prendere un punto.

676
00:35:23,410 --> 00:35:24,427
Continuo ad andarci.

677
00:35:24,427 --> 00:35:25,760
Due, oh, che è meglio di uno.

678
00:35:25,760 --> 00:35:27,100
Ho intenzione di ottenere almeno due.

679
00:35:27,100 --> 00:35:28,610
Trovo un tre.

680
00:35:28,610 --> 00:35:31,450
So che sto andando ottenere tre.

681
00:35:31,450 --> 00:35:34,690
>> E il punto sopra che,
il mio avversario sta andando

682
00:35:34,690 --> 00:35:38,540
darmi qualcosa che è
minore o uguale a tre.

683
00:35:38,540 --> 00:35:40,940
E ora posso smettere.

684
00:35:40,940 --> 00:35:46,290
Perché nella scelta tra me essere
in grado di ottenere un cinque e il mio avversario

685
00:35:46,290 --> 00:35:52,290
darmi qualcosa di meno di tre,
Sono sempre andando a prendere quel cinque.

686
00:35:52,290 --> 00:35:56,810
Quindi non valuto che
parte inferiore della struttura a tutti.

687
00:35:56,810 --> 00:35:59,470
>> Ora, questo può sembrare minore.

688
00:35:59,470 --> 00:36:03,630
Ma quando piccoli pezzi di aritmetica,
superiore e inferiore,

689
00:36:03,630 --> 00:36:10,640
può tagliare via intere parti di
questo albero in crescita esponenziale,

690
00:36:10,640 --> 00:36:14,280
che porta ad un enorme
quantità di risparmio, risparmio

691
00:36:14,280 --> 00:36:17,630
che sono abbastanza grandi che ho
può iniziare a giocare in modo competitivo

692
00:36:17,630 --> 00:36:21,330
a più giochi complessi.

693
00:36:21,330 --> 00:36:27,030
>> Va bene, se guardiamo le dimensioni
e la complessità dei diversi giochi,

694
00:36:27,030 --> 00:36:29,470
tic-tac-toe è stato il nostro semplice esempio.

695
00:36:29,470 --> 00:36:32,150
Abbiamo una piccola tavola, tre a tre.

696
00:36:32,150 --> 00:36:36,030
Otteniamo, al massimo, una media di
circa quattro diverse scelte

697
00:36:36,030 --> 00:36:38,440
come andiamo attraverso il gioco.

698
00:36:38,440 --> 00:36:42,720
Abbiamo da qualche parte intorno al 10
quinto possibili diverse foglie.

699
00:36:42,720 --> 00:36:45,200
E la costruzione di un tic-tac-toe
giocatore, beh, abbiamo appena fatto.

700
00:36:45,200 --> 00:36:47,460
È facile.

701
00:36:47,460 --> 00:36:49,890
>> Se andiamo fino a qualcosa di più
complesso, come Connect Four.

702
00:36:49,890 --> 00:36:53,170
Ti ricordi di questo gioco in cui
si lascia cadere i piccoli gettoni?

703
00:36:53,170 --> 00:36:58,490
Si tratta di un sei da sette a bordo,
Non che molto più grande, ancora

704
00:36:58,490 --> 00:37:00,770
ha circa la stessa ramificazione
fattore come tic-tac-toe.

705
00:37:00,770 --> 00:37:05,410
Ho circa quattro scelte
dove posso mettere le cose in.

706
00:37:05,410 --> 00:37:10,760
Ma ora, ho molto di più
conduce, 10 al 21 di alimentazione.

707
00:37:10,760 --> 00:37:14,440
Questo è qualcosa che è facile
abbastanza che risolviamo subito.

708
00:37:14,440 --> 00:37:17,560
>> Dama, più si complex--
ottenuto un otto per otto bordo.

709
00:37:17,560 --> 00:37:20,570
Tu sei solo su metà della
in qualsiasi momento, anche se.

710
00:37:20,570 --> 00:37:24,930
Hai una ramificazione
fattore che è circa 2,8.

711
00:37:24,930 --> 00:37:28,160
Bene, abbiamo un paio
mosse si può prendere.

712
00:37:28,160 --> 00:37:33,870
Hai avuto circa 10 per le foglie 31,
più grandi e più grandi, e grandi spazi.

713
00:37:33,870 --> 00:37:37,340
Come ho per la ricerca in
quegli spazi sempre più grandi,

714
00:37:37,340 --> 00:37:42,220
in quel momento che le cose come alfa-beta e
essere in grado di tagliare via i rami interi

715
00:37:42,220 --> 00:37:44,420
diventa essenziale.

716
00:37:44,420 --> 00:37:47,440
>> Ora, dama era abbastanza facile nel 1992.

717
00:37:47,440 --> 00:37:51,400
Un programma per computer chiamato
Chinook battere le pedine mondo

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

719
00:37:53,590 --> 00:37:57,260
E da allora, non
giocatore maestro umano ha

720
00:37:57,260 --> 00:38:02,290
stato in grado di battere i migliori
sistemi computazionali.

721
00:38:02,290 --> 00:38:06,570
Se guardiamo a qualcosa come gli scacchi, ora
ancora una volta, abbiamo un otto per otto bordo.

722
00:38:06,570 --> 00:38:09,870
Ma noi abbiamo molto più complessa
pezzi, molto più complessi. movimenti

723
00:38:09,870 --> 00:38:14,610
Abbiamo un fattore di ramificazione di circa
35, 35 possibili mosse in media

724
00:38:14,610 --> 00:38:20,030
che posso prendere, e uno stato
spazio, un numero di foglie

725
00:38:20,030 --> 00:38:28,950
che è cresciuto a 10 alla potenza 123,
un enorme numero di possibilità.

726
00:38:28,950 --> 00:38:35,570
>> Ancora oggi, i moderni processori
sono in grado di farlo con successo.

727
00:38:35,570 --> 00:38:43,900
Nel 1995 e poi nel 1997, un computer
programma chiamato Deep Blue costruito da IBM

728
00:38:43,900 --> 00:38:49,601
che correva su un supercomputer gigante
battere il campione del mondo in carica,

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

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

731
00:38:54,000 --> 00:38:56,650
Questo è stato un punto di svolta.

732
00:38:56,650 --> 00:39:00,620
Oggi, tuttavia, lo stesso trattamento
Potenza siede sul mio MacBook.

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

734
00:39:04,180 --> 00:39:06,440
>> Velocità di elaborazione continua
sempre più veloce.

735
00:39:06,440 --> 00:39:09,500
Possiamo valutare più
tavole più veloce.

736
00:39:09,500 --> 00:39:14,550
Ma ancora più importante, abbiamo una migliore
funzioni di valutazione e una migliore potatura

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

738
00:39:15,460 --> 00:39:19,560
Così possiamo cercare il
spazio più complesso.

739
00:39:19,560 --> 00:39:22,350
Il più grande del consiglio di amministrazione
giochi che si può pensare,

740
00:39:22,350 --> 00:39:26,310
qualcosa di simile Go che è
ha ottenuto un 19 da 19 a bordo,

741
00:39:26,310 --> 00:39:32,490
ora improvvisamente, siamo oltre il punto
dove sistemi computazionali possono vincere.

742
00:39:32,490 --> 00:39:34,530
Non c'è computazionale
sistema là fuori

743
00:39:34,530 --> 00:39:38,880
che può battere un giocatore professionista Go.

744
00:39:38,880 --> 00:39:45,000
I migliori sistemi oggi rango esso su
il genere di buon livello amatoriale.

745
00:39:45,000 --> 00:39:49,285
Quindi c'è ancora un bel po 'fuori
lì che non si può ottenere ancora.

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

747
00:39:51,840 --> 00:39:55,360
>> Va bene, questi
giochi da tavolo tradizionali,

748
00:39:55,360 --> 00:39:58,560
questi tipi di sistemi in cui
costruire questo minimax, se è ottenuto

749
00:39:58,560 --> 00:40:06,300
alfa-beta o meno, questi algoritmi funzionano
perché ci sono alcuni vincoli.

750
00:40:06,300 --> 00:40:08,520
Abbiamo informazioni perfetto
sul mondo.

751
00:40:08,520 --> 00:40:11,690
Sappiamo dove tutti i pezzi sono.

752
00:40:11,690 --> 00:40:13,570
Il mondo è statico.

753
00:40:13,570 --> 00:40:16,220
Nessuno arriva a spostare il
pezzi in tutto, mentre io sono

754
00:40:16,220 --> 00:40:20,640
seduto lì a pensare, prendendo il mio turno.

755
00:40:20,640 --> 00:40:23,140
C'è uno spazio di azione che è discreta.

756
00:40:23,140 --> 00:40:26,900
Posso mettere la mia pedina qui,
o posso mettere la mia pedina qui.

757
00:40:26,900 --> 00:40:30,520
Non mi è permesso di mettere il mio pedone su
la linea tra le due piazze.

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

759
00:40:34,430 --> 00:40:36,520
>> E, infine, le azioni
sono deterministiche.

760
00:40:36,520 --> 00:40:39,790
Io so che se dico,
Torre di cavaliere a tre,

761
00:40:39,790 --> 00:40:44,660
la mia Torre sta per finire al cavaliere
tre, purché sia ​​una mossa valida.

762
00:40:44,660 --> 00:40:47,830
Non c'è incertezza su questo.

763
00:40:47,830 --> 00:40:52,490
Ora, come vado a più
diversi tipi di giochi,

764
00:40:52,490 --> 00:40:55,960
dobbiamo spezzare tali ipotesi.

765
00:40:55,960 --> 00:41:00,020
>> Che cosa se vado a qualcosa
come i videogiochi classici?

766
00:41:00,020 --> 00:41:04,180
Ecco una selezione video
giochi da Atari 2600.

767
00:41:04,180 --> 00:41:05,180
Cosa devo lassù?

768
00:41:05,180 --> 00:41:08,440
Ho Frogger, Spazio
Invaders, Pitfall, e Pac-Man.

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

770
00:41:11,290 --> 00:41:14,840
Quali tipi di ambienti
devo qui ora?

771
00:41:14,840 --> 00:41:16,900
Quale di queste ipotesi
devo rompere?

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

773
00:41:19,410 --> 00:41:21,570
>> Ebbene, dipende dal gioco.

774
00:41:21,570 --> 00:41:28,170
Potrei giocare a scacchi sul 2600, e
sarebbe proprio come lo era prima.

775
00:41:28,170 --> 00:41:33,020
Per la maggior parte di questi sistemi, c'è
conoscenza completa circa il mondo.

776
00:41:33,020 --> 00:41:36,300
C'è tutto
azioni deterministiche.

777
00:41:36,300 --> 00:41:38,330
Ma di solito, il mondo del
non statico.

778
00:41:38,330 --> 00:41:41,970
Cioè, mentre io sono seduto lì
in attesa, qualcosa si sta muovendo.

779
00:41:41,970 --> 00:41:44,320
I fantasmi sono venuta a prendermi.

780
00:41:44,320 --> 00:41:46,570
Lo scorpione mi segue sotto.

781
00:41:46,570 --> 00:41:48,880
Gli invasori spaziali sono
sempre più vicina.

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

783
00:41:54,020 --> 00:41:55,510
Come ben si può fare contro questi?

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

785
00:41:58,640 --> 00:42:02,790
>> Qualche anno fa, Google
aveva un progetto chiamato

786
00:42:02,790 --> 00:42:12,030
DeepMind, dove si allenavano un computer
programma per giocare Atari 2600 giochi.

787
00:42:12,030 --> 00:42:16,120
E se pensate che questo non è grave
affari, i risultati del loro studio

788
00:42:16,120 --> 00:42:19,920
sono stati pubblicati su Nature, così
solo circa buono una pubblicazione

789
00:42:19,920 --> 00:42:22,500
come si può eventualmente ottenere.

790
00:42:22,500 --> 00:42:24,340
Ed ecco quanto bene si sono esibiti.

791
00:42:24,340 --> 00:42:29,220
>> Hanno un algoritmo che sedeva
e guardato solo gli ingressi dello schermo.

792
00:42:29,220 --> 00:42:34,080
Ha ottenuto istruzioni di sorta
le regole del gioco.

793
00:42:34,080 --> 00:42:42,610
E avrebbe dovuto capire,
ha basato la sua partitura, quanto bene si stava facendo.

794
00:42:42,610 --> 00:42:46,560
Questo era un sistema che utilizza qualcosa
chiamato apprendimento per rinforzo.

795
00:42:46,560 --> 00:42:48,380
Cioè, ha guardato a suo punteggio.

796
00:42:48,380 --> 00:42:51,620
E se si fosse un buon punteggio, ha detto,
Dovrei ricordare quelle cose.

797
00:42:51,620 --> 00:42:53,310
E devo fare quelli di nuovo.

798
00:42:53,310 --> 00:42:56,450
E se si ha un cattivo cliente, ha detto,
Non dovrei fare di nuovo quelle cose.

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

800
00:42:59,750 --> 00:43:03,430
>> Questa è la performance
di tali sistemi addestrati

801
00:43:03,430 --> 00:43:07,490
permesso di giocare per un
poche ore su ogni gioco,

802
00:43:07,490 --> 00:43:12,490
confrontato con giocatori professionisti.

803
00:43:12,490 --> 00:43:19,670
Così per tutti i giochi che sono
sul lato sinistro di questa linea,

804
00:43:19,670 --> 00:43:25,920
questo programma per computer autodidatta
sovraperformato i giocatori professionisti.

805
00:43:25,920 --> 00:43:29,690
E per tutto il
a destra, i giocatori professionali

806
00:43:29,690 --> 00:43:30,920
erano ancora il migliore.

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

808
00:43:34,040 --> 00:43:36,850
Per qualcosa che sapeva
nulla circa le regole, che

809
00:43:36,850 --> 00:43:43,020
non sapeva nulla della struttura del
giochi, questo è la prestazione impressionante.

810
00:43:43,020 --> 00:43:45,660
E questo è ciò che siamo in grado di fare oggi.

811
00:43:45,660 --> 00:43:50,239
>> OK, direte voi, ma se ci
pensare di AI in giochi,

812
00:43:50,239 --> 00:43:52,530
Normalmente pensiamo al
cose che possiamo realmente

813
00:43:52,530 --> 00:43:54,180
sedersi e giocare contro.

814
00:43:54,180 --> 00:43:58,760
Se mi siedo e suono
StarCraft, o io gioco gratuito Sieve,

815
00:43:58,760 --> 00:44:01,870
l'avversario computer è il
persona che controlla gli Zerg,

816
00:44:01,870 --> 00:44:06,770
o il controllo del altra civiltà.

817
00:44:06,770 --> 00:44:11,920
Come fanno quei giocatori
effettivamente trovare loro mosse?

818
00:44:11,920 --> 00:44:18,810
>> Ebbene, questi giochi sono strutturati
più o meno allo stesso modo in cui i nostri giochi da tavolo,

819
00:44:18,810 --> 00:44:22,250
questi giochi che ti
collettivamente chiamare quattro giochi di X,

820
00:44:22,250 --> 00:44:26,040
esplorare, expand-- dimenticare quelli.

821
00:44:26,040 --> 00:44:26,980
Cosa sono?

822
00:44:26,980 --> 00:44:32,150
Esplora, espandere, e spegnere,
Credo che sia l'ultima.

823
00:44:32,150 --> 00:44:36,060
Ma sono fondamentalmente
esplorazione e impera giochi.

824
00:44:36,060 --> 00:44:41,020
In genere, il computer avversario
ci deve informazioni limitate.

825
00:44:41,020 --> 00:44:45,486
Non sanno esattamente che cosa è
succede dietro quella nebbia di guerra.

826
00:44:45,486 --> 00:44:47,735
Essi non arrivare a vedere che cosa
avete nel vostro inventario.

827
00:44:47,735 --> 00:44:50,240

828
00:44:50,240 --> 00:44:52,800
>> C'è un ambiente che è dinamico.

829
00:44:52,800 --> 00:44:56,180
Tutto sta cambiando tutto il tempo.

830
00:44:56,180 --> 00:45:00,290
Non si arriva a sedersi e
l'ora di prendere la vostra mossa.

831
00:45:00,290 --> 00:45:02,810
Ma la maggior parte le cose sono ancora discrete.

832
00:45:02,810 --> 00:45:04,200
Devo mettere la mia città qui.

833
00:45:04,200 --> 00:45:06,750
O devo mettere la mia città qui.

834
00:45:06,750 --> 00:45:08,950
E tutto è deterministico.

835
00:45:08,950 --> 00:45:14,660
Quando dico, spostare la mia unità qui, la mia unità
si muove qui, a meno che un ostacolo improvviso

836
00:45:14,660 --> 00:45:17,700
entra in gioco.

837
00:45:17,700 --> 00:45:21,610
Ora, questo non è tutto di computer
giochi che sono là fuori oggi.

838
00:45:21,610 --> 00:45:27,320
>> Quando sarò andato e io gioco una prima persona di tipo
gioco, qualcosa come ladro o Fallout

839
00:45:27,320 --> 00:45:33,350
o Skyrim, o Halo, ora
Ho avversari controllati dal computer

840
00:45:33,350 --> 00:45:37,860
che sono là fuori che hanno
una situazione molto diversa.

841
00:45:37,860 --> 00:45:40,020
Hanno, ancora, informazioni limitate.

842
00:45:40,020 --> 00:45:43,420
Hanno solo possono vedere un
certo campo di vista.

843
00:45:43,420 --> 00:45:45,180
L'ambiente è ancora dinamico.

844
00:45:45,180 --> 00:45:48,280
Le cose stanno cambiando tutto il tempo.

845
00:45:48,280 --> 00:45:52,300
>> Ma ora ho un molto più
spazio azione continua.

846
00:45:52,300 --> 00:45:57,170
Posso essere solo un Sbirciare
po 'fuori dalla porta.

847
00:45:57,170 --> 00:46:00,650
E alcuni giochi, la mia
azioni sono stocastico.

848
00:46:00,650 --> 00:46:04,590
Ho la possibilità di provare a saltare su quel muro,
ma ho avuto la possibilità di fallire.

849
00:46:04,590 --> 00:46:08,280

850
00:46:08,280 --> 00:46:14,550
Questi tipi di giochi sono sempre più vicini
e più vicino al tipo di controller

851
00:46:14,550 --> 00:46:17,330
che costruiamo nella robotica.

852
00:46:17,330 --> 00:46:21,050
>> Nel campo della robotica, dobbiamo assumere
che abbiamo informazioni limitate.

853
00:46:21,050 --> 00:46:23,070
Abbiamo sensori che
ci raccontano il mondo.

854
00:46:23,070 --> 00:46:25,860
Abbiamo un sempre mutevole,
ambiente dinamico.

855
00:46:25,860 --> 00:46:30,440
Abbiamo un mondo in cui lo spazio è
continuo, piuttosto che discreta.

856
00:46:30,440 --> 00:46:36,260
E le nostre azioni, quando cerchiamo
loro, hanno la possibilità di fallire.

857
00:46:36,260 --> 00:46:40,960
E infatti, calcio moderno
controller per il tuo avversario Halo,

858
00:46:40,960 --> 00:46:48,690
o per quelle NPC in Skyrim, in fondo
eseguire piccole architetture di robotica.

859
00:46:48,690 --> 00:46:50,380
>> Sentono il mondo.

860
00:46:50,380 --> 00:46:52,910
Costruiscono un modello del mondo.

861
00:46:52,910 --> 00:46:57,950
Calcolano basano su una serie di
obiettivi che vorrebbero realizzare.

862
00:46:57,950 --> 00:47:03,110
Hanno in programma azioni basate
su ciò che sanno.

863
00:47:03,110 --> 00:47:07,940
E questi sono esattamente gli stessi tipi
di sistemi che costruiamo nella robotica.

864
00:47:07,940 --> 00:47:11,420
Quindi queste architetture, a
portare questo nuovo insieme,

865
00:47:11,420 --> 00:47:14,500
sono spesso piuttosto stesso.

866
00:47:14,500 --> 00:47:16,340
>> Quindi vediamo se possiamo vedere che.

867
00:47:16,340 --> 00:47:19,210
Torniamo al nostro
esempio tic-tac-toe.

868
00:47:19,210 --> 00:47:22,690
E ho intenzione di chiedere un paio di mia
post-doc a venire e mi aiutano.

869
00:47:22,690 --> 00:47:26,970
Così Chen Ming, e Alessandro, e
Olivier, se voi ragazzi sarebbe venuto fuori.

870
00:47:26,970 --> 00:47:32,080

871
00:47:32,080 --> 00:47:35,440
E ho intenzione di bisogno
un paio di volontari

872
00:47:35,440 --> 00:47:37,590
>> OK, ho visto una mano destra
lì in mezzo.

873
00:47:37,590 --> 00:47:39,965
Mi permetta di prendere un altro, qualcuno
ulteriormente nella parte posteriore forse.

874
00:47:39,965 --> 00:47:40,881
Va bene, laggiù.

875
00:47:40,881 --> 00:47:41,490
Vieni su.

876
00:47:41,490 --> 00:47:44,190

877
00:47:44,190 --> 00:47:45,335
Tutto ok.

878
00:47:45,335 --> 00:47:49,490
Quindi cerchiamo di prendere quella copertina in basso.

879
00:47:49,490 --> 00:48:03,700
E se voi ragazzi sarebbero venuti a destra
tornato intorno qui per me, fantastico.

880
00:48:03,700 --> 00:48:06,580
>> Quindi questo è un robot chiamato Baxter.

881
00:48:06,580 --> 00:48:10,880
E Baxter è un robot che è un
piattaforma commerciale, progettata

882
00:48:10,880 --> 00:48:13,030
da una società chiamata Rethink.

883
00:48:13,030 --> 00:48:16,580
E questo robot è progettato
per la produzione su piccola scala.

884
00:48:16,580 --> 00:48:19,265
Ma oggi stiamo andando a
usarlo per giocare a tic-tac-toe.

885
00:48:19,265 --> 00:48:21,930

886
00:48:21,930 --> 00:48:27,150
Ora, questo robot è anche qualcosa
questo è relativamente unico.

887
00:48:27,150 --> 00:48:32,950
Perché se fossi stato da nessuna parte
vicino a un sistema di automazione standard di fabbrica

888
00:48:32,950 --> 00:48:39,580
sistema, sarei molto gravi
pericolo di essere feriti.

889
00:48:39,580 --> 00:48:45,600
>> Baxter, tuttavia, è progettato per essere
relativamente sicuro per interagire.

890
00:48:45,600 --> 00:48:48,680
E così posso spingere su questo robot.

891
00:48:48,680 --> 00:48:52,350
E si può vedere che è un po '
po 'flessibili come si muove intorno.

892
00:48:52,350 --> 00:48:57,250
E posso riposizionarla
dove mi piacerebbe andare.

893
00:48:57,250 --> 00:49:03,410
Ora, in un normale sistema robotizzato,
avremmo una serie di giunti qui

894
00:49:03,410 --> 00:49:07,970
che sarebbe direttamente
rispondere ai comandi di posizione.

895
00:49:07,970 --> 00:49:13,180
E non sarebbero necessariamente cura
se si muovevano attraverso l'aria aperta,

896
00:49:13,180 --> 00:49:15,555
o se si muovevano
attraverso la mia cassa toracica.

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
E di solito, se si fosse
qui con un sistema industriale,

900
00:49:22,090 --> 00:49:23,400
si dovrebbe andare da nessuna parte vicino ad esso.

901
00:49:23,400 --> 00:49:26,280
Ci sarebbero giallo
nastro di sicurezza tutto intorno.

902
00:49:26,280 --> 00:49:28,310
Questo sistema ha un
design leggermente diverso

903
00:49:28,310 --> 00:49:32,130
per essere più gentile e più facile
per le persone di interagire con,

904
00:49:32,130 --> 00:49:36,380
dal fatto che in ciascun giunto, c'è una molla.

905
00:49:36,380 --> 00:49:39,110
E piuttosto che controllare
una posizione esatta,

906
00:49:39,110 --> 00:49:43,110
controlliamo una certa quantità di
coppia, una certa quantità di forza,

907
00:49:43,110 --> 00:49:45,874
che vorremmo essere in quella primavera.

908
00:49:45,874 --> 00:49:47,790
Va bene, così mi permetta
prendere i nostri volontari qui.

909
00:49:47,790 --> 00:49:48,540
Ciao come ti chiami?

910
00:49:48,540 --> 00:49:49,010
>> PUBBLICO: Louis.

911
00:49:49,010 --> 00:49:49,635
>> SPEAKER: Louis.

912
00:49:49,635 --> 00:49:50,490
Felice di vederti.

913
00:49:50,490 --> 00:49:50,990
E?

914
00:49:50,990 --> 00:49:51,610
>> PUBBLICO: David.

915
00:49:51,610 --> 00:49:51,960
>> SPEAKER: David.

916
00:49:51,960 --> 00:49:52,550
Felice di conoscerti.

917
00:49:52,550 --> 00:49:54,508
Se voi ragazzi avrebbe aspettato
proprio qui per un secondo,

918
00:49:54,508 --> 00:49:56,420
Sto per darvi
la possibilità di fare questo.

919
00:49:56,420 --> 00:50:00,610
Quindi questo robot, se è venuta
e se si spinge delicatamente su di esso,

920
00:50:00,610 --> 00:50:03,780
si sta andando a vedere che
si muove un po '.

921
00:50:03,780 --> 00:50:06,349
E se si afferra bene
qui sul polso appena

922
00:50:06,349 --> 00:50:09,390
sopra dove quei pulsanti sono,
sembra che si dovrebbe prendere i pulsanti,

923
00:50:09,390 --> 00:50:13,100
ma prendere a destra sopra di esso, invece, ti
essere in grado di manipolare molto delicatamente

924
00:50:13,100 --> 00:50:14,545
attraverso lo spazio.

925
00:50:14,545 --> 00:50:15,920
Louis, si vuole fare un tentativo?

926
00:50:15,920 --> 00:50:19,465
Quindi dare solo un po '
spingere per iniziare.

927
00:50:19,465 --> 00:50:23,190
E poi se si mette le dita
proprio lì e tenere su ad esso,

928
00:50:23,190 --> 00:50:24,807
perché si muoverà per voi allora.

929
00:50:24,807 --> 00:50:27,824

930
00:50:27,824 --> 00:50:29,365
Va bene, si vuole fare un tentativo?

931
00:50:29,365 --> 00:50:29,980
Vieni su.

932
00:50:29,980 --> 00:50:32,300
Quindi dare solo un dolce
spingere lì per iniziare.

933
00:50:32,300 --> 00:50:33,820
Si può sentire come ci si sente.

934
00:50:33,820 --> 00:50:40,060
E poi se si afferra proprio lì,
sarete in grado di manovrare intorno.

935
00:50:40,060 --> 00:50:41,280
>> OK.

936
00:50:41,280 --> 00:50:47,360
Quindi tipicamente, questo tipo di un robot sarebbe
essere utilizzato per la fabbricazione su piccola scala.

937
00:50:47,360 --> 00:50:50,980
E ho intenzione di spostare questo braccio solo
giù di mezzo un po 'qui.

938
00:50:50,980 --> 00:50:55,750
Ma oggi, stiamo andando a utilizzare il
stesso sistema di gioco tic-tac-toe

939
00:50:55,750 --> 00:50:59,520
sulla base di minimax che abbiamo costruito in precedenza.

940
00:50:59,520 --> 00:51:00,549
ok?

941
00:51:00,549 --> 00:51:02,340
Così, voi ragazzi siete ogni
andando a giocare un gioco.

942
00:51:02,340 --> 00:51:04,210
Louis, si sta andando ad essere il primo.

943
00:51:04,210 --> 00:51:05,920
Vorrei solo tenere qui per un secondo.

944
00:51:05,920 --> 00:51:10,949
Sto per avere ti trovi a destra
qui, solo così tutti possono vedere.

945
00:51:10,949 --> 00:51:11,990
Voi ragazzi impostare qui?

946
00:51:11,990 --> 00:51:13,120
>> ROBOT: Benvenuti.

947
00:51:13,120 --> 00:51:15,910
Giochiamo tic-tac-toe.

948
00:51:15,910 --> 00:51:20,860
Non cogliere il token prima
Io dico che è il vostro turno.

949
00:51:20,860 --> 00:51:22,050
Avvio il gioco.

950
00:51:22,050 --> 00:51:27,900

951
00:51:27,900 --> 00:51:28,750
È il mio turno.

952
00:51:28,750 --> 00:51:47,002

953
00:51:47,002 --> 00:51:50,210
SPEAKER: Ora, se si poteva prendere uno dei
i vostri pezzi e andare avanti e posizionarlo.

954
00:51:50,210 --> 00:51:51,446
ROBOT: È il tuo turno.

955
00:51:51,446 --> 00:51:53,430
[Risata]

956
00:51:53,430 --> 00:51:54,836
È il mio turno.

957
00:51:54,836 --> 00:51:56,820
[Risata]

958
00:51:56,820 --> 00:52:12,196

959
00:52:12,196 --> 00:52:15,680
[Risata]

960
00:52:15,680 --> 00:52:16,570
Tocca a te.

961
00:52:16,570 --> 00:52:21,397

962
00:52:21,397 --> 00:52:23,688
SPEAKER: La razza umana è
Conto su di te qui, Louis.

963
00:52:23,688 --> 00:52:27,440

964
00:52:27,440 --> 00:52:28,350
>> ROBOT: È il mio turno.

965
00:52:28,350 --> 00:52:44,810

966
00:52:44,810 --> 00:52:47,015
>> SPEAKER: Così Baxter
bloccato qui.

967
00:52:47,015 --> 00:52:49,670

968
00:52:49,670 --> 00:52:52,480
>> ROBOT: È il tuo turno.

969
00:52:52,480 --> 00:52:53,360
È il mio turno.

970
00:52:53,360 --> 00:53:14,730

971
00:53:14,730 --> 00:53:16,810
Tocca a te.

972
00:53:16,810 --> 00:53:17,760
È il mio turno.

973
00:53:17,760 --> 00:53:21,330

974
00:53:21,330 --> 00:53:23,830
SPEAKER: E ti faremo Baxter
completare la sua ultima mossa qui.

975
00:53:23,830 --> 00:53:36,622

976
00:53:36,622 --> 00:53:39,090
>> [Risata]

977
00:53:39,090 --> 00:53:40,480
>> ROBOT: Questo è un pareggio.

978
00:53:40,480 --> 00:53:42,030
Io vincerò la prossima volta.

979
00:53:42,030 --> 00:53:43,365
>> [Risata]

980
00:53:43,365 --> 00:53:45,210
>> SPEAKER: Va bene,
grazie mille, Louis.

981
00:53:45,210 --> 00:53:46,094
Grazie.

982
00:53:46,094 --> 00:53:46,980
Si può andare in questo modo.

983
00:53:46,980 --> 00:53:49,759
>> ROBOT: avvio il gioco.

984
00:53:49,759 --> 00:53:51,800
SPEAKER: Così mi spiego
a voi un altro po '

985
00:53:51,800 --> 00:53:55,410
po 'prima di arrivare la nostra rivincita qui.

986
00:53:55,410 --> 00:53:57,200
Che cosa sta succedendo?

987
00:53:57,200 --> 00:53:59,430
Quindi il robot ha una parte superiore della fotocamera fino qui.

988
00:53:59,430 --> 00:54:01,330
Ed è guardando la scacchiera.

989
00:54:01,330 --> 00:54:04,470
Ed è vedere se
che ha un O rosso o blu

990
00:54:04,470 --> 00:54:10,450
e X. bianco come quelli ottenere immessi sul
bordo, che è fondamentalmente lo stesso ingresso

991
00:54:10,450 --> 00:54:13,890
che saremmo leggendo in da
la nostra struttura dati dal nostro schermo.

992
00:54:13,890 --> 00:54:17,290
E 'in esecuzione lo stesso
algoritmo minimax di essere

993
00:54:17,290 --> 00:54:21,010
in grado di trovare dove
mettere un buon segno.

994
00:54:21,010 --> 00:54:24,820
>> E poi stiamo dando un comando su
dove ci piacerebbe un token da collocare.

995
00:54:24,820 --> 00:54:26,120
Il braccio si muove fuori.

996
00:54:26,120 --> 00:54:31,750
E 'con un pinza a depressione da applicare
qualche aspirazione a quel pezzo di legno,

997
00:54:31,750 --> 00:54:35,240
raccoglierla, spostarla a destra
posto, e quindi rilasciare l'aspirazione

998
00:54:35,240 --> 00:54:36,950
e rilasciarlo.

999
00:54:36,950 --> 00:54:38,990
Va bene, stiamo andando
per dare un altro colpo

1000
00:54:38,990 --> 00:54:40,930
con un po 'più intelligente giocatore qui.

1001
00:54:40,930 --> 00:54:42,290
Sei pronto?

1002
00:54:42,290 --> 00:54:46,150
Va bene, se si fosse stare fino
qui e dare a-- girare in questo modo

1003
00:54:46,150 --> 00:54:47,955
modo da poter vedere tutti.

1004
00:54:47,955 --> 00:54:48,830
E poi [incomprensibile].

1005
00:54:48,830 --> 00:54:49,330
>> ROBOT: È il mio turno.

1006
00:54:49,330 --> 00:54:50,455
>> SPEAKER: Baxter avrà inizio.

1007
00:54:50,455 --> 00:55:10,750

1008
00:55:10,750 --> 00:55:11,730
Tocca a te.

1009
00:55:11,730 --> 00:55:16,490

1010
00:55:16,490 --> 00:55:17,520
È il mio turno.

1011
00:55:17,520 --> 00:55:38,740

1012
00:55:38,740 --> 00:55:39,690
Tocca a te.

1013
00:55:39,690 --> 00:55:46,330

1014
00:55:46,330 --> 00:55:47,165
È il mio turno.

1015
00:55:47,165 --> 00:56:01,252

1016
00:56:01,252 --> 00:56:06,192
>> [Risata]

1017
00:56:06,192 --> 00:56:08,542
>> SPEAKER: [WHISPERING] Basta
lasciatelo andare avanti e vincere.

1018
00:56:08,542 --> 00:56:09,500
ROBOT: È il tuo turno.

1019
00:56:09,500 --> 00:56:15,099

1020
00:56:15,099 --> 00:56:15,890
SPEAKER: Va bene.

1021
00:56:15,890 --> 00:56:20,390

1022
00:56:20,390 --> 00:56:21,360
>> ROBOT: È il mio turno.

1023
00:56:21,360 --> 00:56:24,825

1024
00:56:24,825 --> 00:56:26,805
>> [Risata]

1025
00:56:26,805 --> 00:56:42,650

1026
00:56:42,650 --> 00:56:43,510
>> Io vinco.

1027
00:56:43,510 --> 00:56:45,620
>> [Risata]

1028
00:56:45,620 --> 00:56:46,595
>> Avvio il gioco.

1029
00:56:46,595 --> 00:56:48,261
>> SPEAKER: Va bene, vi ringrazio molto.

1030
00:56:48,261 --> 00:56:50,180

1031
00:56:50,180 --> 00:56:55,590
Va bene, penso che abbiamo tempo per
un giocatore tic-tac-toe più eccellente,

1032
00:56:55,590 --> 00:57:00,490
qualcuno che possa mettere questa cosa a
corrispondono, che sa quello che stanno facendo.

1033
00:57:00,490 --> 00:57:03,010
>> [Risata]

1034
00:57:03,010 --> 00:57:05,560
>> Chi va a essere il nostro campione qui?

1035
00:57:05,560 --> 00:57:08,110
Va bene, i tuoi amici ti volontario.

1036
00:57:08,110 --> 00:57:11,190
Questo è abbastanza buono per me.

1037
00:57:11,190 --> 00:57:12,194
Dimmi di nuovo il tuo nome.

1038
00:57:12,194 --> 00:57:12,860
PUBBLICO: Tamir.

1039
00:57:12,860 --> 00:57:14,193
SPEAKER: Tamir, bello vederti.

1040
00:57:14,193 --> 00:57:19,270
Va bene, ancora una volta, stiamo andando a mettere
proprio qui in modo che tutti possano vedere voi.

1041
00:57:19,270 --> 00:57:22,070
Tu sei il nostro rappresentante
in questa partita ora.

1042
00:57:22,070 --> 00:57:24,540
Baxter è uno e oh oh e.

1043
00:57:24,540 --> 00:57:26,300
O mi dispiace, uno oh e uno.

1044
00:57:26,300 --> 00:57:27,490
E tocca a voi qui.

1045
00:57:27,490 --> 00:57:29,340
Baxter si arriva a muoversi prima, però.

1046
00:57:29,340 --> 00:57:30,435
Così.

1047
00:57:30,435 --> 00:57:31,310
ROBOT: È il mio turno.

1048
00:57:31,310 --> 00:57:45,226

1049
00:57:45,226 --> 00:57:48,208
>> [Risata]

1050
00:57:48,208 --> 00:57:52,720

1051
00:57:52,720 --> 00:57:55,780
>> Tocca a te.

1052
00:57:55,780 --> 00:57:56,845
È il mio turno.

1053
00:57:56,845 --> 00:58:18,130

1054
00:58:18,130 --> 00:58:18,965
Tocca a te.

1055
00:58:18,965 --> 00:58:28,751

1056
00:58:28,751 --> 00:58:30,248
È il mio turno.

1057
00:58:30,248 --> 00:58:51,210

1058
00:58:51,210 --> 00:58:52,160
Tocca a te.

1059
00:58:52,160 --> 00:59:00,854

1060
00:59:00,854 --> 00:59:03,365
>> [Risata]

1061
00:59:03,365 --> 00:59:04,240
ROBOT: È il mio turno.

1062
00:59:04,240 --> 00:59:06,930
SPEAKER: E 'molto più difficile quando
si sta in piedi qui, gente.

1063
00:59:06,930 --> 00:59:19,400

1064
00:59:19,400 --> 00:59:21,840
[Risata]

1065
00:59:21,840 --> 00:59:26,730

1066
00:59:26,730 --> 00:59:29,054
ROBOT: Voi umani sono così facile da battere.

1067
00:59:29,054 --> 00:59:30,803
[Risate e applausi]

1068
00:59:30,803 --> 00:59:31,886
SPEAKER: Grazie mille.

1069
00:59:31,886 --> 00:59:34,692
ROBOT: vinco.

1070
00:59:34,692 --> 00:59:35,400
Avvio il gioco.

1071
00:59:35,400 --> 00:59:39,500
>> SPEAKER: Va bene, allora grazie molto
tanto da Olivier, e ad Alessandro,

1072
00:59:39,500 --> 00:59:41,616
e di Chen Ming.

1073
00:59:41,616 --> 00:59:45,600
>> [APPLAUSI]

1074
00:59:45,600 --> 00:59:47,040
>> Voglio fare un ultimo punto.

1075
00:59:47,040 --> 00:59:51,630
Così Baxter per lo
finisce qui, truffato.

1076
00:59:51,630 --> 00:59:54,160

1077
00:59:54,160 --> 00:59:56,310
E questo è stato inaspettato.

1078
00:59:56,310 --> 01:00:00,440
Uno del fantastico
cose di IA è che noi

1079
01:00:00,440 --> 01:00:05,070
fare un lavoro in AI in modo che possiamo costruire
davvero interessante e intelligente

1080
01:00:05,070 --> 01:00:06,930
dispositivi.

1081
01:00:06,930 --> 01:00:10,130
Ma facciamo anche il lavoro in AI
perché ci dice qualcosa

1082
01:00:10,130 --> 01:00:13,940
su come gli esseri umani sono intelligenti.

1083
01:00:13,940 --> 01:00:17,280
>> Uno dei preferiti
studi dal mio laboratorio è

1084
01:00:17,280 --> 01:00:23,660
guardare cosa succede quando
macchine inaspettatamente barare.

1085
01:00:23,660 --> 01:00:27,070
Lo abbiamo fatto in origine non con
Baxter giocare tic-tac-toe,

1086
01:00:27,070 --> 01:00:30,340
ma con un robot più piccolo di nome Nao,
che ha giocato rock-carta-forbici.

1087
01:00:30,340 --> 01:00:33,010

1088
01:00:33,010 --> 01:00:35,800
E a volte dopo
giocando un sacco

1089
01:00:35,800 --> 01:00:41,580
di annoiare rock-carta-forbici giochi,
il robot avrebbe gettato un gesto,

1090
01:00:41,580 --> 01:00:48,616
perdere, e poi cambiare improvvisamente
il suo gesto e dire, vinco.

1091
01:00:48,616 --> 01:00:50,480
>> [Risata]

1092
01:00:50,480 --> 01:00:56,090
>> Ora, a volte ci piacerebbe anche avere il robot,
proprio come un controllo, lanciare un gesto,

1093
01:00:56,090 --> 01:01:01,270
vincere, e cambiare il suo gesto
da perdere, gettare la partita,

1094
01:01:01,270 --> 01:01:04,070
imbrogliare per perdere.

1095
01:01:04,070 --> 01:01:07,540
E che non è quasi come convincente.

1096
01:01:07,540 --> 01:01:09,890
Il robot che inganna
al fine di vincere la gente

1097
01:01:09,890 --> 01:01:14,660
rispondere come se fosse
fuori per loro, come si

1098
01:01:14,660 --> 01:01:17,690
sta cercando attivamente la loro distruzione.

1099
01:01:17,690 --> 01:01:19,210
>> [Risata]

1100
01:01:19,210 --> 01:01:20,990
>> Diventa un agente.

1101
01:01:20,990 --> 01:01:21,840
E 'come una persona.

1102
01:01:21,840 --> 01:01:23,970
Ha convinzione e intenzione.

1103
01:01:23,970 --> 01:01:27,470
E non è buona intenzione.

1104
01:01:27,470 --> 01:01:33,790
E il robot che genera l'
gioco è solo un malfunzionamento.

1105
01:01:33,790 --> 01:01:36,990
E 'solo un dispositivo rotto.

1106
01:01:36,990 --> 01:01:41,405
Mi permetta di mostrare un paio di esempi
di che da alcuni dei nostri partecipanti.

1107
01:01:41,405 --> 01:01:43,990

1108
01:01:43,990 --> 01:01:45,600
Quindi, ecco barare al fine di perdere.

1109
01:01:45,600 --> 01:01:46,266
>> [RIPRODUZIONE VIDEO]

1110
01:01:46,266 --> 01:01:47,010
- [Incomprensibile] vincere.

1111
01:01:47,010 --> 01:01:49,550
Giochiamo.

1112
01:01:49,550 --> 01:01:50,538
>> -Aspetta cosa?

1113
01:01:50,538 --> 01:01:54,490

1114
01:01:54,490 --> 01:01:55,352
>> - [Incomprensibile] vincere.

1115
01:01:55,352 --> 01:01:58,280
Giochiamo.

1116
01:01:58,280 --> 01:01:59,400
>> [Incomprensibile] vincere.

1117
01:01:59,400 --> 01:02:02,290
Giochiamo.

1118
01:02:02,290 --> 01:02:05,490
>> SPEAKER: E qui è barare per vincere.

1119
01:02:05,490 --> 01:02:06,438
>> Sì, ho vinto.

1120
01:02:06,438 --> 01:02:07,394
Giochiamo.

1121
01:02:07,394 --> 01:02:08,828
>> -Non Puoi farlo.

1122
01:02:08,828 --> 01:02:10,740
>> [Risata]

1123
01:02:10,740 --> 01:02:12,174

1124
01:02:12,174 --> 01:02:13,979
>> Sì, ho vinto.

1125
01:02:13,979 --> 01:02:14,520
-Hai barato.

1126
01:02:14,520 --> 01:02:17,990

1127
01:02:17,990 --> 01:02:20,010
Hai imbrogliato ora.

1128
01:02:20,010 --> 01:02:21,140
>> Sì, ho vinto.

1129
01:02:21,140 --> 01:02:22,940
>> Ehi, voi baro.

1130
01:02:22,940 --> 01:02:26,670
Abusi, super imbroglione.

1131
01:02:26,670 --> 01:02:27,650
>> [FINE RIPRODUZIONE]

1132
01:02:27,650 --> 01:02:31,130
>> SPEAKER: Questi diverso
Reazioni rapidamente

1133
01:02:31,130 --> 01:02:34,890
cambiare la nostra percezione del dispositivo.

1134
01:02:34,890 --> 01:02:36,780
Questo significa che
abbiamo volutamente costruiamo

1135
01:02:36,780 --> 01:02:40,370
macchine che ingannano perché è
la migliore ingegneria che possiamo fare?

1136
01:02:40,370 --> 01:02:44,680
No, ma ci dice qualcosa
veramente interessante di persone.

1137
01:02:44,680 --> 01:02:49,710
Quella cosa che voi e trucchi
ruba la tua vittoria, che è

1138
01:02:49,710 --> 01:02:53,660
qualcosa di vivo, che è
animano, questo è fuori per voi.

1139
01:02:53,660 --> 01:02:54,680
Ha stato mentale.

1140
01:02:54,680 --> 01:02:55,400
Ha credenza.

1141
01:02:55,400 --> 01:02:57,170
Ha intenzione.

1142
01:02:57,170 --> 01:03:01,540
>> Quella cosa che porge la
gioco a voi, che non è.

1143
01:03:01,540 --> 01:03:04,670
Questo è solo un malfunzionamento.

1144
01:03:04,670 --> 01:03:08,900
Questo in molti modi perché è
facile buttare il gioco con i bambini.

1145
01:03:08,900 --> 01:03:12,050
Ma se si tenta di imbrogliare loro
e una sorta di cantare vittoria

1146
01:03:12,050 --> 01:03:15,200
quando, si sa, solo per ridurre il
gioco, che ti cattura subito.

1147
01:03:15,200 --> 01:03:19,040

1148
01:03:19,040 --> 01:03:23,140
Questi tipi di effetti che
vediamo che esce di AI,

1149
01:03:23,140 --> 01:03:26,490
ci insegnano molto su noi stessi.

1150
01:03:26,490 --> 01:03:28,076
>> Va bene, questo è tutto per oggi.

1151
01:03:28,076 --> 01:03:30,450
Grazie infinite a David e
il team di produzione di Harvard

1152
01:03:30,450 --> 01:03:32,350
per scendere.

1153
01:03:32,350 --> 01:03:33,820
>> [APPLAUSI]

1154
01:03:33,820 --> 01:03:36,760

1155
01:03:36,760 --> 01:03:41,840
>> Ci vediamo per un quiz,
e poi per un ultima lezione.

1156
01:03:41,840 --> 01:03:43,025
Buona giornata.

1157
01:03:43,025 --> 01:03:44,965
>> [APPLAUSI]

1158
01:03:44,965 --> 01:03:48,360

1159
01:03:48,360 --> 01:03:51,825
>> [RIPRODUZIONE DI BRANI MUSICALI]

1160
01:03:51,825 --> 01:03:54,950
DAVID J MALAN: Beh, abbiamo probabilmente bisogno
di introdurre un qualche tipo di crittografia,

1161
01:03:54,950 --> 01:03:55,450
destra?

1162
01:03:55,450 --> 01:03:58,650
Perché allora le intestazioni dei
queste richieste HTTP saranno

1163
01:03:58,650 --> 01:04:01,530
strapazzate in modo che chiunque
cercando di intercettare il traffico

1164
01:04:01,530 --> 01:04:03,400
non sarà effettivamente in grado di vederli.

1165
01:04:03,400 --> 01:04:05,254
Quindi qual è la soluzione a questo problema?

1166
01:04:05,254 --> 01:04:07,920
Beh, abbiamo bisogno di introdurre in realtà
crittografia nella formula,

1167
01:04:07,920 --> 01:04:11,010
in modo che quando la persona è
trasmissione dei dati da A a B,

1168
01:04:11,010 --> 01:04:12,390
possiamo send-- sicuro

1169
01:04:12,390 --> 01:04:14,590
>> [Risata]

1170
01:04:14,590 --> 01:04:19,530
>> L'informazione in modo che il
avversario non può, infatti, vedere.