1
00:00:00,000 --> 00:00:01,924
>> [Música tocando]

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

3
00:00:10,600 --> 00:00:13,280
>> COLUNA: Bem-vindo de volta, todo mundo.

4
00:00:13,280 --> 00:00:15,440
Este é CS50.

5
00:00:15,440 --> 00:00:21,040
E hoje, nós temos um monte de
coisas interessantes para falar.

6
00:00:21,040 --> 00:00:25,500
Primeiro, porém, eu tenho que lembrá-
você de algumas coisas administrativas.

7
00:00:25,500 --> 00:00:30,160
Esta semana é um questionário, quarta-
ou para a secção de Yale

8
00:00:30,160 --> 00:00:32,940
às terças-feiras e quintas-feiras, na quinta-feira.

9
00:00:32,940 --> 00:00:38,170
Não há comentários do quiz
hoje à noite na Universidade de Yale, 05:30 - 07:00.

10
00:00:38,170 --> 00:00:40,030
Em Harvard, eles gravaram um ontem.

11
00:00:40,030 --> 00:00:43,000
E todos podem ver que online.

12
00:00:43,000 --> 00:00:49,406
>> Além disso, esta semana ou início da próxima semana,
nós temos nossa última palestra CS50.

13
00:00:49,406 --> 00:00:51,450
[Gemidos] Eu sei.

14
00:00:51,450 --> 00:00:54,140
Ele veio tão cedo.

15
00:00:54,140 --> 00:00:57,820
Estudantes de Yale terá um live
palestra aqui na escola de direito

16
00:00:57,820 --> 00:00:59,920
auditório na sexta-feira.

17
00:00:59,920 --> 00:01:01,140
Haverá bolo.

18
00:01:01,140 --> 00:01:05,570
Estudantes de Harvard terá a
última palestra em Sanders na segunda-feira.

19
00:01:05,570 --> 00:01:08,050
Haverá também bolo.

20
00:01:08,050 --> 00:01:14,000
>> Além disso, esta semana na sexta-feira, para aqueles
de vocês que estão vindo para New Haven,

21
00:01:14,000 --> 00:01:15,740
temos a Expo CS50.

22
00:01:15,740 --> 00:01:18,850
Temos mais de 30
diferentes grupos registrados

23
00:01:18,850 --> 00:01:22,530
para lhe mostrar tudo
de veleiros autónomos,

24
00:01:22,530 --> 00:01:27,170
para sistemas que reconhecem
retratos digitais, para o computador

25
00:01:27,170 --> 00:01:32,100
música e música produzida por computador.

26
00:01:32,100 --> 00:01:33,610
Então, por favor se juntar a nós.

27
00:01:33,610 --> 00:01:36,460
Eu acho que vai ser um grande momento.

28
00:01:36,460 --> 00:01:40,320
>> Hoje, porém, temos de
continuar a falar sobre AI,

29
00:01:40,320 --> 00:01:43,150
sobre a inteligência artificial.

30
00:01:43,150 --> 00:01:46,070
E uma das coisas que
nós estamos indo para chegar ao hoje

31
00:01:46,070 --> 00:01:51,750
é a idéia de como
usar o AI para resolver problemas.

32
00:01:51,750 --> 00:01:54,690
Agora, como sempre, vamos começar
com algo simples.

33
00:01:54,690 --> 00:01:57,120
E nós vamos começar
com uma idéia simples.

34
00:01:57,120 --> 00:01:59,920
E isso é usando a pesquisa.

35
00:01:59,920 --> 00:02:06,990
>> Então, imagine por um minuto que eu
tem uma tarefa que eu preciso para executar.

36
00:02:06,990 --> 00:02:11,970
E eu gostaria de ter essa tarefa
automatizado por algum agente software.

37
00:02:11,970 --> 00:02:17,100
Imagine que eu estou tentando reservar um conjunto
de voos a partir de, digamos, Boston

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

39
00:02:20,040 --> 00:02:24,230
Eu poderia passar e eu poderia usar
um de busca on-line maravilhosa

40
00:02:24,230 --> 00:02:28,790
ferramentas, o que vai fazer
basicamente o mesmo processo que estamos

41
00:02:28,790 --> 00:02:30,030
indo a pé até hoje.

42
00:02:30,030 --> 00:02:34,100
Mas se você não tem que
ferramenta, o que você faria?

43
00:02:34,100 --> 00:02:37,570
>> Bem, você pode olhar e
ver e dizer, eu estou em Boston.

44
00:02:37,570 --> 00:02:41,520
O que os voos estão disponíveis para mim?

45
00:02:41,520 --> 00:02:44,390
Agora, talvez eu tenha três
possíveis vôos a partir de Boston

46
00:02:44,390 --> 00:02:47,180
que vai caber o tempo
quando eu preciso sair.

47
00:02:47,180 --> 00:02:48,830
Eu poderia voar para Chicago.

48
00:02:48,830 --> 00:02:50,130
Ou eu poderia voar para Miami.

49
00:02:50,130 --> 00:02:53,340
Ou eu poderia voar para Nova York.

50
00:02:53,340 --> 00:02:56,980
Eu poderia, então, olhar de cada um
uma daquelas cidades de destino

51
00:02:56,980 --> 00:03:00,650
e pensar sobre o que locais
Eu poderia chegar

52
00:03:00,650 --> 00:03:03,020
de cada uma dessas cidades individuais.

53
00:03:03,020 --> 00:03:07,390
>> Então, talvez a partir de Chicago, eu posso conseguir
um vôo direto para San Francisco.

54
00:03:07,390 --> 00:03:09,550
Isso é excelente.

55
00:03:09,550 --> 00:03:12,360
Ou eu poderia pegar um vôo para Denver.

56
00:03:12,360 --> 00:03:16,970
Agora, talvez que o vôo para San Francisco
é a solução perfeita para mim,

57
00:03:16,970 --> 00:03:19,530
mas talvez não.

58
00:03:19,530 --> 00:03:22,180
Talvez eu estou procurando algo
isso é um pouco mais barato

59
00:03:22,180 --> 00:03:24,920
ou um pouco melhor para o meu horário.

60
00:03:24,920 --> 00:03:29,197
E para que eu pudesse olhar para o que os outros
possibilidades podem estar lá fora.

61
00:03:29,197 --> 00:03:30,280
Então, eu poderia olhar para Denver.

62
00:03:30,280 --> 00:03:33,870
E a partir de Denver, bem, talvez
Eu posso pegar um vôo para Austin.

63
00:03:33,870 --> 00:03:37,080
E a partir de Austin, talvez eu possa obter uma
voo para Phoenix e da Phoenix

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

65
00:03:40,190 --> 00:03:42,730
Agora, eu não estou pronto ainda.

66
00:03:42,730 --> 00:03:45,640
Porque talvez haja uma
com voos directos de Nova Iorque

67
00:03:45,640 --> 00:03:47,850
a San Francisco que é perfeito para mim.

68
00:03:47,850 --> 00:03:53,354
Ou talvez haja um vôo de Miami
através de Denver que é muito mais barato.

69
00:03:53,354 --> 00:03:54,270
Então, eu ainda tenho que ir.

70
00:03:54,270 --> 00:03:58,200
E eu ainda tenho que olhar para todos aqueles
cidades que eu ainda não investigados.

71
00:03:58,200 --> 00:04:04,220
Eu tenho que verificar exaustivamente todas
as possibilidades que eu possa ter.

72
00:04:04,220 --> 00:04:09,610
>> Assim, a partir de Nova Iorque, talvez eu possa obter uma
voo para Nashville, e de Nashville

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

74
00:04:10,336 --> 00:04:11,460
E então eu sei onde estou.

75
00:04:11,460 --> 00:04:14,252
E então eu sei a partir de Austin, eu posso
voar para Phoenix e da Phoenix

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

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

78
00:04:18,240 --> 00:04:22,830
Se eu voar para Miami primeira, porém,
talvez eu possa pegar um vôo de Miami

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

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

81
00:04:27,950 --> 00:04:30,860
>> E agora eu tentei tudo
das possibilidades.

82
00:04:30,860 --> 00:04:36,310
Eu construí-se neste gráfico que
me mostra todas as possíveis rotas

83
00:04:36,310 --> 00:04:37,790
que eu poderia ser capaz de tomar.

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

85
00:04:40,510 --> 00:04:43,640
Quando nós representamos estes
tipos de problemas,

86
00:04:43,640 --> 00:04:47,870
nós não estamos indo para representar
-los explicitamente como este gráfico,

87
00:04:47,870 --> 00:04:51,590
porque esse gráfico não representa
a história de onde fomos.

88
00:04:51,590 --> 00:04:55,260
Sabendo que eu voei de
Phoenix para San Francisco

89
00:04:55,260 --> 00:05:01,690
não me diga se eu vim via
Nashville, ou através de Denver, ou através de Miami.

90
00:05:01,690 --> 00:05:06,430
>> Então, o que eu vou fazer é em vez
Vou levar este mesmo problema,

91
00:05:06,430 --> 00:05:09,140
e eu vou representá-lo como uma árvore.

92
00:05:09,140 --> 00:05:14,300
E na raiz da árvore, na
topo, eu vou colocar o lugar que eu comecei,

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

94
00:05:16,590 --> 00:05:19,310
E a partir de Boston, eu vou olhar para
todos os possíveis locais

95
00:05:19,310 --> 00:05:20,380
que eu possa viajar.

96
00:05:20,380 --> 00:05:25,480
Bem, neste caso, eu tinha três,
Chicago, Nova York e Miami.

97
00:05:25,480 --> 00:05:29,850
E então eu vou explorar cada um dos
essas crianças na árvore.

98
00:05:29,850 --> 00:05:32,690
>> De Chicago, vi
que eu tinha dois vôos.

99
00:05:32,690 --> 00:05:35,940
Eu poderia voar diretamente para
San Francisco ou Denver.

100
00:05:35,940 --> 00:05:37,740
Agora San Francisco, que é o meu objetivo.

101
00:05:37,740 --> 00:05:39,790
Esse é o meu destino.

102
00:05:39,790 --> 00:05:42,220
Isso vai ser uma folha dessa árvore.

103
00:05:42,220 --> 00:05:45,340
Ou seja, eu nunca estou indo para ir
em algum lugar após San Francisco.

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

105
00:05:47,850 --> 00:05:50,340
De Denver, embora,
Eu posso voar a partir de Denver

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

107
00:05:54,220 --> 00:05:56,050
E agora novamente, cheguei a uma folha.

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

109
00:05:59,470 --> 00:06:03,980
>> Eu poderia, então, voltar para a próxima
cidade que eu ainda não totalmente explorado.

110
00:06:03,980 --> 00:06:07,440
Isso seria Nova York, ir
volta-se para o topo da minha árvore,

111
00:06:07,440 --> 00:06:09,160
desçam para Nova York.

112
00:06:09,160 --> 00:06:12,700
De Nova York, eu posso voar para
Nashville, de Nashville a Austin,

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

114
00:06:17,290 --> 00:06:20,170
E, finalmente, uma cidade que eu
não olhei ainda, Miami.

115
00:06:20,170 --> 00:06:24,600
>> Bem, a partir de Miami eu disse que tinha dois
possibilidades, Nashville ou Austin.

116
00:06:24,600 --> 00:06:28,810
Se eu voar para Nashville, bem, então eu vôo
a partir de Nashville, para Austin, para Phoenix,

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

118
00:06:29,640 --> 00:06:33,600
Se eu voar para Austin, eu vôo Austin,
para Phoenix, a San Francisco.

119
00:06:33,600 --> 00:06:36,340
E agora eu tenho uma árvore.

120
00:06:36,340 --> 00:06:37,230
É uma árvore completa.

121
00:06:37,230 --> 00:06:41,890
É todas as possibilidades e
todos os caminhos que eu poderia tomar.

122
00:06:41,890 --> 00:06:44,310
Isto é, se eu começar no
raiz da árvore no topo

123
00:06:44,310 --> 00:06:47,860
e eu descer para um dos
sai, ele diz-me não só

124
00:06:47,860 --> 00:06:50,480
onde eu vou
acabar, San Francisco,

125
00:06:50,480 --> 00:06:53,670
mas ele me diz a rota que
Eu preciso levar para chegar lá.

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

127
00:06:56,400 --> 00:06:59,690
>> Agora, qual destes é o melhor?

128
00:06:59,690 --> 00:07:02,430
Bem, nada sobre isso
problema ainda me diz

129
00:07:02,430 --> 00:07:04,710
qual delas é a melhor solução.

130
00:07:04,710 --> 00:07:09,270
Talvez eu me importo mais sobre
quanto tempo eu estou no ar,

131
00:07:09,270 --> 00:07:12,350
ou a distância que eu estou voando.

132
00:07:12,350 --> 00:07:16,410
Nesse caso, Chicago para San
Francisco pode ser o menor número

133
00:07:16,410 --> 00:07:18,910
de milhas no ar.

134
00:07:18,910 --> 00:07:20,860
>> Talvez eu me preocupo com o custo.

135
00:07:20,860 --> 00:07:23,680
E todos nós sabemos voos directos
são geralmente mais caros.

136
00:07:23,680 --> 00:07:26,610
Então, talvez se eu levar isso
tipo de rota para trás

137
00:07:26,610 --> 00:07:30,650
através de Miami, Nashville,
Austin, Phoenix, talvez, em seguida,

138
00:07:30,650 --> 00:07:34,070
Eu recebo um preço mais baixo.

139
00:07:34,070 --> 00:07:36,440
Mas eu poderia otimizar em qualquer
critérios que me interessa.

140
00:07:36,440 --> 00:07:39,790
Quem tem o melhor em
voo Wi-Fi, ou que

141
00:07:39,790 --> 00:07:43,110
aeroportos têm a melhor comida disponível.

142
00:07:43,110 --> 00:07:47,280
E cada um desses pode
me dar uma solução diferente

143
00:07:47,280 --> 00:07:49,215
que eu vejo como sendo o melhor.

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

145
00:07:51,990 --> 00:07:54,400
>> Esses tipos de problemas,
onde vamos

146
00:07:54,400 --> 00:07:58,480
para construir esta árvore de
possibilidades e, em seguida

147
00:07:58,480 --> 00:08:02,100
olhar para cada um desses
caminhos individuais, e examinar

148
00:08:02,100 --> 00:08:05,270
qual desses fulfills
um critério para nós,

149
00:08:05,270 --> 00:08:08,790
vamos chamá-
esses problemas de busca.

150
00:08:08,790 --> 00:08:11,280
E nós temos lotes de
algoritmos, alguns dos quais

151
00:08:11,280 --> 00:08:15,270
temos visto já, ir
e explorar aquelas árvores.

152
00:08:15,270 --> 00:08:19,270
Poderíamos fazê-lo da maneira que eu
apenas fiz, uma busca em profundidade,

153
00:08:19,270 --> 00:08:22,900
indo para baixo, tanto quanto pudermos até nós
bateu uma folha, e, em seguida, voltando-se,

154
00:08:22,900 --> 00:08:24,787
e indo para a direita de volta para baixo.

155
00:08:24,787 --> 00:08:26,870
Ou podemos fazer o que é
chamado de busca em largura.

156
00:08:26,870 --> 00:08:29,675
Poderíamos expandir tudo
na parte superior, e, em seguida

157
00:08:29,675 --> 00:08:31,550
tudo uma linha
embaixo que, em seguida,

158
00:08:31,550 --> 00:08:35,240
tudo uma linha debaixo daquele.

159
00:08:35,240 --> 00:08:41,250
Essas árvores de busca
são fundamentais para a AI.

160
00:08:41,250 --> 00:08:46,570
Mas eles não começ completamente
certo o tempo todo.

161
00:08:46,570 --> 00:08:51,600
De fato, em muitos dos casos
que realmente se preocupam,

162
00:08:51,600 --> 00:08:54,430
queremos construir uma árvore,
mas nós não, na verdade,

163
00:08:54,430 --> 00:08:57,140
começa a fazer todas as decisões.

164
00:08:57,140 --> 00:09:00,940
>> Estas são situações chamadas
busca adversarial, também conhecido

165
00:09:00,940 --> 00:09:05,390
como a forma de escrever playing game
sistemas e ser pago por isso.

166
00:09:05,390 --> 00:09:07,940
Mas estes são os tipos
de sistemas onde

167
00:09:07,940 --> 00:09:12,920
pode começar a escolher quando eu ir de
Boston, qual cidade eu ir para a próxima.

168
00:09:12,920 --> 00:09:19,990
Mas depois disso, alguém pode obter
para tomar a decisão sobre onde eu voar.

169
00:09:19,990 --> 00:09:24,040
Portanto, para construir estes
tipos de estruturas, estamos

170
00:09:24,040 --> 00:09:28,510
vai ter que tomar um pouco
abordagem diferente para ele.

171
00:09:28,510 --> 00:09:31,060
Nós não vamos ser capazes de
basta pesquisar através da árvore

172
00:09:31,060 --> 00:09:35,000
mais, porque nós não somos
aquele que está no controle

173
00:09:35,000 --> 00:09:38,180
de cada um desses pontos de decisão.

174
00:09:38,180 --> 00:09:42,590
>> Então, vamos imaginar uma simples
jogo como tic-tac-toe.

175
00:09:42,590 --> 00:09:46,730
Eu poderia começar com um
Placa completamente em branco.

176
00:09:46,730 --> 00:09:49,580
E em tic-tac-dedo do pé,
X consegue jogar primeiro.

177
00:09:49,580 --> 00:09:53,890
E para que eu pudesse pensar em tudo o
movimentos possíveis que X poderia fazer.

178
00:09:53,890 --> 00:09:57,420
E se eu sou o único jogo
o X, isso é ótimo.

179
00:09:57,420 --> 00:10:01,020
Tenho nove possível
move que eu posso fazer.

180
00:10:01,020 --> 00:10:05,000
Eu poderia colocar um X em qualquer uma
destes nove posições.

181
00:10:05,000 --> 00:10:10,710
>> E, em seguida, a partir de cada um daqueles, I
podia imaginar o que acontece em seguida.

182
00:10:10,710 --> 00:10:14,130
Bem, neste caso, a outra
jogador iria começar a tomar um rumo.

183
00:10:14,130 --> 00:10:15,660
O iria começar a tomar um rumo.

184
00:10:15,660 --> 00:10:19,510
E de cada um desses, há
seria oito lugares diferentes

185
00:10:19,510 --> 00:10:22,980
O que poderia colocar o seu marcador.

186
00:10:22,980 --> 00:10:25,790
>> Vamos dizer que eu decidi que eu era
vai colocar um X no centro.

187
00:10:25,790 --> 00:10:28,810
Que sempre parece que
um bom movimento de abertura.

188
00:10:28,810 --> 00:10:34,870
Eu poderia olhar para baixo que, a
oito movimentos possíveis que O faz.

189
00:10:34,870 --> 00:10:37,320
Agora, se eu estou jogando X, isso é maravilhoso.

190
00:10:37,320 --> 00:10:41,740
Eu começar a escolher qual deles eu
ir para o um no meio.

191
00:10:41,740 --> 00:10:45,000
Mas agora ó começa a escolher.

192
00:10:45,000 --> 00:10:48,750
E eu não tenho controle
sobre essa decisão.

193
00:10:48,750 --> 00:10:51,670
>> Mas a partir de cada um daqueles
possíveis posições de tabuleiro,

194
00:10:51,670 --> 00:10:54,020
há então um outro
conjunto de possibilidades.

195
00:10:54,020 --> 00:10:56,700
Quando se trata de ser
minha vez novamente, eu faria

196
00:10:56,700 --> 00:11:01,500
começa a escolher e dizer, bem,
O se move para o bem,

197
00:11:01,500 --> 00:11:06,110
o ponto médio do lado esquerdo, em seguida,
Eu tenho um conjunto de possibilidades

198
00:11:06,110 --> 00:11:09,740
onde eu possa tomar o meu próximo passo.

199
00:11:09,740 --> 00:11:14,140
Desses, eu poderia considerar todos
as possibilidades debaixo deles.

200
00:11:14,140 --> 00:11:18,030
E, em seguida, O obteria
para escolher entre aqueles.

201
00:11:18,030 --> 00:11:22,290
>> E eu poderia continuar a construir esta
árvore até que eu cheguei ao ponto

202
00:11:22,290 --> 00:11:26,960
onde quer alguém
ganha o que é game--

203
00:11:26,960 --> 00:11:31,070
tem que ser considerada uma folha node--
ou o conselho está completamente cheio

204
00:11:31,070 --> 00:11:32,704
e ninguém ganhou.

205
00:11:32,704 --> 00:11:34,370
E isso também vai ser um nó folha.

206
00:11:34,370 --> 00:11:35,411
Isso vai ser um empate.

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

208
00:11:37,820 --> 00:11:41,680
>> Mas a coisa complicada com isto é
se isso fosse apenas uma pesquisa regular

209
00:11:41,680 --> 00:11:44,269
problema, eu seria capaz de
digamos, bem, X deve ir aqui.

210
00:11:44,269 --> 00:11:45,560
E O caminho deve ir para lá.

211
00:11:45,560 --> 00:11:46,770
E então X deve ir aqui.

212
00:11:46,770 --> 00:11:48,269
E, em seguida, deve ir O caminho até lá.

213
00:11:48,269 --> 00:11:51,860
E então X pode obter três
em uma fila, e eu ganhar.

214
00:11:51,860 --> 00:11:54,870
E o jogo seria mais
em cinco movimentos, três para mim,

215
00:11:54,870 --> 00:11:57,710
dois para o meu adversário.

216
00:11:57,710 --> 00:12:01,300
Mas eu nem sempre consegue escolher isso.

217
00:12:01,300 --> 00:12:03,720
>> Então, em vez disso, o que nós somos
vai ter que fazer

218
00:12:03,720 --> 00:12:06,270
é que nós vamos ter
para ter uma nova estratégia.

219
00:12:06,270 --> 00:12:09,350
E que a estratégia
algoritmos jogo-playing costumam usar

220
00:12:09,350 --> 00:12:12,000
é o que é chamado minimax.

221
00:12:12,000 --> 00:12:15,500
A idéia central do
minimax é que nós somos

222
00:12:15,500 --> 00:12:21,365
vai escolher o movimento que dá
o nosso adversário o pior conjunto possível

223
00:12:21,365 --> 00:12:22,790
de movimentos que eles podem fazer.

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

225
00:12:25,570 --> 00:12:28,870
Não me faz nenhum bem
para escolher um movimento onde

226
00:12:28,870 --> 00:12:31,952
Eu poderia ser capaz de vencer depois
que, porque o meu adversário não é

227
00:12:31,952 --> 00:12:33,160
vai me dar essa chance.

228
00:12:33,160 --> 00:12:37,770
Eles vão escolher alguns
resultado terrível para mim.

229
00:12:37,770 --> 00:12:42,010
Então eu vou fazer o
mova que força o meu adversário

230
00:12:42,010 --> 00:12:45,760
para fazer algo melhor para mim.

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

232
00:12:46,260 --> 00:12:48,410
Vamos ver como isso se desenrola.

233
00:12:48,410 --> 00:12:51,640
Então aqui está o nosso algoritmo em pseudocódigo.

234
00:12:51,640 --> 00:12:54,450
Nós estamos indo para gerar
toda a árvore de jogo.

235
00:12:54,450 --> 00:12:56,757
Nós vamos construir
toda a estrutura.

236
00:12:56,757 --> 00:12:57,840
E então nós vamos passar.

237
00:12:57,840 --> 00:13:02,100
E mesmo no fundo em cada um dos
nós terminais, em cada uma das folhas,

238
00:13:02,100 --> 00:13:07,850
vamos avaliar como
valioso é que para mim?

239
00:13:07,850 --> 00:13:11,690
E nós estamos indo para as coisas de valor que
são bons para mim como sendo positivo.

240
00:13:11,690 --> 00:13:14,460
As coisas que não são boas para mim
vai ser menos positivo ou zero,

241
00:13:14,460 --> 00:13:16,480
ou mesmo negativo.

242
00:13:16,480 --> 00:13:19,240
>> Assim, em tic-tac-toe, talvez
uma vitória para mim é bom.

243
00:13:19,240 --> 00:13:20,290
Essa é uma pergunta.

244
00:13:20,290 --> 00:13:22,400
E um empate é zero.

245
00:13:22,400 --> 00:13:26,230
E algo que é uma perda para
me, talvez isso é uma negativa.

246
00:13:26,230 --> 00:13:29,620
Tudo o que importa é que o melhor
é para mim, quanto maior a pontuação

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

248
00:13:32,160 --> 00:13:36,690
A partir destas possibilidades no
fundo, então vamos filtrar para cima.

249
00:13:36,690 --> 00:13:40,650
E quando é a minha chance de escolher
entre um conjunto de alternativas,

250
00:13:40,650 --> 00:13:44,460
Eu vou escolher o que é
obteve a maior pontuação.

251
00:13:44,460 --> 00:13:47,200
>> E sempre que ele é meu
oponentes virar para escolher,

252
00:13:47,200 --> 00:13:52,350
Eu vou assumir que eles estão indo para
escolher aquele com a pontuação mais baixa.

253
00:13:52,350 --> 00:13:56,090
E se eu fizer isso todo o caminho
até o topo da árvore,

254
00:13:56,090 --> 00:14:03,150
Vou ter escolhido um caminho que dá
me o melhor resultado que eu possa obter,

255
00:14:03,150 --> 00:14:09,110
assumindo que o meu adversário
faz todos os movimentos certos.

256
00:14:09,110 --> 00:14:11,940
>> Tudo bem, então vamos ver
isso em ação pela primeira vez.

257
00:14:11,940 --> 00:14:14,980
E então nós vamos realmente
olhar para o código para ele.

258
00:14:14,980 --> 00:14:16,780
Então imagine eu tenho este grande árvore.

259
00:14:16,780 --> 00:14:18,280
E agora eu não estou jogando tic-tac-toe.

260
00:14:18,280 --> 00:14:20,405
Eu queria dar-lhe
algo um pouco mais rico.

261
00:14:20,405 --> 00:14:23,560
Então, eu tenho um pouco de jogo onde
há muitas pontuações diferentes

262
00:14:23,560 --> 00:14:26,390
que eu poderia ter no final.

263
00:14:26,390 --> 00:14:27,980
E assim eu construir essa árvore completa.

264
00:14:27,980 --> 00:14:29,070
E eu começo a mover em primeiro lugar.

265
00:14:29,070 --> 00:14:31,290
Eu sou a raiz da árvore.

266
00:14:31,290 --> 00:14:36,150
>> E eu começar a escolher isso-- isso fico
para maximizar através daquele primeiro nó.

267
00:14:36,150 --> 00:14:38,410
E então meu adversário tem que ir.

268
00:14:38,410 --> 00:14:41,910
E então eu tenho que ir mais uma vez.

269
00:14:41,910 --> 00:14:46,830
Assim, na parte inferior, eu tenho um conjunto de
possibilidades que eu posso escolher,

270
00:14:46,830 --> 00:14:50,570
diferentes estados terminais do jogo.

271
00:14:50,570 --> 00:14:54,980
Se eu estou para baixo em que
extrema esquerda canto,

272
00:14:54,980 --> 00:14:58,867
e eu ver que eu tenho uma escolha
entre um e oito, sete, e um dois,

273
00:14:58,867 --> 00:15:00,450
bem, eu sou o único que começa a escolher.

274
00:15:00,450 --> 00:15:02,910
Então, eu estou indo para escolher
o melhor das pessoas.

275
00:15:02,910 --> 00:15:05,650
Eu vou escolher o oito.

276
00:15:05,650 --> 00:15:10,090
>> Então eu sei que se eu
descer a esse ponto,

277
00:15:10,090 --> 00:15:13,890
Eu vou ser capaz de conseguir que os oito pontos.

278
00:15:13,890 --> 00:15:17,410
Se eu acabar no próximo ponto
sobre, sobre o próximo nó,

279
00:15:17,410 --> 00:15:20,760
um nove, um, ou um seis, bem, eu sou
vai escolher a melhor delas.

280
00:15:20,760 --> 00:15:21,950
Eu vou escolher a nove.

281
00:15:21,950 --> 00:15:24,880
Se eu tiver uma escolha entre
dois e quatro, e um,

282
00:15:24,880 --> 00:15:28,240
Eu vou escolher a quatro, o mais alto.

283
00:15:28,240 --> 00:15:31,990
>> Agora, se eu olhar para o nível
acima disso, meu adversário

284
00:15:31,990 --> 00:15:34,440
é o que se tem de fazer essa escolha.

285
00:15:34,440 --> 00:15:37,040
Então, o meu adversário começa a
escolher, eu gostaria de dar-lhe

286
00:15:37,040 --> 00:15:39,250
a única coisa que está acontecendo
para tirá-lo oito pontos,

287
00:15:39,250 --> 00:15:41,916
ou eu dar-lhe a coisa que é
vai dar-lhe nove pontos,

288
00:15:41,916 --> 00:15:45,240
ou a coisa que está acontecendo
para dar-lhe quatro pontos?

289
00:15:45,240 --> 00:15:49,130
E o meu adversário, sendo
racional, vai

290
00:15:49,130 --> 00:15:53,470
escolher o mínimo daqueles,
vai escolher a quatro.

291
00:15:53,470 --> 00:15:56,020
>> E eu posso fazer isso
através de toda a árvore.

292
00:15:56,020 --> 00:15:59,110
Eu posso ir para baixo para que
conjunto do meio de três.

293
00:15:59,110 --> 00:16:01,517
E eu posso escolher entre
um, três, e cinco.

294
00:16:01,517 --> 00:16:02,350
E eu começar a escolher.

295
00:16:02,350 --> 00:16:03,810
Então eu escolher um de cinco.

296
00:16:03,810 --> 00:16:05,340
Posso escolher três, nove, ou dois.

297
00:16:05,340 --> 00:16:07,570
Eu começar a escolher, então eu escolher o nove.

298
00:16:07,570 --> 00:16:09,290
Seis, cinco, ou dois, eu escolho.

299
00:16:09,290 --> 00:16:11,539
Eu começar a escolher a seis.

300
00:16:11,539 --> 00:16:13,080
Nível acima do que, quem começa a escolher?

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

302
00:16:16,280 --> 00:16:18,140
Quem começa a escolher?

303
00:16:18,140 --> 00:16:20,000
O outro cara, o meu adversário.

304
00:16:20,000 --> 00:16:22,583
Então, eles escolher cinco,
nove, ou seis, qual?

305
00:16:22,583 --> 00:16:23,410
>> AUDIÊNCIA: A cinco.

306
00:16:23,410 --> 00:16:25,250
>> COLUNA: Eles escolhem a cinco.

307
00:16:25,250 --> 00:16:27,400
Começam a escolher o mínimo.

308
00:16:27,400 --> 00:16:29,690
E, em seguida, o último,
escolher um, dois, ou três.

309
00:16:29,690 --> 00:16:31,720
Eu começar a escolher, então eu escolher três.

310
00:16:31,720 --> 00:16:34,370
Nove, sete, ou dois, eu escolho nove.

311
00:16:34,370 --> 00:16:37,070
E 11, seis, ou quatro, eu escolher 11.

312
00:16:37,070 --> 00:16:41,190
Meu oponente em seguida, escolhe três,
nove, ou 11, escolhe o mínimo.

313
00:16:41,190 --> 00:16:43,290
Ele me dá um três.

314
00:16:43,290 --> 00:16:47,780
E, finalmente, na parte superior da
a árvore, eu começar a escolher novamente.

315
00:16:47,780 --> 00:16:51,190
E eu começar a escolher entre
quatro, cinco, ou três.

316
00:16:51,190 --> 00:16:52,270
Então eu levo a cinco.

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

318
00:16:55,070 --> 00:17:00,891
>> Se eu tenho que controlar tudo, eu
tomar o caminho que levou ao 11.

319
00:17:00,891 --> 00:17:02,390
Mas eu não conseguir fazer essa escolha.

320
00:17:02,390 --> 00:17:04,220
Se eu ir por esse caminho.

321
00:17:04,220 --> 00:17:10,710
Meu oponente vai me forçar a
a escolha que conduz a um de três.

322
00:17:10,710 --> 00:17:14,530
Então, o melhor que eu posso fazer é
para dar esse ramo meio,

323
00:17:14,530 --> 00:17:19,859
fazer essa escolha é que, eventualmente,
vai me levar a cinco pontos.

324
00:17:19,859 --> 00:17:23,230
Isso é o que faz minimax.

325
00:17:23,230 --> 00:17:23,807
>> Tudo certo.

326
00:17:23,807 --> 00:17:24,890
Vamos dar uma olhada nisso.

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

328
00:17:27,480 --> 00:17:32,330
Então, aqui no CS50
IDE é um programa que

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

330
00:17:36,540 --> 00:17:40,100
Nós vamos construir
-se uma representação.

331
00:17:40,100 --> 00:17:44,390
Nós vamos ter dois opponent--
ou dois jogadores, o nosso computador

332
00:17:44,390 --> 00:17:46,090
jogador e um jogador humano.

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

334
00:17:48,980 --> 00:17:53,090
O jogador número um vai jogar
o O. Isso vai ser o jogador máquina.

335
00:17:53,090 --> 00:17:55,747
Começam a se mover segundo.

336
00:17:55,747 --> 00:17:57,830
E o outro jogador, o nosso
jogador humano, será X.

337
00:17:57,830 --> 00:17:59,880
>> E para tornar minha vida um
pouco simples, eu vou

338
00:17:59,880 --> 00:18:03,060
rotular esse jogador um negativo.

339
00:18:03,060 --> 00:18:05,026
Então eu só posso multiplicar
por um negativo para trocar

340
00:18:05,026 --> 00:18:06,400
entre um e o outro jogador.

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

342
00:18:09,030 --> 00:18:12,250
Tudo bem, então vamos dar uma olhada
o que na verdade estamos indo fazer.

343
00:18:12,250 --> 00:18:15,840
Nós vamos definir o nosso conselho.

344
00:18:15,840 --> 00:18:19,060
Vai ser, bem, nós vamos
para permitir que ele seja três por três,

345
00:18:19,060 --> 00:18:21,580
ou podemos até mesmo jogar
cinco por cinco ou sete

346
00:18:21,580 --> 00:18:28,870
por sete tic-tac-dedo do pé se você
como, com base em alguma dimensão D.

347
00:18:28,870 --> 00:18:31,260
>> E nós vamos ter um casal
de funções auxiliares

348
00:18:31,260 --> 00:18:34,360
que vai fazer coisas como
inicializar o screen-- ou desculpe,

349
00:18:34,360 --> 00:18:38,900
inicializar nossas variáveis, desmarque a
tela, chamar a bordo na tela,

350
00:18:38,900 --> 00:18:41,060
um que verifica uma placa
para ver se ou não

351
00:18:41,060 --> 00:18:44,520
há um vencedor, aquele que
analisa através da linha de comando,

352
00:18:44,520 --> 00:18:50,670
apenas para ajudar, aquele que lê em
entrada, e uma função chamada minimax.

353
00:18:50,670 --> 00:18:52,746
E isso é o que
vamos mais gosta.

354
00:18:52,746 --> 00:18:54,120
Mas vamos olhar primeiro para o principal.

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

356
00:18:57,490 --> 00:18:58,510
>> O que nós fazemos?

357
00:18:58,510 --> 00:19:00,570
Bem, vamos
analisar a linha de comando,

358
00:19:00,570 --> 00:19:04,300
acabou de ler e ver o que
placa de dimensão que nós gostaríamos de ter.

359
00:19:04,300 --> 00:19:07,330
Vamos iniciar o nosso conselho.

360
00:19:07,330 --> 00:19:10,360
E então nós vamos entrar em um
grande laço selvagem, repetidamente

361
00:19:10,360 --> 00:19:16,630
aceitar se move até que o jogo é
ganhou, ou não há nenhum movimento à esquerda.

362
00:19:16,630 --> 00:19:20,560
Cada vez que passar por isso
loop, vamos limpar a tela.

363
00:19:20,560 --> 00:19:23,290
Vamos chamar a bordo na tela.

364
00:19:23,290 --> 00:19:28,750
E nós estamos deliberadamente tipo de
abstraindo estes afastado como sub-rotinas,

365
00:19:28,750 --> 00:19:32,030
de modo que não temos que se preocupar muito
sobre os detalhes de como eles acontecem.

366
00:19:32,030 --> 00:19:33,480
>> Você vai ter o código mais tarde hoje.

367
00:19:33,480 --> 00:19:37,970
E se você quiser olhar através
e descobrir, você pode vê-los todos.

368
00:19:37,970 --> 00:19:39,890
Mas nós vamos desenhar uma placa na tela.

369
00:19:39,890 --> 00:19:43,620
E então nós vamos verificar e
ver, temos um vencedor?

370
00:19:43,620 --> 00:19:46,290
Alguém ganhou este jogo?

371
00:19:46,290 --> 00:19:49,260
Se eles têm, vamos imprimir
uma mensagem de vitória.

372
00:19:49,260 --> 00:19:51,680
E nós vamos terminar o jogo.

373
00:19:51,680 --> 00:19:54,510
>> Também vamos verificar e
ver se há um empate.

374
00:19:54,510 --> 00:19:56,620
Vai ser fácil para ver se há um empate.

375
00:19:56,620 --> 00:20:00,700
Isto significa que todos os espaços são cheios,
mas não houve ainda um vencedor.

376
00:20:00,700 --> 00:20:03,580
Podemos declarar um empate e ser feito.

377
00:20:03,580 --> 00:20:10,530
Em seguida, o verdadeiro se meat--
é um jogador de máquina,

378
00:20:10,530 --> 00:20:14,120
vamos permitir que
jogador máquina para pesquisa

379
00:20:14,120 --> 00:20:19,500
através da utilização deste algoritmo minimax,
para encontrar a melhor jogada que ele pode.

380
00:20:19,500 --> 00:20:22,310
E então nós vamos colocar esse movimento para cima.

381
00:20:22,310 --> 00:20:27,640
>> Caso contrário, se é um jogador humano,
leremos alguma entrada do humano.

382
00:20:27,640 --> 00:20:30,800
E então se é o humano
jogador ou o jogador máquina,

383
00:20:30,800 --> 00:20:32,800
vamos fazer um par pouco
bits de verificação de erros,

384
00:20:32,800 --> 00:20:36,910
garantir que se mantém dentro dos limites
das dimensões reais do bordo

385
00:20:36,910 --> 00:20:40,040
que temos, certifique-
que é que o espaço vazio,

386
00:20:40,040 --> 00:20:43,570
que ninguém colocar uma
peça já estava lá.

387
00:20:43,570 --> 00:20:45,810
E então nós vamos apenas colocar
uma peça no tabuleiro,

388
00:20:45,810 --> 00:20:51,550
alterar o jogador para a camada seguinte, e
incrementar quantos movimentos ter acontecido.

389
00:20:51,550 --> 00:20:54,090
>> Esse é o principal laço para
o nosso jogo tic-tac-toe.

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

391
00:20:57,000 --> 00:21:02,340
Minimax, então, é exatamente
o algoritmo que antes.

392
00:21:02,340 --> 00:21:04,710
O único ajuste que
nós fizemos, para que possamos

393
00:21:04,710 --> 00:21:07,290
pode desempenhar maior
placas dimensionais é que nós temos

394
00:21:07,290 --> 00:21:11,070
mantido esse parâmetro extra chamado profundidade.

395
00:21:11,070 --> 00:21:14,870
E profundidade apenas diz, se eu sou
procura para baixo através daquela árvore

396
00:21:14,870 --> 00:21:19,022
e eu fico tão longe para baixo
além de algum nível de profundidade

397
00:21:19,022 --> 00:21:20,730
que eu só não quero
para ir mais longe,

398
00:21:20,730 --> 00:21:25,630
Eu vou parar e apenas
avaliar a bordo naquele ponto.

399
00:21:25,630 --> 00:21:27,310
Vou verificar e ver se há um vencedor.

400
00:21:27,310 --> 00:21:29,240
Se houver um vencedor, eu devolvê-los.

401
00:21:29,240 --> 00:21:31,720
Caso contrário, eu vou passar por um loop.

402
00:21:31,720 --> 00:21:34,380
E eu vou dizer, para todos
as possíveis localizações

403
00:21:34,380 --> 00:21:38,080
que eu poderia possivelmente
tomar como minha mudança, eu vou

404
00:21:38,080 --> 00:21:43,760
construir uma placa hipotética que
inclui a minha jogada em que o conselho,

405
00:21:43,760 --> 00:21:45,960
e, em seguida, chama recursivamente minimax.

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

407
00:21:49,360 --> 00:21:53,900
>> Se é a minha jogada, eu tenho que encontrar o
aquele que tem a maior pontuação.

408
00:21:53,900 --> 00:21:58,710
Se é movimento do meu oponente, encontramos
aquele que tem a pontuação mínima.

409
00:21:58,710 --> 00:22:02,240
E tudo o resto é
mantendo apenas registro.

410
00:22:02,240 --> 00:22:04,789
Tudo bem, então vamos ver esta corrida.

411
00:22:04,789 --> 00:22:06,830
Na verdade, talvez o que pudermos
obter um par de voluntários

412
00:22:06,830 --> 00:22:09,930
para vir e jogar tic-tac-toe.

413
00:22:09,930 --> 00:22:12,780
[Inaudível] um, e um
mais, dois, ali mesmo.

414
00:22:12,780 --> 00:22:13,550
Vamos lá para cima.

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

416
00:22:19,290 --> 00:22:23,650
>> Então, vamos em frente e
reinicie esta completamente.

417
00:22:23,650 --> 00:22:24,150
Então, oi.

418
00:22:24,150 --> 00:22:24,920
>> AUDIÊNCIA: Oi.

419
00:22:24,920 --> 00:22:25,420
>> COLUNA: Qual é o seu nome?

420
00:22:25,420 --> 00:22:26,086
>> AUDIÊNCIA: Gorav.

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

422
00:22:26,840 --> 00:22:27,800
>> AUDIÊNCIA: Eu sou Layla.

423
00:22:27,800 --> 00:22:29,490
>> Orador: E Layla, e Layla, desculpe.

424
00:22:29,490 --> 00:22:30,384
Vamos lá para cima.

425
00:22:30,384 --> 00:22:32,050
Gorav, nós vamos ter de ir primeiro.

426
00:22:32,050 --> 00:22:37,710
E eu vou pedir-lhe para ser um não
terrivelmente bom jogador tic-tac-toe.

427
00:22:37,710 --> 00:22:40,130
OK, então toda a pressão está fora em você.

428
00:22:40,130 --> 00:22:44,660
Vamos ver, porém, que a nossa máquina
jogador pode realmente fazer alguma coisa inteligente.

429
00:22:44,660 --> 00:22:45,310
Então vá em frente.

430
00:22:45,310 --> 00:22:49,830
Você vai digitar em que coordenam
você gostaria de colocar o seu X in.

431
00:22:49,830 --> 00:22:55,170
A0, OK, ea máquina tem ido
imediatamente e colocar sua marca na A1.

432
00:22:55,170 --> 00:22:56,640
>> Coloque a O no tabuleiro.

433
00:22:56,640 --> 00:22:58,970
Tudo bem, agora vá em frente.

434
00:22:58,970 --> 00:23:00,193
Onde você gostaria de ir?

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
Nosso jogador máquina tomou
o quadrado do meio, bloqueou você.

438
00:23:08,430 --> 00:23:10,320
Então isso foi uma boa,
coisa inteligente para que ele faça.

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

440
00:23:13,430 --> 00:23:14,250
Você bloqueou.

441
00:23:14,250 --> 00:23:15,210
Isso é excelente.

442
00:23:15,210 --> 00:23:16,390
Ele marca o canto lá.

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

444
00:23:23,890 --> 00:23:30,430
>> E ele vai forçá-lo a
tomar o último espaço, B0.

445
00:23:30,430 --> 00:23:32,220
E o jogo termina em empate.

446
00:23:32,220 --> 00:23:35,030
Mas teve um razoável
jogo contra você, certo?

447
00:23:35,030 --> 00:23:36,956
Tudo bem, muito obrigado, Gorav.

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

449
00:23:40,860 --> 00:23:44,723
>> Tudo bem, Layla, vamos
o jogo em você aqui.

450
00:23:44,723 --> 00:23:46,940
>> AUDIÊNCIA: Oh, ótimo.

451
00:23:46,940 --> 00:23:49,950
>> COLUNA: Nós estamos indo dar-
você quatro por quatro tic-tac-toe.

452
00:23:49,950 --> 00:23:54,760
Agora, em quatro por quatro, você tem que ganhar
com quatro em uma fileira, e não três em uma fileira.

453
00:23:54,760 --> 00:23:56,135
E é toda sua.

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

455
00:24:02,180 --> 00:24:04,420
Assim Layla levou D1.

456
00:24:04,420 --> 00:24:11,730
Estamos indo para seguir
nosso jogador do computador aqui.

457
00:24:11,730 --> 00:24:16,910
Três por três tic-tac-toe é o tipo
de coisa que é fácil para todos nós.

458
00:24:16,910 --> 00:24:21,960
Mas ainda é bom ver o
jogador do computador fazendo movimentos inteligentes.

459
00:24:21,960 --> 00:24:23,725
Quatro por quatro começa a
ser um pouco mais complicado.

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

461
00:24:42,960 --> 00:24:44,230
>> Bem feito.

462
00:24:44,230 --> 00:24:46,210
Tudo bem, então Layla do finalizou.

463
00:24:46,210 --> 00:24:48,270
Oh, e devemos ter terminado ali.

464
00:24:48,270 --> 00:24:51,870
Mas vamos fazer mais uma aqui.

465
00:24:51,870 --> 00:24:53,480
Então, Layla, obrigado.

466
00:24:53,480 --> 00:24:55,112
Bem feito.

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

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

469
00:25:00,410 --> 00:25:04,750
>> Assim, o nosso jogador tic-tac-toe vai
e através encontra locais,

470
00:25:04,750 --> 00:25:07,040
resolve-los usando este minimax.

471
00:25:07,040 --> 00:25:08,990
E eu tinha uma configuração de profundidade
em que, para que ele

472
00:25:08,990 --> 00:25:11,010
não iria correr muito rápido,
que é provavelmente porque

473
00:25:11,010 --> 00:25:16,790
Layla foi capaz de ir bem em frente
como ela fez, e fez muito bem.

474
00:25:16,790 --> 00:25:20,450
Mas esses sistemas que apenas
passar e força bruta

475
00:25:20,450 --> 00:25:23,870
ir mais fundo e mais profundo, e mais profundo,
e manter a encontrar a solução

476
00:25:23,870 --> 00:25:29,890
que eles precisam, esses tipos de sistemas
são bastante bem-sucedido para estes, bem,

477
00:25:29,890 --> 00:25:32,700
jogos de tabuleiro padrão.

478
00:25:32,700 --> 00:25:37,060
>> E, de fato, se olharmos para um
três por três jogo tic-tac-toe,

479
00:25:37,060 --> 00:25:40,040
este é basicamente um problema resolvido.

480
00:25:40,040 --> 00:25:45,430
E este é um diagrama maravilhoso
Randall Munroe de XKCD em,

481
00:25:45,430 --> 00:25:52,130
mostrando qual você deve se mover
tomar, dada movimentos do seu oponente.

482
00:25:52,130 --> 00:25:56,420
Isso é algo que pudéssemos
facilmente especificar antes do tempo.

483
00:25:56,420 --> 00:26:00,180
Mas o que acontece quando chegarmos a mais
jogos complexos, jogos mais complicados,

484
00:26:00,180 --> 00:26:05,690
onde existem placas maiores, mais
possibilidades, a estratégia mais profunda?

485
00:26:05,690 --> 00:26:09,660
>> Acontece que este
força bruta procura ainda

486
00:26:09,660 --> 00:26:14,150
faz razoavelmente bem, excepto
quando você chegar ao ponto

487
00:26:14,150 --> 00:26:19,230
onde a árvore é tão grande
que você não pode representar tudo.

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

489
00:26:22,370 --> 00:26:28,280
Quando você não pode calcular toda a árvore,
quando você não pode ir para a frente e empurre

490
00:26:28,280 --> 00:26:32,204
-se para o ponto onde você tem
começado a árvore inteira na memória,

491
00:26:32,204 --> 00:26:34,370
ou se você pode obtê-lo
na memória e ela só vai

492
00:26:34,370 --> 00:26:39,200
levá-lo muito tempo para pesquisar
-lo, você tem que fazer algo mais inteligente.

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

494
00:26:42,620 --> 00:26:46,450
>> A fim de fazer isso, você
tem que fazer duas coisas.

495
00:26:46,450 --> 00:26:49,030
Primeiro, você tem que encontrar algum
forma de limitar a sua profundidade.

496
00:26:49,030 --> 00:26:50,370
Bem, isso é OK.

497
00:26:50,370 --> 00:26:55,740
Podemos encontrar algumas agradáveis, mínimo
e dizer, você só pode ir tão fundo.

498
00:26:55,740 --> 00:27:00,890
Mas quando você faz isso, isso significa que você
ter estas placas parcialmente incompletos.

499
00:27:00,890 --> 00:27:04,770
E você tem que escolher, eu gosto
esta placa parcialmente incompleta,

500
00:27:04,770 --> 00:27:08,600
ou esta placa parcialmente incompleta?

501
00:27:08,600 --> 00:27:11,910
>> E em nossos quatro por
quatro jogo tic-tac-toe,

502
00:27:11,910 --> 00:27:15,240
nosso jogador do computador desceu
para a parte inferior e disse,

503
00:27:15,240 --> 00:27:16,800
Eu tenho duas placas diferentes.

504
00:27:16,800 --> 00:27:17,940
Nenhum dos dois é uma vitória.

505
00:27:17,940 --> 00:27:19,120
Nenhum dos dois é uma perda.

506
00:27:19,120 --> 00:27:22,070
Nenhum dos dois é um empate.

507
00:27:22,070 --> 00:27:24,100
Como posso escolher entre eles?

508
00:27:24,100 --> 00:27:26,200
E ele não tinha uma
forma inteligente de fazer isso.

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

510
00:27:28,910 --> 00:27:32,850
>> Vemos esse tipo de
avaliação acontecem o tempo todo

511
00:27:32,850 --> 00:27:35,290
como nós entrar em jogos mais complexos.

512
00:27:35,290 --> 00:27:37,600
O xadrez é um grande exemplo.

513
00:27:37,600 --> 00:27:41,550
No xadrez, temos, em primeiro lugar
de tudo, uma placa de maior.

514
00:27:41,550 --> 00:27:43,370
Nós temos muito mais peças.

515
00:27:43,370 --> 00:27:47,930
E o posicionamento destas peças
e da maneira que essas peças se movem

516
00:27:47,930 --> 00:27:50,370
é criticamente importante.

517
00:27:50,370 --> 00:27:53,700
Então, se eu quiser usar minimax,
Eu preciso ser capaz de especificar

518
00:27:53,700 --> 00:27:58,240
e dizer, esta placa, onde
ninguém ganhou ou perdeu, no entanto,

519
00:27:58,240 --> 00:28:04,310
é de alguma forma melhor do que este outro
placa, onde ninguém ganhou ou perdeu.

520
00:28:04,310 --> 00:28:06,740
>> Para fazer isso, eu poderia fazê-
coisas como eu poderia apenas

521
00:28:06,740 --> 00:28:10,787
contar quantas peças que eu tenho
e quantas peças você tem?

522
00:28:10,787 --> 00:28:12,870
Ou eu poderia dar diferente
peças pontos diferentes.

523
00:28:12,870 --> 00:28:14,420
Minha rainha vale 20 pontos.

524
00:28:14,420 --> 00:28:16,500
Seu peão vale um ponto.

525
00:28:16,500 --> 00:28:18,920
Quem tem mais pontos no total?

526
00:28:18,920 --> 00:28:22,300
Ou eu poderia considerar coisas como:
quem tem o melhor posição do tabuleiro?

527
00:28:22,300 --> 00:28:26,820
Quem é a vez seguinte,
qualquer coisa que eu puder

528
00:28:26,820 --> 00:28:31,220
não para avaliar com mais precisão
qual destas possibilidades

529
00:28:31,220 --> 00:28:34,660
é melhor sem
considerando exaustivamente

530
00:28:34,660 --> 00:28:36,565
cada movimento que poderia vir depois disso.

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

532
00:28:39,740 --> 00:28:45,130
>> Agora, para fazer esse trabalho,
uma das coisas que é

533
00:28:45,130 --> 00:28:48,680
vai se tornar realmente importante
para nós não é apenas se movendo em linha reta

534
00:28:48,680 --> 00:28:53,720
até uma determinada profundidade
limite, mas ser capaz de dizer:

535
00:28:53,720 --> 00:28:59,380
uma dessas idéias que eu
têm é tão ruim que é

536
00:28:59,380 --> 00:29:02,280
não vale a pena considerar
todas as formas possíveis

537
00:29:02,280 --> 00:29:06,680
que as coisas podem ir de mal a pior.

538
00:29:06,680 --> 00:29:12,760
Para fazer isso, vamos adicionar em minimax
um princípio chamado alph-beta.

539
00:29:12,760 --> 00:29:16,340
E alfa-beta diz,
se você tiver uma má idéia,

540
00:29:16,340 --> 00:29:22,840
não perca seu tempo tentando
descobrir exatamente como é ruim.

541
00:29:22,840 --> 00:29:24,990
>> Então aqui está o que vamos fazer.

542
00:29:24,990 --> 00:29:28,620
Nós vamos ter a mesma
princípios que tínhamos antes,

543
00:29:28,620 --> 00:29:32,200
o mesmo tipo minimax
de pesquisa, só nós somos

544
00:29:32,200 --> 00:29:37,570
vai acompanhar, não só do
valores reais de que dispomos, mas vamos

545
00:29:37,570 --> 00:29:41,440
acompanhar o melhor possível
valor que eu poderia chegar,

546
00:29:41,440 --> 00:29:45,700
eo pior possível
resultado que eu poderia ter.

547
00:29:45,700 --> 00:29:50,470
E qualquer momento o pior possível
coisa é olhar provável,

548
00:29:50,470 --> 00:29:52,694
Eu vou abandonar essa parte da árvore.

549
00:29:52,694 --> 00:29:54,610
E eu não vou incomodar mesmo
olhando para ele anymore.

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

551
00:29:57,680 --> 00:30:02,600
>> Tudo bem, então imagine que comecemos
com esta mesma árvore jogo exato.

552
00:30:02,600 --> 00:30:05,200
E agora nós estamos indo para ir
de novo, todo o caminho

553
00:30:05,200 --> 00:30:07,200
para que canto inferior esquerdo.

554
00:30:07,200 --> 00:30:11,180
E nesse canto inferior esquerdo canto, nós
olhar e avaliamos esta placa.

555
00:30:11,180 --> 00:30:15,700
Talvez seja um quatro por quatro tic-tac-toe
placa, ou talvez é um tabuleiro de xadrez.

556
00:30:15,700 --> 00:30:18,620
Mas olhamos para ele, e nós avaliamos
-lo, e nós temos um valor de oito.

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

558
00:30:22,290 --> 00:30:28,030
>> Nesse ponto, sabemos que
nós estamos indo para obter, pelo menos,

559
00:30:28,030 --> 00:30:32,380
oito pontos de esta decisão inferior.

560
00:30:32,380 --> 00:30:36,620
Não importa o que o outro
dois são, que sete e que dois.

561
00:30:36,620 --> 00:30:38,580
Eles poderiam ser quaisquer valores
eles queriam ser.

562
00:30:38,580 --> 00:30:41,279
Nós vamos chegar a
menos oito pontos.

563
00:30:41,279 --> 00:30:43,070
Tudo bem, mas poderíamos
vá em frente e confira.

564
00:30:43,070 --> 00:30:45,080
Talvez um deles é melhor do que oito.

565
00:30:45,080 --> 00:30:46,000
>> Nós olhamos para o sete.

566
00:30:46,000 --> 00:30:46,910
Está melhor do que oito?

567
00:30:46,910 --> 00:30:48,680
Não, isso não muda
nossa opinião em tudo.

568
00:30:48,680 --> 00:30:49,460
Nós olhamos para os dois.

569
00:30:49,460 --> 00:30:50,543
Está melhor do que oito?

570
00:30:50,543 --> 00:30:52,580
Não, isso não muda
nossa opinião em tudo.

571
00:30:52,580 --> 00:30:55,480
Portanto, agora sabemos que já esgotou
todas as possibilidades lá.

572
00:30:55,480 --> 00:30:58,330
Nós não estamos indo para chegar
nada melhor do que oito.

573
00:30:58,330 --> 00:31:01,310
Nós estamos indo para obter exatamente oito.

574
00:31:01,310 --> 00:31:03,825
>> E assim nós mudamos esse nó e
digamos, que é agora uma certeza.

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

576
00:31:07,010 --> 00:31:10,270
Nós subir um nível acima disso.

577
00:31:10,270 --> 00:31:13,820
E agora sabemos alguma coisa
sobre esse nível de minimização.

578
00:31:13,820 --> 00:31:18,560
Nós sabemos que nós nunca vamos chegar
mais de oito pontos se descemos

579
00:31:18,560 --> 00:31:20,910
nessa direção.

580
00:31:20,910 --> 00:31:22,980
Porque mesmo se os
outros dois ramos vir

581
00:31:22,980 --> 00:31:26,170
para ser fantástico e vale a pena
milhares de pontos, cada,

582
00:31:26,170 --> 00:31:31,666
o nosso adversário nos dará a
mínimo, e nos dá a oito.

583
00:31:31,666 --> 00:31:32,790
Tudo bem, bem, vamos ver.

584
00:31:32,790 --> 00:31:35,190
Vamos continuar por esse caminho.

585
00:31:35,190 --> 00:31:38,490
Descemos para que médio à esquerda.

586
00:31:38,490 --> 00:31:40,560
Olhamos para baixo e vemos que há um nove.

587
00:31:40,560 --> 00:31:45,590
Sabemos que vamos chegar
pelo menos nove pontos, indo para baixo

588
00:31:45,590 --> 00:31:47,720
que caminho do meio.

589
00:31:47,720 --> 00:31:52,110
E, neste ponto, podemos apenas fazer uma pausa.

590
00:31:52,110 --> 00:31:56,910
E podemos dizer, olha, eu
conhecer no nível acima,

591
00:31:56,910 --> 00:32:01,160
Eu estou indo para obter não mais do que oito
aponta para baixo, indo nesta direção.

592
00:32:01,160 --> 00:32:05,670
Mas se eu fui para o meio
caminho em vez do caminho da esquerda,

593
00:32:05,670 --> 00:32:08,980
Gostaria de obter pelo menos nove pontos.

594
00:32:08,980 --> 00:32:13,590
>> Meu oponente é nunca vai
deixe-me ir por esse caminho do meio.

595
00:32:13,590 --> 00:32:14,650
Começam a escolher.

596
00:32:14,650 --> 00:32:18,140
E eles estão indo para escolher o
caminho para a esquerda em direção a oito,

597
00:32:18,140 --> 00:32:23,650
em vez de no meio em direção
o que é, pelo menos, nove pontos.

598
00:32:23,650 --> 00:32:25,334
Então, nesse ponto, eu vou parar.

599
00:32:25,334 --> 00:32:26,500
E eu vou dizer, você sabe o quê?

600
00:32:26,500 --> 00:32:29,990
Eu não tenho que olhar para
mais baixo nessa direção.

601
00:32:29,990 --> 00:32:32,270
Porque eu nunca vou chegar lá.

602
00:32:32,270 --> 00:32:36,660
>> Eu posso ignorar que um,
e eu posso ignorar que seis,

603
00:32:36,660 --> 00:32:39,720
porque isso nunca vai acontecer.

604
00:32:39,720 --> 00:32:42,470
Então, eu vou descer e eu vou
Considere o seguinte possibilidade.

605
00:32:42,470 --> 00:32:44,830
Eu vou lá e digo, eu vejo um dois.

606
00:32:44,830 --> 00:32:47,125
Eu sei que se eu ficar aqui, eu sou
vai ficar pelo menos dois.

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

608
00:32:49,810 --> 00:32:50,470
ESTÁ BEM.

609
00:32:50,470 --> 00:32:51,520
I continuar.

610
00:32:51,520 --> 00:32:52,440
Eu vejo um quatro.

611
00:32:52,440 --> 00:32:54,920
Eu sei que estou indo para obter, pelo menos, quatro.

612
00:32:54,920 --> 00:32:57,200
Ainda há muito entre
quatro e oito, no entanto.

613
00:32:57,200 --> 00:32:58,454
Então eu continuo indo.

614
00:32:58,454 --> 00:32:59,870
Eu olho para baixo e vejo que há um.

615
00:32:59,870 --> 00:33:01,614
Tudo bem, eu sei que se
I ir por este caminho,

616
00:33:01,614 --> 00:33:03,280
Eu vou ser capaz de escolher o quatro.

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

618
00:33:06,540 --> 00:33:08,980
O que o meu adversário vai fazer?

619
00:33:08,980 --> 00:33:12,310
Entre algo que me dá
oito, algo que me dá quatro,

620
00:33:12,310 --> 00:33:14,730
e que algo
me dá, pelo menos, nove,

621
00:33:14,730 --> 00:33:17,550
bem, ele vai me dar quatro.

622
00:33:17,550 --> 00:33:20,110
E eu sei agora no
muito alto, eu vou

623
00:33:20,110 --> 00:33:23,145
para ser capaz de obter, pelo menos,
quatro pontos fora deste jogo.

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

625
00:33:27,030 --> 00:33:30,900
>> Toda a idéia de alfa-beta
é cortar partes da árvore para

626
00:33:30,900 --> 00:33:32,530
que eu não olhar para eles anymore.

627
00:33:32,530 --> 00:33:35,964
Mas ainda parece que eu estive
olhando para um monte da árvore.

628
00:33:35,964 --> 00:33:36,880
Vamos continuar indo para baixo.

629
00:33:36,880 --> 00:33:38,305
Vamos descer a próxima agora.

630
00:33:38,305 --> 00:33:39,680
Lá no fundo, eu encontrar um.

631
00:33:39,680 --> 00:33:41,030
Eu sei que estou indo para obter, pelo menos, um.

632
00:33:41,030 --> 00:33:41,690
Eu fico olhando.

633
00:33:41,690 --> 00:33:42,625
>> I encontrar um três.

634
00:33:42,625 --> 00:33:44,250
Eu sei que estou indo para obter, pelo menos, três.

635
00:33:44,250 --> 00:33:44,840
I continuar.

636
00:33:44,840 --> 00:33:45,660
I encontrar um cinco.

637
00:33:45,660 --> 00:33:49,760
Eu sei que estou indo para obter cinco
se eu descer nesse caminho.

638
00:33:49,760 --> 00:33:52,580
E eu também sei, em seguida,
que o meu adversário, se eu

639
00:33:52,580 --> 00:33:55,510
escolher o meio de
os três grandes escolhas,

640
00:33:55,510 --> 00:34:01,440
ele vai me dar
algo que é cinco ou menos.

641
00:34:01,440 --> 00:34:02,150
>> ESTÁ BEM.

642
00:34:02,150 --> 00:34:03,400
Eu posso continuar lá.

643
00:34:03,400 --> 00:34:06,470
Eu posso olhar para baixo e eu
pode-se dizer, o que eu vou

644
00:34:06,470 --> 00:34:08,239
de obter, se eu descer o caminho do meio?

645
00:34:08,239 --> 00:34:09,909
Eu estou indo para obter, assim, três lá.

646
00:34:09,909 --> 00:34:12,080
Eu estou indo para obter algo
que é pelo menos três.

647
00:34:12,080 --> 00:34:16,030
Ainda há coisas entre
três e cinco, então eu continue procurando.

648
00:34:16,030 --> 00:34:20,203
Oh, um nove, eu vou definitivamente
levar isso ao longo de um três.

649
00:34:20,203 --> 00:34:22,744
Eu estou indo para obter, pelo menos, nove
se eu for por esse caminho do meio.

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

651
00:34:25,530 --> 00:34:31,010
>> Agora o meu adversário pára e diz:
olhe, não há nenhum ponto anymore.

652
00:34:31,010 --> 00:34:33,669
Eu sei que o meu
minimização oponente, ele é

653
00:34:33,669 --> 00:34:36,210
vai me dar a coisa que é
menos do que ou igual a cinco,

654
00:34:36,210 --> 00:34:39,030
ao invés da coisa que é
maior do que ou igual a nove.

655
00:34:39,030 --> 00:34:39,530
Eu paro.

656
00:34:39,530 --> 00:34:40,779
Eu não olho mais para isso.

657
00:34:40,779 --> 00:34:43,280
I continuar.

658
00:34:43,280 --> 00:34:44,850
>> Eu olho para baixo em um presente.

659
00:34:44,850 --> 00:34:46,370
Até o fundo, eu acho um seis.

660
00:34:46,370 --> 00:34:50,040
Eu sei que estou indo para obter, pelo menos, seis.

661
00:34:50,040 --> 00:34:53,130
E o que eu posso fazer?

662
00:34:53,130 --> 00:34:54,877
Eu posso parar.

663
00:34:54,877 --> 00:34:57,460
Porque não há uma escolha entre
algo que é, pelo menos, seis

664
00:34:57,460 --> 00:34:59,250
e algo que é
menos de cinco anos, ele é

665
00:34:59,250 --> 00:35:02,570
vai dar-me a coisa
que é menos do que cinco.

666
00:35:02,570 --> 00:35:04,779
E agora eu sei que eu vou
para obter exatamente essa escolha.

667
00:35:04,779 --> 00:35:06,195
Eu estou indo para obter que cinco escolha.

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

669
00:35:08,980 --> 00:35:10,010
>> Eu voltar a subir até o topo.

670
00:35:10,010 --> 00:35:11,450
Que é que eu vou
escolher entre algo

671
00:35:11,450 --> 00:35:14,449
que é maior do que ou igual a quatro,
ou algo que é igual a cinco?

672
00:35:14,449 --> 00:35:17,140
Eu vou tomar algo
que é, pelo menos, cinco anos.

673
00:35:17,140 --> 00:35:20,490
Desço o último caminho, todos
o caminho até o fundo.

674
00:35:20,490 --> 00:35:21,260
Há um um.

675
00:35:21,260 --> 00:35:23,410
OK, pelo menos eu estou indo para obter um ponto.

676
00:35:23,410 --> 00:35:24,427
I continuar.

677
00:35:24,427 --> 00:35:25,760
Dois, oh, isso é melhor do que uma.

678
00:35:25,760 --> 00:35:27,100
Eu estou indo para obter, pelo menos, dois.

679
00:35:27,100 --> 00:35:28,610
I encontrar um três.

680
00:35:28,610 --> 00:35:31,450
Eu sei que estou indo para obter três.

681
00:35:31,450 --> 00:35:34,690
>> E o ponto de cima que,
o meu adversário vai

682
00:35:34,690 --> 00:35:38,540
para me dar algo que é
menos do que ou igual a três.

683
00:35:38,540 --> 00:35:40,940
E agora eu posso parar.

684
00:35:40,940 --> 00:35:46,290
Porque na escolha entre eu estar
capaz de obter um cinco e meu oponente

685
00:35:46,290 --> 00:35:52,290
dando-me uma coisa inferior a três,
Eu sempre vou ter que cinco.

686
00:35:52,290 --> 00:35:56,810
Então eu não avaliar que
parte inferior da árvore de todo.

687
00:35:56,810 --> 00:35:59,470
>> Agora, isto pode parecer menor.

688
00:35:59,470 --> 00:36:03,630
Mas quando pequenos pedaços de aritmética,
superior e inferior,

689
00:36:03,630 --> 00:36:10,640
pode cortar partes inteiras de
esta árvore em crescimento exponencial,

690
00:36:10,640 --> 00:36:14,280
que conduz a um enorme
quantidade de poupança, poupança

691
00:36:14,280 --> 00:36:17,630
que são grandes o suficiente para que eu
pode começar a jogar competitivamente

692
00:36:17,630 --> 00:36:21,330
em jogos mais complexos.

693
00:36:21,330 --> 00:36:27,030
>> Tudo bem, se olharmos para o tamanho
e complexidade de jogos diferentes,

694
00:36:27,030 --> 00:36:29,470
tic-tac-toe foi o nosso exemplo fácil.

695
00:36:29,470 --> 00:36:32,150
Temos uma pequena placa, três por três.

696
00:36:32,150 --> 00:36:36,030
Ficamos com, no máximo, uma média de
cerca de quatro diferentes opções

697
00:36:36,030 --> 00:36:38,440
como nós atravessamos o jogo.

698
00:36:38,440 --> 00:36:42,720
Temos algo em torno de 10 a
possíveis folhas diferentes quinto.

699
00:36:42,720 --> 00:36:45,200
Ea construção de um tic-tac-toe
jogador, bem, nós só fiz isso.

700
00:36:45,200 --> 00:36:47,460
Isso é fácil.

701
00:36:47,460 --> 00:36:49,890
>> Se formos até algo mais
complexo, como Connect Four.

702
00:36:49,890 --> 00:36:53,170
Você se lembra deste jogo onde
você deixar cair as pequenas fichas em?

703
00:36:53,170 --> 00:36:58,490
É uma placa de seis por sete,
não muito maior, ainda

704
00:36:58,490 --> 00:37:00,770
tem aproximadamente a mesma ramificação
fator como tic-tac-toe.

705
00:37:00,770 --> 00:37:05,410
Eu tenho cerca de quatro escolhas
onde posso colocar as coisas em.

706
00:37:05,410 --> 00:37:10,760
Mas agora, eu tenho muito mais
leva, 10 elevado à potência 21.

707
00:37:10,760 --> 00:37:14,440
Isso é algo que é fácil
o suficiente para que nós resolvê-lo imediatamente.

708
00:37:14,440 --> 00:37:17,560
>> Checkers, mais você complex--
tem um oito por oito bordo.

709
00:37:17,560 --> 00:37:20,570
Você está apenas na metade da
los a qualquer momento, no entanto.

710
00:37:20,570 --> 00:37:24,930
Você tem uma ramificação
fator que é cerca de 2,8.

711
00:37:24,930 --> 00:37:28,160
Bem, temos um casal
move-se você pode tomar.

712
00:37:28,160 --> 00:37:33,870
Você tem cerca de 10 a 31 de folhas,
espaços maiores e maiores, e maiores.

713
00:37:33,870 --> 00:37:37,340
Como eu tenho que pesquisar
esses espaços cada vez maiores,

714
00:37:37,340 --> 00:37:42,220
que é quando as coisas como beta e alfa-
sendo capaz de cortar ramos inteiros

715
00:37:42,220 --> 00:37:44,420
torna-se essencial.

716
00:37:44,420 --> 00:37:47,440
>> Agora, damas foi fácil o suficiente em 1992.

717
00:37:47,440 --> 00:37:51,400
Um programa de computador chamado
Chinook bater as damas mundo

718
00:37:51,400 --> 00:37:53,590
campeão, Marion Tinsley.

719
00:37:53,590 --> 00:37:57,260
E, desde então, não
jogador de mestre humano tem

720
00:37:57,260 --> 00:38:02,290
foi capaz de vencer o melhor
sistemas computacionais.

721
00:38:02,290 --> 00:38:06,570
Se olharmos para algo como xadrez, agora
novamente, temos um oito por oito bordo.

722
00:38:06,570 --> 00:38:09,870
Mas temos muito mais complexo
peças, tanto os movimentos mais complexos.

723
00:38:09,870 --> 00:38:14,610
Temos um fator de ramificação de cerca de
35, 35 movimentos possíveis em média

724
00:38:14,610 --> 00:38:20,030
que eu possa tomar, e um estado
espaço, um número de folhas

725
00:38:20,030 --> 00:38:28,950
que cresceu de 10 para 123 o poder,
um número enorme de possibilidades.

726
00:38:28,950 --> 00:38:35,570
>> Mesmo assim, os processadores modernos
são capazes de fazer isso com sucesso.

727
00:38:35,570 --> 00:38:43,900
Em 1995 e, em seguida, em 1997, um computador
programa chamado Deep Blue construído pela IBM

728
00:38:43,900 --> 00:38:49,601
que corria em um supercomputador gigante
bater o atual campeão mundial,

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
Este foi um ponto de viragem.

732
00:38:56,650 --> 00:39:00,620
Hoje, porém, que a mesma transformação
poder se senta no meu MacBook.

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

734
00:39:04,180 --> 00:39:06,440
>> Velocidade de processamento mantém
ficando mais rápido e mais rápido.

735
00:39:06,440 --> 00:39:09,500
Nós podemos avaliar mais e mais
placas mais rápidas e mais rápido.

736
00:39:09,500 --> 00:39:14,550
Mas o mais importante, temos melhor
funções de avaliação e melhor poda

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

738
00:39:15,460 --> 00:39:19,560
Assim, podemos procurar o
espaço mais complexo.

739
00:39:19,560 --> 00:39:22,350
A maior do conselho
jogos que podemos pensar,

740
00:39:22,350 --> 00:39:26,310
Vai algo como isso é
tem uma placa de 19 por 19,

741
00:39:26,310 --> 00:39:32,490
Agora, de repente, nós estamos além do ponto
onde os sistemas computacionais pode ganhar.

742
00:39:32,490 --> 00:39:34,530
Não há nenhum computacional
sistema lá fora,

743
00:39:34,530 --> 00:39:38,880
que pode bater um jogador profissional Go.

744
00:39:38,880 --> 00:39:45,000
Os melhores sistemas de hoje classificá-lo sobre
o tipo de bom nível amador.

745
00:39:45,000 --> 00:39:49,285
Assim, ainda há um pouco para fora
há que você não pode chegar a ainda.

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

747
00:39:51,840 --> 00:39:55,360
>> Tudo bem, estas
jogos de tabuleiro tradicionais,

748
00:39:55,360 --> 00:39:58,560
estes tipos de sistemas onde
construir essa minimax, se ele tem

749
00:39:58,560 --> 00:40:06,300
alfa-beta ou não, estes algoritmos de trabalhar
porque há certas restrições.

750
00:40:06,300 --> 00:40:08,520
Nós temos a informação perfeita
sobre o mundo.

751
00:40:08,520 --> 00:40:11,690
Nós sabemos onde estão todas as peças.

752
00:40:11,690 --> 00:40:13,570
O mundo é estático.

753
00:40:13,570 --> 00:40:16,220
Ninguém fica para mover o
pedaços ao redor, enquanto eu estou

754
00:40:16,220 --> 00:40:20,640
sentado lá pensando, tomando minha vez.

755
00:40:20,640 --> 00:40:23,140
Há um espaço de ação que é discreta.

756
00:40:23,140 --> 00:40:26,900
Eu posso colocar o meu peão aqui,
ou eu posso colocar meu peão aqui.

757
00:40:26,900 --> 00:40:30,520
Eu não estou autorizado a colocar o meu peão em
a linha entre os dois quadrados.

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

759
00:40:34,430 --> 00:40:36,520
>> E, finalmente, as acções
são deterministas.

760
00:40:36,520 --> 00:40:39,790
Eu sei que se eu digo,
rook cavaleiro para três,

761
00:40:39,790 --> 00:40:44,660
minha torre vai acabar no cavaleiro
três, desde que é um movimento válido.

762
00:40:44,660 --> 00:40:47,830
Não há nenhuma incerteza sobre isso.

763
00:40:47,830 --> 00:40:52,490
Agora, como eu ir para mais
diferentes tipos de jogos,

764
00:40:52,490 --> 00:40:55,960
nós temos que quebrar essas suposições.

765
00:40:55,960 --> 00:41:00,020
>> E se eu ir para algo
como clássicos jogos de vídeo?

766
00:41:00,020 --> 00:41:04,180
Aqui está uma seleção de vídeo
jogos do Atari 2600.

767
00:41:04,180 --> 00:41:05,180
O que eu tenho lá em cima?

768
00:41:05,180 --> 00:41:08,440
Eu tenho Frogger, Espaço
Invaders, Pitfall, e Pac-Man.

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

770
00:41:11,290 --> 00:41:14,840
Que tipos de ambientes
eu tenho aqui agora?

771
00:41:14,840 --> 00:41:16,900
Qual dessas premissas
eu tenho que quebrar?

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

773
00:41:19,410 --> 00:41:21,570
>> Bem, isso depende do jogo.

774
00:41:21,570 --> 00:41:28,170
Eu poderia jogar xadrez em 2600, e
seria exatamente como era antes.

775
00:41:28,170 --> 00:41:33,020
Para a maioria destes sistemas, há
conhecimento completo sobre o mundo.

776
00:41:33,020 --> 00:41:36,300
Há completamente
ações determinista.

777
00:41:36,300 --> 00:41:38,330
Mas, geralmente, o mundo
não estático.

778
00:41:38,330 --> 00:41:41,970
Ou seja, enquanto eu estou sentado lá
esperando, algo está se movendo.

779
00:41:41,970 --> 00:41:44,320
Os fantasmas estão vindo para me pegar.

780
00:41:44,320 --> 00:41:46,570
O escorpião está me seguindo por baixo.

781
00:41:46,570 --> 00:41:48,880
Os invasores do espaço são
chegando cada vez mais perto.

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

783
00:41:54,020 --> 00:41:55,510
Como bem podemos fazer contra isso?

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

785
00:41:58,640 --> 00:42:02,790
>> Alguns anos atrás, o Google
tinha um projeto chamado

786
00:42:02,790 --> 00:42:12,030
DeepMind, onde eles treinaram um computador
programa de jogar Atari 2600 jogos.

787
00:42:12,030 --> 00:42:16,120
E se você acha que isso não é grave
negócio, os resultados de seu estudo

788
00:42:16,120 --> 00:42:19,920
foram publicados na revista Nature, de modo
quase tão bom uma publicação

789
00:42:19,920 --> 00:42:22,500
como você pode eventualmente chegar.

790
00:42:22,500 --> 00:42:24,340
E aqui está como bem eles realizados.

791
00:42:24,340 --> 00:42:29,220
>> Eles têm um algoritmo que se sentou
e viu apenas as entradas de tela.

792
00:42:29,220 --> 00:42:34,080
Ele tem nenhuma instrução que seja
sobre as regras do jogo.

793
00:42:34,080 --> 00:42:42,610
E era para descobrir,
baseou a sua pontuação, o quão bem ele estava fazendo.

794
00:42:42,610 --> 00:42:46,560
Este foi um sistema que utilizado algo
chamado de aprendizado por reforço.

795
00:42:46,560 --> 00:42:48,380
Ou seja, ele olhou para a sua pontuação.

796
00:42:48,380 --> 00:42:51,620
E se ele obteve uma boa pontuação, ele disse:
Eu deveria me lembrar dessas coisas.

797
00:42:51,620 --> 00:42:53,310
E eu deveria fazer aqueles outra vez.

798
00:42:53,310 --> 00:42:56,450
E se ele obteve uma nota ruim, ele disse:
Eu não deveria fazer essas coisas novamente.

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

800
00:42:59,750 --> 00:43:03,430
>> Este é o desempenho
desses sistemas formados

801
00:43:03,430 --> 00:43:07,490
autorizado a jogar por um
algumas horas em cada jogo,

802
00:43:07,490 --> 00:43:12,490
comparados com jogadores profissionais.

803
00:43:12,490 --> 00:43:19,670
Portanto, para todos os jogos que estão
para o lado esquerdo desta linha,

804
00:43:19,670 --> 00:43:25,920
Este programa de computador auto-treinados
superaram os jogadores profissionais.

805
00:43:25,920 --> 00:43:29,690
E para que tudo o
direito, os jogadores profissionais

806
00:43:29,690 --> 00:43:30,920
ainda foram os melhores.

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

808
00:43:34,040 --> 00:43:36,850
Para algo que sabia
nada sobre as regras, que

809
00:43:36,850 --> 00:43:43,020
não sabia nada sobre a estrutura do
jogos, este é um desempenho impressionante.

810
00:43:43,020 --> 00:43:45,660
E é isso que nós somos capazes de fazer hoje.

811
00:43:45,660 --> 00:43:50,239
>> OK, você diz, mas se nós
pensar sobre AI em jogos,

812
00:43:50,239 --> 00:43:52,530
normalmente pensamos sobre a
coisas que podemos realmente

813
00:43:52,530 --> 00:43:54,180
sentar e jogar contra.

814
00:43:54,180 --> 00:43:58,760
Se eu me sento e toco
StarCraft, ou eu jogo gratuito Sieve,

815
00:43:58,760 --> 00:44:01,870
o adversário é o computador
pessoa que controla o Zerg,

816
00:44:01,870 --> 00:44:06,770
ou o controlo do outro civilização.

817
00:44:06,770 --> 00:44:11,920
Como esses jogadores
realmente encontrar seus movimentos?

818
00:44:11,920 --> 00:44:18,810
>> Bem, estes jogos são estruturados
da mesma maneira como os nossos jogos de tabuleiro,

819
00:44:18,810 --> 00:44:22,250
estes jogos que vamos
chamar colectivamente quatro jogos X,

820
00:44:22,250 --> 00:44:26,040
explorar, expand-- esquecer os queridos.

821
00:44:26,040 --> 00:44:26,980
O que eles são?

822
00:44:26,980 --> 00:44:32,150
Explorar, expandir e extinguir,
Eu acho que é a última.

823
00:44:32,150 --> 00:44:36,060
Mas eles são, basicamente,
jogos de exploração e conquistar.

824
00:44:36,060 --> 00:44:41,020
Normalmente, o adversário do computador
não tem informações limitadas.

825
00:44:41,020 --> 00:44:45,486
Eles não sabem exatamente o que está
acontecendo por trás dessa névoa da guerra.

826
00:44:45,486 --> 00:44:47,735
Eles não conseguem ver o que
você tem em seu inventário.

827
00:44:47,735 --> 00:44:50,240

828
00:44:50,240 --> 00:44:52,800
>> Há um ambiente que é dinâmico.

829
00:44:52,800 --> 00:44:56,180
Tudo está mudando o tempo todo.

830
00:44:56,180 --> 00:45:00,290
Você não consegue sentar-se e
esperar para tomar a sua jogada.

831
00:45:00,290 --> 00:45:02,810
Mas a maioria das coisas que ainda são discretos.

832
00:45:02,810 --> 00:45:04,200
Eu tenho que colocar minha cidade aqui.

833
00:45:04,200 --> 00:45:06,750
Ou eu tenho que colocar minha cidade aqui.

834
00:45:06,750 --> 00:45:08,950
E tudo é determinista.

835
00:45:08,950 --> 00:45:14,660
Quando eu digo, mover minha unidade aqui, minha unidade
move-se aqui, a não ser um obstáculo de repente

836
00:45:14,660 --> 00:45:17,700
entra em jogo.

837
00:45:17,700 --> 00:45:21,610
Agora, isso não é tudo computador
jogos que estão por aí hoje.

838
00:45:21,610 --> 00:45:27,320
>> Se eu ir e eu jogo um primeiro tipo pessoa
jogo, algo como ladrão ou Fallout

839
00:45:27,320 --> 00:45:33,350
ou Skyrim, ou o Halo, agora
Eu tenho adversários controlados pelo computador

840
00:45:33,350 --> 00:45:37,860
que estão lá fora, que têm
uma situação muito diferente.

841
00:45:37,860 --> 00:45:40,020
Eles têm, de novo, informações limitadas.

842
00:45:40,020 --> 00:45:43,420
Eles só podem ver um
certo campo de visão.

843
00:45:43,420 --> 00:45:45,180
O ambiente é ainda dinâmico.

844
00:45:45,180 --> 00:45:48,280
As coisas estão mudando o tempo todo.

845
00:45:48,280 --> 00:45:52,300
>> Mas agora eu tenho um muito mais
espaço de ação contínua.

846
00:45:52,300 --> 00:45:57,170
Eu posso ser apenas exibir uma
pouco fora da porta.

847
00:45:57,170 --> 00:46:00,650
E alguns jogos, a minha
ações são estocástica.

848
00:46:00,650 --> 00:46:04,590
Eu começar a tentar saltar sobre essa parede,
mas eu tenho a chance de fracassar.

849
00:46:04,590 --> 00:46:08,280

850
00:46:08,280 --> 00:46:14,550
Estes tipos de jogos estão se aproximando
e mais próximas para os tipos de controladores

851
00:46:14,550 --> 00:46:17,330
que nós construímos em robótica.

852
00:46:17,330 --> 00:46:21,050
>> Em robótica, temos que assumir
que temos informação limitada.

853
00:46:21,050 --> 00:46:23,070
Temos que sensores
conte-nos sobre o mundo.

854
00:46:23,070 --> 00:46:25,860
Nós temos um sempre mudando,
ambiente dinâmico.

855
00:46:25,860 --> 00:46:30,440
Temos um mundo em que o espaço é
contínua, em vez de discreta.

856
00:46:30,440 --> 00:46:36,260
E nossas ações, quando tentamos
eles, tem uma chance de fracassar.

857
00:46:36,260 --> 00:46:40,960
E, de fato, jogo moderno
controladores para o seu adversário de Halo,

858
00:46:40,960 --> 00:46:48,690
ou para os NPCs em Skyrim, basicamente,
executar pequenas arquiteturas robóticas.

859
00:46:48,690 --> 00:46:50,380
>> Eles sentem o mundo.

860
00:46:50,380 --> 00:46:52,910
Eles construir um modelo do mundo.

861
00:46:52,910 --> 00:46:57,950
Eles computam com base em um conjunto de
objetivos que gostaria de realizar.

862
00:46:57,950 --> 00:47:03,110
Eles planejam ações baseadas
sobre o que eles sabem.

863
00:47:03,110 --> 00:47:07,940
E esses são exatamente os mesmos tipos
dos sistemas que construímos em robótica.

864
00:47:07,940 --> 00:47:11,420
Assim, essas arquiteturas, para
trazer isso de volta juntos,

865
00:47:11,420 --> 00:47:14,500
são muitas vezes bastante o mesmo.

866
00:47:14,500 --> 00:47:16,340
>> Então, vamos ver se podemos ver isso.

867
00:47:16,340 --> 00:47:19,210
Vamos voltar ao nosso
exemplo tic-tac-toe.

868
00:47:19,210 --> 00:47:22,690
E eu vou pedir um par de meu
pós-docs para vir e me ajudar.

869
00:47:22,690 --> 00:47:26,970
Então, Chen Ming, e Alessandro, e
Olivier, se vocês viriam para cima.

870
00:47:26,970 --> 00:47:32,080

871
00:47:32,080 --> 00:47:35,440
E eu vou precisar
um par de voluntários

872
00:47:35,440 --> 00:47:37,590
>> OK, eu vi um direito mão
lá no meio.

873
00:47:37,590 --> 00:47:39,965
Deixe-me dar mais um, alguém
ainda mais na parte de trás, talvez.

874
00:47:39,965 --> 00:47:40,881
Tudo bem, lá.

875
00:47:40,881 --> 00:47:41,490
Vamos lá para cima.

876
00:47:41,490 --> 00:47:44,190

877
00:47:44,190 --> 00:47:45,335
Tudo certo.

878
00:47:45,335 --> 00:47:49,490
Portanto, vamos ter que tampa para baixo.

879
00:47:49,490 --> 00:48:03,700
E se vocês viriam direita
de volta por aqui para mim, fantástico.

880
00:48:03,700 --> 00:48:06,580
>> Portanto, este é um robô chamado Baxter.

881
00:48:06,580 --> 00:48:10,880
E Baxter é um robô que é uma
plataforma comercial, projetado

882
00:48:10,880 --> 00:48:13,030
por uma empresa chamada Rethink.

883
00:48:13,030 --> 00:48:16,580
E este robô é concebido
para a fabricação em pequena escala.

884
00:48:16,580 --> 00:48:19,265
Mas hoje nós estamos indo para
usá-lo para jogar tic-tac-toe.

885
00:48:19,265 --> 00:48:21,930

886
00:48:21,930 --> 00:48:27,150
Agora, este robô também é algo
que é relativamente única.

887
00:48:27,150 --> 00:48:32,950
Porque se eu estivesse em pé em qualquer lugar
perto de uma fábrica automação padrão

888
00:48:32,950 --> 00:48:39,580
sistema, eu estaria em muito grave
perigo de ser ferido.

889
00:48:39,580 --> 00:48:45,600
>> Baxter, no entanto, foi concebida para ser
relativamente seguro para interagir com.

890
00:48:45,600 --> 00:48:48,680
E para que eu possa empurrar este robô.

891
00:48:48,680 --> 00:48:52,350
E você pode ver que é um pouco
pouco flexível que se move ao redor.

892
00:48:52,350 --> 00:48:57,250
E eu posso reposicioná-la
onde eu gostaria que ele vá.

893
00:48:57,250 --> 00:49:03,410
Agora em um sistema robótico normal,
teríamos um conjunto de articulações aqui

894
00:49:03,410 --> 00:49:07,970
que seria directamente
respondendo aos comandos de posição.

895
00:49:07,970 --> 00:49:13,180
E eles não necessariamente se preocupam
se eles estavam se movendo através de ar livre,

896
00:49:13,180 --> 00:49:15,555
ou se eles estavam se movendo
através da minha caixa torácica.

897
00:49:15,555 --> 00:49:18,410

898
00:49:18,410 --> 00:49:19,120
>> ESTÁ BEM.

899
00:49:19,120 --> 00:49:22,090
E normalmente, se você fosse
aqui com um sistema industrial,

900
00:49:22,090 --> 00:49:23,400
você iria a lugar nenhum perto dele.

901
00:49:23,400 --> 00:49:26,280
Haveria amarelo
fita de segurança ao redor dele.

902
00:49:26,280 --> 00:49:28,310
Este sistema tem um
desenho ligeiramente diferente

903
00:49:28,310 --> 00:49:32,130
para ser mais amigável e mais fácil
para as pessoas a interagir com,

904
00:49:32,130 --> 00:49:36,380
em que em cada uma das juntas, há uma mola.

905
00:49:36,380 --> 00:49:39,110
E, em vez de controlar
uma posição exata,

906
00:49:39,110 --> 00:49:43,110
que controla uma certa quantidade de
de torque, uma certa quantidade de força,

907
00:49:43,110 --> 00:49:45,874
que gostaríamos de estar nessa primavera.

908
00:49:45,874 --> 00:49:47,790
Tudo bem, então deixem-me
levar nossos voluntários aqui.

909
00:49:47,790 --> 00:49:48,540
Oi, qual é o seu nome?

910
00:49:48,540 --> 00:49:49,010
>> AUDIÊNCIA: Louis.

911
00:49:49,010 --> 00:49:49,635
>> COLUNA: Louis.

912
00:49:49,635 --> 00:49:50,490
É bom te ver.

913
00:49:50,490 --> 00:49:50,990
E?

914
00:49:50,990 --> 00:49:51,610
>> AUDIÊNCIA: David.

915
00:49:51,610 --> 00:49:51,960
>> COLUNA: David.

916
00:49:51,960 --> 00:49:52,550
Bom te conhecer.

917
00:49:52,550 --> 00:49:54,508
Se vocês esperariam
aqui mesmo por um segundo,

918
00:49:54,508 --> 00:49:56,420
eu vou te dar
a chance de fazer isso.

919
00:49:56,420 --> 00:50:00,610
Portanto, este robô, se você vir para cima
e se você empurrar delicadamente sobre ele,

920
00:50:00,610 --> 00:50:03,780
você vai ver que
ele se move um pouco.

921
00:50:03,780 --> 00:50:06,349
E se você agarrá-lo direito
aqui no pulso apenas

922
00:50:06,349 --> 00:50:09,390
acima de onde os botões são, ele
Parece que você deve agarrar os botões,

923
00:50:09,390 --> 00:50:13,100
mas pegue à direita acima em vez disso, você vai
ser capaz de manipular-se muito suavemente

924
00:50:13,100 --> 00:50:14,545
através do espaço.

925
00:50:14,545 --> 00:50:15,920
Louis, você quer dar-lhe uma tentativa?

926
00:50:15,920 --> 00:50:19,465
Então, dar-lhe apenas um pouco
empurrar para começar.

927
00:50:19,465 --> 00:50:23,190
E então se você colocar os dedos
ali e agarrar a ele,

928
00:50:23,190 --> 00:50:24,807
porque ele vai passar para você, então.

929
00:50:24,807 --> 00:50:27,824

930
00:50:27,824 --> 00:50:29,365
Tudo bem, você quer dar-lhe uma tentativa?

931
00:50:29,365 --> 00:50:29,980
Vamos lá para cima.

932
00:50:29,980 --> 00:50:32,300
Então, dar-lhe apenas uma suave
empurrar lá para começar.

933
00:50:32,300 --> 00:50:33,820
Você pode sentir o que é como.

934
00:50:33,820 --> 00:50:40,060
E então se você agarrá-lo ali mesmo,
você vai ser capaz de manobrar em torno.

935
00:50:40,060 --> 00:50:41,280
>> ESTÁ BEM.

936
00:50:41,280 --> 00:50:47,360
Então, normalmente, este tipo de um robô faria
ser utilizado para o fabrico de pequena escala.

937
00:50:47,360 --> 00:50:50,980
E eu vou mover este braço apenas
para baixo fora do caminho um pouco aqui.

938
00:50:50,980 --> 00:50:55,750
Mas hoje, nós estamos indo para usar o
mesmo sistema de jogo tic-tac-toe

939
00:50:55,750 --> 00:50:59,520
baseado em minimax que construímos antes.

940
00:50:59,520 --> 00:51:00,549
ok?

941
00:51:00,549 --> 00:51:02,340
Então, vocês são cada
vai jogar um jogo.

942
00:51:02,340 --> 00:51:04,210
Louis, você está indo para ser o primeiro.

943
00:51:04,210 --> 00:51:05,920
Deixe-me apenas realizar-se aqui por um segundo.

944
00:51:05,920 --> 00:51:10,949
Eu vou ter você ficar bem
aqui, apenas para que todos possam vê-lo.

945
00:51:10,949 --> 00:51:11,990
Vocês estão configurar aqui?

946
00:51:11,990 --> 00:51:13,120
>> ROBOT: Bem-vindo.

947
00:51:13,120 --> 00:51:15,910
Vamos jogar tic-tac-toe.

948
00:51:15,910 --> 00:51:20,860
Não segure o token antes
Eu digo que é a sua vez.

949
00:51:20,860 --> 00:51:22,050
Eu iniciar o jogo.

950
00:51:22,050 --> 00:51:27,900

951
00:51:27,900 --> 00:51:28,750
É a minha vez.

952
00:51:28,750 --> 00:51:47,002

953
00:51:47,002 --> 00:51:50,210
COLUNA: Agora, se você pudesse tomar uma das
suas peças e ir em frente e colocá-lo.

954
00:51:50,210 --> 00:51:51,446
ROBOT: É a sua vez.

955
00:51:51,446 --> 00:51:53,430
[RISO]

956
00:51:53,430 --> 00:51:54,836
É a minha vez.

957
00:51:54,836 --> 00:51:56,820
[RISO]

958
00:51:56,820 --> 00:52:12,196

959
00:52:12,196 --> 00:52:15,680
[RISO]

960
00:52:15,680 --> 00:52:16,570
É sua vez.

961
00:52:16,570 --> 00:52:21,397

962
00:52:21,397 --> 00:52:23,688
SPEAKER: A raça humana é
contando com você aqui, Louis.

963
00:52:23,688 --> 00:52:27,440

964
00:52:27,440 --> 00:52:28,350
>> ROBOT: É a minha vez.

965
00:52:28,350 --> 00:52:44,810

966
00:52:44,810 --> 00:52:47,015
>> COLUNA: Então Baxter
bloqueado com sucesso aqui.

967
00:52:47,015 --> 00:52:49,670

968
00:52:49,670 --> 00:52:52,480
>> ROBOT: É a sua vez.

969
00:52:52,480 --> 00:52:53,360
É a minha vez.

970
00:52:53,360 --> 00:53:14,730

971
00:53:14,730 --> 00:53:16,810
É sua vez.

972
00:53:16,810 --> 00:53:17,760
É a minha vez.

973
00:53:17,760 --> 00:53:21,330

974
00:53:21,330 --> 00:53:23,830
Orador: E nós vamos deixar Baxter
terminar a sua última jogada aqui.

975
00:53:23,830 --> 00:53:36,622

976
00:53:36,622 --> 00:53:39,090
>> [RISO]

977
00:53:39,090 --> 00:53:40,480
>> ROBOT: Isso é um empate.

978
00:53:40,480 --> 00:53:42,030
Eu vou ganhar da próxima vez.

979
00:53:42,030 --> 00:53:43,365
>> [RISO]

980
00:53:43,365 --> 00:53:45,210
>> COLUNA: Tudo bem,
muito obrigado, Louis.

981
00:53:45,210 --> 00:53:46,094
Obrigado.

982
00:53:46,094 --> 00:53:46,980
Você pode ir por este caminho.

983
00:53:46,980 --> 00:53:49,759
>> ROBOT: eu iniciar o jogo.

984
00:53:49,759 --> 00:53:51,800
COLUNA: Então deixe-me explicar
para você um pouco mais

985
00:53:51,800 --> 00:53:55,410
pouco antes de chegarmos a nossa revanche aqui.

986
00:53:55,410 --> 00:53:57,200
O que exatamente está acontecendo?

987
00:53:57,200 --> 00:53:59,430
Assim, o robô tem uma câmera em cima aqui.

988
00:53:59,430 --> 00:54:01,330
E ele está olhando para a placa.

989
00:54:01,330 --> 00:54:04,470
E está vendo se
ele tem um O vermelho ou um azul

990
00:54:04,470 --> 00:54:10,450
e X. branco como aqueles são colocados no
placa, que é basicamente a mesma entrada

991
00:54:10,450 --> 00:54:13,890
que estaríamos lendo a partir
nossa estrutura de dados da nossa tela.

992
00:54:13,890 --> 00:54:17,290
Ele está correndo o mesmo
algoritmo minimax ser

993
00:54:17,290 --> 00:54:21,010
capaz de encontrar onde
colocar um bom sinal.

994
00:54:21,010 --> 00:54:24,820
>> E então nós estamos dando um comando sobre
onde nós gostaria de um token para ser colocado.

995
00:54:24,820 --> 00:54:26,120
O braço está se movendo para fora.

996
00:54:26,120 --> 00:54:31,750
É usando um dispositivo de preensão de vácuo para aplicar
alguma sucção para que a peça de madeira,

997
00:54:31,750 --> 00:54:35,240
pegá-lo, movê-lo para a direita
local, e em seguida, solte a sucção

998
00:54:35,240 --> 00:54:36,950
e largá-lo.

999
00:54:36,950 --> 00:54:38,990
Tudo bem, vamos
para dar-lhe mais um tiro

1000
00:54:38,990 --> 00:54:40,930
com um jogador um pouco mais esperto aqui.

1001
00:54:40,930 --> 00:54:42,290
Esta pronto?

1002
00:54:42,290 --> 00:54:46,150
Tudo bem, se você ficar até
aqui e dar um-- resultando nesse caminho

1003
00:54:46,150 --> 00:54:47,955
assim você pode ver toda a gente.

1004
00:54:47,955 --> 00:54:48,830
E então [inaudível].

1005
00:54:48,830 --> 00:54:49,330
>> ROBOT: É a minha vez.

1006
00:54:49,330 --> 00:54:50,455
>> COLUNA: Baxter vai começar.

1007
00:54:50,455 --> 00:55:10,750

1008
00:55:10,750 --> 00:55:11,730
É sua vez.

1009
00:55:11,730 --> 00:55:16,490

1010
00:55:16,490 --> 00:55:17,520
É a minha vez.

1011
00:55:17,520 --> 00:55:38,740

1012
00:55:38,740 --> 00:55:39,690
É sua vez.

1013
00:55:39,690 --> 00:55:46,330

1014
00:55:46,330 --> 00:55:47,165
É a minha vez.

1015
00:55:47,165 --> 00:56:01,252

1016
00:56:01,252 --> 00:56:06,192
>> [RISO]

1017
00:56:06,192 --> 00:56:08,542
>> COLUNA: [sussurrando] Apenas
deixá-lo ir em frente e vencer.

1018
00:56:08,542 --> 00:56:09,500
ROBOT: É a sua vez.

1019
00:56:09,500 --> 00:56:15,099

1020
00:56:15,099 --> 00:56:15,890
COLUNA: Isso é OK.

1021
00:56:15,890 --> 00:56:20,390

1022
00:56:20,390 --> 00:56:21,360
>> ROBOT: É a minha vez.

1023
00:56:21,360 --> 00:56:24,825

1024
00:56:24,825 --> 00:56:26,805
>> [RISO]

1025
00:56:26,805 --> 00:56:42,650

1026
00:56:42,650 --> 00:56:43,510
>> Eu ganho.

1027
00:56:43,510 --> 00:56:45,620
>> [RISO]

1028
00:56:45,620 --> 00:56:46,595
>> Eu iniciar o jogo.

1029
00:56:46,595 --> 00:56:48,261
>> COLUNA: Tudo bem, muito obrigado.

1030
00:56:48,261 --> 00:56:50,180

1031
00:56:50,180 --> 00:56:55,590
Tudo bem, eu acho que nós temos tempo para
mais um excelente jogador de tic-tac-toe,

1032
00:56:55,590 --> 00:57:00,490
alguém que pode colocar essa coisa de
corresponderem, que sabe o que está fazendo.

1033
00:57:00,490 --> 00:57:03,010
>> [RISO]

1034
00:57:03,010 --> 00:57:05,560
>> Quem vai ser o nosso campeão aqui?

1035
00:57:05,560 --> 00:57:08,110
Tudo bem, seus amigos ofereceram-lhe.

1036
00:57:08,110 --> 00:57:11,190
Isso é bom o suficiente para mim.

1037
00:57:11,190 --> 00:57:12,194
Diga-me o seu nome novamente.

1038
00:57:12,194 --> 00:57:12,860
AUDIÊNCIA: Tamir.

1039
00:57:12,860 --> 00:57:14,193
COLUNA: Tamir, bom vê-lo.

1040
00:57:14,193 --> 00:57:19,270
Tudo bem, mais uma vez, vamos colocá-lo
até aqui para que todos possam vê-lo.

1041
00:57:19,270 --> 00:57:22,070
Você é o nosso representante
neste jogo agora.

1042
00:57:22,070 --> 00:57:24,540
Baxter é um e oh e oh.

1043
00:57:24,540 --> 00:57:26,300
Ou Desculpe, uma oh e um.

1044
00:57:26,300 --> 00:57:27,490
E cabe a você aqui.

1045
00:57:27,490 --> 00:57:29,340
Baxter vai começar a mover-se em primeiro lugar, no entanto.

1046
00:57:29,340 --> 00:57:30,435
Assim.

1047
00:57:30,435 --> 00:57:31,310
ROBOT: É a minha vez.

1048
00:57:31,310 --> 00:57:45,226

1049
00:57:45,226 --> 00:57:48,208
>> [RISO]

1050
00:57:48,208 --> 00:57:52,720

1051
00:57:52,720 --> 00:57:55,780
>> É sua vez.

1052
00:57:55,780 --> 00:57:56,845
É a minha vez.

1053
00:57:56,845 --> 00:58:18,130

1054
00:58:18,130 --> 00:58:18,965
É sua vez.

1055
00:58:18,965 --> 00:58:28,751

1056
00:58:28,751 --> 00:58:30,248
É a minha vez.

1057
00:58:30,248 --> 00:58:51,210

1058
00:58:51,210 --> 00:58:52,160
É sua vez.

1059
00:58:52,160 --> 00:59:00,854

1060
00:59:00,854 --> 00:59:03,365
>> [RISO]

1061
00:59:03,365 --> 00:59:04,240
ROBOT: É a minha vez.

1062
00:59:04,240 --> 00:59:06,930
COLUNA: É muito mais difícil quando
você está de pé aqui, gente.

1063
00:59:06,930 --> 00:59:19,400

1064
00:59:19,400 --> 00:59:21,840
[RISO]

1065
00:59:21,840 --> 00:59:26,730

1066
00:59:26,730 --> 00:59:29,054
ROBOT: Vocês humanos são tão fáceis de bater.

1067
00:59:29,054 --> 00:59:30,803
[Risos e aplausos]

1068
00:59:30,803 --> 00:59:31,886
COLUNA: Muito obrigado.

1069
00:59:31,886 --> 00:59:34,692
ROBOT: eu ganhar.

1070
00:59:34,692 --> 00:59:35,400
Eu iniciar o jogo.

1071
00:59:35,400 --> 00:59:39,500
>> Palestrante: Tudo bem, então muito obrigado
muito a Olivier, e Alessandro,

1072
00:59:39,500 --> 00:59:41,616
e Chen Ming.

1073
00:59:41,616 --> 00:59:45,600
>> [Aplausos]

1074
00:59:45,600 --> 00:59:47,040
>> Eu quero fazer um último ponto.

1075
00:59:47,040 --> 00:59:51,630
Assim Baxter no próprio
termina aí, enganado.

1076
00:59:51,630 --> 00:59:54,160

1077
00:59:54,160 --> 00:59:56,310
E isso era inesperado.

1078
00:59:56,310 --> 01:00:00,440
Um dos fantástica
coisas sobre AI é que nós

1079
01:00:00,440 --> 01:00:05,070
fazer o trabalho em AI para que possamos construir
realmente interessante e inteligente

1080
01:00:05,070 --> 01:00:06,930
dispositivos.

1081
01:00:06,930 --> 01:00:10,130
Mas nós também fazemos trabalho em AI
porque nos diz algo

1082
01:00:10,130 --> 01:00:13,940
sobre como os humanos são inteligentes.

1083
01:00:13,940 --> 01:00:17,280
>> Um dos favoritos
estudos de meu laboratório é

1084
01:00:17,280 --> 01:00:23,660
olhando para o que acontece quando
máquinas inesperadamente batota.

1085
01:00:23,660 --> 01:00:27,070
Fizemos isso originalmente não com
Baxter jogar tic-tac-dedo do pé,

1086
01:00:27,070 --> 01:00:30,340
mas com um robô menor chamado Nao,
que jogou pedra-papel-tesoura.

1087
01:00:30,340 --> 01:00:33,010

1088
01:00:33,010 --> 01:00:35,800
E, às vezes após
jogando lotes e lotes

1089
01:00:35,800 --> 01:00:41,580
de perfuração de jogos de pedra-papel-tesoura,
o robô jogaria um gesto,

1090
01:00:41,580 --> 01:00:48,616
perder, e, em seguida, mudar de repente
seu gesto e dizer, eu ganho.

1091
01:00:48,616 --> 01:00:50,480
>> [RISO]

1092
01:00:50,480 --> 01:00:56,090
>> Agora, às vezes nós também teríamos o robô,
assim como um controle, jogue um gesto,

1093
01:00:56,090 --> 01:01:01,270
ganhar, e alterar o seu gesto
a perder, jogar o jogo,

1094
01:01:01,270 --> 01:01:04,070
enganar a fim de perder.

1095
01:01:04,070 --> 01:01:07,540
E isso não é tão atraente.

1096
01:01:07,540 --> 01:01:09,890
O robô que engana
a fim de ganhar pessoas

1097
01:01:09,890 --> 01:01:14,660
para responder como se fosse
para obtê-los, como ele

1098
01:01:14,660 --> 01:01:17,690
está se esforçando para sua destruição.

1099
01:01:17,690 --> 01:01:19,210
>> [RISO]

1100
01:01:19,210 --> 01:01:20,990
>> Torna-se um agente.

1101
01:01:20,990 --> 01:01:21,840
É como se fosse uma pessoa.

1102
01:01:21,840 --> 01:01:23,970
Tem crença e intenção.

1103
01:01:23,970 --> 01:01:27,470
E não é boa intenção.

1104
01:01:27,470 --> 01:01:33,790
E o robô que joga o
jogo é apenas mau funcionamento.

1105
01:01:33,790 --> 01:01:36,990
É apenas um dispositivo quebrado.

1106
01:01:36,990 --> 01:01:41,405
Deixe-me mostrar-lhe um par de exemplos
de que a partir de alguns dos nossos participantes.

1107
01:01:41,405 --> 01:01:43,990

1108
01:01:43,990 --> 01:01:45,600
Então aqui está traindo a fim de perder.

1109
01:01:45,600 --> 01:01:46,266
>> [REPRODUÇÃO DE VÍDEO]

1110
01:01:46,266 --> 01:01:47,010
- [Inaudível] ganhar.

1111
01:01:47,010 --> 01:01:49,550
Vamos jogar.

1112
01:01:49,550 --> 01:01:50,538
>> -Espere o que?

1113
01:01:50,538 --> 01:01:54,490

1114
01:01:54,490 --> 01:01:55,352
>> - [Inaudível] ganhar.

1115
01:01:55,352 --> 01:01:58,280
Vamos jogar.

1116
01:01:58,280 --> 01:01:59,400
>> [Inaudível] ganhar.

1117
01:01:59,400 --> 01:02:02,290
Vamos jogar.

1118
01:02:02,290 --> 01:02:05,490
>> Orador: E aqui é batota para ganhar.

1119
01:02:05,490 --> 01:02:06,438
>> Sim, eu ganho.

1120
01:02:06,438 --> 01:02:07,394
Vamos jogar.

1121
01:02:07,394 --> 01:02:08,828
>> -Você Não pode fazer isso.

1122
01:02:08,828 --> 01:02:10,740
>> [RISO]

1123
01:02:10,740 --> 01:02:12,174

1124
01:02:12,174 --> 01:02:13,979
>> Sim, eu ganho.

1125
01:02:13,979 --> 01:02:14,520
-Você trapaceou.

1126
01:02:14,520 --> 01:02:17,990

1127
01:02:17,990 --> 01:02:20,010
Você traiu agora.

1128
01:02:20,010 --> 01:02:21,140
>> Sim, eu ganho.

1129
01:02:21,140 --> 01:02:22,940
>> Ei, você trapaceiro.

1130
01:02:22,940 --> 01:02:26,670
Você enganar, super fraude.

1131
01:02:26,670 --> 01:02:27,650
>> [FIM DE REPRODUÇÃO]

1132
01:02:27,650 --> 01:02:31,130
>> COLUNA: Estes diferente
reações rapidamente

1133
01:02:31,130 --> 01:02:34,890
mudar a nossa percepção do dispositivo.

1134
01:02:34,890 --> 01:02:36,780
Isso significa que
nós deliberadamente construir

1135
01:02:36,780 --> 01:02:40,370
máquinas que se enganam porque é isso
a melhor engenharia que podemos fazer?

1136
01:02:40,370 --> 01:02:44,680
Não, mas nos diz algo
realmente interessante sobre as pessoas.

1137
01:02:44,680 --> 01:02:49,710
Aquela coisa que você engana e
rouba sua vitória, que é

1138
01:02:49,710 --> 01:02:53,660
algo que está vivo, isso é
animar, que está fora para começá-lo.

1139
01:02:53,660 --> 01:02:54,680
Ele tem estado mental.

1140
01:02:54,680 --> 01:02:55,400
Tem crença.

1141
01:02:55,400 --> 01:02:57,170
Tem a intenção.

1142
01:02:57,170 --> 01:03:01,540
>> Aquela coisa que as mãos
jogo para você, que não é.

1143
01:03:01,540 --> 01:03:04,670
Isso é apenas mau funcionamento.

1144
01:03:04,670 --> 01:03:08,900
Isto é, em muitos aspectos, porque é
fácil de jogar o jogo com as crianças.

1145
01:03:08,900 --> 01:03:12,050
Mas se você tentar enganá-los
e tipo de reivindicar a vitória

1146
01:03:12,050 --> 01:03:15,200
quando, você sabe, só para encurtar o
jogo, eles vão pegá-lo imediatamente.

1147
01:03:15,200 --> 01:03:19,040

1148
01:03:19,040 --> 01:03:23,140
Esses tipos de efeitos que
vemos que sai da AI,

1149
01:03:23,140 --> 01:03:26,490
eles nos ensinam muito sobre nós mesmos.

1150
01:03:26,490 --> 01:03:28,076
>> Tudo bem, é isso por hoje.

1151
01:03:28,076 --> 01:03:30,450
Muito obrigado a David e
a equipe de produção Harvard

1152
01:03:30,450 --> 01:03:32,350
para descer.

1153
01:03:32,350 --> 01:03:33,820
>> [Aplausos]

1154
01:03:33,820 --> 01:03:36,760

1155
01:03:36,760 --> 01:03:41,840
>> Vamos vê-lo em um questionário,
e, em seguida, para uma última palestra.

1156
01:03:41,840 --> 01:03:43,025
Tenha um bom dia.

1157
01:03:43,025 --> 01:03:44,965
>> [Aplausos]

1158
01:03:44,965 --> 01:03:48,360

1159
01:03:48,360 --> 01:03:51,825
>> [Música tocando]

1160
01:03:51,825 --> 01:03:54,950
DAVID MALAN J: Bem, nós provavelmente precisará
para introduzir algum tipo de criptografia,

1161
01:03:54,950 --> 01:03:55,450
certo?

1162
01:03:55,450 --> 01:03:58,650
Porque, então, os cabeçalhos de
esses pedidos HTTP será

1163
01:03:58,650 --> 01:04:01,530
mexidos para que qualquer pessoa
tentando capturar seu tráfego

1164
01:04:01,530 --> 01:04:03,400
não vai realmente ser capaz de vê-los.

1165
01:04:03,400 --> 01:04:05,254
Então, qual é a solução para este problema?

1166
01:04:05,254 --> 01:04:07,920
Bem, nós precisamos realmente introduzir
criptografia na fórmula,

1167
01:04:07,920 --> 01:04:11,010
de modo que quando essa pessoa
a transmissão de dados a partir de A para B,

1168
01:04:11,010 --> 01:04:12,390
nós podemos seguramente send--

1169
01:04:12,390 --> 01:04:14,590
>> [RISO]

1170
01:04:14,590 --> 01:04:19,530
>> A informação de uma maneira que o
adversário não pode, de fato, vê-lo.