1
00:00:00,000 --> 00:00:01,924
>> [Jouer de la musique]

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

3
00:00:10,600 --> 00:00:13,280
>> CONFÉRENCIER: Bienvenue à tous.

4
00:00:13,280 --> 00:00:15,440
Ceci est CS50.

5
00:00:15,440 --> 00:00:21,040
Et aujourd'hui, nous avons beaucoup de
choses intéressantes à raconter.

6
00:00:21,040 --> 00:00:25,500
Mais d'abord, je dois rappeler
vous d'un certain nombre de choses administratives.

7
00:00:25,500 --> 00:00:30,160
Cette semaine est un jeu-questionnaire, le mercredi
ou pour la section de Yale

8
00:00:30,160 --> 00:00:32,940
les mardis et jeudis, le jeudi.

9
00:00:32,940 --> 00:00:38,170
Il ya des critiques de quiz
ce soir à Yale, 05 heures 30-à-7:00.

10
00:00:38,170 --> 00:00:40,030
À Harvard, ils ont enregistré un hier.

11
00:00:40,030 --> 00:00:43,000
Et tout le monde peut regarder cette ligne.

12
00:00:43,000 --> 00:00:49,406
>> Aussi, cette semaine ou au début de la semaine prochaine,
nous avons notre dernière conférence CS50.

13
00:00:49,406 --> 00:00:51,450
[Gémissements] Je sais.

14
00:00:51,450 --> 00:00:54,140
Il est venu si tôt.

15
00:00:54,140 --> 00:00:57,820
Étudiants de Yale auront un direct
sermonner ici à l'école de droit

16
00:00:57,820 --> 00:00:59,920
auditorium vendredi.

17
00:00:59,920 --> 00:01:01,140
Il y aura du gâteau.

18
00:01:01,140 --> 00:01:05,570
Les étudiants de Harvard auront la
dernière conférence à Sanders lundi.

19
00:01:05,570 --> 00:01:08,050
Il y aura aussi gâteau.

20
00:01:08,050 --> 00:01:14,000
>> Aussi, cette semaine, le vendredi, pour ceux
d'entre vous qui viennent à New Haven,

21
00:01:14,000 --> 00:01:15,740
nous avons l'Expo de CS50.

22
00:01:15,740 --> 00:01:18,850
Nous avons plus de 30
différents groupes enregistrés

23
00:01:18,850 --> 00:01:22,530
à vous montrer tout
de voiliers autonomes,

24
00:01:22,530 --> 00:01:27,170
aux systèmes qui reconnaissent
portraits numériques, à l'ordinateur

25
00:01:27,170 --> 00:01:32,100
la musique et la musique produite par ordinateur.

26
00:01:32,100 --> 00:01:33,610
Alors s'il vous plaît vous joindre à nous.

27
00:01:33,610 --> 00:01:36,460
Je pense que ça va être un grand moment.

28
00:01:36,460 --> 00:01:40,320
>> Aujourd'hui, cependant, nous arrivons à
continuer à parler de l'IA,

29
00:01:40,320 --> 00:01:43,150
à propos de l'intelligence artificielle.

30
00:01:43,150 --> 00:01:46,070
Et l'une des choses qui
nous allons arriver à aujourd'hui

31
00:01:46,070 --> 00:01:51,750
est l'idée de la façon de
AI utiliser pour résoudre des problèmes.

32
00:01:51,750 --> 00:01:54,690
Maintenant, comme toujours, nous allons commencer
avec quelque chose de simple.

33
00:01:54,690 --> 00:01:57,120
Et nous allons commencer
avec une idée simple.

34
00:01:57,120 --> 00:01:59,920
Et voilà en utilisant la recherche.

35
00:01:59,920 --> 00:02:06,990
>> Alors, imaginez un instant que je
avoir une tâche que je dois accomplir.

36
00:02:06,990 --> 00:02:11,970
Et je voudrais avoir cette tâche
automatisée par un agent logiciel.

37
00:02:11,970 --> 00:02:17,100
Imaginez que je suis en train de réserver un ensemble
des vols au départ de, disons, Boston

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

39
00:02:20,040 --> 00:02:24,230
Je pourrais passer et je pouvais utiliser
l'un des merveilleux recherche en ligne

40
00:02:24,230 --> 00:02:28,790
outils, qui va faire
essentiellement le même processus que nous sommes

41
00:02:28,790 --> 00:02:30,030
aller à pied à travers aujourd'hui.

42
00:02:30,030 --> 00:02:34,100
Mais si vous ne disposez que
outil, que feriez-vous?

43
00:02:34,100 --> 00:02:37,570
>> Eh bien, vous pourriez regarder et
vois et dis, je suis à Boston.

44
00:02:37,570 --> 00:02:41,520
Qu'est-ce que les vols sont disponibles pour moi?

45
00:02:41,520 --> 00:02:44,390
Maintenant, peut-être je ai trois
vols possibles sur Boston

46
00:02:44,390 --> 00:02:47,180
qui correspondra à l'heure
quand je dois partir.

47
00:02:47,180 --> 00:02:48,830
Je pouvais voler à Chicago.

48
00:02:48,830 --> 00:02:50,130
Ou je pouvais voler à Miami.

49
00:02:50,130 --> 00:02:53,340
Ou je pouvais voler à New York.

50
00:02:53,340 --> 00:02:56,980
Je pourrais alors chercher de chaque
une de ces villes de destination

51
00:02:56,980 --> 00:03:00,650
et de réfléchir à quels endroits
Je pouvais atteindre

52
00:03:00,650 --> 00:03:03,020
à partir de chacune de ces villes.

53
00:03:03,020 --> 00:03:07,390
>> Alors peut-être de Chicago, je peux obtenir
un vol direct à destination de San Francisco.

54
00:03:07,390 --> 00:03:09,550
Cela est excellent.

55
00:03:09,550 --> 00:03:12,360
Ou je pourrais obtenir un vol à destination de Denver.

56
00:03:12,360 --> 00:03:16,970
Maintenant, peut-être que le vol à San Francisco
est la solution parfaite pour moi,

57
00:03:16,970 --> 00:03:19,530
mais peut-être pas.

58
00:03:19,530 --> 00:03:22,180
Peut-être que je cherche quelque chose
qui est un peu moins cher

59
00:03:22,180 --> 00:03:24,920
ou un peu mieux pour mon calendrier.

60
00:03:24,920 --> 00:03:29,197
Et donc je pourrais chercher ce que les autres
possibilités pourraient être là-bas.

61
00:03:29,197 --> 00:03:30,280
Donc, je pourrais regarder Denver.

62
00:03:30,280 --> 00:03:33,870
Et à partir de Denver, ainsi, peut-être
Je peux obtenir un vol pour Austin.

63
00:03:33,870 --> 00:03:37,080
Et à partir de Austin, peut-être je peux obtenir un
vol pour Phoenix, et de Phoenix

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

65
00:03:40,190 --> 00:03:42,730
Maintenant, je ne suis pas encore fini.

66
00:03:42,730 --> 00:03:45,640
Parce que peut-être il ya une
vol direct de New York

67
00:03:45,640 --> 00:03:47,850
à San Francisco qui est parfait pour moi.

68
00:03:47,850 --> 00:03:53,354
Ou peut-être il ya un vol de Miami
grâce à Denver qui est beaucoup moins cher.

69
00:03:53,354 --> 00:03:54,270
Donc, je dois encore aller.

70
00:03:54,270 --> 00:03:58,200
Et je dois encore regarder tous ceux
villes que je ne suis pas encore étudiées.

71
00:03:58,200 --> 00:04:04,220
Je dois vérifier exhaustive l'ensemble des
les possibilités que je pourrais avoir.

72
00:04:04,220 --> 00:04:09,610
>> Donc, à partir de New York, peut-être je peux obtenir un
vol à destination de Nashville, et de Nashville

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

74
00:04:10,336 --> 00:04:11,460
Et puis, je sais où je suis.

75
00:04:11,460 --> 00:04:14,252
Et puis je sais de Austin, je peux
vol à Phoenix, et de Phoenix

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

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

78
00:04:18,240 --> 00:04:22,830
Si je vole premier à Miami, cependant,
peut-être je peux obtenir un vol de Miami

79
00:04:22,830 --> 00:04:25,080
à Nashville, ou de Miami à Austin.

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

81
00:04:27,950 --> 00:04:30,860
>> Et maintenant, je l'ai essayé tous
des possibilités.

82
00:04:30,860 --> 00:04:36,310
Je ai construit ce graphique que
me montre tous les itinéraires possibles

83
00:04:36,310 --> 00:04:37,790
que je pourrais être en mesure de prendre.

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

85
00:04:40,510 --> 00:04:43,640
Quand nous représenter ces
sortes de problèmes,

86
00:04:43,640 --> 00:04:47,870
on ne va pas à représenter
les explicitement comme ce graphique,

87
00:04:47,870 --> 00:04:51,590
parce que ce graphique ne représente pas
l'histoire de l'endroit où nous sommes allés.

88
00:04:51,590 --> 00:04:55,260
Sachant que je pris l'avion de
Phoenix à San Francisco

89
00:04:55,260 --> 00:05:01,690
ne me dites pas que je suis venu par l'intermédiaire
Nashville, ou via Denver, ou via Miami.

90
00:05:01,690 --> 00:05:06,430
>> Donc ce que je vais faire à la place est
Je vais prendre ce même problème,

91
00:05:06,430 --> 00:05:09,140
et je vais le représenter comme un arbre.

92
00:05:09,140 --> 00:05:14,300
Et à la racine de l'arbre, à la
dessus, je vais mettre l'endroit que je commencé,

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

94
00:05:16,590 --> 00:05:19,310
Et de Boston, je vais regarder
tous les emplacements possibles

95
00:05:19,310 --> 00:05:20,380
que je peux voyager à.

96
00:05:20,380 --> 00:05:25,480
Eh bien, dans ce cas, je devais trois,
Chicago, New York et Miami.

97
00:05:25,480 --> 00:05:29,850
Et puis, je vais explorer chacun des
ces enfants dans l'arbre.

98
00:05:29,850 --> 00:05:32,690
>> De Chicago, je voyais
que je devais deux vols.

99
00:05:32,690 --> 00:05:35,940
Je pouvais voler directement à
San Francisco ou Denver.

100
00:05:35,940 --> 00:05:37,740
Maintenant San Francisco, qui est mon objectif.

101
00:05:37,740 --> 00:05:39,790
Voilà ma destination.

102
00:05:39,790 --> 00:05:42,220
Cela va être une feuille de cet arbre.

103
00:05:42,220 --> 00:05:45,340
Voilà, je ne vais jamais aller
quelque part après San Francisco.

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

105
00:05:47,850 --> 00:05:50,340
De Denver, cependant,
Je peux voler de Denver

106
00:05:50,340 --> 00:05:54,220
à Austin, Austin à partir de Phoenix,
et de Phoenix à San Francisco.

107
00:05:54,220 --> 00:05:56,050
Et maintenant encore, je suis arrivé à une feuille.

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

109
00:05:59,470 --> 00:06:03,980
>> Je pourrais alors revenir à la prochaine
ville que je ne l'ai pas entièrement exploré.

110
00:06:03,980 --> 00:06:07,440
Ce serait New York, aller
Retour au sommet de mon arbre,

111
00:06:07,440 --> 00:06:09,160
descendre à New York.

112
00:06:09,160 --> 00:06:12,700
De New York, je peux voler à
Nashville, de Nashville à Austin,

113
00:06:12,700 --> 00:06:17,290
de Austin à Phoenix, et
de Phoenix à San Francisco.

114
00:06:17,290 --> 00:06:20,170
Et enfin, une ville que je
ne l'ont pas encore regardé, Miami.

115
00:06:20,170 --> 00:06:24,600
>> Eh bien, à partir de Miami, je dit que je devais deux
possibilités, Nashville ou Austin.

116
00:06:24,600 --> 00:06:28,810
Si je prends l'avion pour Nashville, eh bien je vole
de Nashville, à Austin, à Phoenix,

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

118
00:06:29,640 --> 00:06:33,600
Si je prends l'avion à Austin, je vole Austin,
à Phoenix, San Francisco.

119
00:06:33,600 --> 00:06:36,340
Et maintenant, je dois un arbre.

120
00:06:36,340 --> 00:06:37,230
Il est un arbre complet.

121
00:06:37,230 --> 00:06:41,890
Il est de toutes les possibilités et
tous les chemins que je pouvais prendre.

122
00:06:41,890 --> 00:06:44,310
Autrement dit, si je me mets à la
racine de l'arbre dans la partie supérieure

123
00:06:44,310 --> 00:06:47,860
et je descends à l'un des
quitte, il me dit non seulement

124
00:06:47,860 --> 00:06:50,480
où je vais
finir, San Francisco,

125
00:06:50,480 --> 00:06:53,670
mais il me dit que la route
Je dois prendre pour y arriver.

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

127
00:06:56,400 --> 00:06:59,690
>> Maintenant, laquelle de ces est le meilleur?

128
00:06:59,690 --> 00:07:02,430
Eh bien, rien à ce sujet
problème me dit encore

129
00:07:02,430 --> 00:07:04,710
de ceux qui est la meilleure solution.

130
00:07:04,710 --> 00:07:09,270
Peut-être que je me soucie le plus à propos de
combien de temps je suis dans l'air,

131
00:07:09,270 --> 00:07:12,350
ou la distance que je prends l'avion.

132
00:07:12,350 --> 00:07:16,410
Dans ce cas, Chicago à San
Francisco pourrait être le nombre le plus court

133
00:07:16,410 --> 00:07:18,910
de miles dans l'air.

134
00:07:18,910 --> 00:07:20,860
>> Peut-être que je me soucie de coût.

135
00:07:20,860 --> 00:07:23,680
Et nous savons tous que des vols directs
sont généralement plus cher.

136
00:07:23,680 --> 00:07:26,610
Alors peut-être si je prends cette
type d'itinéraire vers l'arrière

137
00:07:26,610 --> 00:07:30,650
par Miami, Nashville,
Austin, Phoenix, peut-être alors

138
00:07:30,650 --> 00:07:34,070
Je reçois un prix inférieur.

139
00:07:34,070 --> 00:07:36,440
Mais je ne pouvais optimiser sur tout
critères que je me soucie.

140
00:07:36,440 --> 00:07:39,790
Qui a le meilleur
vol Wi-Fi, ou qui

141
00:07:39,790 --> 00:07:43,110
aéroports ont la meilleure nourriture disponible.

142
00:07:43,110 --> 00:07:47,280
Et chacun de ceux qui pourraient
me donner une solution différente

143
00:07:47,280 --> 00:07:49,215
que je vois comme étant le meilleur.

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

145
00:07:51,990 --> 00:07:54,400
>> Ces sortes de problèmes,
où nous allons

146
00:07:54,400 --> 00:07:58,480
de construire sur cet arbre de
possibilités, et puis

147
00:07:58,480 --> 00:08:02,100
Examinons chacun de ceux
parcours individuels, et d'examiner

148
00:08:02,100 --> 00:08:05,270
qui remplit de ces
un critère pour nous,

149
00:08:05,270 --> 00:08:08,790
nous allons appeler
ces problèmes de recherche.

150
00:08:08,790 --> 00:08:11,280
Et nous avons beaucoup de
algorithmes, dont certaines

151
00:08:11,280 --> 00:08:15,270
nous avons déjà vu, d'aller
et d'explorer ces arbres.

152
00:08:15,270 --> 00:08:19,270
Nous pourrions le faire de la manière que je
n'a tout simplement, une recherche en profondeur d'abord,

153
00:08:19,270 --> 00:08:22,900
aller aussi loin que nous pouvons jusqu'à ce que nous
frapper une feuille, puis de revenir en place,

154
00:08:22,900 --> 00:08:24,787
et d'aller droit vers le bas.

155
00:08:24,787 --> 00:08:26,870
Ou nous pourrions faire ce qui est
appelé algorithme de parcours en largeur.

156
00:08:26,870 --> 00:08:29,675
Nous pourrions développer tout
au sommet, puis

157
00:08:29,675 --> 00:08:31,550
tout une ligne
dessous, et ensuite,

158
00:08:31,550 --> 00:08:35,240
tout une ligne en dessous qui.

159
00:08:35,240 --> 00:08:41,250
Ces arbres de recherche
sont fondamentales pour AI.

160
00:08:41,250 --> 00:08:46,570
Mais ils ne reçoivent pas assez
à droite tout le temps.

161
00:08:46,570 --> 00:08:51,600
En fait, dans beaucoup de cas
que nous nous soucions vraiment,

162
00:08:51,600 --> 00:08:54,430
nous voulons construire un arbre,
mais nous ne le faisons pas fait

163
00:08:54,430 --> 00:08:57,140
arriver à faire toutes les décisions.

164
00:08:57,140 --> 00:09:00,940
>> Ce sont des situations appelées
recherche contradictoire, aussi connu

165
00:09:00,940 --> 00:09:05,390
comme la façon d'écrire jouer au jeu
systèmes et être payé pour cela.

166
00:09:05,390 --> 00:09:07,940
Mais ce sont les types
des systèmes où je

167
00:09:07,940 --> 00:09:12,920
pourrait obtenir de choisir quand je vais partir
Boston, la ville où je vais à la prochaine.

168
00:09:12,920 --> 00:09:19,990
Mais après cela, quelqu'un d'autre pourrait obtenir
de prendre la décision sur l'endroit où je vole.

169
00:09:19,990 --> 00:09:24,040
Donc, pour construire ces
sortes de structures, nous sommes

170
00:09:24,040 --> 00:09:28,510
allez avoir à prendre un peu
approche différente.

171
00:09:28,510 --> 00:09:31,060
Nous ne serons pas en mesure de
il suffit de chercher dans l'arbre

172
00:09:31,060 --> 00:09:35,000
plus, parce que nous ne sommes pas
celui qui est dans le contrôle

173
00:09:35,000 --> 00:09:38,180
de chacun de ces points de décision.

174
00:09:38,180 --> 00:09:42,590
>> Alors imaginons simple
jeu comme tic-tac-toe.

175
00:09:42,590 --> 00:09:46,730
Je pourrais commencer par une
conseil complètement vide.

176
00:09:46,730 --> 00:09:49,580
Et en tic-tac-toe,
X arrive à jouer en premier.

177
00:09:49,580 --> 00:09:53,890
Et donc je ne pouvais penser à toutes les
coups possibles que X puisse faire.

178
00:09:53,890 --> 00:09:57,420
Et si je suis le seul jeu
X, qui est grand.

179
00:09:57,420 --> 00:10:01,020
Je dois neuf possible
propose que je peux faire.

180
00:10:01,020 --> 00:10:05,000
Je pourrais mettre un X dans l'une quelconque
de ces neuf postes.

181
00:10:05,000 --> 00:10:10,710
>> Et puis, de chacun de ces, je
pouvait imaginer ce qui arrive ensuite.

182
00:10:10,710 --> 00:10:14,130
Eh bien, dans ce cas, l'autre
joueur devrait recevoir de prendre un virage.

183
00:10:14,130 --> 00:10:15,660
O serait l'occasion de prendre un virage.

184
00:10:15,660 --> 00:10:19,510
Et à partir de chacune des personnes, il
serait huit endroits différents

185
00:10:19,510 --> 00:10:22,980
O qui pourrait placer leur marqueur.

186
00:10:22,980 --> 00:10:25,790
>> Disons que je décidai que je suis
va mettre un X dans le centre.

187
00:10:25,790 --> 00:10:28,810
Cela semble toujours comme
un bon mouvement d'ouverture.

188
00:10:28,810 --> 00:10:34,870
Je pourrais regarder en dessous de ce que, le
huit coups possibles que O fait.

189
00:10:34,870 --> 00:10:37,320
Maintenant, si je joue X, qui est merveilleux.

190
00:10:37,320 --> 00:10:41,740
Je peux choisir qui je
aller, l'une au milieu.

191
00:10:41,740 --> 00:10:45,000
Mais maintenant, O obtient de choisir.

192
00:10:45,000 --> 00:10:48,750
Et je ne ai pas le contrôle
sur cette décision.

193
00:10:48,750 --> 00:10:51,670
>> Mais à partir de chacun de ces
postes du conseil d'administration possibles,

194
00:10:51,670 --> 00:10:54,020
il ya alors une autre
un ensemble de possibilités.

195
00:10:54,020 --> 00:10:56,700
Quand il vient à être
à mon tour, je ne retournerais

196
00:10:56,700 --> 00:11:01,500
obtenir de choisir et de dire, eh bien,
si O se déplace dans le bien,

197
00:11:01,500 --> 00:11:06,110
l'endroit du milieu sur la gauche, puis
Je dois un ensemble de possibilités

198
00:11:06,110 --> 00:11:09,740
où je peux prendre mon prochain déménagement.

199
00:11:09,740 --> 00:11:14,140
De ceux-là, je pourrais considérer tous
les possibilités en dessous.

200
00:11:14,140 --> 00:11:18,030
Et puis O recevrait
de choisir parmi ceux-ci.

201
00:11:18,030 --> 00:11:22,290
>> Et je pourrais continuer à construire cette
arbre jusqu'à ce que je suis arrivé au point

202
00:11:22,290 --> 00:11:26,960
où quelqu'un soit
remporte le game-- qui est

203
00:11:26,960 --> 00:11:31,070
arrivés à être considérés comme une feuille node--
ou le conseil est complètement plein

204
00:11:31,070 --> 00:11:32,704
et personne n'a gagné.

205
00:11:32,704 --> 00:11:34,370
Et cela va aussi être un nœud feuille.

206
00:11:34,370 --> 00:11:35,411
Cela va être un match nul.

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

208
00:11:37,820 --> 00:11:41,680
>> Mais la chose la plus délicate avec ceci est
si cela était juste une recherche normale

209
00:11:41,680 --> 00:11:44,269
problème, je serais en mesure de
par exemple, eh bien, X devrait aller ici.

210
00:11:44,269 --> 00:11:45,560
Et O devrait aller bien là-bas.

211
00:11:45,560 --> 00:11:46,770
Et puis X devrait aller ici.

212
00:11:46,770 --> 00:11:48,269
Et puis O devrait aller bien là-bas.

213
00:11:48,269 --> 00:11:51,860
Et puis X peut obtenir trois
dans une rangée, et je gagne.

214
00:11:51,860 --> 00:11:54,870
Et le jeu serait plus
en cinq mouvements, trois pour moi,

215
00:11:54,870 --> 00:11:57,710
deux pour mon adversaire.

216
00:11:57,710 --> 00:12:01,300
Mais je ne suis pas toujours de choisir cela.

217
00:12:01,300 --> 00:12:03,720
>> Ainsi, au lieu, ce que nous sommes
allez avoir à faire

218
00:12:03,720 --> 00:12:06,270
est que nous allons devoir
d'avoir une nouvelle stratégie.

219
00:12:06,270 --> 00:12:09,350
Et que la stratégie
algorithmes de jeu vidéo utilisent souvent

220
00:12:09,350 --> 00:12:12,000
est ce qu'on appelle minimax.

221
00:12:12,000 --> 00:12:15,500
L'idée centrale de
Minimax est que nous sommes

222
00:12:15,500 --> 00:12:21,365
aller chercher le mouvement qui donne
notre adversaire le pire de jeu possible

223
00:12:21,365 --> 00:12:22,790
de mouvements qu'ils peuvent faire.

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

225
00:12:25,570 --> 00:12:28,870
Il ne me fait pas de bien
de choisir un mouvement où

226
00:12:28,870 --> 00:12:31,952
Je pourrais être capable de gagner après
que, parce que mon adversaire est pas

227
00:12:31,952 --> 00:12:33,160
va me donner cette chance.

228
00:12:33,160 --> 00:12:37,770
Ils vont choisir une
résultat terrible pour moi.

229
00:12:37,770 --> 00:12:42,010
Donc, je vais faire la
déplacer qui force mon adversaire

230
00:12:42,010 --> 00:12:45,760
de faire quelque chose de mieux pour moi.

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

232
00:12:46,260 --> 00:12:48,410
Voyons comment cela se joue.

233
00:12:48,410 --> 00:12:51,640
Alors, voici notre algorithme en pseudo.

234
00:12:51,640 --> 00:12:54,450
Nous allons générer
l'arbre entier de jeu.

235
00:12:54,450 --> 00:12:56,757
Nous allons construire
la structure entière.

236
00:12:56,757 --> 00:12:57,840
Et puis nous allons passer en revue.

237
00:12:57,840 --> 00:13:02,100
Et tout en bas à chacune de la
les noeuds terminaux, sur chacune des feuilles,

238
00:13:02,100 --> 00:13:07,850
nous évaluons comment
précieux est que pour moi?

239
00:13:07,850 --> 00:13:11,690
Et nous allons à des choses de valeur qui
sont bonnes pour moi comme étant positif.

240
00:13:11,690 --> 00:13:14,460
Les choses qui ne sont pas bonnes pour moi
sera moins positif, ou nul,

241
00:13:14,460 --> 00:13:16,480
ou même négative.

242
00:13:16,480 --> 00:13:19,240
>> Donc, en tic-tac-toe, peut-être
une victoire pour moi est bon.

243
00:13:19,240 --> 00:13:20,290
Voilà un.

244
00:13:20,290 --> 00:13:22,400
Et une cravate est de zéro.

245
00:13:22,400 --> 00:13:26,230
Et quelque chose qui est une perte pour
moi, peut-être est une valeur négative.

246
00:13:26,230 --> 00:13:29,620
Tout ce qui importe est que la meilleure
il est pour moi, plus le score

247
00:13:29,620 --> 00:13:32,160
qu'il reçoit.

248
00:13:32,160 --> 00:13:36,690
A partir de ces possibilités à la
bas, puis nous allons filtrer vers le haut.

249
00:13:36,690 --> 00:13:40,650
Et quand il est ma chance de choisir
parmi un ensemble d'alternatives,

250
00:13:40,650 --> 00:13:44,460
Je vais choisir celui qui est
a obtenu le score le plus élevé.

251
00:13:44,460 --> 00:13:47,200
>> Et chaque fois qu'il est mon
adversaires tour de choisir,

252
00:13:47,200 --> 00:13:52,350
Je suppose qu'ils vont
choisir celui avec le score le plus bas.

253
00:13:52,350 --> 00:13:56,090
Et si je fais ça tout le chemin
au sommet de l'arbre,

254
00:13:56,090 --> 00:14:03,150
Je l'ai choisi une voie qui donne
moi le meilleur résultat que je peux obtenir,

255
00:14:03,150 --> 00:14:09,110
en supposant que mon adversaire
rend tous les bons mouvements.

256
00:14:09,110 --> 00:14:11,940
>> Très bien, alors voyons
ceci dans l'action première.

257
00:14:11,940 --> 00:14:14,980
Et puis nous allons effectivement
regarder le code pour elle.

258
00:14:14,980 --> 00:14:16,780
Alors, imaginez que je dois ce grand arbre.

259
00:14:16,780 --> 00:14:18,280
Et maintenant, je ne joue pas de tic-tac-toe.

260
00:14:18,280 --> 00:14:20,405
Je voulais vous donner
quelque chose d'un peu plus riche.

261
00:14:20,405 --> 00:14:23,560
Donc, je dois un jeu où
il ya beaucoup de différents scores

262
00:14:23,560 --> 00:14:26,390
que je pouvais avoir à la fin.

263
00:14:26,390 --> 00:14:27,980
Et si je construis cet arbre complet.

264
00:14:27,980 --> 00:14:29,070
Et je reçois de se déplacer en premier.

265
00:14:29,070 --> 00:14:31,290
Je suis à la racine de l'arbre.

266
00:14:31,290 --> 00:14:36,150
>> Et je peux choisir that-- si je reçois
de maximiser à travers ce premier noeud.

267
00:14:36,150 --> 00:14:38,410
Et puis mon adversaire arrive à aller.

268
00:14:38,410 --> 00:14:41,910
Et puis je reçois d'aller une fois de plus.

269
00:14:41,910 --> 00:14:46,830
Donc, au bas, je dois un ensemble de
possibilités que je peux choisir,

270
00:14:46,830 --> 00:14:50,570
différents états terminaux du jeu.

271
00:14:50,570 --> 00:14:54,980
Si je suis dans ce que
extrême gauche coin,

272
00:14:54,980 --> 00:14:58,867
et je vois que je dois un choix
entre un huit, sept, et un deux,

273
00:14:58,867 --> 00:15:00,450
bien, je suis celui qui obtient de choisir.

274
00:15:00,450 --> 00:15:02,910
Donc, je vais choisir
le meilleur l'un de ceux.

275
00:15:02,910 --> 00:15:05,650
Je vais choisir le huit.

276
00:15:05,650 --> 00:15:10,090
>> Donc, je sais que si jamais je
descendre à ce point,

277
00:15:10,090 --> 00:15:13,890
Je serai en mesure d'obtenir que les huit points.

278
00:15:13,890 --> 00:15:17,410
Si je me retrouve au point suivant
plus, le noeud suivant sur,

279
00:15:17,410 --> 00:15:20,760
neuf, un, ou d'un six, bien, je suis
va choisir le meilleur d'entre eux.

280
00:15:20,760 --> 00:15:21,950
Je vais choisir le neuf.

281
00:15:21,950 --> 00:15:24,880
Si je dois choisir entre
deux, quatre, et un,

282
00:15:24,880 --> 00:15:28,240
Je vais choisir le quatre, le plus haut.

283
00:15:28,240 --> 00:15:31,990
>> Maintenant, si je regarde le niveau
ci-dessus que, mon adversaire

284
00:15:31,990 --> 00:15:34,440
est l'un arrive à faire ce choix.

285
00:15:34,440 --> 00:15:37,040
Donc, mon adversaire arrive à
choisis, ce que je veux lui donner

286
00:15:37,040 --> 00:15:39,250
la chose qui se passe
de lui faire huit points,

287
00:15:39,250 --> 00:15:41,916
ou dois-je lui donne la chose qui est
vais lui donner neuf points,

288
00:15:41,916 --> 00:15:45,240
ou de la chose qui va
de lui donner quatre points?

289
00:15:45,240 --> 00:15:49,130
Et mon adversaire, étant
rationnelle, va

290
00:15:49,130 --> 00:15:53,470
de choisir le minimum de personnes,
va choisir quatre.

291
00:15:53,470 --> 00:15:56,020
>> Et je peux le faire
à travers l'ensemble de l'arbre.

292
00:15:56,020 --> 00:15:59,110
Je peux descendre à ce que
ensemble du milieu de trois.

293
00:15:59,110 --> 00:16:01,517
Et je peux choisir entre
un, trois et cinq.

294
00:16:01,517 --> 00:16:02,350
Et je peux choisir.

295
00:16:02,350 --> 00:16:03,810
Je choisis donc cinq.

296
00:16:03,810 --> 00:16:05,340
Je peux choisir trois, neuf ou deux.

297
00:16:05,340 --> 00:16:07,570
Je peux choisir, je choisis donc neuf.

298
00:16:07,570 --> 00:16:09,290
Six, cinq, ou deux, je choisis.

299
00:16:09,290 --> 00:16:11,539
Je peux choisir les six.

300
00:16:11,539 --> 00:16:13,080
Niveau supérieur à celui qui reprend de choisir?

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

302
00:16:16,280 --> 00:16:18,140
Qui va choisir?

303
00:16:18,140 --> 00:16:20,000
L'autre gars, mon adversaire.

304
00:16:20,000 --> 00:16:22,583
Alors, ils choisissent cinq,
neuf ans, ou six, lequel?

305
00:16:22,583 --> 00:16:23,410
>> AUDIENCE: Le cinq.

306
00:16:23,410 --> 00:16:25,250
>> CONFÉRENCIER: ils choisissent les cinq.

307
00:16:25,250 --> 00:16:27,400
Ils apprennent à choisir le minimum.

308
00:16:27,400 --> 00:16:29,690
Et puis le dernier,
choisir un, deux, ou trois.

309
00:16:29,690 --> 00:16:31,720
Je peux choisir, si je choisis trois.

310
00:16:31,720 --> 00:16:34,370
Neuf, sept, ou deux, je choisis de neuf.

311
00:16:34,370 --> 00:16:37,070
Et 11, six, ou quatre, je choisis 11.

312
00:16:37,070 --> 00:16:41,190
Mon adversaire choisit alors trois,
neuf ans, ou 11, choisit le minimum.

313
00:16:41,190 --> 00:16:43,290
Il me donne trois.

314
00:16:43,290 --> 00:16:47,780
Et puis enfin au sommet de
l'arbre, je reçois de choisir à nouveau.

315
00:16:47,780 --> 00:16:51,190
Et je peux choisir entre
quatre, cinq, ou trois.

316
00:16:51,190 --> 00:16:52,270
Donc, je prends les cinq.

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

318
00:16:55,070 --> 00:17:00,891
>> Si je suis de tout contrôler, je ferais
prendre le chemin qui conduit à la 11.

319
00:17:00,891 --> 00:17:02,390
Mais je ne reçois pas de faire ce choix.

320
00:17:02,390 --> 00:17:04,220
Si je vais dans cette voie.

321
00:17:04,220 --> 00:17:10,710
Mon adversaire va me forcer à
le choix qui mène à un trois.

322
00:17:10,710 --> 00:17:14,530
Donc, le meilleur que je peux faire est
de prendre cette branche médiane,

323
00:17:14,530 --> 00:17:19,859
faire ce choix qui est finalement
va me conduire à cinq points.

324
00:17:19,859 --> 00:17:23,230
Voilà ce que fait minimax.

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

326
00:17:23,807 --> 00:17:24,890
Jetons un coup d'oeil.

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

328
00:17:27,480 --> 00:17:32,330
Donc, ici, dans le CS50
IDE est un programme qui

329
00:17:32,330 --> 00:17:36,540
met en œuvre Minimax à jouer tic-tac-toe.

330
00:17:36,540 --> 00:17:40,100
Nous allons construire
une représentation.

331
00:17:40,100 --> 00:17:44,390
Nous allons avoir deux opponent--
ou deux joueurs, notre ordinateur

332
00:17:44,390 --> 00:17:46,090
joueur et un joueur humain.

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

334
00:17:48,980 --> 00:17:53,090
Numéro du joueur un joueront
O. Ce sera le joueur de machine.

335
00:17:53,090 --> 00:17:55,747
Ils apprennent à se déplacer seconde.

336
00:17:55,747 --> 00:17:57,830
Et l'autre joueur, notre
joueur humain, sera X.

337
00:17:57,830 --> 00:17:59,880
>> Et de faire de ma vie un
peu simple, je vais

338
00:17:59,880 --> 00:18:03,060
pour marquer que l'un des joueurs négative.

339
00:18:03,060 --> 00:18:05,026
Donc, je ne peux multiplier
par une négatif à échanger

340
00:18:05,026 --> 00:18:06,400
entre une et l'autre joueur.

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

342
00:18:09,030 --> 00:18:12,250
Très bien, nous allons donc jeter un oeil à
ce que nous allons réellement faire.

343
00:18:12,250 --> 00:18:15,840
Nous allons définir notre conseil d'administration.

344
00:18:15,840 --> 00:18:19,060
Il va y avoir, eh bien, nous allons
à lui permettre d'être trois par trois,

345
00:18:19,060 --> 00:18:21,580
ou nous pouvons même jouer
cinq par cinq ou sept

346
00:18:21,580 --> 00:18:28,870
par sept tic-tac-toe Si vous souhaitez
comme, basée sur une dimension D.

347
00:18:28,870 --> 00:18:31,260
>> Et nous avons un couple
de fonctions auxiliaires

348
00:18:31,260 --> 00:18:34,360
ça va faire des choses comme
initialiser le screen-- ou désolé,

349
00:18:34,360 --> 00:18:38,900
initialiser nos variables, décochez la
écran, dessiner la carte sur l'écran,

350
00:18:38,900 --> 00:18:41,060
celui qui vérifie un conseil
pour voir si oui ou non

351
00:18:41,060 --> 00:18:44,520
il ya un gagnant, celui qui
parse grâce à la ligne de commande,

352
00:18:44,520 --> 00:18:50,670
juste pour aider, celui qui lit dans
entrée, et une fonction appelée minimax.

353
00:18:50,670 --> 00:18:52,746
Et qui est celui
nous intéressent le plus.

354
00:18:52,746 --> 00:18:54,120
Mais regardons d'abord à la principale.

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

356
00:18:57,490 --> 00:18:58,510
>> Qu'est-ce qu'on fait?

357
00:18:58,510 --> 00:19:00,570
Eh bien, nous allons
analyser notre ligne de commande,

358
00:19:00,570 --> 00:19:04,300
il suffit de lire et voir ce
dimension bord, nous aimerions avoir.

359
00:19:04,300 --> 00:19:07,330
Nous allons initialiser notre conseil d'administration.

360
00:19:07,330 --> 00:19:10,360
Et puis nous entrerons dans un
grande boucle sauvage, à plusieurs reprises

361
00:19:10,360 --> 00:19:16,630
accepter déplace jusqu'à ce que le jeu est
gagné, ou il n'y a pas de mouvements de gauche.

362
00:19:16,630 --> 00:19:20,560
Chaque fois que nous allons à travers ce
boucle, nous allons effacer l'écran.

363
00:19:20,560 --> 00:19:23,290
Nous allons dessiner la carte sur l'écran.

364
00:19:23,290 --> 00:19:28,750
Et nous sommes délibérément sorte de
abstraire ces loin que les sous-programmes,

365
00:19:28,750 --> 00:19:32,030
de sorte que nous ne devons pas nous inquiéter trop
sur les détails de la façon dont ils se produisent.

366
00:19:32,030 --> 00:19:33,480
>> Vous aurez le code plus tard aujourd'hui.

367
00:19:33,480 --> 00:19:37,970
Et si vous voulez regarder à travers
et découvrez, vous pouvez les voir tous.

368
00:19:37,970 --> 00:19:39,890
Mais nous allons dessiner une carte sur l'écran.

369
00:19:39,890 --> 00:19:43,620
Et puis nous vérifions et
voir, ne nous avons un gagnant?

370
00:19:43,620 --> 00:19:46,290
Quelqu'un a gagné ce jeu?

371
00:19:46,290 --> 00:19:49,260
Si elles ont, nous allons imprimer
un message de victoire.

372
00:19:49,260 --> 00:19:51,680
Et nous allons finir le jeu.

373
00:19:51,680 --> 00:19:54,510
>> Nous allons également vérifier et
voir si il ya un lien.

374
00:19:54,510 --> 00:19:56,620
Il sera facile de voir si il ya un lien.

375
00:19:56,620 --> 00:20:00,700
Cela veut dire que tous les espaces sont remplis,
mais il n'a pas encore été un gagnant.

376
00:20:00,700 --> 00:20:03,580
Nous pouvons déclarer une cravate et être fait.

377
00:20:03,580 --> 00:20:10,530
Alors la vraie meat-- si
il est un joueur de la machine,

378
00:20:10,530 --> 00:20:14,120
nous allons permettre que
joueur de machine à la recherche

379
00:20:14,120 --> 00:20:19,500
grâce à l'aide de cet algorithme de Minimax,
pour trouver le meilleur coup qu'il peut.

380
00:20:19,500 --> 00:20:22,310
Et puis nous allons mettre en place ce mouvement.

381
00:20:22,310 --> 00:20:27,640
>> Sinon, si il est un joueur humain,
nous lisons une certaine entrée de l'humain.

382
00:20:27,640 --> 00:20:30,800
Et puis, que ce soit l'homme
joueur ou le joueur de machine,

383
00:20:30,800 --> 00:20:32,800
nous ferons peu un couple
bits de contrôle d'erreur,

384
00:20:32,800 --> 00:20:36,910
assurez-vous qu'il reste dans les limites
des dimensions réelles du conseil

385
00:20:36,910 --> 00:20:40,040
que nous avons, assurez-
que cet espace est vide,

386
00:20:40,040 --> 00:20:43,570
que de ne mettre la une
pièce déjà là.

387
00:20:43,570 --> 00:20:45,810
Et puis nous venons de mettre
une pièce sur le plateau,

388
00:20:45,810 --> 00:20:51,550
changer le joueur à la couche suivante, et
incrémenter le nombre de mouvements ont passé.

389
00:20:51,550 --> 00:20:54,090
>> Voilà la boucle principale pour
notre jeu de tic-tac-toe.

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

391
00:20:57,000 --> 00:21:02,340
Minimax, alors, est exactement
l'algorithme que nous avant.

392
00:21:02,340 --> 00:21:04,710
Le seul ajustement qui
nous avons fait de sorte que nous

393
00:21:04,710 --> 00:21:07,290
peut jouer plus
conseils dimensions est que nous avons

394
00:21:07,290 --> 00:21:11,070
gardé ce paramètre supplémentaire appelé profondeur.

395
00:21:11,070 --> 00:21:14,870
Et la profondeur dit juste, si je suis
la recherche vers le bas par cet arbre

396
00:21:14,870 --> 00:21:19,022
et je suis tellement loin vers le bas
delà d'un certain niveau de profondeur

397
00:21:19,022 --> 00:21:20,730
que je ne veux tout simplement pas
d'aller plus loin,

398
00:21:20,730 --> 00:21:25,630
Je vais arrêter et juste
évaluer le conseil à ce point.

399
00:21:25,630 --> 00:21:27,310
Je vais vérifier et voir si il ya un gagnant.

400
00:21:27,310 --> 00:21:29,240
Si il ya un gagnant, je les retourne.

401
00:21:29,240 --> 00:21:31,720
Sinon, je vais passer par une boucle.

402
00:21:31,720 --> 00:21:34,380
Et je vais le dire, pour l'ensemble de
les emplacements possibles

403
00:21:34,380 --> 00:21:38,080
que je pouvais peut-
prendre comme mon déménagement, je vais

404
00:21:38,080 --> 00:21:43,760
construire un conseil fictif que
comprend mon déménagement de ce conseil,

405
00:21:43,760 --> 00:21:45,960
puis appelle de manière récursive minimax.

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

407
00:21:49,360 --> 00:21:53,900
>> Si elle est mon déménagement, je reçois pour trouver le
celui qui a le plus grand score.

408
00:21:53,900 --> 00:21:58,710
Si il est le déménagement de mon adversaire, nous trouvons
celui qui a obtenu le score minimum.

409
00:21:58,710 --> 00:22:02,240
Et tout le reste est
tenue juste fiche.

410
00:22:02,240 --> 00:22:04,789
Très bien, alors voyons ce terme.

411
00:22:04,789 --> 00:22:06,830
En fait, nous pouvons peut-
obtenir un couple de bénévoles

412
00:22:06,830 --> 00:22:09,930
à venir et de jouer tic-tac-toe.

413
00:22:09,930 --> 00:22:12,780
[Inaudible] l'un, et l'autre
De plus, deux, juste là.

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

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

416
00:22:19,290 --> 00:22:23,650
>> Allons donc de l'avant et
redémarrer cela complètement.

417
00:22:23,650 --> 00:22:24,150
Alors, salut.

418
00:22:24,150 --> 00:22:24,920
>> AUDIENCE: Salut.

419
00:22:24,920 --> 00:22:25,420
>> CONFÉRENCIER: Quel est votre nom?

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

421
00:22:26,086 --> 00:22:26,840
CONFÉRENCIER: Gorav.

422
00:22:26,840 --> 00:22:27,800
>> AUDIENCE: Je suis Layla.

423
00:22:27,800 --> 00:22:29,490
>> CONFÉRENCIER: Et Layla, et Layla, désolé.

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

425
00:22:30,384 --> 00:22:32,050
Gorav, nous allons devoir vous allez d'abord.

426
00:22:32,050 --> 00:22:37,710
Et je vais vous demander d'être un pas
terriblement bon joueur tic-tac-toe.

427
00:22:37,710 --> 00:22:40,130
OK, donc toute la pression est hors de vous.

428
00:22:40,130 --> 00:22:44,660
Voyons, cependant, que notre machine
joueur peut réellement faire quelque chose d'intelligent.

429
00:22:44,660 --> 00:22:45,310
Donc vas-y.

430
00:22:45,310 --> 00:22:49,830
Vous allez taper dans lequel coordonner
vous voulez mettre votre X.

431
00:22:49,830 --> 00:22:55,170
A0, OK, et la machine est allé
immédiatement et de mettre sa marque dans A1.

432
00:22:55,170 --> 00:22:56,640
>> Mettez l'O sur la carte.

433
00:22:56,640 --> 00:22:58,970
Bon, maintenant aller de l'avant.

434
00:22:58,970 --> 00:23:00,193
Où voudrais-tu aller?

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
Notre joueur de machine a pris
le carré du milieu, vous bloqué.

438
00:23:08,430 --> 00:23:10,320
Donc, ce fut un bon,
chose la plus intelligente à faire pour elle.

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

440
00:23:13,430 --> 00:23:14,250
Vous avez bloqué il.

441
00:23:14,250 --> 00:23:15,210
Cela est excellent.

442
00:23:15,210 --> 00:23:16,390
Il tire le corner il.

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

444
00:23:23,890 --> 00:23:30,430
>> Et il va vous forcer à
prendre le dernier espace, B0.

445
00:23:30,430 --> 00:23:32,220
Et le match se termine par un match nul.

446
00:23:32,220 --> 00:23:35,030
Mais il a joué un raisonnable
jeu contre vous, non?

447
00:23:35,030 --> 00:23:36,956
Très bien, merci beaucoup, Gorav.

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

449
00:23:40,860 --> 00:23:44,723
>> Tout droit, Layla, nous allons
le jeu sur vous ici.

450
00:23:44,723 --> 00:23:46,940
>> AUDIENCE: Oh, génial.

451
00:23:46,940 --> 00:23:49,950
>> Président: Nous allons donner
vous quatre par quatre tic-tac-toe.

452
00:23:49,950 --> 00:23:54,760
Maintenant, en quatre par quatre, vous avez à gagner
avec quatre dans une rangée, pas trois dans une rangée.

453
00:23:54,760 --> 00:23:56,135
Et il est tout à toi.

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

455
00:24:02,180 --> 00:24:04,420
Donc, Layla a pris D1.

456
00:24:04,420 --> 00:24:11,730
Nous allons maintenant suivre
notre lecteur de l'ordinateur ici.

457
00:24:11,730 --> 00:24:16,910
Trois par trois tic-tac-toe est le genre
de chose qui est facile pour nous tous.

458
00:24:16,910 --> 00:24:21,960
Mais il est toujours agréable de voir la
lecteur de l'ordinateur faire des mouvements intelligents.

459
00:24:21,960 --> 00:24:23,725
Quatre par quatre arrive à
être un peu plus délicat.

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

461
00:24:42,960 --> 00:24:44,230
>> Bien fait.

462
00:24:44,230 --> 00:24:46,210
Très bien, alors Layla réussit.

463
00:24:46,210 --> 00:24:48,270
Oh, et nous aurions dû se terminer là.

464
00:24:48,270 --> 00:24:51,870
Mais nous allons faire un de plus ici.

465
00:24:51,870 --> 00:24:53,480
Donc, Layla, je vous remercie.

466
00:24:53,480 --> 00:24:55,112
Bien fait.

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

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

469
00:25:00,410 --> 00:25:04,750
>> Donc, notre joueur de tic-tac-toe va
grâce et trouve des emplacements,

470
00:25:04,750 --> 00:25:07,040
résout les utilisant ce minimax.

471
00:25:07,040 --> 00:25:08,990
Et je devais un réglage de la profondeur
sur cette sorte qu'il

472
00:25:08,990 --> 00:25:11,010
ne serait pas courir trop vite,
qui est probablement la raison pour laquelle

473
00:25:11,010 --> 00:25:16,790
Layla était capable d'aller bien à l'avance
comme elle l'a fait, et a très bien fait.

474
00:25:16,790 --> 00:25:20,450
Mais ces systèmes que juste
passer et la force brute

475
00:25:20,450 --> 00:25:23,870
aller plus loin, et plus profond, et plus profond,
et continuer à trouver la solution

476
00:25:23,870 --> 00:25:29,890
dont ils ont besoin, ces types de systèmes
sont tout à fait réussi à ceux-ci, ainsi,

477
00:25:29,890 --> 00:25:32,700
jeux de société classiques.

478
00:25:32,700 --> 00:25:37,060
>> Et en fait, si nous regardons un
trois par trois jeu de tic-tac-toe,

479
00:25:37,060 --> 00:25:40,040
ceci est fondamentalement un problème résolu.

480
00:25:40,040 --> 00:25:45,430
Et cela est un schéma merveilleuse
Randall Munroe à partir XKCD,

481
00:25:45,430 --> 00:25:52,130
montrant quels déplacer, vous devriez
prendre, compte tenu des mouvements de votre adversaire.

482
00:25:52,130 --> 00:25:56,420
Ceci est quelque chose que nous pourrions
facilement spécifier à l'avance.

483
00:25:56,420 --> 00:26:00,180
Mais qu'advient-il que nous aurons plus
jeux complexes, des jeux plus complexes,

484
00:26:00,180 --> 00:26:05,690
où il ya des grandes planches, plus
possibilités, la stratégie de plus profond?

485
00:26:05,690 --> 00:26:09,660
>> Il se trouve que ce
force brute Still Searching

486
00:26:09,660 --> 00:26:14,150
fait assez bien, sauf
lorsque vous arrivez au point

487
00:26:14,150 --> 00:26:19,230
où cet arbre est si grand
que vous ne pouvez pas représenter tout.

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

489
00:26:22,370 --> 00:26:28,280
Lorsque vous ne pouvez pas calculer la totalité de l'arbre,
lorsque vous ne pouvez pas aller de l'avant et pousser

490
00:26:28,280 --> 00:26:32,204
vous au point où vous avez
obtenu la totalité de l'arbre dans la mémoire,

491
00:26:32,204 --> 00:26:34,370
ou si vous pouvez l'obtenir
dans la mémoire et il sera simplement

492
00:26:34,370 --> 00:26:39,200
vous prendre beaucoup trop de temps à la recherche par le biais
elle, vous avez à faire quelque chose plus intelligente.

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

494
00:26:42,620 --> 00:26:46,450
>> Pour ce faire, vous
avoir à faire deux choses.

495
00:26:46,450 --> 00:26:49,030
Tout d'abord, vous devez trouver un certain
manière de limiter la profondeur.

496
00:26:49,030 --> 00:26:50,370
Eh bien, voilà OK.

497
00:26:50,370 --> 00:26:55,740
Nous pouvons trouver une belle, strict minimum
et dire, vous ne pouvez aller si profond.

498
00:26:55,740 --> 00:27:00,890
Mais quand vous faites cela, cela signifie que vous
avoir ces planches partiellement incomplètes.

499
00:27:00,890 --> 00:27:04,770
Et vous avez à choisir, dois-je l'aime
cette planche partiellement incomplète,

500
00:27:04,770 --> 00:27:08,600
ou ce conseil partiellement incomplète?

501
00:27:08,600 --> 00:27:11,910
>> Et sur notre quatre par
quatre matchs de tic-tac-toe,

502
00:27:11,910 --> 00:27:15,240
notre lecteur de l'ordinateur descendit
au fond et il a dit,

503
00:27:15,240 --> 00:27:16,800
Je ai deux cartes différentes.

504
00:27:16,800 --> 00:27:17,940
Ni l'un est une victoire.

505
00:27:17,940 --> 00:27:19,120
Ni l'un est une perte.

506
00:27:19,120 --> 00:27:22,070
Ni l'un est une cravate.

507
00:27:22,070 --> 00:27:24,100
Comment puis-je choisir entre les deux?

508
00:27:24,100 --> 00:27:26,200
Et il n'a pas de
façon intelligente de le faire.

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

510
00:27:28,910 --> 00:27:32,850
>> Nous voyons ce genre de
évaluation arrive tout le temps

511
00:27:32,850 --> 00:27:35,290
que nous entrons dans des jeux plus complexes.

512
00:27:35,290 --> 00:27:37,600
Echecs est un excellent exemple.

513
00:27:37,600 --> 00:27:41,550
Aux échecs, nous avons, d'abord
de tous, une planche plus grande.

514
00:27:41,550 --> 00:27:43,370
Nous avons beaucoup plus de morceaux.

515
00:27:43,370 --> 00:27:47,930
Et le positionnement de ces pièces
et la façon dont ces morceaux déplacer

516
00:27:47,930 --> 00:27:50,370
est d'une importance cruciale.

517
00:27:50,370 --> 00:27:53,700
Donc, si je veux utiliser Minimax,
Je dois être en mesure de préciser

518
00:27:53,700 --> 00:27:58,240
et dire, ce conseil, où
personne n'a encore gagné ou perdu,

519
00:27:58,240 --> 00:28:04,310
est en quelque sorte mieux que cet autre
conseil d'administration, où personne n'a gagné ou perdu.

520
00:28:04,310 --> 00:28:06,740
>> Pour ce faire, je pourrais faire
choses comme je pourrais juste

521
00:28:06,740 --> 00:28:10,787
compter le nombre de pièces que je dois
et combien de pièces avez-vous?

522
00:28:10,787 --> 00:28:12,870
Ou je pourrais donner différente
morceaux différents points.

523
00:28:12,870 --> 00:28:14,420
Ma reine vaut 20 points.

524
00:28:14,420 --> 00:28:16,500
Votre pion vaut un point.

525
00:28:16,500 --> 00:28:18,920
Qui a le plus de points au total?

526
00:28:18,920 --> 00:28:22,300
Ou je pourrais envisager des choses comme,
Qui a le mieux la position du conseil d'administration?

527
00:28:22,300 --> 00:28:26,820
A qui le tour suivant,
tout ce que je peux

528
00:28:26,820 --> 00:28:31,220
ne d'évaluer de façon plus précise
lequel de ces possibilités

529
00:28:31,220 --> 00:28:34,660
est mieux sans
considérant exhaustive

530
00:28:34,660 --> 00:28:36,565
chaque mouvement qui pourrait venir après.

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

532
00:28:39,740 --> 00:28:45,130
>> Maintenant, pour faire ce travail,
l'une des choses qui est

533
00:28:45,130 --> 00:28:48,680
va devenir vraiment important
pour nous est pas seulement déplacent en ligne droite

534
00:28:48,680 --> 00:28:53,720
jusqu'à une profondeur particulière
limite, mais être capable de dire,

535
00:28:53,720 --> 00:28:59,380
une de ces idées que je
ont est si mauvais qu'il est

536
00:28:59,380 --> 00:29:02,280
pas la peine de considérer
tous les moyens possibles

537
00:29:02,280 --> 00:29:06,680
que les choses peuvent aller de mal en pis.

538
00:29:06,680 --> 00:29:12,760
Pour ce faire, nous allons ajouter dans Minimax
un principe appelé alph-bêta.

539
00:29:12,760 --> 00:29:16,340
Et alpha-bêta dit,
si vous avez une mauvaise idée,

540
00:29:16,340 --> 00:29:22,840
ne perdez pas votre temps à essayer de
de savoir exactement à quel point il est.

541
00:29:22,840 --> 00:29:24,990
>> Donc, voici ce que nous allons faire.

542
00:29:24,990 --> 00:29:28,620
Nous allons prendre le même
principes que nous avions avant,

543
00:29:28,620 --> 00:29:32,200
le même type minimax
de la recherche, que nous sommes

544
00:29:32,200 --> 00:29:37,570
va suivre, non seulement de la
valeurs réelles que nous avons, mais nous allons

545
00:29:37,570 --> 00:29:41,440
garder une trace de la meilleure possible
la valeur que je pouvais obtenir,

546
00:29:41,440 --> 00:29:45,700
et le pire possible
résultat que je pouvais avoir.

547
00:29:45,700 --> 00:29:50,470
Et chaque fois que le pire
chose est à la recherche de chances,

548
00:29:50,470 --> 00:29:52,694
Je vais abandonner cette partie de l'arbre.

549
00:29:52,694 --> 00:29:54,610
Et je vais même pas la peine
regardant plus.

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

551
00:29:57,680 --> 00:30:02,600
>> Très bien, alors imaginons que nous commençons
avec ce même arbre de jeu exact.

552
00:30:02,600 --> 00:30:05,200
Et maintenant, nous allons aller
nouveau vers le bas, tout en bas

553
00:30:05,200 --> 00:30:07,200
dans ce coin en bas à gauche.

554
00:30:07,200 --> 00:30:11,180
Et dans ce coin en bas à gauche, nous
regardons et nous évaluons ce conseil.

555
00:30:11,180 --> 00:30:15,700
Peut-être qu'il est un quatre par quatre tic-tac-toe
conseil, ou peut-être qu'il est un échiquier.

556
00:30:15,700 --> 00:30:18,620
Mais nous regardons, et nous évaluons
il, et nous obtenons une valeur de huit ans.

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

558
00:30:22,290 --> 00:30:28,030
>> À ce moment, nous savons que
nous allons obtenir au moins

559
00:30:28,030 --> 00:30:32,380
huit points de cette décision de fond.

560
00:30:32,380 --> 00:30:36,620
Il n'a pas d'importance ce que l'autre
sont deux, sept et que que deux.

561
00:30:36,620 --> 00:30:38,580
Ils pourraient être les valeurs
ils voulaient être.

562
00:30:38,580 --> 00:30:41,279
Nous allons obtenir au
moins huit points.

563
00:30:41,279 --> 00:30:43,070
Très bien, mais nous pourrions
aller de l'avant et vérifier.

564
00:30:43,070 --> 00:30:45,080
Peut-être que l'un d'eux est meilleur que huit.

565
00:30:45,080 --> 00:30:46,000
>> Nous regardons le sept.

566
00:30:46,000 --> 00:30:46,910
Est-ce mieux de huit?

567
00:30:46,910 --> 00:30:48,680
Non, cela ne change pas
notre avis à tous.

568
00:30:48,680 --> 00:30:49,460
Nous regardons les deux.

569
00:30:49,460 --> 00:30:50,543
Est-ce mieux de huit?

570
00:30:50,543 --> 00:30:52,580
Non, cela ne change pas
notre avis à tous.

571
00:30:52,580 --> 00:30:55,480
Alors maintenant, nous savons que nous avons épuisé
toutes les possibilités là-bas.

572
00:30:55,480 --> 00:30:58,330
On ne va pas pour obtenir
rien de mieux que de huit.

573
00:30:58,330 --> 00:31:01,310
Nous allons obtenir exactement huit.

574
00:31:01,310 --> 00:31:03,825
>> Et si nous changeons ce nœud et
par exemple, qui est maintenant une certitude.

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

576
00:31:07,010 --> 00:31:10,270
Nous montons d'un niveau au-dessus.

577
00:31:10,270 --> 00:31:13,820
Et maintenant, nous savons quelque chose
à propos de ce niveau de minimisation.

578
00:31:13,820 --> 00:31:18,560
Nous savons que nous ne pourrons jamais obtenir
plus de huit points si nous descendons

579
00:31:18,560 --> 00:31:20,910
cette direction.

580
00:31:20,910 --> 00:31:22,980
Parce que même si ceux-
deux autres branches se révèlent

581
00:31:22,980 --> 00:31:26,170
être fantastique et de la valeur
des milliers de points chacun,

582
00:31:26,170 --> 00:31:31,666
notre adversaire va nous donner la
minimum, et nous donner les huit.

583
00:31:31,666 --> 00:31:32,790
Tout droit, eh bien, nous allons voir.

584
00:31:32,790 --> 00:31:35,190
Nous allons continuer dans cette voie.

585
00:31:35,190 --> 00:31:38,490
Nous descendons à celle du milieu sur le côté gauche.

586
00:31:38,490 --> 00:31:40,560
Nous regardons vers le bas et nous voyons qu'il ya un neuf.

587
00:31:40,560 --> 00:31:45,590
Nous savons que nous allons obtenir
au moins neuf points en descendant

588
00:31:45,590 --> 00:31:47,720
cette route milieu.

589
00:31:47,720 --> 00:31:52,110
Et à ce stade, nous ne pouvons mettre en pause.

590
00:31:52,110 --> 00:31:56,910
Et nous pouvons dire, regardez, je
savoir dans le niveau au-dessus,

591
00:31:56,910 --> 00:32:01,160
Je vais chercher pas plus de huit
Points by aller dans cette direction.

592
00:32:01,160 --> 00:32:05,670
Mais si je suis descendu au milieu
chemin au lieu de la voie de gauche,

593
00:32:05,670 --> 00:32:08,980
Je voudrais obtenir au moins neuf points.

594
00:32:08,980 --> 00:32:13,590
>> Mon adversaire ne va jamais
laissez-moi aller dans cette voie du milieu.

595
00:32:13,590 --> 00:32:14,650
Ils obtiennent de choisir.

596
00:32:14,650 --> 00:32:18,140
Et ils vont choisir le
chemin à gauche vers le huit,

597
00:32:18,140 --> 00:32:23,650
plutôt que sur le milieu vers
ce qui est au moins neuf points.

598
00:32:23,650 --> 00:32:25,334
Donc, à ce moment-là, je vais arrêter.

599
00:32:25,334 --> 00:32:26,500
Et je vais le dire, vous savez quoi?

600
00:32:26,500 --> 00:32:29,990
Je ne dois regarder tout
plus bas dans cette direction.

601
00:32:29,990 --> 00:32:32,270
Parce que je ne vais jamais y arriver.

602
00:32:32,270 --> 00:32:36,660
>> Je peux sauter celui-là,
et je peux sauter que six,

603
00:32:36,660 --> 00:32:39,720
parce que cela ne se fera jamais.

604
00:32:39,720 --> 00:32:42,470
Donc, je vais descendre, et je vais
envisager la possibilité suivante.

605
00:32:42,470 --> 00:32:44,830
Je vais là-bas, et je le dis, je vois deux.

606
00:32:44,830 --> 00:32:47,125
Je sais que si je reçois ici, je suis
allez obtenir au moins deux.

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

608
00:32:49,810 --> 00:32:50,470
D'ACCORD.

609
00:32:50,470 --> 00:32:51,520
Je continue.

610
00:32:51,520 --> 00:32:52,440
Je vois quatre.

611
00:32:52,440 --> 00:32:54,920
Je sais que je vais avoir au moins quatre.

612
00:32:54,920 --> 00:32:57,200
Il ya encore beaucoup entre
quatre et huit, cependant.

613
00:32:57,200 --> 00:32:58,454
Donc je continue.

614
00:32:58,454 --> 00:32:59,870
Je regarde et je vois qu'il ya un.

615
00:32:59,870 --> 00:33:01,614
Très bien, je sais que si
Je vais dans cette voie,

616
00:33:01,614 --> 00:33:03,280
Je vais être en mesure de choisir les quatre.

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

618
00:33:06,540 --> 00:33:08,980
Qu'est-ce que mon adversaire va faire?

619
00:33:08,980 --> 00:33:12,310
Entre quelque chose qui me donne
huit, quelque chose qui me donne quatre,

620
00:33:12,310 --> 00:33:14,730
et quelque chose que
me donne au moins neuf,

621
00:33:14,730 --> 00:33:17,550
Eh bien, il va me donner quatre.

622
00:33:17,550 --> 00:33:20,110
Et je sais maintenant à la
très haut, je vais

623
00:33:20,110 --> 00:33:23,145
pour être en mesure d'obtenir au moins
quatre points sur ce jeu.

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

625
00:33:27,030 --> 00:33:30,900
>> L'idée de l'alpha-bêta
est de couper les parties de l'arbre de sorte

626
00:33:30,900 --> 00:33:32,530
que je ne regarde plus à eux.

627
00:33:32,530 --> 00:33:35,964
Mais il semble encore comme je l'ai été
en regardant beaucoup de l'arbre.

628
00:33:35,964 --> 00:33:36,880
Gardons descendre.

629
00:33:36,880 --> 00:33:38,305
Nous descendons la prochaine maintenant.

630
00:33:38,305 --> 00:33:39,680
Tout en bas, je trouve un.

631
00:33:39,680 --> 00:33:41,030
Je sais que je vais avoir au moins un.

632
00:33:41,030 --> 00:33:41,690
Je continue la recherche.

633
00:33:41,690 --> 00:33:42,625
>> Je trouve trois.

634
00:33:42,625 --> 00:33:44,250
Je sais que je vais avoir au moins trois.

635
00:33:44,250 --> 00:33:44,840
Je continue.

636
00:33:44,840 --> 00:33:45,660
Je trouve cinq.

637
00:33:45,660 --> 00:33:49,760
Je sais que je vais obtenir cinq
si je descends dans cette voie.

638
00:33:49,760 --> 00:33:52,580
Et je sais aussi alors
que mon adversaire, si je

639
00:33:52,580 --> 00:33:55,510
choisir le milieu de
les trois grands choix,

640
00:33:55,510 --> 00:34:01,440
il va me donner
quelque chose qui est de cinq ou moins.

641
00:34:01,440 --> 00:34:02,150
>> D'ACCORD.

642
00:34:02,150 --> 00:34:03,400
Je peux continuer à aller là-bas.

643
00:34:03,400 --> 00:34:06,470
Je peux regarder en bas et je
peut dire, que vais-je

644
00:34:06,470 --> 00:34:08,239
à obtenir si je descends la voie du milieu?

645
00:34:08,239 --> 00:34:09,909
Je vais à obtenir, ainsi, trois là.

646
00:34:09,909 --> 00:34:12,080
Je vais obtenir quelque chose
qui est au moins trois.

647
00:34:12,080 --> 00:34:16,030
Il ya encore des choses entre
trois et cinq, donc je continuer à chercher.

648
00:34:16,030 --> 00:34:20,203
Oh, neuf, Je vais certainement
prendre que sur trois.

649
00:34:20,203 --> 00:34:22,744
Je vais d'obtenir au moins neuf
si je vais dans cette voie du milieu.

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

651
00:34:25,530 --> 00:34:31,010
>> Maintenant, mon adversaire arrête et dit,
Regardez, il n'y a aucun point plus.

652
00:34:31,010 --> 00:34:33,669
Je sais que mon
minimisation adversaire, il est

653
00:34:33,669 --> 00:34:36,210
va me donner la chose qui est
inférieur ou égal à cinq,

654
00:34:36,210 --> 00:34:39,030
plutôt que la chose qui est
supérieure ou égale à neuf.

655
00:34:39,030 --> 00:34:39,530
J'arrête.

656
00:34:39,530 --> 00:34:40,779
Je ne regarde pas plus à cela.

657
00:34:40,779 --> 00:34:43,280
Je continue.

658
00:34:43,280 --> 00:34:44,850
>> Je regarde en bas sur celui-ci.

659
00:34:44,850 --> 00:34:46,370
Vers le bas, je trouve un six.

660
00:34:46,370 --> 00:34:50,040
Je sais que je vais avoir au moins six.

661
00:34:50,040 --> 00:34:53,130
Et qu'est-ce que je peux faire?

662
00:34:53,130 --> 00:34:54,877
Je peux arrêter.

663
00:34:54,877 --> 00:34:57,460
Parce qu'il ya un choix entre
quelque chose qui est au moins six

664
00:34:57,460 --> 00:34:59,250
et quelque chose qui est
moins de cinq ans, il est

665
00:34:59,250 --> 00:35:02,570
va me donner la chose
qui est inférieur à cinq.

666
00:35:02,570 --> 00:35:04,779
Et maintenant, je sais que je vais
pour obtenir exactement ce choix.

667
00:35:04,779 --> 00:35:06,195
Je vais obtenir que cinq choix.

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

669
00:35:08,980 --> 00:35:10,010
>> Je remonte vers le haut.

670
00:35:10,010 --> 00:35:11,450
Qui vais-je
choisir entre quelque chose

671
00:35:11,450 --> 00:35:14,449
qui est supérieur ou égal à quatre,
ou quelque chose qui est égal à cinq?

672
00:35:14,449 --> 00:35:17,140
Je vais prendre quelque chose
qui est au moins cinq ans.

673
00:35:17,140 --> 00:35:20,490
Je descends le dernier chemin, tout
le chemin vers le bas.

674
00:35:20,490 --> 00:35:21,260
Il ya un.

675
00:35:21,260 --> 00:35:23,410
OK, au moins, je vais me faire un point.

676
00:35:23,410 --> 00:35:24,427
Je continue.

677
00:35:24,427 --> 00:35:25,760
Deux, oh, qui est mieux qu'une.

678
00:35:25,760 --> 00:35:27,100
Je vais d'obtenir au moins deux.

679
00:35:27,100 --> 00:35:28,610
Je trouve trois.

680
00:35:28,610 --> 00:35:31,450
Je sais que je vais obtenir trois.

681
00:35:31,450 --> 00:35:34,690
>> Et le point ci-dessus que,
mon adversaire va

682
00:35:34,690 --> 00:35:38,540
de me donner quelque chose qui est
inférieur ou égal à trois.

683
00:35:38,540 --> 00:35:40,940
Et maintenant, je peux arrêter.

684
00:35:40,940 --> 00:35:46,290
Parce que dans le choix entre moi étant
mesure d'obtenir un de cinq ans et mon adversaire

685
00:35:46,290 --> 00:35:52,290
me donner quelque chose de moins de trois,
Je vais toujours à prendre que cinq.

686
00:35:52,290 --> 00:35:56,810
Donc, je ne évaluent pas que
partie inférieure de l'arbre du tout.

687
00:35:56,810 --> 00:35:59,470
>> Maintenant, cela peut sembler mineur.

688
00:35:59,470 --> 00:36:03,630
Mais quand des petits morceaux de l'arithmétique,
supérieure et inférieure,

689
00:36:03,630 --> 00:36:10,640
peut couper des parties entières de
cet arbre croît de façon exponentielle,

690
00:36:10,640 --> 00:36:14,280
qui mène à un énorme
Montant des économies, économies

691
00:36:14,280 --> 00:36:17,630
qui sont assez grand pour que je
peut commencer à jouer en compétition

692
00:36:17,630 --> 00:36:21,330
à des jeux plus complexes.

693
00:36:21,330 --> 00:36:27,030
>> Très bien, si nous regardons la taille
et la complexité des différents jeux,

694
00:36:27,030 --> 00:36:29,470
tic-tac-toe était notre exemple simple.

695
00:36:29,470 --> 00:36:32,150
Nous avons un petit conseil, trois par trois.

696
00:36:32,150 --> 00:36:36,030
Nous obtenons, tout au plus, une moyenne de
environ quatre choix différents

697
00:36:36,030 --> 00:36:38,440
que nous avançons dans le jeu.

698
00:36:38,440 --> 00:36:42,720
Nous avons quelque part autour de 10 à la
cinquième possibles différentes feuilles.

699
00:36:42,720 --> 00:36:45,200
Et la construction d'un tic tac-toe
joueur, eh bien, nous avons juste fait.

700
00:36:45,200 --> 00:36:47,460
C'est facile.

701
00:36:47,460 --> 00:36:49,890
>> Si nous montons à quelque chose de plus
complexe, comme Connect Four.

702
00:36:49,890 --> 00:36:53,170
Vous rappelez-vous ce jeu où
vous déposez les petits jetons en?

703
00:36:53,170 --> 00:36:58,490
Il est un conseil de six à sept heures,
pas beaucoup plus grand, encore

704
00:36:58,490 --> 00:37:00,770
a environ la même ramification
FACTOR tic-tac-toe.

705
00:37:00,770 --> 00:37:05,410
Je dois environ quatre choix
où je peux mettre les choses en.

706
00:37:05,410 --> 00:37:10,760
Mais maintenant, je dois beaucoup plus
conduit, 10 au 21 courant.

707
00:37:10,760 --> 00:37:14,440
Voilà quelque chose qui est facile
assez que nous résolvons tout de suite.

708
00:37:14,440 --> 00:37:17,560
>> Checkers, plus vous complex--
obtenu huit par huit bord.

709
00:37:17,560 --> 00:37:20,570
Vous êtes seulement sur la moitié de
à tout moment, si.

710
00:37:20,570 --> 00:37:24,930
Vous avez une ramification
facteur qui est d'environ 2,8.

711
00:37:24,930 --> 00:37:28,160
Eh bien, nous avons un couple
se déplace, vous pouvez prendre.

712
00:37:28,160 --> 00:37:33,870
Vous avez environ 10 à feuilles 31e,
des espaces plus grands et plus grands, et plus.

713
00:37:33,870 --> 00:37:37,340
Comme je l'ai grâce à la recherche
ces espaces plus en plus,

714
00:37:37,340 --> 00:37:42,220
qui est quand les choses comme alpha-bêta et
être capable de couper des branches entières

715
00:37:42,220 --> 00:37:44,420
devient essentiel.

716
00:37:44,420 --> 00:37:47,440
>> Maintenant, dames était assez facile en 1992.

717
00:37:47,440 --> 00:37:51,400
Un programme informatique appelé
Chinook a battu les dames du monde

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

719
00:37:53,590 --> 00:37:57,260
Et depuis lors, aucune
lecteur maître humain a

720
00:37:57,260 --> 00:38:02,290
été en mesure de battre le meilleur
systèmes informatiques.

721
00:38:02,290 --> 00:38:06,570
Si nous regardons quelque chose comme les échecs, maintenant
encore une fois, nous avons huit par huit bord.

722
00:38:06,570 --> 00:38:09,870
Mais nous avons beaucoup plus complexe
pièces, une grande partie des mouvements plus complexes.

723
00:38:09,870 --> 00:38:14,610
Nous avons un facteur de branchement d'environ
35, 35 coups possibles en moyenne

724
00:38:14,610 --> 00:38:20,030
que je peux prendre, et un état
l'espace, un certain nombre de feuilles

725
00:38:20,030 --> 00:38:28,950
qui a grandi à 10 à la puissance 123e,
un nombre énorme de possibilités.

726
00:38:28,950 --> 00:38:35,570
>> Même encore, les processeurs modernes
sont en mesure de le faire avec succès.

727
00:38:35,570 --> 00:38:43,900
En 1995 puis en 1997, un ordinateur
programme appelé Deep Blue construit par IBM

728
00:38:43,900 --> 00:38:49,601
qui a eu lieu sur un supercalculateur géant
battre le champion du monde actuel,

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
Ce fut un point tournant.

732
00:38:56,650 --> 00:39:00,620
Aujourd'hui, cependant, que même traitement
le pouvoir est assis sur mon MacBook.

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

734
00:39:04,180 --> 00:39:06,440
>> La vitesse de traitement continue
plus en plus vite.

735
00:39:06,440 --> 00:39:09,500
Nous pouvons évaluer plus en plus
conseils rapides et plus rapide.

736
00:39:09,500 --> 00:39:14,550
Mais plus important encore, nous avons mieux
fonctions d'évaluation et de mieux l'élagage

737
00:39:14,550 --> 00:39:15,460
méthodes.

738
00:39:15,460 --> 00:39:19,560
Donc, nous pouvons rechercher la
l'espace de manière plus complexe.

739
00:39:19,560 --> 00:39:22,350
Le plus gros de la carte
jeux que nous pouvons penser,

740
00:39:22,350 --> 00:39:26,310
quelque chose comme Go qui est
obtenu un conseil de 19 à 19 ans,

741
00:39:26,310 --> 00:39:32,490
tout à coup, nous avons dépassé le point
où les systèmes informatiques peuvent gagner.

742
00:39:32,490 --> 00:39:34,530
Il n'y a pas de calcul
système là-bas

743
00:39:34,530 --> 00:39:38,880
qui peut battre un joueur professionnel Go.

744
00:39:38,880 --> 00:39:45,000
Les meilleurs systèmes aujourd'hui rang qu'elle propos
le genre de bon niveau amateur.

745
00:39:45,000 --> 00:39:49,285
Donc, il ya encore un peu out
là que vous ne pouvez pas encore.

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

747
00:39:51,840 --> 00:39:55,360
>> Tous les droits, ceux-ci
jeux de société traditionnels,

748
00:39:55,360 --> 00:39:58,560
ces types de systèmes où nous
construire ce Minimax, si elle a obtenu

749
00:39:58,560 --> 00:40:06,300
alpha-bêta ou non, ces algorithmes fonctionnent
parce qu'il ya certaines contraintes.

750
00:40:06,300 --> 00:40:08,520
Nous avons des informations parfaite
sur le monde.

751
00:40:08,520 --> 00:40:11,690
Nous savons où toutes les pièces sont.

752
00:40:11,690 --> 00:40:13,570
Le monde est statique.

753
00:40:13,570 --> 00:40:16,220
Personne ne reçoit de déplacer le
pièces autour pendant que je suis

754
00:40:16,220 --> 00:40:20,640
assis là à penser, en prenant à mon tour.

755
00:40:20,640 --> 00:40:23,140
Il ya un espace d'action qui est discrète.

756
00:40:23,140 --> 00:40:26,900
Je peux mettre mon pion ici,
ou je peux mettre mon pion ici.

757
00:40:26,900 --> 00:40:30,520
Je ne suis pas autorisé à mettre mon pion sur
la ligne entre les deux places.

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

759
00:40:34,430 --> 00:40:36,520
>> Et enfin, les actions
sont déterministes.

760
00:40:36,520 --> 00:40:39,790
Je sais que si je dis,
tour de chevalier de trois,

761
00:40:39,790 --> 00:40:44,660
mon tour va finir au chevalier
trois, tant qu'il est un mouvement valide.

762
00:40:44,660 --> 00:40:47,830
Il n'y a pas d'incertitude à ce sujet.

763
00:40:47,830 --> 00:40:52,490
Maintenant, comme je vais au plus
différents types de jeux,

764
00:40:52,490 --> 00:40:55,960
nous devons briser ces hypothèses.

765
00:40:55,960 --> 00:41:00,020
>> Qu'est-ce que si je vais à quelque chose
comme les jeux vidéo classiques?

766
00:41:00,020 --> 00:41:04,180
Voici une sélection de vidéo
jeux de l'Atari 2600.

767
00:41:04,180 --> 00:41:05,180
Que dois-je là?

768
00:41:05,180 --> 00:41:08,440
Je dois Frogger, Espace
Invaders, Pitfall, et Pac-Man.

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

770
00:41:11,290 --> 00:41:14,840
Quels types d'environnements
dois-je ici?

771
00:41:14,840 --> 00:41:16,900
Laquelle de ces hypothèses
dois-je briser?

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

773
00:41:19,410 --> 00:41:21,570
>> Eh bien, cela dépend de la partie.

774
00:41:21,570 --> 00:41:28,170
Je pourrais jouer aux échecs sur la 2600, et
il serait juste comme il était avant.

775
00:41:28,170 --> 00:41:33,020
Pour la plupart de ces systèmes, il y a
une connaissance complète sur le monde.

776
00:41:33,020 --> 00:41:36,300
Il est tout à fait
actions déterministes.

777
00:41:36,300 --> 00:41:38,330
Mais généralement, le monde de
plus statique.

778
00:41:38,330 --> 00:41:41,970
Autrement dit, alors que je suis assis là
attente, quelque chose bouge.

779
00:41:41,970 --> 00:41:44,320
Les fantômes viennent me chercher.

780
00:41:44,320 --> 00:41:46,570
Le scorpion me suit dessous.

781
00:41:46,570 --> 00:41:48,880
Les envahisseurs de l'espace sont
se rapprocher de plus en plus.

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

783
00:41:54,020 --> 00:41:55,510
Comment bien pouvons-nous faire contre cela?

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

785
00:41:58,640 --> 00:42:02,790
>> Il ya quelques années, Google
avait un projet appelé

786
00:42:02,790 --> 00:42:12,030
Deepmind, où ils ont formé un ordinateur
programme de jouer Atari 2600 jeux.

787
00:42:12,030 --> 00:42:16,120
Et si vous pensez que cela est pas sérieux
affaires, les résultats de leur étude

788
00:42:16,120 --> 00:42:19,920
ont été publiés dans la revue Nature, de sorte
à peu près aussi bonne une publication

789
00:42:19,920 --> 00:42:22,500
que vous pouvez éventuellement obtenir.

790
00:42:22,500 --> 00:42:24,340
Et voici comment ils ont joué.

791
00:42:24,340 --> 00:42:29,220
>> Ils ont un algorithme qui était assis
et regardé seulement les entrées de l'écran.

792
00:42:29,220 --> 00:42:34,080
Il a obtenu aucune instruction que ce soit
sur les règles du jeu.

793
00:42:34,080 --> 00:42:42,610
Et il était censé comprendre,
basé son score, comment il faisait.

794
00:42:42,610 --> 00:42:46,560
Ce fut un système qui utilise quelque chose
appelé apprentissage par renforcement.

795
00:42:46,560 --> 00:42:48,380
Qui est, il regarda son score.

796
00:42:48,380 --> 00:42:51,620
Et si elle a obtenu un bon score, il a dit,
Je me souviens de ces choses.

797
00:42:51,620 --> 00:42:53,310
Et je dois faire ceux nouveau.

798
00:42:53,310 --> 00:42:56,450
Et si elle a obtenu une mauvaise note, il dit,
Je ne devrais pas faire ces choses à nouveau.

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

800
00:42:59,750 --> 00:43:03,430
>> Ceci est la performance
de ces systèmes formés

801
00:43:03,430 --> 00:43:07,490
autorisé à jouer pour une
quelques heures sur chaque jeu,

802
00:43:07,490 --> 00:43:12,490
comparés aux joueurs professionnels.

803
00:43:12,490 --> 00:43:19,670
Donc, pour tous les jeux qui sont
sur le côté gauche de cette ligne,

804
00:43:19,670 --> 00:43:25,920
ce programme informatique autodidacte
surperformé les joueurs professionnels.

805
00:43:25,920 --> 00:43:29,690
Et pour que tout le
droite, les joueurs professionnels

806
00:43:29,690 --> 00:43:30,920
étaient toujours le meilleur.

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

808
00:43:34,040 --> 00:43:36,850
Pour quelque chose qui savait
rien sur les règles, que

809
00:43:36,850 --> 00:43:43,020
rien sur la structure du savait
jeux, ceci est impressionnante performance.

810
00:43:43,020 --> 00:43:45,660
Et voilà ce que nous sommes en mesure de faire aujourd'hui.

811
00:43:45,660 --> 00:43:50,239
>> OK, vous dites, mais si nous
penser AI dans les jeux,

812
00:43:50,239 --> 00:43:52,530
normalement nous pensons à la
les choses que nous pouvons réellement

813
00:43:52,530 --> 00:43:54,180
asseoir et jouer contre.

814
00:43:54,180 --> 00:43:58,760
Si je asseoir et je joue
StarCraft, ou je joue Sieve gratuit,

815
00:43:58,760 --> 00:44:01,870
l'adversaire d'ordinateur est le
personne contrôlant les Zergs,

816
00:44:01,870 --> 00:44:06,770
ou autre commande de la civilisation.

817
00:44:06,770 --> 00:44:11,920
Comment font ces joueurs
effectivement trouver leurs mouvements?

818
00:44:11,920 --> 00:44:18,810
>> Eh bien, ces jeux sont structurés
de la même façon que nos jeux de société,

819
00:44:18,810 --> 00:44:22,250
ces jeux que nous allons
appeler collectivement quatre jeux X,

820
00:44:22,250 --> 00:44:26,040
explorer, expand-- oublier les petits.

821
00:44:26,040 --> 00:44:26,980
Que sont-ils?

822
00:44:26,980 --> 00:44:32,150
Explorez, développez, et d'éteindre,
Je pense est le dernier.

823
00:44:32,150 --> 00:44:36,060
Mais ils sont essentiellement
exploration et de conquête de jeux.

824
00:44:36,060 --> 00:44:41,020
Typiquement, l'adversaire d'ordinateur
il a peu d'informations.

825
00:44:41,020 --> 00:44:45,486
Ils ne savent pas exactement ce qui est
passe derrière ce brouillard de la guerre.

826
00:44:45,486 --> 00:44:47,735
Ils ne reçoivent pas de voir ce
vous avez dans votre inventaire.

827
00:44:47,735 --> 00:44:50,240

828
00:44:50,240 --> 00:44:52,800
>> Il ya un environnement qui est dynamique.

829
00:44:52,800 --> 00:44:56,180
Tout change tout le temps.

830
00:44:56,180 --> 00:45:00,290
Vous ne recevez pas de s'asseoir et
attendre pour prendre votre déménagement.

831
00:45:00,290 --> 00:45:02,810
Mais la plupart des choses sont encore discrète.

832
00:45:02,810 --> 00:45:04,200
Je dois mettre ma ville ici.

833
00:45:04,200 --> 00:45:06,750
Ou je dois mettre ma ville ici.

834
00:45:06,750 --> 00:45:08,950
Et tout est déterministe.

835
00:45:08,950 --> 00:45:14,660
Quand je dis, déplacer mon unité ici, mon unité
se déplace ici, sauf si un obstacle soudain

836
00:45:14,660 --> 00:45:17,700
entre en jeu.

837
00:45:17,700 --> 00:45:21,610
Maintenant, ce nest pas tout ordinateur
jeux qui sont là aujourd'hui.

838
00:45:21,610 --> 00:45:27,320
>> Si je vais et je joue un premier type de personne
jeu, quelque chose comme voleur ou Fallout

839
00:45:27,320 --> 00:45:33,350
ou Skyrim, ou Halo, maintenant
Je dois adversaires de l'ordinateur

840
00:45:33,350 --> 00:45:37,860
qui sont là-bas qui ont
une situation très différente.

841
00:45:37,860 --> 00:45:40,020
Ils ont, à nouveau, des informations limitées.

842
00:45:40,020 --> 00:45:43,420
Ils ne peuvent voir un
certain champ de vision.

843
00:45:43,420 --> 00:45:45,180
L'environnement est toujours dynamique.

844
00:45:45,180 --> 00:45:48,280
Les choses changent tout le temps.

845
00:45:48,280 --> 00:45:52,300
>> Mais maintenant, je dois beaucoup plus
espace d'action continue.

846
00:45:52,300 --> 00:45:57,170
Je peux être tout à la dérobée un
peu en dehors de la porte.

847
00:45:57,170 --> 00:46:00,650
Et certains jeux, mon
actions sont stochastiques.

848
00:46:00,650 --> 00:46:04,590
Je reçois d'essayer de sauter par-dessus ce mur,
mais je l'ai eu la chance d'échouer.

849
00:46:04,590 --> 00:46:08,280

850
00:46:08,280 --> 00:46:14,550
Ces types de jeux se rapprochent
et plus proche de la nature des contrôleurs

851
00:46:14,550 --> 00:46:17,330
que nous construisons dans la robotique.

852
00:46:17,330 --> 00:46:21,050
>> En robotique, nous avons à assumer
que nous avons des informations limitées.

853
00:46:21,050 --> 00:46:23,070
Nous avons capteurs
nous dire sur le monde.

854
00:46:23,070 --> 00:46:25,860
Nous avons une toujours changeante,
environnement dynamique.

855
00:46:25,860 --> 00:46:30,440
Nous avons un monde dans lequel l'espace est
continue, plutôt que discrète.

856
00:46:30,440 --> 00:46:36,260
Et nos actions, quand nous essayons
eux, ont une chance d'échouer.

857
00:46:36,260 --> 00:46:40,960
Et en fait, jeu moderne
contrôleurs pour votre adversaire Halo,

858
00:46:40,960 --> 00:46:48,690
ou pour les PNJ dans Skyrim, essentiellement
gérer de petites architectures de robotique.

859
00:46:48,690 --> 00:46:50,380
>> Ils sentent le monde.

860
00:46:50,380 --> 00:46:52,910
Ils construisent un modèle du monde.

861
00:46:52,910 --> 00:46:57,950
Ils calculent basés sur un ensemble de
objectifs qu'ils aimeraient accomplir.

862
00:46:57,950 --> 00:47:03,110
Ils prévoient des actions en fonction
sur ce qu'ils savent.

863
00:47:03,110 --> 00:47:07,940
Et ce sont exactement les mêmes types
des systèmes que nous construisons dans la robotique.

864
00:47:07,940 --> 00:47:11,420
Donc, ces architectures, à
ramener cela ensemble,

865
00:47:11,420 --> 00:47:14,500
sont souvent tout à fait la même.

866
00:47:14,500 --> 00:47:16,340
>> Donc, nous allons voir si nous pouvons voir que.

867
00:47:16,340 --> 00:47:19,210
Revenons à notre
exemple de tic-tac-toe.

868
00:47:19,210 --> 00:47:22,690
Et je vais demander à un couple de mon
post-docs à venir et aidez-moi.

869
00:47:22,690 --> 00:47:26,970
Donc, Chen Ming, et Alessandro, et
Olivier, si vous les gars viendrait.

870
00:47:26,970 --> 00:47:32,080

871
00:47:32,080 --> 00:47:35,440
Et je vais avoir besoin
un couple de bénévoles

872
00:47:35,440 --> 00:47:37,590
>> OK, je vis un droit de main
y dans le milieu.

873
00:47:37,590 --> 00:47:39,965
Permettez-moi de prendre un de plus, quelqu'un
plus loin dans le dos peut-être.

874
00:47:39,965 --> 00:47:40,881
Tout à droite, là-bas.

875
00:47:40,881 --> 00:47:41,490
Monte.

876
00:47:41,490 --> 00:47:44,190

877
00:47:44,190 --> 00:47:45,335
Bien.

878
00:47:45,335 --> 00:47:49,490
Prenons donc que la couverture vers le bas.

879
00:47:49,490 --> 00:48:03,700
Et si vous les gars viendrait droit
Retour ici pour moi, fantastique.

880
00:48:03,700 --> 00:48:06,580
>> Alors ceci est un robot appelé Baxter.

881
00:48:06,580 --> 00:48:10,880
Et Baxter est un robot qui est un
plate-forme commerciale, conçue

882
00:48:10,880 --> 00:48:13,030
par une compagnie appelée Rethink.

883
00:48:13,030 --> 00:48:16,580
Et ce robot est conçu
pour la fabrication à petite échelle.

884
00:48:16,580 --> 00:48:19,265
Mais aujourd'hui, nous allons
l'utiliser pour jouer tic-tac-toe.

885
00:48:19,265 --> 00:48:21,930

886
00:48:21,930 --> 00:48:27,150
Maintenant, ce robot est aussi quelque chose
qui est relativement unique.

887
00:48:27,150 --> 00:48:32,950
Parce que si je trouvais partout
près d'une automatisation d'usine standard

888
00:48:32,950 --> 00:48:39,580
système, je serais en très grave
danger d'être blessé.

889
00:48:39,580 --> 00:48:45,600
>> Baxter, cependant, est conçu pour être
relativement sûr pour interagir avec.

890
00:48:45,600 --> 00:48:48,680
Et donc je peux pousser sur ce robot.

891
00:48:48,680 --> 00:48:52,350
Et vous pouvez le voir, il est un peu
peu souple, car il se déplace.

892
00:48:52,350 --> 00:48:57,250
Et je peux repositionner
où je voudrais qu'il aille.

893
00:48:57,250 --> 00:49:03,410
Or, dans un système robotique normale,
nous aurions un ensemble de joints ici

894
00:49:03,410 --> 00:49:07,970
ce serait directement
répondre aux commandes de position.

895
00:49:07,970 --> 00:49:13,180
Et ils ne se soucieraient pas nécessairement
si ils se déplacent à travers l'air ouvert,

896
00:49:13,180 --> 00:49:15,555
ou si elles se déplaçaient
à travers ma cage thoracique.

897
00:49:15,555 --> 00:49:18,410

898
00:49:18,410 --> 00:49:19,120
>> D'ACCORD.

899
00:49:19,120 --> 00:49:22,090
Et généralement, si vous étiez
ici avec un système industriel,

900
00:49:22,090 --> 00:49:23,400
vous iriez loin d'elle.

901
00:49:23,400 --> 00:49:26,280
Il y aurait jaune
bande de sécurité tout autour de lui.

902
00:49:26,280 --> 00:49:28,310
Ce système a un
design légèrement différent

903
00:49:28,310 --> 00:49:32,130
pour être plus convivial et plus facile
pour les gens d'interagir avec,

904
00:49:32,130 --> 00:49:36,380
en ce que dans chaque commune, il ya un ressort.

905
00:49:36,380 --> 00:49:39,110
Et plutôt que de contrôler
une position exacte,

906
00:49:39,110 --> 00:49:43,110
nous contrôlons une certaine quantité de
couple, une certaine quantité de la force,

907
00:49:43,110 --> 00:49:45,874
que nous aimerions être sur que le printemps.

908
00:49:45,874 --> 00:49:47,790
Très bien, alors laissez-moi
prendre nos bénévoles ici.

909
00:49:47,790 --> 00:49:48,540
Salut quel est ton nom?

910
00:49:48,540 --> 00:49:49,010
>> AUDIENCE: Louis.

911
00:49:49,010 --> 00:49:49,635
>> CONFÉRENCIER: Louis.

912
00:49:49,635 --> 00:49:50,490
Ravi de vous voir.

913
00:49:50,490 --> 00:49:50,990
Et?

914
00:49:50,990 --> 00:49:51,610
>> AUDIENCE: David.

915
00:49:51,610 --> 00:49:51,960
>> Conférencier: David.

916
00:49:51,960 --> 00:49:52,550
Enchanté de faire votre connaissance.

917
00:49:52,550 --> 00:49:54,508
Si vous les gars attendrait
ici pour une seconde,

918
00:49:54,508 --> 00:49:56,420
Je vais vous donner
une chance de le faire.

919
00:49:56,420 --> 00:50:00,610
Donc, ce robot, si vous venez
et si vous appuyez doucement sur elle,

920
00:50:00,610 --> 00:50:03,780
vous allez voir que
il se déplace un peu.

921
00:50:03,780 --> 00:50:06,349
Et si vous prenez à droite
ici sur le poignet juste

922
00:50:06,349 --> 00:50:09,390
ci-dessus où les boutons sont, il
semble que vous devez saisir les boutons,

923
00:50:09,390 --> 00:50:13,100
mais saisir juste au-dessus à la place, vous aurez
être capable de manipuler très doucement

924
00:50:13,100 --> 00:50:14,545
à travers l'espace.

925
00:50:14,545 --> 00:50:15,920
Louis, vous voulez faire un essai?

926
00:50:15,920 --> 00:50:19,465
Afin de lui donner un peu
pousser pour commencer.

927
00:50:19,465 --> 00:50:23,190
Et puis si vous mettez vos doigts
juste là et accrocher à elle,

928
00:50:23,190 --> 00:50:24,807
car il se déplacera pour vous alors.

929
00:50:24,807 --> 00:50:27,824

930
00:50:27,824 --> 00:50:29,365
Très bien, vous voulez faire un essai?

931
00:50:29,365 --> 00:50:29,980
Monte.

932
00:50:29,980 --> 00:50:32,300
Afin de lui donner juste une douce
pousser là pour commencer.

933
00:50:32,300 --> 00:50:33,820
Vous pouvez vous sentir comme ce qu'il est.

934
00:50:33,820 --> 00:50:40,060
Et puis si vous prenez juste là,
vous serez en mesure de manœuvrer autour.

935
00:50:40,060 --> 00:50:41,280
>> D'ACCORD.

936
00:50:41,280 --> 00:50:47,360
Donc, généralement, ce genre d'un robot serait
être utilisé pour la fabrication de petits échelle.

937
00:50:47,360 --> 00:50:50,980
Et je vais passer ce bras juste
bas de la route un peu ici.

938
00:50:50,980 --> 00:50:55,750
Mais aujourd'hui, nous allons utiliser le
même système de jeu de tic-tac-toe

939
00:50:55,750 --> 00:50:59,520
basé sur Minimax que nous avons construit plus tôt.

940
00:50:59,520 --> 00:51:00,549
D'accord?

941
00:51:00,549 --> 00:51:02,340
Donc, vous les gars sont chacun
va jouer un jeu.

942
00:51:02,340 --> 00:51:04,210
Louis, vous allez être le premier.

943
00:51:04,210 --> 00:51:05,920
Permettez-moi de hold-up ici pour une seconde.

944
00:51:05,920 --> 00:51:10,949
Je vais devoir vous vous tenez droit
ici, donc tout le monde peut vous voir.

945
00:51:10,949 --> 00:51:11,990
Êtes-vous les gars mis en place ici?

946
00:51:11,990 --> 00:51:13,120
>> ROBOT: Bienvenue.

947
00:51:13,120 --> 00:51:15,910
Jouons tic-tac-toe.

948
00:51:15,910 --> 00:51:20,860
Ne pas saisir votre jeton avant
Je dis que ce sera votre tour.

949
00:51:20,860 --> 00:51:22,050
Je commence le jeu.

950
00:51:22,050 --> 00:51:27,900

951
00:51:27,900 --> 00:51:28,750
C'est mon tour.

952
00:51:28,750 --> 00:51:47,002

953
00:51:47,002 --> 00:51:50,210
CONFÉRENCIER: Maintenant, si vous pouviez prendre un des
vos morceaux et aller de l'avant et placez-le.

954
00:51:50,210 --> 00:51:51,446
ROBOT: Il est de votre tour.

955
00:51:51,446 --> 00:51:53,430
[RIRE]

956
00:51:53,430 --> 00:51:54,836
C'est mon tour.

957
00:51:54,836 --> 00:51:56,820
[RIRE]

958
00:51:56,820 --> 00:52:12,196

959
00:52:12,196 --> 00:52:15,680
[RIRE]

960
00:52:15,680 --> 00:52:16,570
C'est à ton tour.

961
00:52:16,570 --> 00:52:21,397

962
00:52:21,397 --> 00:52:23,688
CONFÉRENCIER: La race humaine est
compte sur vous ici, Louis.

963
00:52:23,688 --> 00:52:27,440

964
00:52:27,440 --> 00:52:28,350
>> ROBOT: Il est mon tour.

965
00:52:28,350 --> 00:52:44,810

966
00:52:44,810 --> 00:52:47,015
>> CONFÉRENCIER: Donc Baxter
bloqué avec succès ici.

967
00:52:47,015 --> 00:52:49,670

968
00:52:49,670 --> 00:52:52,480
>> ROBOT: Il est de votre tour.

969
00:52:52,480 --> 00:52:53,360
C'est mon tour.

970
00:52:53,360 --> 00:53:14,730

971
00:53:14,730 --> 00:53:16,810
C'est à ton tour.

972
00:53:16,810 --> 00:53:17,760
C'est mon tour.

973
00:53:17,760 --> 00:53:21,330

974
00:53:21,330 --> 00:53:23,830
CONFÉRENCIER: Et nous allons laisser Baxter
terminer son dernier coup ici.

975
00:53:23,830 --> 00:53:36,622

976
00:53:36,622 --> 00:53:39,090
>> [RIRE]

977
00:53:39,090 --> 00:53:40,480
>> ROBOT: Voilà une cravate.

978
00:53:40,480 --> 00:53:42,030
Je vais gagner la prochaine fois.

979
00:53:42,030 --> 00:53:43,365
>> [RIRE]

980
00:53:43,365 --> 00:53:45,210
>> CONFÉRENCIER: Très bien,
merci beaucoup, Louis.

981
00:53:45,210 --> 00:53:46,094
Merci.

982
00:53:46,094 --> 00:53:46,980
Vous pouvez aller dans cette voie.

983
00:53:46,980 --> 00:53:49,759
>> ROBOT: je commence le jeu.

984
00:53:49,759 --> 00:53:51,800
CONFÉRENCIER: Alors laissez-moi vous expliquer
vous un peu plus

985
00:53:51,800 --> 00:53:55,410
peu avant nous obtenons notre revanche ici.

986
00:53:55,410 --> 00:53:57,200
Qu'est-ce qui se passe exactement?

987
00:53:57,200 --> 00:53:59,430
Ainsi, le robot a une caméra là-haut ici.

988
00:53:59,430 --> 00:54:01,330
Et ça en regardant la carte.

989
00:54:01,330 --> 00:54:04,470
Et il est de voir si
il a un O rouge ou bleu

990
00:54:04,470 --> 00:54:10,450
et X. blanc comme ceux se placé sur le
conseil d'administration, qui est essentiellement la même entrée

991
00:54:10,450 --> 00:54:13,890
que nous serions en train de lire depuis
notre structure de données de notre écran.

992
00:54:13,890 --> 00:54:17,290
Il fonctionne de la même
algorithme minimax être

993
00:54:17,290 --> 00:54:21,010
en mesure de trouver où
placer un bon coup.

994
00:54:21,010 --> 00:54:24,820
>> Et puis nous donner un ordre à propos
où nous aimerions un jeton pour être placé.

995
00:54:24,820 --> 00:54:26,120
Le bras se déplace sur.

996
00:54:26,120 --> 00:54:31,750
Il utilise une pince à vide à appliquer
aspiration à une certaine pièce de bois qui,

997
00:54:31,750 --> 00:54:35,240
le ramasser, le déplacer vers la droite
place, puis relâchez l'aspiration

998
00:54:35,240 --> 00:54:36,950
et déposez-le.

999
00:54:36,950 --> 00:54:38,990
Très bien, nous allons
pour lui donner une autre chance

1000
00:54:38,990 --> 00:54:40,930
avec un lecteur légèrement plus intelligent ici.

1001
00:54:40,930 --> 00:54:42,290
Tu es prêt?

1002
00:54:42,290 --> 00:54:46,150
Très bien, si vous voulez reposer jusqu'à
ici et donner a-- tourner de cette façon

1003
00:54:46,150 --> 00:54:47,955
de sorte que vous pouvez voir tout le monde.

1004
00:54:47,955 --> 00:54:48,830
Et puis [inaudible].

1005
00:54:48,830 --> 00:54:49,330
>> ROBOT: Il est mon tour.

1006
00:54:49,330 --> 00:54:50,455
>> CONFÉRENCIER: Baxter va commencer.

1007
00:54:50,455 --> 00:55:10,750

1008
00:55:10,750 --> 00:55:11,730
C'est à ton tour.

1009
00:55:11,730 --> 00:55:16,490

1010
00:55:16,490 --> 00:55:17,520
C'est mon tour.

1011
00:55:17,520 --> 00:55:38,740

1012
00:55:38,740 --> 00:55:39,690
C'est à ton tour.

1013
00:55:39,690 --> 00:55:46,330

1014
00:55:46,330 --> 00:55:47,165
C'est mon tour.

1015
00:55:47,165 --> 00:56:01,252

1016
00:56:01,252 --> 00:56:06,192
>> [RIRE]

1017
00:56:06,192 --> 00:56:08,542
>> CONFÉRENCIER: [WHISPERING] Juste
laissez-le aller de l'avant et gagner.

1018
00:56:08,542 --> 00:56:09,500
ROBOT: Il est de votre tour.

1019
00:56:09,500 --> 00:56:15,099

1020
00:56:15,099 --> 00:56:15,890
Président: Cela est OK.

1021
00:56:15,890 --> 00:56:20,390

1022
00:56:20,390 --> 00:56:21,360
>> ROBOT: Il est mon tour.

1023
00:56:21,360 --> 00:56:24,825

1024
00:56:24,825 --> 00:56:26,805
>> [RIRE]

1025
00:56:26,805 --> 00:56:42,650

1026
00:56:42,650 --> 00:56:43,510
>> Je gagne.

1027
00:56:43,510 --> 00:56:45,620
>> [RIRE]

1028
00:56:45,620 --> 00:56:46,595
>> Je commence le jeu.

1029
00:56:46,595 --> 00:56:48,261
>> CONFÉRENCIER: Très bien, je vous remercie beaucoup.

1030
00:56:48,261 --> 00:56:50,180

1031
00:56:50,180 --> 00:56:55,590
Très bien, je pense que nous avons le temps pour
encore un excellent joueur de tic-tac-toe,

1032
00:56:55,590 --> 00:57:00,490
quelqu'un qui peut mettre cette chose à
correspondent, qui sait ce qu'ils font.

1033
00:57:00,490 --> 00:57:03,010
>> [RIRE]

1034
00:57:03,010 --> 00:57:05,560
>> Qui va être notre champion ici?

1035
00:57:05,560 --> 00:57:08,110
Très bien, vos amis vous volontaire.

1036
00:57:08,110 --> 00:57:11,190
Cela est assez bon pour moi.

1037
00:57:11,190 --> 00:57:12,194
Dites-moi votre nom à nouveau.

1038
00:57:12,194 --> 00:57:12,860
AUDIENCE: Tamir.

1039
00:57:12,860 --> 00:57:14,193
CONFÉRENCIER: Tamir, agréable de vous voir.

1040
00:57:14,193 --> 00:57:19,270
Tout droit, encore une fois, nous allons vous mettre
juste ici que tout le monde peut vous voir.

1041
00:57:19,270 --> 00:57:22,070
Vous êtes notre représentant
dans ce match aujourd'hui.

1042
00:57:22,070 --> 00:57:24,540
Baxter est un et oh et oh.

1043
00:57:24,540 --> 00:57:26,300
Ou désolé, oh l'un et l'autre.

1044
00:57:26,300 --> 00:57:27,490
Et il est à vous ici.

1045
00:57:27,490 --> 00:57:29,340
Baxter va se faire le premier pas, cependant.

1046
00:57:29,340 --> 00:57:30,435
Ainsi.

1047
00:57:30,435 --> 00:57:31,310
ROBOT: Il est mon tour.

1048
00:57:31,310 --> 00:57:45,226

1049
00:57:45,226 --> 00:57:48,208
>> [RIRE]

1050
00:57:48,208 --> 00:57:52,720

1051
00:57:52,720 --> 00:57:55,780
>> C'est à ton tour.

1052
00:57:55,780 --> 00:57:56,845
C'est mon tour.

1053
00:57:56,845 --> 00:58:18,130

1054
00:58:18,130 --> 00:58:18,965
C'est à ton tour.

1055
00:58:18,965 --> 00:58:28,751

1056
00:58:28,751 --> 00:58:30,248
C'est mon tour.

1057
00:58:30,248 --> 00:58:51,210

1058
00:58:51,210 --> 00:58:52,160
C'est à ton tour.

1059
00:58:52,160 --> 00:59:00,854

1060
00:59:00,854 --> 00:59:03,365
>> [RIRE]

1061
00:59:03,365 --> 00:59:04,240
ROBOT: Il est mon tour.

1062
00:59:04,240 --> 00:59:06,930
CONFÉRENCIER: Il est beaucoup plus difficile quand
vous êtes debout ici, les gens.

1063
00:59:06,930 --> 00:59:19,400

1064
00:59:19,400 --> 00:59:21,840
[RIRE]

1065
00:59:21,840 --> 00:59:26,730

1066
00:59:26,730 --> 00:59:29,054
ROBOT: Vous les humains sont si faciles à battre.

1067
00:59:29,054 --> 00:59:30,803
[Rires et applaudissements]

1068
00:59:30,803 --> 00:59:31,886
CONFÉRENCIER: Merci beaucoup.

1069
00:59:31,886 --> 00:59:34,692
ROBOT: je gagne.

1070
00:59:34,692 --> 00:59:35,400
Je commence le jeu.

1071
00:59:35,400 --> 00:59:39,500
>> Président: Très bien, alors merci
beaucoup à Olivier, et Alessandro,

1072
00:59:39,500 --> 00:59:41,616
et Chen Ming.

1073
00:59:41,616 --> 00:59:45,600
>> [APPLAUDISSEMENTS]

1074
00:59:45,600 --> 00:59:47,040
>> Je veux faire un dernier point.

1075
00:59:47,040 --> 00:59:51,630
Donc Baxter à la très
arrêter là, triché.

1076
00:59:51,630 --> 00:59:54,160

1077
00:59:54,160 --> 00:59:56,310
Et ce fut inattendu.

1078
00:59:56,310 --> 01:00:00,440
Un du fantastique
choses à propos de AI est que nous

1079
01:00:00,440 --> 01:00:05,070
faire des travaux en IA de sorte que nous pouvons construire
vraiment intéressant et intelligent

1080
01:00:05,070 --> 01:00:06,930
appareils.

1081
01:00:06,930 --> 01:00:10,130
Mais nous faisons aussi des travaux en IA
car il nous dit quelque chose

1082
01:00:10,130 --> 01:00:13,940
sur la façon dont les êtres humains sont intelligents.

1083
01:00:13,940 --> 01:00:17,280
>> L'un des favoris
les études de mon laboratoire est

1084
01:00:17,280 --> 01:00:23,660
en regardant ce qui se passe quand
machines trichent de façon inattendue.

1085
01:00:23,660 --> 01:00:27,070
Nous l'avons fait à l'origine pas
Baxter jouer tic-tac-toe,

1086
01:00:27,070 --> 01:00:30,340
mais plus petite avec un robot nommé Nao,
qui a joué roche-papier-ciseaux.

1087
01:00:30,340 --> 01:00:33,010

1088
01:00:33,010 --> 01:00:35,800
Et parfois après
jouer beaucoup, beaucoup

1089
01:00:35,800 --> 01:00:41,580
d'ennuyer Pierre-Feuille-Ciseaux jeux,
le robot jetterait un geste,

1090
01:00:41,580 --> 01:00:48,616
perdre, et puis soudainement changer
son geste et de dire, je gagne.

1091
01:00:48,616 --> 01:00:50,480
>> [RIRE]

1092
01:00:50,480 --> 01:00:56,090
>> Maintenant, parfois, nous aurions également le robot,
tout comme un contrôle, jetez un geste,

1093
01:00:56,090 --> 01:01:01,270
gagner, et changer son geste
à perdre, jeter le match,

1094
01:01:01,270 --> 01:01:04,070
tricher pour perdre.

1095
01:01:04,070 --> 01:01:07,540
Et qui est loin d'être aussi convaincant.

1096
01:01:07,540 --> 01:01:09,890
Le robot qui triche
afin de gagner les gens

1097
01:01:09,890 --> 01:01:14,660
à répondre comme si elle était
out pour les obtenir, comme il

1098
01:01:14,660 --> 01:01:17,690
recherche activement leur destruction.

1099
01:01:17,690 --> 01:01:19,210
>> [RIRE]

1100
01:01:19,210 --> 01:01:20,990
>> Il devient un agent.

1101
01:01:20,990 --> 01:01:21,840
Il est comme une personne.

1102
01:01:21,840 --> 01:01:23,970
Il a la conviction et l'intention.

1103
01:01:23,970 --> 01:01:27,470
Et il est pas bonne intention.

1104
01:01:27,470 --> 01:01:33,790
Et le robot qui lance le
jeu est juste un dysfonctionnement.

1105
01:01:33,790 --> 01:01:36,990
Il est juste un appareil défectueux.

1106
01:01:36,990 --> 01:01:41,405
Permettez-moi de vous montrer quelques exemples
de ce à partir de quelques-uns de nos participants.

1107
01:01:41,405 --> 01:01:43,990

1108
01:01:43,990 --> 01:01:45,600
Alors, voici la tricherie dans le but de perdre.

1109
01:01:45,600 --> 01:01:46,266
>> [LECTURE VIDÉO]

1110
01:01:46,266 --> 01:01:47,010
- [Inaudible] gagner.

1111
01:01:47,010 --> 01:01:49,550
Jouons.

1112
01:01:49,550 --> 01:01:50,538
>> -Attends quoi?

1113
01:01:50,538 --> 01:01:54,490

1114
01:01:54,490 --> 01:01:55,352
>> - [Inaudible] gagner.

1115
01:01:55,352 --> 01:01:58,280
Jouons.

1116
01:01:58,280 --> 01:01:59,400
>> [Inaudible] gagner.

1117
01:01:59,400 --> 01:02:02,290
Jouons.

1118
01:02:02,290 --> 01:02:05,490
>> CONFÉRENCIER: Et voici la tricherie pour gagner.

1119
01:02:05,490 --> 01:02:06,438
>> Oui, je gagne.

1120
01:02:06,438 --> 01:02:07,394
Jouons.

1121
01:02:07,394 --> 01:02:08,828
>> -Vous Ne pouvez pas faire cela.

1122
01:02:08,828 --> 01:02:10,740
>> [RIRE]

1123
01:02:10,740 --> 01:02:12,174

1124
01:02:12,174 --> 01:02:13,979
>> Oui, je gagne.

1125
01:02:13,979 --> 01:02:14,520
-Tu as triché.

1126
01:02:14,520 --> 01:02:17,990

1127
01:02:17,990 --> 01:02:20,010
Vous avez triché maintenant.

1128
01:02:20,010 --> 01:02:21,140
>> Oui, je gagne.

1129
01:02:21,140 --> 01:02:22,940
>> Hé, vous tricheur.

1130
01:02:22,940 --> 01:02:26,670
Vous trichez, super tricheur.

1131
01:02:26,670 --> 01:02:27,650
>> [FIN LECTURE]

1132
01:02:27,650 --> 01:02:31,130
>> CONFÉRENCIER: Ces différentes
réactions rapidement

1133
01:02:31,130 --> 01:02:34,890
changer notre perception de l'appareil.

1134
01:02:34,890 --> 01:02:36,780
Cela veut dire que
nous construisons délibérément

1135
01:02:36,780 --> 01:02:40,370
machines qui trichent parce que ce
la meilleure ingénierie que nous pouvons faire?

1136
01:02:40,370 --> 01:02:44,680
Non, mais il nous dit quelque chose
vraiment intéressant sur les gens.

1137
01:02:44,680 --> 01:02:49,710
Cette chose que vous et astuces
vole votre victoire, que ce

1138
01:02:49,710 --> 01:02:53,660
quelque chose qui est vivant, qui est
Animer, qui est là pour vous attraper.

1139
01:02:53,660 --> 01:02:54,680
Il a l'état mental.

1140
01:02:54,680 --> 01:02:55,400
Il a la conviction.

1141
01:02:55,400 --> 01:02:57,170
Il a l'intention.

1142
01:02:57,170 --> 01:03:01,540
>> Cette chose qui tend le
jeu pour vous, qui est pas.

1143
01:03:01,540 --> 01:03:04,670
Voilà tout dysfonctionnement.

1144
01:03:04,670 --> 01:03:08,900
Ceci est à bien des égards pourquoi il est
facile de jeter le jeu avec les enfants.

1145
01:03:08,900 --> 01:03:12,050
Mais si vous essayez de les tromper
et une sorte de prétendre à la victoire

1146
01:03:12,050 --> 01:03:15,200
quand, vous le savez, juste pour raccourcir la
jeu, ils vous attrapent tout de suite.

1147
01:03:15,200 --> 01:03:19,040

1148
01:03:19,040 --> 01:03:23,140
Ces types d'effets que
nous voyons sortir de l'IA,

1149
01:03:23,140 --> 01:03:26,490
ils nous apprennent beaucoup de choses sur nous-mêmes.

1150
01:03:26,490 --> 01:03:28,076
>> Tout à droite, qui est tout pour aujourd'hui.

1151
01:03:28,076 --> 01:03:30,450
Merci beaucoup à David et
l'équipe de production de Harvard

1152
01:03:30,450 --> 01:03:32,350
pour descendre.

1153
01:03:32,350 --> 01:03:33,820
>> [APPLAUDISSEMENTS]

1154
01:03:33,820 --> 01:03:36,760

1155
01:03:36,760 --> 01:03:41,840
>> Nous vous verrons pour un quizz,
puis pour une dernière lecture.

1156
01:03:41,840 --> 01:03:43,025
Bonne journée.

1157
01:03:43,025 --> 01:03:44,965
>> [APPLAUDISSEMENTS]

1158
01:03:44,965 --> 01:03:48,360

1159
01:03:48,360 --> 01:03:51,825
>> [Jouer de la musique]

1160
01:03:51,825 --> 01:03:54,950
DAVID MALAN J: Eh bien, nous avons probablement besoin
d'introduire une sorte de cryptage,

1161
01:03:54,950 --> 01:03:55,450
droit?

1162
01:03:55,450 --> 01:03:58,650
Car alors les en-têtes de
ces requêtes HTTP seront

1163
01:03:58,650 --> 01:04:01,530
brouillés afin que quiconque
essayer de renifler votre trafic

1164
01:04:01,530 --> 01:04:03,400
ne sera pas réellement être en mesure de les voir.

1165
01:04:03,400 --> 01:04:05,254
Alors, quelle est la solution à ce problème?

1166
01:04:05,254 --> 01:04:07,920
Eh bien, nous devons effectivement introduire
chiffrement dans la formule,

1167
01:04:07,920 --> 01:04:11,010
de sorte que lorsque ladite personne est
transmettre des données de A à B,

1168
01:04:11,010 --> 01:04:12,390
nous pouvons en toute sécurité send--

1169
01:04:12,390 --> 01:04:14,590
>> [RIRE]

1170
01:04:14,590 --> 01:04:19,530
>> Les informations contenues dans une manière que le
adversaire ne peut pas, en fait, le voir.