[MUSIC nagpe-play] Tagapagsalita: Maligayang pagbabalik, sa lahat. Ito ay CS50. At ngayon, kami ay may isang pulutong ng mga kagiliw-giliw na mga bagay-bagay na makipag-usap tungkol sa. Una, bagaman, kailangan kong ipaalala iyo ng ilang mga administrative mga bagay-bagay. Sa linggong ito ay pagsusulit isa, Miyerkules o para sa seksyon ng Yale tuwing Martes at Huwebes, sa Huwebes. May mga quiz review ngayong gabi sa Yale, 5:30-07:00. Sa Harvard, naitala nila ang isa kahapon. At ang lahat ay maaaring panoorin na online. Gayundin, sa linggong ito o sa susunod na linggo, na namin ang aming huling CS50 panayam. [Groans] alam ko. Ito ay dumating upang lalong madaling panahon. Yale mag-aaral ay magkaroon ng isang live magbigay ng panayam dito sa law school auditorium sa Biyernes. Magkakaroon ng cake. Harvard mag-aaral ay magkakaroon ng huling panayam sa Sanders sa Lunes. Magkakaroon din ng cake. Gayundin, sa linggong ito sa Biyernes, para sa mga sa iyo kung sino ang paparating sa New Haven, kami ay ang CS50 Expo. Mayroon kaming higit sa 30 nakarehistro sa iba't ibang grupo upang ipakita sa iyo ang lahat ng bagay mula autonomous sailboats, sa mga sistema na makilala digital portrait, sa computer musika at music computer-produce. Kaya mangyaring sumali sa amin. Sa tingin ko ito ay magiging isang magandang panahon. Ngayon, bagaman, na nakukuha namin na patuloy na pakikipag-usap tungkol sa AI, tungkol sa artificial intelligence. At isa sa mga bagay na kami ay pagpunta upang makakuha ng sa ngayon ay ang ideya ng kung paano gamitin Ai upang malutas ang problema. Ngayon, gaya ng lagi, magsimula na tayo na may isang bagay simple. At kami ay pagpunta upang simulan ang may isang simpleng ideya. At na gamit sa paghahanap. Kaya isipin para sa isang minuto na ako magkaroon ng isang gawain na kailangan kong gawin. At gusto ko na magkaroon na gawain awtomatikong sa pamamagitan ng ilang mga software agent. Isipin na sinusubukan ko na mag-book ng set ng mga byahe mula sa, sabihin nating, Boston sa San Francisco. Ako ay pumunta sa pamamagitan ng at ako ay maaaring gamitin ang isa sa mga kahanga-hangang mga online na paghahanap mga kasangkapan, na kung saan ay pagpunta sa gawin isa lamang ang parehong proseso na hindi namin pagpunta sa paglalakad sa pamamagitan ng araw na ito. Ngunit kung hindi ka magkaroon ng na tool, ano ang gusto mong gawin? Well, maaari mong tingnan at makita at sabihin, ako sa Boston. Anong flight ang magagamit ko? Ngayon, siguro Mayroon akong tatlong posibleng flight sa labas ng Boston na magkasya ang oras kapag kailangan kong umalis. Kaya kong lumipad sa Chicago. O kaya kong lumipad sa Miami. O kaya kong lumipad sa New York. Maaari ko pagkatapos ay tumingin mula sa bawat isa sa mga destination lungsod at isipin ang tungkol sa kung ano ang mga lokasyon Kaya kong posibleng maabot mula sa bawat isa sa mga indibidwal na mga lungsod. Kaya marahil mula sa Chicago, ang maaari kong makuha isang direktang flight sa San Francisco. Iyan ay mahusay. O maaari ba akong makakuha ng isang flight sa Denver. Ngayon, marahil na flight papuntang San Francisco ay ang perpektong solusyon para sa akin, ngunit marahil hindi. Siguro Naghahanap ako para sa isang bagay na ang isang maliit na piraso ng mas mura o mas mabuti nang kaunti para sa aking schedule. At kaya ako ay maaaring maghanap para sa kung ano ang iba pang mga maaaring lumitaw diyan posibilidad. Kaya maaari kong tumingin sa Denver. At mula sa Denver, well, siguro Maaari ba akong makakuha ng isang flight sa Austin. At mula sa Austin, baka maaari akong makakuha ng isang byahe sa Phoenix, at mula sa Phoenix sa San Francisco. Ngayon, hindi ko pa tapos. Dahil siguro mayroong isang direktang flight mula sa New York sa San Francisco na ay perpekto para sa akin. O siguro mayroong isang flight mula sa Miami sa pamamagitan ng Denver na ng maraming mas mura. Kaya ko pa rin pumunta. At ako pa rin upang tumingin sa lahat ng mga mga lungsod na hindi ko pa iimbestigahan. Kailangan ko bang exhaustively suriin ang lahat ng mga ang mga posibilidad na maaaring mayroon ako. Kaya mula sa New York, baka maaari akong makakuha ng isang flight sa Nashville, at mula sa Nashville sa Austin. At pagkatapos ay alam ko kung nasaan ako. At pagkatapos ay ako malaman mula sa Austin, maaari ko lumipad sa Phoenix, at mula sa Phoenix sa San Francisco. Kung una lumipad ako sa Miami, bagaman, marahil maaari ba akong makakuha ng isang flight mula sa Miami sa Nashville, o mula sa Miami sa Austin. At ngayon ko na sinubukan lahat sa mga posibilidad. Na binuo ko up graph na ito na nagpapakita sa akin ang lahat ng posibleng mga ruta na maaaring ma-kunin ko. Kapag kami ay kumakatawan sa mga mga uri ng mga problema, hindi namin pagpunta upang kumatawan ito tahasang bilang graph na ito, dahil graph na ay hindi kumakatawan ang kasaysayan ng kung saan namin na wala na. Alam na nagsakay ko mula sa Phoenix patungo sa San Francisco ay hindi sabihin sa akin kung ako ay dumating sa pamamagitan ng Nashville, o sa pamamagitan ng Denver, o sa pamamagitan ng Miami. Kaya kung ano ang makikita ko sa halip ay Kukunin ko ang parehong problema, at kukunin ko na kumakatawan ito bilang isang puno. At sa ugat ng puno, sa top, makikita ko bang ilagay ang mga lugar na ako nagsimula, Boston. At mula sa Boston, kukunin ko na tingnan sa lahat ng mga posibleng lokasyon na maaari kong paglalakbay sa. Well, sa kasong ito, tatlong, Chicago, New York, at Miami. At pagkatapos ay kukunin ko na galugarin ang bawat isa sa ang mga batang ito sa tree. Mula sa Chicago, nakita ko na ako ay may dalawang mga flight. Kaya kong lumipad direkta sa San Francisco o sa Denver. Ngayon San Francisco, na ang aking mga layunin. Iyon ang aking destinasyon. Iyon ay magiging isang dahon ng punong kahoy na ito. Iyon ay, hindi ako pagpunta sa pumunta lugar pagkatapos San Francisco. Mula sa Denver, bagaman, Maaari ko bang lumipad mula sa Denver sa Austin, mula sa Austin sa Phoenix, at mula sa Phoenix sa San Francisco. At muli ngayon, naabot ako ng isang dahon. Maaari ko bang pagkatapos ay bumalik sa susunod na lungsod na hindi ako ganap na ginalugad. Iyon ay magiging New York, pumunta back up sa tuktok ng aking mga puno, bumaba sa New York. Mula sa New York, maaari ko bang lumipad sa Nashville, mula sa Nashville sa Austin, mula sa Austin sa Phoenix, at mula sa Phoenix sa San Francisco. At sa wakas, isang bayan ko hindi pa tumingin sa, Miami. Well, mula sa Miami sinabi ko ako ay may dalawang posibilidad, Nashville o Austin. Kung lumipad ako sa Nashville, kung sa gayon ako lumipad mula sa Nashville, sa Austin, sa Phoenix, sa San Francisco. Kung lumipad ako sa Austin, lumipad ako Austin, sa Phoenix, sa San Francisco. At ngayon ay mayroon akong isang puno. Ito ay isang kumpletong tree. Ito ay ang lahat ng mga posibilidad at lahat ng mga landas na maaari kong gawin. Iyon ay, kung sisimulan ko sa ugat ng puno sa tuktok at ako'y mababa sa isa sa mga dahon, ito ay nagsasabi sa akin hindi lamang kung saan ako pagpunta sa end up, San Francisco, ngunit ito ay nagsasabi sa akin ang ruta na Kailangan kong gawin upang makarating doon. Ngayon, kung saan ang isa sa mga ito ay ang pinakamahusay na? Well, wala tungkol sa mga ito pa nagsasabi sa akin na problema kung alin sa mga ito ay ang pinakamahusay na solusyon. Siguro pag-aalaga ko ang karamihan tungkol sa kung gaano karaming oras ako sa hangin, o ang distansya na ako lumilipad. Sa kasong iyon, Chicago patungo sa San Francisco ay maaaring ang pinakamaikling bilang milya sa hangin. Siguro ako na nagmamalasakit sa gastos. At alam nating lahat direktang flight ay karaniwang mas mahal. Kaya siguro kung kumuha ako ng ganitong uri ng paurong ruta sa pamamagitan ng Miami, Nashville, Austin, Phoenix, siguro pagkatapos Kumuha ako ng isang mas mababang presyo. Ngunit maaari ko bang i-optimize sa anumang criteria na ako pag-aalaga ang tungkol sa. Sinong nakuha ang pinakamahusay sa flight Wi-Fi, o kung saan airports may magagamit ang pinakamahusay na pagkain. At bawat isa sa mga baka bigyan ako ng isang iba't ibang mga solusyon na nakikita ko bilang ang pinakamahusay. Ang mga uri ng mga problema, kung saan kami pupunta upang buuin palabas na ito na puno ng mga posibilidad, at pagkatapos ay tingnan bawat isa sa mga indibidwal na landas, at suriin kung alin sa mga fulfills isang pamantayan para sa atin, kami ay pagpunta sa tumawag sa mga problema sa paghahanap. At kami ay may maraming mga algorithms, ang ilan sa nakita namin na, upang pumunta at galugarin ang mga puno. Maaari naming gawin ito sa paraan na ako ginawa lamang, ang isang paghahanap depth-una, lapag tulad ng maaari naming hanggang sa kami hit isang dahon, at pagkatapos ay babalik up, at pagpunta sa kanan likod down. O maaari naming gawin kung ano ang tinatawag na lawak-unang paghahanap. Kami ay maaaring mapalawak ang lahat ng bagay sa itaas, at pagkatapos ay ang lahat ng bagay sa isang linya sa ilalim na, at pagkatapos ay ang lahat ng bagay sa isang linya sa ilalim na. Ang mga search puno ay pangunahing sa AI. Subalit ang mga ito ay hindi masyadong makakuha ng ito ng tama sa lahat ng oras. Sa katunayan, sa isang pulutong ng mga kaso na ang tunay na pag-aalaga namin ang tungkol sa, nais namin na bumuo ng isang puno, ngunit hindi namin talagang makakuha upang gumawa ng lahat ng mga desisyon. Ang mga ito ay tinatawag na mga sitwasyon adversarial paghahanap, na kilala rin bilang kung paano sumulat ng paglalaro laro systems at mababayaran para dito. Ngunit ang mga ito ay ang mga uri ng sistema kung saan ako ay maaaring makakuha ng upang piliin kung kailan ako pumunta mula sa Boston, na lungsod pumunta ako sa susunod. Subalit matapos na, ang ibang tao ay maaaring makakuha ng upang gumawa ng mga desisyon tungkol sa kung saan ako lumipad. Kaya upang bumuo ng mga uri kaayusan, hindi namin pagpunta sa may upang gumawa ng isang bahagyang iba't ibang mga diskarte na ito. Hindi namin pagpunta upang ma- lamang ng paghahanap sa pamamagitan ng mga puno sa ngayon, dahil hindi kami ang isang bagay na nasa kontrol ng bawat isa sa mga desisyon ng mga puntos. Kaya sabihin isipin ang isang simple laro tulad ng tic-tac-daliri sa paa. Kaya kong magsimula sa isang ganap na blangko board. At sa tic-tac-daliri, Makakakuha X kang maglaro. At kaya ako ay maaaring isipin ang tungkol sa lahat ng mga posibleng gumagalaw na maaaring gumawa ng X. At kung ako ang isa sa paglalaro ang X, na malaki. Mayroon akong siyam na posible gumagalaw na maaari kong gawin. Maaari ko bang ilagay ang isang X sa anumang isang ng siyam na mga posisyon sa mga. At pagkatapos ay mula sa bawat isa sa mga iyon, ako maaaring isipin kung ano ang susunod na mangyayari. Well, sa kasong ito, ang iba pang mga player ay makakuha ng upang kumuha ng isang pagliko. O nais makakuha ng upang kumuha ng isang pagliko. At mula sa bawat isa sa mga, may ay walong iba't ibang lugar na O maaaring ilagay ang kanilang mga marker. Ipagpalagay natin na ako ay nagpasya na ako ay pagpunta sa ilagay ang isang X sa sentro. Na palaging tila tulad ng isang magandang pagbubukas ilipat. Kaya kong tumingin sa ilalim nito, ang walong posibleng gumagalaw na gumagawa ng O. Ngayon, kung ako naglalaro X, na kahanga-hanga. Nakukuha ko upang pumili ng isa ko pumunta sa, ang isa sa gitna. Ngunit ngayon ay makakakuha O pumili. At hindi ko magkaroon ng kontrol higit na desisyon. Subalit mula sa bawat isa sa mga posibleng posisyon board, mayroong pagkatapos ay isa pang set ng mga posibilidad. Kapag ito ay dumating upang maging my i-on muli, nais ko makakuha upang pumili at sabihin, well, kung O gumagalaw sa, well, gitna spot sa kaliwa, at pagkatapos ay Mayroon akong isang hanay ng mga posibilidad kung saan maaari kong kunin ang aking susunod na ilipat. Mula sa mga, maaari ko isaalang-alang ang lahat ng ang mga posibilidad sa ilalim nila. At pagkatapos O nais makakuha ng upang makapili sa mga iyon. At ako ay maaaring panatilihin ang gusali na ito punong kahoy hanggang sa nakuha ko sa punto kung saan ang alinman sa isang tao nanalo ang game-- na Nakakuha na isinasaalang-alang ang isang dahon node-- o ang board ay ganap na full at walang sinuman ay nanalo. At na pupuntahan din na maging isang dahon node. Iyon ay magiging isang itali. Ngunit ang mga bagay na nakakalito sa mga ito ay kung ito ay lamang ng isang regular na paghahanap Ang problema, gusto kong ma- sabihin nating, well, dapat pumunta dito X. At O dapat pumunta paraan banda roon. At pagkatapos X ay dapat pumunta sa paglipas dito. At pagkatapos O dapat pumunta paraan banda roon. At pagkatapos X ay makakakuha ng tatlong sa isang hilera, at manalo ako. At ang laro ay higit sa sa limang gumagalaw, tatlo para sa akin, dalawang para sa aking mga kalaban. Ngunit hindi ako palaging makakuha upang pumili na. Kaya sa halip, kung ano ang hindi namin pagpunta sa may sa gawin ay kami ay pagpunta sa may na magkaroon ng isang bagong diskarte. At ang mga diskarte na madalas na ginagamit ng game-paglalaro algorithms ay kung ano ang tawag dito minimax. Ang pangunahing ideya ng minimax ay na hindi namin pagpunta sa pick paglipat na nagbibigay sa ang aming mga kalaban ang pinakamasama posibleng set ng gumagalaw na maaari nilang gawin. Hindi ito ginagawa sa akin ng anumang magandang upang pumili ng isang ilipat kung saan Maaari ko magagawang upang manalo pagkatapos ng na, dahil ang aking mga kalaban ay hindi pagpunta sa bigyan ako ng pagkakataong iyon. Sila ay pagpunta sa pumili ng ilang mga kakila-kilabot na resulta para sa akin. Kaya ako ng pagpunta sa gawin ang lumipat na ang mga pwersang aking kalaban upang gawin ang isang bagay na mas mahusay para sa akin. Lahat tama. Tayo'y makita kung paano na gumaganap natin. Kaya narito ang aming mga algorithm sa pseudocode. Kami ay pagpunta sa bumuo ng ang buong puno ng laro. Kami ay pagpunta sa bumuo ng ang buong istraktura. At pagkatapos kami ay pumunta sa pamamagitan ng. At sa pinakadulo ibaba sa bawat isa sa terminal nodes, sa bawat isa sa mga dahon, susuriin namin kung paano mahalaga ay na sa akin? At kami ay pagpunta sa halaga ng mga bagay na ay mabuti para sa akin bilang positibo. Mga bagay na hindi mabuti para sa akin ay mas mababa positive, o zero, o kahit na negatibo. Kaya sa tic-tac-daliri, siguro isang panalo para sa akin ay mabuti. Iyan ay isang isa. At ang kurbatang ay zero. At isang bagay na ang isang pagkawala para sa sa akin, marahil na isang negatibong isa. Ang lahat na bagay ay na ang mga mas mahusay na ito ay para sa akin, mas mataas na iskor na natatanggap nito. Mula sa mga posibilidad sa ibaba, pagkatapos namin i-filter ang pataas. At kapag ito ay ang aking pagkakataon upang piliin sa gitna ng isang set ng mga alternatibo, Makikita ko bang piliin ang isa na nakakuha ng pinakamataas na iskor. At sa tuwing ito ay aking kalaban i upang pumili, Kukunin ko ay ipinapalagay na sila ay pagpunta sa piliin ang isa na may pinakamababang iskor. At kung gagawin ko ito sa lahat ng mga paraan hanggang sa tuktok ng puno, Makikita Aking pinili ng isang landas na nagbibigay sa akin ang pinakamahusay na mga resulta na maaari kong makuha, sa pag-aakala na ang aking kalaban gumagawa ng lahat ng mga karapatan gumagalaw. Tingnan natin ang lahat ng karapatan, kaya hayaan ito sa aksyon muna. At pagkatapos ay bibigyan namin ng aktwal tingnan ang code para dito. Kaya isipin mayroon akong ito malaking puno. At ngayon, hindi ako naglalaro tic-tac-daliri sa paa. Nais kong ibigay sa iyo isang bagay Medyo mas mayamang. Kaya Mayroon akong ilang mga laro kung saan may maraming iba't-ibang mga marka ng na ako ay maaaring magkaroon ng sa dulo. At kaya ako ay bumuo ng ito kumpletong tree. At nakukuha ko sa unang ilipat. Ako ay sa ugat ng mga punong kahoy. At nakukuha ko upang pumili na- kaya nakukuha ko upang i-maximize sa kabuuan na unang node. At pagkatapos ay makakakuha ng aking mga kalaban na pumunta. At pagkatapos ay ako makakakuha ng upang pumunta nang isa pang beses. Kaya down sa ibaba, ako ay may isang hanay ng mga mga posibilidad na maaari kong pumili mula sa, iba't-ibang mga terminal estado ng laro. Kung ako pababa ko sa na malayo pakaliwa kamay sulok, at nakikita ko na Mayroon akong isang pagpipilian sa pagitan ng isang walong, isang pitong, at ng dalawa, well, ako ang isa na hindi nakakaabala sa mga pinili. Kaya ako ng pagpunta sa pumili ang pinakamahusay na isa sa mga iyon. Pupunta ako upang piliin ang alas-otso. Kaya alam ko na kung ako ba makakuha ng pababa sa puntong iyon, Kukunin ko magagawang upang makakuha ng na walong puntos. Kapag ako ay humantong sa susunod na point higit sa, ang susunod na node sa loob, isang siyam, isang isa, o isang anim, well, ako pagpunta upang piliin ang pinakamahusay sa mga iyon. Makikita ko bang piliin ang siyam. Kung ako ay may isang pagpipilian sa pagitan dalawa, at apat na, at ang isa, Makikita ko bang piliin ang apat na, ang pinakamataas. Ngayon, kung ako ay tumingin sa ang antas sa itaas na, ang aking kalaban ang isa ay makakakuha ng upang gumawa ng mga pagpili. Kaya ang aking mga kalaban ay nakakakuha sa pumili, ang gusto kong ibigay sa kanya ang bagay na nangyayari upang makakuha ng kanya walong puntos, o huwag kong ibigay sa kanya ang mga bagay na pagpunta sa magbibigay sa kanya ng siyam na puntos, o ang mga bagay na nangyayari upang bigyan siya ng apat na puntos? At ang aking mga kalaban, pagiging may talino, ay pagpunta upang piliin ang mga minimum na mga, ay pagpunta upang piliin ang apat. At maaari kong gawin ito sa pamamagitan ng buong tree. Maaari ba akong pumunta down na iyon middle set ng tatlo. At maaari kong pumili sa pagitan ng isa, tatlo, lima. At nakukuha ko na pumili. Kaya pinili ko ang isang limang. Maaari ba akong pumili ng tatlo, siyam, o dalawang. Nakukuha ko upang pumili, kaya pinili ko ang siyam. Anim, lima, o dalawa, pinili ko. Nakukuha ko upang piliin ang anim. Level itaas na, kung sino upang piliin? Kung sino ang pipiliin? Ang iba pang mga tao, ang aking kalaban. Kaya pumili sila ng limang, siyam, o anim na, na kung saan ang isa? Madla: Ang limang. Tagapagsalita: nilang piliin ang lima. Makakuha ng mga ito upang piliin ang minimum. At pagkatapos ay ang huling isa, pumili ng isa, dalawa, o tatlo. Nakukuha ko upang pumili, kaya pinili ko ang tatlo. Siyam, pitong, o dalawa, pinili ko ang siyam. At 11, anim, o apat, pinili ko 11. Aking kalaban pagkatapos ay pinipili ng tatlo, siyam, o 11, pinipili ang minimum. Siya ay nagbibigay sa akin ng isang tatlong. At pagkatapos ay sa wakas sa tuktok ng bunga ng punong kahoy na nakukuha ko upang pumili muli. At nakukuha ko upang pumili sa pagitan isang apat, ang isang limang, o tatlo. Kaya kumuha ako ng lima. Kung nakuha ko upang makontrol ang lahat ng bagay, gusto ko gawin ang mga landas na humantong sa 11. Ngunit hindi ko makakuha upang gumawa ng mga pagpili. Kung bababa ako na path. Aking kalaban ay lakas sa akin sa ang pagpipilian na humahantong sa isang tatlong. Kaya ang pinakamahusay na maaari kong gawin ay na kumuha na middle branch, gumawa na pagpipilian na huli pagpunta sa humantong sa akin na limang puntos. Iyan ang ginagawa minimax. Lahat tama. Tingnan natin ang isang pagtingin sa na. Kaya dito sa CS50 IDE ay isang programa na nagpapatupad minimax maglaro tic-tac-daliri sa paa. Kami ay pagpunta sa bumuo ng up ng isang representasyon. Kami ay pagpunta sa may dalawang opponent-- o dalawang manlalaro, ang aming computer player at isang tao na player. Number Player ay ang isa ay naglalaro ang O. Iyon ay makikita ang machine player. Makakuha ng mga ito upang ilipat ang second. At ang iba pang player, ang aming player ng tao, ay X. At upang gumawa ng aking buhay ng isang maliit na simple, pupuntahan ko sa label na ang mga negatibong sa isang manlalaro. Kaya ko lang multiply sa pamamagitan ng negatibong isa upang magpalitan pagitan ng isang player at iba pang mga. Kumuha ng isang pagtingin sa lahat ng mga karapatan, kaya hayaan kung ano ang aktwal na kami ay pagpunta sa gawin. Kami ay pagpunta upang tukuyin ang aming board. Ito ay pagpunta sa maging, well, kami ay pagpunta upang payagan ang mga ito upang maging tatlong sa pamamagitan ng tatlong, o maaari naming kahit na i-play limang sa pamamagitan ng lima o pitong sa pamamagitan ng pitong tic-tac-daliri kung gusto mo sa tulad ng, batay sa ilang mga dimensyon D. At kami ay may isang pares ng helper function na kailangan gawin ang mga bagay tulad magpasimula ng screen-- o sorry, magpasimula ng aming mga variable, i-clear ang screen, gumuhit ng board sa screen, isa na tseke sa isang board upang makita kung o hindi mayroong isang winner, isa na Pina-parse sa pamamagitan ng command line, para lamang makatulong sa labas, isa na bumabasa sa input, at ang isang function na tinatawag na minimax. At iyon ang isa Makikita pinapahalagahan namin ang karamihan tungkol sa. Ngunit una Tingnan natin ang mga pangunahing ipaalam. Ano ang gagawin namin? Well, kami ay pagpunta sa parse ang aming command line, basahin lamang sa at makita kung ano ang dimension board nais naming magkaroon. Susubukan naming magpasimula ng aming board. At pagkatapos ay gagamitin namin magpasok ng isa malaking ligaw loop, paulit-ulit na tanggapin gumagalaw hanggang ang laro ay won, o walang gumagalaw kaliwa. Sa bawat oras na pumunta kami sa pamamagitan ng na loop, kami ay i-clear ang screen. Susubukan naming gumuhit ng board sa screen. At hindi namin sadyang uri ng abstracting mga layo bilang subroutines, upang hindi tayo kailangang mag-alala masyadong marami tungkol sa mga detalye ng kung paano sila mangyari. Magkakaroon ka mamaya sa araw na ang code. At kung gusto mong hanapin sa pamamagitan ng at malaman, maaari mong makita ang mga ito sa lahat. Ngunit kami ay gumuhit ng isang board sa screen. At pagkatapos ay gagamitin namin suriin at makita, kailangan namin ng isang nagwagi? Ay nanalo ng isang tao ang larong ito? Kung mayroon sila, makikita naming i-print out ng isang mensahe pagtatagumpay. At kami na tapusin ang laro. Ipapakita rin namin na suriin at tingnan kung may isang itali. Makikita ito ay madaling makita kung may isang itali. Ibig sabihin nito na ang lahat ng mga puwang ay puno na, ngunit may ay hindi pa isang nagwagi. Maaari naming ipahayag ang isang itali at gawin. Pagkatapos ay ang tunay karne-- kung ito ay isang machine player, Makikita pinapayagan namin na machine player sa paghahanap sa pamamagitan ng paggamit na ito minimax algorithm, upang mahanap ang pinakamahusay na ilipat na maaari ito. At pagkatapos ay maglalagay kami na ilipat up. Kung hindi man, kung ito ay isang tao na player, ipapakita namin basahin ang ilang mga input mula sa mga tao. At pagkatapos ay kung ito ay ang tao player o ang machine player, gagawin namin ang isang pares kaunti bits ng error checking, tiyakin na ito ay mananatiling sa loob ng hangganan ng aktwal na sukat ng board na mayroon kami, tiyakin na space na walang laman, na walang ni ilagay ang isang piraso doon na. At pagkatapos namin lamang ilagay isang piraso sa board, baguhin ang player sa susunod na layer, at paglakas gaano karaming mga gumagalaw na nangyari. Iyon ang pangunahing loop para sa aming tic-tac-daliri laro. Minimax, pagkatapos, ay eksaktong ang algorithm na kami dati. Ang tanging pag-aayos na ginawa naming kaya na namin maaaring i-play ng mas mataas na dimensional boards ay hindi namin malinis na ito ng karagdagang mga parameter na tinatawag na depth. At malalim na lang sabi, kung hindi ako naghahanap pababa sa pamamagitan ng punong kahoy na at kumuha ako sa ngayon down lampas ilang mga malalim na antas na ako lang ang hindi gusto upang magpatuloy, Pupunta ako upang ihinto at lamang suriin ang mga board sa puntong iyon. Kukunin ko i-check at tingnan kung mayroong isang nagwagi. Kung mayroong isang nagwagi, bumalik ako sa kanila. Kung hindi man, kailangan ko pumunta sa pamamagitan ng isang loop. At sasabihin ko, para sa lahat ng ang mga posibleng lokasyon na maaari kong posibleng tumagal bilang aking ilipat, kukunin ko bumuo ng isang hypothetical board na Kabilang dito ang aking paglipat sa na board, at pagkatapos ay recursively tawag minimax. Kung ito ay ang aking ilipat, nakukuha ko upang mahanap ang isa na nakuha ang pinakamalaking puntos. Kung ito ay ilipat ang aking mga kalaban, nakita namin ang isa na ang Nakakuha ang minimum na puntos. At lahat ng iba pa ay lang record-iingat. Tingnan natin ito run Lahat ng karapatan, kaya hayaan. Sa totoo lang, siguro makakaya namin makakuha ng isang pares ng mga boluntaryo upang makabuo ng at i-play tic-tac-daliri sa paa. [Hindi marinig] isa, at isa higit pa, dalawa, may karapatan. Lumapit sa up. Kaya sabihin sige at i-restart ito nang tuluyan. So, hi. Madla: Hi. Tagapagsalita: Ano ang pangalan mo? Madla: Gorav. Tagapagsalita: Gorav. Madla: Ako Layla. Tagapagsalita: At Layla, at Layla, paumanhin. Lumapit sa up. Gorav, kami ay pagpunta sa may unang pumunta ka. At ako pagpunta sa hilingin sa iyo na maging isang hindi masyado magandang tic-tac-daliri player. OK, kaya ang lahat ng presyon ay off sa iyo. Tingnan natin, bagaman, na ipaalam sa aming mga makina maaari talagang gawin ang isang bagay na player smart. Kaya sige lang. Ikaw ay pagpunta sa i-type sa kung saan coordinate nais mong ilagay ang iyong mga X in. A0, OK, at ang mga makina ay wala na kaagad at ilagay ang kanyang marka sa A1. Ilagay ang O sa board. Lahat ng karapatan, ngayon sige. Saan mo gustong pumunta? C2. Ang aming mga machine player ay nagsagawa gitna square, naka-block sa iyo. Kaya na ay isang magandang, matalino na bagay para sa mga ito upang gawin. Na-block mo ito. Iyan ay mahusay. Ito ay tumatagal ng sulok doon. At ito ay pagpunta upang pilitin mong gawin ang isa huling space, B0. At ang laro ay nagtatapos sa isang itali. Ngunit ito nilalaro ng isang makatwirang game laban sa iyo, di ba? Lahat ng mga karapatan, salamat talaga, Gorav. [Palakpakan] Lahat ng mga karapatan, Layla, kami ay pagpunta up ang laro sa iyo dito. Madla: Oh, great. Tagapagsalita: Kami ay pagpunta sa bigyan iyo ng apat na sa pamamagitan ng apat tic-tac-daliri sa paa. Ngayon, sa pamamagitan ng apat na apat, mayroon kang upang manalo may apat sa isang hilera, hindi tatlong sa isang hilera. At lahat ng ito sa iyo. Kaya Layla kinuha D1. Ngayon Kami ay pagpunta sa sundin ang aming mga computer na player dito. Tatlong sa pamamagitan ng tatlong tic-tac-daliri ay ang uri ng mga bagay na madali para sa ating lahat. Ngunit ito ay maganda pa rin upang makita ang paggawa ng smart gumagalaw computer player. Apat sa pamamagitan ng apat makakakuha sa maging isang maliit na trickier. Maayos na Natapos. Lahat ng karapatan, kaya Layla tapos off. Oh, at kami ay dapat may natapos doon. Ngunit sabihin gawin ang isa pang up dito. Kaya Layla, salamat. Maayos na Natapos. [Palakpakan] Kaya napupunta ang aming tic-tac-daliri manlalaro pamamagitan at hahanap ng mga lokasyon, malulutas nito ang mga ito gamit ang minimax. At ako ay may isang setting lalim sa na upang ang mga ito hindi tatakbo masyadong mabilis, na kung saan ay marahil kung bakit Layla ay maaaring pumunta ng mabuti mauna tulad ng ginawa niya, at ginawa nang mahusay. Ngunit ang mga sistema na lamang pumunta sa pamamagitan at malupit na puwersa pumunta mas malalim, at mas malalim, at mas malalim, at panatilihin ang paghahanap ng solusyon na kailangan nila, ang mga uri ng sistema ng ay lubos na matagumpay sa mga ito, na rin, standard board games. At sa katunayan, kung tiningnan namin sa isang tatlong sa pamamagitan ng tatlong tic-tac-daliri laro, ito ay karaniwang isang problema malulutas. At ito ay isang kahanga-hangang diagram mula sa Randall Munroe sa XKCD, na nagpapakita kung saan ililipat mo dapat tumagal, ibinigay na gumagalaw ng iyong kalaban. Ito ay isang bagay na maaaring namin madaling tukuyin maagang ng panahon. Ngunit ano ang mangyayari bilang makuha namin sa mas maraming kumplikadong mga laro, mas masalimuot games, kung saan may mga malaking boards, mas posibilidad, mas malalim na diskarte? Ito ay lumiliko out na ito malupit na puwersa naghahanap pa rin ay makatwirang mabuti, maliban kapag ikaw ay makakuha sa punto kung saan puno na ay kaya malaki na hindi ka maaaring kumatawan sa lahat ng ito. Kapag hindi ka maaaring kalkulahin ang buong puno, kapag hindi ka maaaring pumunta pasulong at push ang iyong sarili sa punto kung saan na sa iyo tapat na paraan ang buong puno sa memorya, o kung maaari mong makuha ito sa memory at ito ay lamang magdadala sa iyo ng paraan masyadong mahaba upang maghanap sa pamamagitan ito, kailangan mong gawin ang isang bagay na mas matalinong. Upang magawa iyon, ikaw may sa gawin ang dalawang bagay. Una, kailangan mong mahanap ang ilang mga paraan ng paglilimita ng iyong malalim. Well, na ang OK. Maaari naming mahanap ang ilang mga nice, hubad minimum at sabihin mo, maaari ka lamang pumunta kaya malalim. Ngunit kapag ginawa mo na, na ang ibig sabihin sa iyo magkaroon ng mga bahagyang hindi kumpleto boards. At kailangan mong pumili, ang gusto ko ito bahagyang hindi kumpleto board, o ito bahagyang hindi kumpleto board? At sa aming apat na sa pamamagitan apat tic-tac-daliri laro, aming computer player got down hanggang sa ibaba at sinabi sa mga ito, Mayroon akong dalawang magkaibang boards. Wala alinman sa isa ay isang panalo. Wala alinman sa isa ay isang pagkawala. Wala alinman sa isa ay ang kurbatang. Paano ako pipili sa pagitan ng mga ito? At hindi ito ay magkakaroon ng isang matalinong paraan ng paggawa na. Nakakakita kami ng ganitong uri ng mangyari pagsusuri sa lahat ng oras bilang makuha namin sa mga mas kumplikadong mga laro. Chess ay isang magandang halimbawa. Sa chess, kami, first sa lahat, ang isang mas malaking board. Mayroon kaming malayo higit pang mga piraso. At ang pagpoposisyon ng mga piraso at ang paraan na ang mga piraso ilipat ay critically mahalaga. Kaya kung gusto kong gumamit ng minimax, Kailangan ko bang maging magagawang tukuyin at sabihin, ang board na ito, kung saan walang ay won o nawala pa, sa anuman ay mas mahusay kaysa sa iba pang mga ito board, kung saan walang ay won o nawala. Upang gawin iyon, maaari kong gawin mga bagay na tulad ko lamang ang maaaring bilangin kung gaano karaming mga piraso ang mayroon ako at kung gaano karaming mga piraso ang mayroon kayo? O baka bigyan ako ng iba't ibang piraso ng iba't ibang mga puntos. My queen ay nagkakahalaga ng 20 puntos. Ang iyong nakasangla ay nagkakahalaga ng isang punto. Sino ang may kabuuang higit pang mga point? Pag-usapan ako ng mga bagay tulad ng, sino ang Nakakuha ang mas mahusay na posisyon board? Kaninong naman ito sa susunod, anumang bagay na maaari kong huwag na suriin ang mas tumpak kung alin sa mga posibilidad ay mas mahusay na walang exhaustively-alang bawat galaw na maaaring dumating pagkatapos na. Ngayon na gumawa ng trabaho, isa sa mga bagay na pagpunta sa maging tunay na mahalaga para sa atin ay hindi lamang ang paglipat ng tuwid down sa isang partikular na lalim limitasyon, ngunit nagagawang sabihin, isa sa mga ideya na ako Mayroon ay masama na ito ay hindi nagkakahalaga isaalang-alang lahat ng posibleng paraan na ang mga bagay ay maaaring pumunta mula sa masamang sa mas masahol pa. Para gawin na, kami ay magdagdag sa minimax isang prinsipyo na tinatawag Alph-beta. At alpha-beta nagsasabing, kung mayroon kang isang masamang ideya, huwag mag-aksaya ng iyong oras na sinusubukan mong alamin kung paano masamang ito ay. Kaya narito kung ano ang namin ang pagpunta sa gawin. Kami ay pagpunta sa gawin ang parehong prinsipyo na kami ay nagkaroon ng bago, parehong minimax type ng paghahanap, lamang hindi namin pagpunta subaybayan, hindi lamang ng aktwal na mga halaga na mayroon kami, ngunit bibigyan namin ng subaybayan ang mga pinakamahusay na posibleng halaga na maaari kong makuha, at ang pinakamasama posibleng kinalabasan maaari ba akong magkaroon. At anumang oras ang pinakamasama posibleng bagay ay naghahanap malamang, Kukunin ko abandunahin na bahagi ng puno. At hindi ko kahit abala pagtingin sa mga ito anymore. Lahat ng karapatan, kaya isipin na sisimulan namin may ito parehong eksaktong puno ng laro. At ngayon kami ay pagpunta upang pumunta down na muli, ang lahat ng mga paraan down sa kaliwang sulok na ilalim. At sa ilalim na sulok sa kaliwa, namin Tumingin at sinusuri namin ang board na ito. Siguro ito ay isang apat na sa pamamagitan ng apat tic-tac-daliri board, o marahil ito ay isang chess board. Ngunit tumingin kami sa mga ito, at sinusuri namin ito, at kami makakuha ng isang halaga ng alas-otso. Sa puntong iyon, alam namin na kami ay pagpunta upang makakuha ng hindi bababa sa walong puntos na ito mula sa ilalim ng desisyon. Hindi mahalaga kung ano ang iba pang mga dalawang ay, na pitong at na dalawa. Sila ay maaaring maging anumang mga halaga na kanilang nais na maging. Kami ay pagpunta upang makakuha ng hindi hindi bababa sa walong puntos. Lahat ng mga karapatan, ngunit maaaring namin sige at tingnan. Siguro isa sa mga ito ay mas mahusay kaysa sa walong. Inaasahan naming sa pitong. Ay na mas mahusay kaysa sa eight? Hindi, na hindi baguhin ang aming mga opinyon sa lahat. Tinitingnan namin ang dalawa. Ay na mas mahusay kaysa sa eight? Hindi, na hindi baguhin ang aming mga opinyon sa lahat. Kaya ngayon ay alam namin na namin naubos lahat ng mga posibilidad doon. Hindi namin pagpunta upang makakuha ng anumang mas maganda kaysa sa walong. Kami ay pagpunta upang makakuha ng eksakto alas-otso. At kaya baguhin natin na buko at sabihin nating, na ay isang katiyakan na ngayon. Pumunta kami ng hanggang sa isang antas sa itaas na. At ngayon ay alam namin ang isang bagay tungkol na antas minimization. Alam namin na hindi kami ay pagpunta upang makakuha ng higit sa walong puntos kung pumunta kami pababa na direksyon. Dahil kahit na sa mga i-out sa iba pang mga dalawang sangay upang maging kapani-paniwala at nagkakahalaga ng libu-libong mga puntos sa bawat isa, ang aming kalaban ay magbigay sa amin ng minimum, at bigyan kami ng alas-otso. Lahat ng mga karapatan, well, tingnan natin. Itatago namin ang pagpunta down na ang landas. Bumaba kami sa gitna na nasa kaliwa. Inaasahan naming down at makita naming may isang siyam. Alam namin na kami ay pagpunta upang makakuha ng hindi bababa sa siyam na puntos sa pamamagitan ng pagpunta pababa na gitnang kalsada. At sa puntong ito, maaari naming lamang i-pause. At maaari naming sabihin, tumingin, ako alam sa mga antas sa itaas, Pupunta ako upang makakuha ng hindi hihigit sa walong puntos sa pamamagitan ng pagpunta pababa direksyon. Ngunit kung bumaba ako sa gitna landas sa halip na ang sa kaliwa path, Gusto kong makakuha ng hindi bababa sa siyam na puntos. Aking mga kalaban ay hindi pagpunta sa hayaan mo akong bumaba na ang gitnang landas. Makakuha ng mga ito upang pumili. At sila ay pagpunta upang piliin ang landas sa kaliwa patungo sa walong, sa halip na pababa sa gitna patungo sa kung ano ang hindi bababa sa siyam na puntos. Kaya sa puntong iyon, magagawa ko bang itigil. At sasabihin ko, alam mo kung ano? Hindi ko na kailangang hanapin ang anumang mas down sa direksyong iyon. Dahil hindi ako pagpunta sa makarating doon. Maaari kong laktawan ang higit sa isa, at maaari kong laktawan ang higit na anim, dahil na ay hindi kailanman pagpunta sa mangyayari. Kaya makikita bababa ako at kukunin ko isaalang-alang ang mga susunod na posibilidad. Bababa ako doon at sinasabi ko, nakikita ko ang isang dalawang. Alam ko kung makakuha ako na dito, ako pagpunta upang makakuha ng hindi bababa sa dalawang. SIGE. Panatilihin ko ang pagpunta. Nakakakita ako ng isang apat. Alam ko ako pagpunta upang makakuha ng hindi bababa sa apat. Mayroon pa rin ng maraming pagitan apat at walong, bagaman. Kaya panatilihing ako pagpunta. Tumingin ako at nakikita ko mayroong isa. Lahat ng mga karapatan, alam ko kung Bababa ako ng path na ito, Pupunta ako sa ma-piliin ang apat. Ano ang aking mga kalaban pagpunta sa gawin? Sa pagitan ng isang bagay na nagbibigay sa akin walong, isang bagay na nagbibigay sa akin ng apat, at isang bagay na ay nagbibigay sa akin ng hindi bababa sa siyam, well, siya ay pagpunta sa bigyan ako ng apat. At alam ko na ngayon sa pinakatuktok, pupuntahan ko na maaaring makakuha ng hindi bababa sa apat na puntos sa larong ito. Ang buong ideya ng alpha-beta ay upang i-cut off bahagi ng puno kaya na hindi ko tingnan ang mga ito. Ngunit ito pa rin hitsura tulad ng ako ay pagtingin sa isang pulutong ng mga punong kahoy. Ni panatilihin ang pagpunta down Hayaan. Kami ay pumunta pababa sa susunod na isa ngayon. Down sa ibaba, nakahanap ako ng isa. Alam ko ako pagpunta upang makakuha ng hindi bababa sa isa. Itago ko na hinahanap. Nakahanap ako ng tatlo. Alam ko ako pagpunta upang makakuha ng hindi bababa sa tatlong. Panatilihin ko ang pagpunta. Nakahanap ako ng lima. Alam ko ako pagpunta upang makakuha ng limang kung makakuha ako pababa sa path na iyon. At ako din alam pagkatapos na ang aking kalaban, kung ako piliin ang gitna ng ang tatlong malaking pagpipilian, siya ay pagpunta upang bigyan ako isang bagay na lima o mas mababa. SIGE. Maaari ko bang panatilihin ang pagpunta doon. Maaari ko bang tingnan ang down at ako Maaari sabihin, kung ano ako pagpunta upang makakuha ng kung pumunta ako pababa sa gitna path? Pupunta ako upang makakuha ng, well, tatlo doon. Pupunta ako upang makakuha ng isang bagay na hindi bababa sa tatlong. May mga bagay-bagay sa pagitan pa rin tatlong at limang, upang panatilihin ko naghahanap. Oh, isang siyam, idedetalye ko talaga tumagal na sa loob ng isang tatlong. Pupunta ako upang makakuha ng hindi bababa sa siyam kung pumunta ako pababa na gitnang landas. Ngayon ang aking mga kalaban ay tumigil at nagsabi, tumingin, walang point anymore. Alam ko na ang aking minimization kalaban, siya ay pagpunta sa magbibigay sa akin ng bagay na mas mababa sa o katumbas ng limang, sa halip na ang bagay na mas malaki kaysa sa o katumbas ng siyam. Itigil ko. Hindi ko tumingin ng anumang higit sa na. Panatilihin ko ang pagpunta. Tumungo ako sa isang ito. Down sa ibaba, nakahanap ako ng anim. Alam ko ako pagpunta upang makakuha ng hindi bababa sa anim. At kung ano ang maaari kong gawin? Maaari ko bang itigil. Dahil mayroong isang pagpipilian sa pagitan ng isang bagay na hindi bababa sa anim at isang bagay na kukulangin sa limang, siya ay pagpunta sa magbibigay sa akin ng bagay na mas mababa sa limang. At ngayon alam ko na ako pagpunta upang makakuha ng eksakto na pagpipilian. Pupunta ako upang makakuha ng na limang pinili. Bumalik ako hanggang sa tuktok. Aling ako pagpunta sa pumili sa pagitan ng isang bagay na mas malaki kaysa sa o katumbas ng apat, o isang bagay na katumbas sa lima? Pupunta ako sa gumawa ng isang bagay na hindi bababa sa lima. Bababa ako sa huling landas, ang lahat ng ng mga paraan pababa hanggang sa ibaba. May isang isa. OK, hindi bababa sa ako pagpunta upang makakuha ng isang punto. Panatilihin ko ang pagpunta. Dalawang, oh, na mas mahusay kaysa isa. Pupunta ako upang makakuha ng hindi bababa sa dalawang. Nakahanap ako ng tatlo. Alam ko ako pagpunta upang makakuha ng tatlo. At ang punto sa itaas na, ang aking mga kalaban ay pagpunta upang bigyan ako ng isang bagay na mas mababa sa o katumbas ng tatlo. At ngayon, maaari ko bang itigil. Dahil sa pagpili sa pagitan ng akin pagiging maaaring makakuha ng isang limang at ang aking kalaban pagbibigay sa akin ng isang bagay na mas mababa kaysa sa tatlong, Laging ako pagpunta sa tumagal na lima. Kaya hindi ko na suriin na ilalim na bahagi ng puno sa lahat. Ngayon, ito ay maaaring mukhang menor de edad. Ngunit kapag maliit na piraso ng arithmetic, mas malaki kaysa at mas mababa sa, Maaari tabasin buong bahagi ng ito exponentially lumalagong puno, na humahantong sa isang malaking halaga ng savings, savings na malaki sapat na ako magsimula ng paglalaro ng mapagkumpitensya sa mas komplikadong laro. Lahat ng karapatan, kung tinitingnan namin ang laki at pagiging kumplikado ng iba't ibang mga games, tic-tac-daliri ay ang aming madaling halimbawa. Nakakuha kami ng isang maliit na board, tatlo sa pamamagitan ng tatlong. Makuha namin, sa karamihan, ang isang average ng tungkol sa apat na iba't ibang mga pagpipilian bilang namin pumunta sa pamamagitan ng laro. Mayroon kaming isang lugar sa paligid 10 sa fifth posibleng iba't ibang mga dahon. At ang pagbuo ng isang tic-tac-daliri player, well, ginawa lamang namin ito. Madali lang. Kung pupunta tayo sa isang bagay na mas complex, tulad Connect Four. Naaalala mo ba ang laro kung saan mong i-drop ang maliit na token sa? Ito ay isang anim na sa pamamagitan ng pitong board, hindi na marami ng mas malaki, hindi pa rin ay tungkol sa parehong sumasanga kadahilanan tulad ng tic-tac-daliri sa paa. Mayroon akong tungkol sa apat na mga pagpipilian kung saan maaari ko bang ilagay ang mga bagay sa. Ngunit ngayon, Mayroon akong ng maraming higit pa leads, 10 hanggang ika-21 kapangyarihan. Iyan ay isang bagay na madaling sapat na malutas namin ito agad-agad. Checkers, mas complex-- mo Nakatanggap ng isang walong sa pamamagitan ng walong board. Ikaw lamang sa kalahati ng ang mga ito sa anumang oras, kahit na. Mayroon kayong isang sumasanga kadahilanan na ang tungkol sa 2.8. Well, namin nakuha ng isang pares gumagalaw na maaari mong gawin. Mayroon kayong 10 hanggang ika-31 na dahon, mas malaki, at mas malaki, at mas malaking puwang. Bilang ako sa paghahanap sa pamamagitan mga malaki at mas malaki na mga puwang, na kapag ang mga bagay tulad ng mga alpha-beta at kawalan ng kakayahang tabasin buong sanga nagiging napakahalaga. Ngayon, pamato ay madaling sapat sa 1992. Isang programa sa computer na tinatawag Chinook matalo ang pamato mundo kampeon, Marion Tinsley. At mula noon, walang human master player ay may nagawang upang talunin ang pinakamahusay computational system. Kung titingnan natin sa isang bagay tulad ng chess, ngayon muli, kami ay may isang walong sa pamamagitan ng walong board. Ngunit kami ay may mas kumplikado piraso, mas kumplikadong mga paggalaw. Kami ay may isang sanga kadahilanan ng tungkol sa 35, 35 posibleng mga gumagalaw sa average na maaari kong gawin, at isang estado space, ang isang bilang ng mga dahon na lumago hanggang 10 sa 123 na kapangyarihan, napakalaking bilang ng mga posibilidad. Kahit pa rin, modernong processors ay magagawang gawin ito matagumpay. Noong 1995 at pagkatapos ay sa 1997, sa isang computer programa na tinatawag na Deep Blue binuo sa pamamagitan ng IBM na tumakbo sa isang higanteng supercomputer matalo ang kasalukuyang kampeon ng mundo, Garry Kasparov. Ito ay isang balik point. Ngayon, bagaman, na parehong processing kapangyarihan nakapatong sa aking MacBook. Bilis Processing mapigil pagkuha ng mas mabilis at mas mabilis. Maaari naming suriin ang higit pa at mas boards mas mabilis at mas mabilis. Ngunit higit sa lahat, kailangan namin ng mas mahusay pagsusuri function at mas mahusay na pruning pamamaraan. Kaya maaari naming maghanap sa space pa complexly. Ang pinakamalaking ng board games na maaari naming isipin, isang bagay tulad ng Go na Nakakuha ng 19 sa pamamagitan ng 19 board, ngayon biglang, hindi namin nakaraang ang punto kung saan maaaring manalo computational system. Walang computational sistema out there na maaaring matalo ng isang propesyonal Go player. Ang pinakamahusay na mga sistema ng ranggo ito ngayon tungkol ang mga uri ng mahusay na antas amateur. Kaya may lubos ng kaunti pa rin sa labas doon na maaari mong hindi pa makapunta sa. Lahat ng mga karapatan, ang mga ito tradisyunal na laro board, mga uri ng mga system kung saan namin magtayo ito minimax, kung ito ay nakuha alpha-beta o hindi, ang mga algorithm sa trabaho dahil mayroong mga tiyak na limitasyon. Mayroon kaming perpektong impormasyon tungkol sa mundo. Alam namin na kung saan ang lahat ng mga piraso ay. Ang mundo ay static. Makakakuha Walang sinuman upang ilipat ang mga piraso sa paligid habang ako upo doon iisip, pagkuha ng aking turn. Mayroong isang space pagkilos na hiwalay. Maaari ko bang ilagay ang aking mga nakasangla dito, o maaari ko bang ilagay ang aking mga nakasangla dito. Hindi ako pinapayagan upang ilagay ang aking nakasangla sa mga linya sa pagitan ng dalawang mga parisukat. At sa wakas, ang mga aksyon ay deterministic. Alam ko na kung sinasabi ko, tore upang knight tatlo, aking tore ay pagpunta sa dulo up sa knight tatlo, hangga't ito ay isang wastong ilipat. Walang kawalan ng katiyakan tungkol sa na. Ngayon, habang pumunta ako sa mas iba't ibang uri ng laro, kami ay may sa basagin ang mga pagpapalagay. Paano kung pumunta ako sa isang bagay tulad ng classic video games? Narito ang isang seleksyon ng mga video laro mula sa Atari 2600. Ano ang mayroon ako doon? Mayroon akong Frogger, Space Manlulupig, patibong, at Pac-Man. Anong mga uri ng mga kapaligiran ang mayroon ako para sa ngayon? Alin sa mga pagpapalagay kailangan kong break? Well, ito ay depende sa laro. Maaari ko bang i-play ang chess sa 2600, at ito ay magiging tulad ng ito ay bago. Para sa karamihan ng mga sistema, mayroong kumpletong kaalaman tungkol sa mundo. May ganap na deterministic aksyon. Ngunit kadalasan, ang mundo ni hindi na static. Iyon ay, habang ako nakaupo doon naghihintay, ang isang bagay ay gumagalaw. Ang multo ay darating upang makakuha ng sa akin. Scorpion ay sumusunod sa akin sa ilalim. Ang space manlulupig ay darating na mas malapit at mas malapit. Kung gaano kahusay ang maaari naming gawin laban sa mga ito? Ilang taon na ang nakalipas, ang Google ay isang proyekto na tinatawag DeepMind, kung saan sila sanay na sa isang computer program upang i-play Atari 2600 laro. At kung sa tingin mo ito ay hindi seryoso negosyo, ang mga resulta ng kanilang pag-aaral ay nai-publish sa Nature, kaya lamang tungkol sa bilang mabuting ng isang publication na maaari mong posibleng makakuha ng. At narito ang kung paano sila gumanap. Sila ay mayroon ng isang algorithm na nakaupo at pinapanood lang ang input screen. Nakuha ko walang mga tagubilin kung ano pa man tungkol sa mga patakaran ng laro. At ito ay dapat na malaman kung, batay sa kanyang puntos, kung gaano kahusay ito ay ginagawa. Ito ay isang sistema na ginagamit ng isang bagay tinatawag na dagdag na mga kagamitan sa pag-aaral. Iyon ay, ito ay tumingin sa kanyang iskor. At kung nakuha ito ng isang magandang marka, ito sinabi, Dapat kong matandaan ang mga bagay-bagay. At ang dapat kong gawin sa mga muli. At kung nakuha ito ng isang masamang iskor, ito sinabi, Hindi ko dapat gawin ang mga bagay. Ito ay ang pagganap ng mga nasanay na mga sistema pinapayagan upang i-play para sa isang ilang oras sa bawat laro, kumpara laban sa mga propesyonal na mga manlalaro. Kaya para sa lahat ng mga laro na sa kaliwang bahagi ng linya na ito, ito self-hasa computer program outperformed ang mga propesyonal na mga manlalaro. At para sa lahat ng bagay upang ang karapatan, ang mga propesyonal na mga manlalaro ay ang pinakamahusay pa rin. Para sa isang bagay na alam walang tungkol sa mga patakaran, na walang tungkol sa istraktura ng mga alam laro, ito ay kahanga-hanga na pagganap. At ito ay kung ano ang hindi namin magawa ngayon. OK, sabihin mo, ngunit kung tayo isipin ang tungkol sa Ai sa games, normal sa tingin namin tungkol sa bagay-bagay na maaari naming talagang umupo at lumaban. Kung ako umupo at i-play ko StarCraft, o i-play ko Free salain, ang computer na kalaban ay ang tao sa pagkontrol ng Zerg, o pagkontrol sa iba pang mga kabihasnan. Paano gawin ang mga manlalaro aktwal na mahanap ang kanilang mga galaw? Well, ang mga laro ay balangkas marami sa parehong paraan tulad ng sa aming mga board games, mga larong ito na bibigyan namin ng sama-sama tumawag apat na laro X, galugarin, expand-- kalimutan ang mga bago. Ano ang mga ito? Galugarin, palawakin, at mapatay, Sa tingin ko ay ang huling isa. Ngunit hindi sila talaga games paggalugad at pagtagumpayan. Kadalasan, ang computer na kalaban doon ay may limitadong impormasyon. Hindi nila alam kung ano mismo ang nangyayari sa likod na hamog na ulap ng digmaan. Hindi sila makakuha ng upang makita kung ano ang mayroon ka sa iyong imbentaryo. May isang kapaligiran na dynamic. Lahat ay nagbabago sa lahat ng oras. Hindi mo na makakuha upang umupo at maghintay upang kumuha ng iyong paglipat. Ngunit karamihan ng mga bagay ay hiwalay pa rin. Kailangan ko bang ilagay ang aking mga lungsod dito. O kailangan kong ilagay ang aking mga lungsod dito. At lahat ng bagay ay deterministic. Kapag sinasabi ko, ilipat ang aking mga unit dito, ang aking yunit gumagalaw dito, maliban kung ang isang balakid bigla dumating sa play. Ngayon, na hindi lahat ng mga computer games na ang mayroon ngayon. Kung pupunta ako at i-play ko ang isang unang uri ng tao laro, isang bagay tulad ng magnanakaw o Fallout o Skyrim, o Halo, ngayon Mayroon akong mga kalaban computer na wala doon na mayroon isang napaka-ibang sitwasyon. Ang mga ito ay, muli, ng limitadong impormasyon. Sila lamang ang maaaring makita ang isang tiyak na field ng pagtingin. Ang kapaligiran ay dynamic pa rin. Mga bagay ay pagbabago sa lahat ng oras. Ngunit ngayon ay mayroon akong isang mas tuloy-tuloy na space action. Maaari ko sumisilip lamang ng isang maliit na piraso sa labas ng pintuan. At ilang mga laro, ang aking mga aksyon ay stochastic. Nakukuha ko na subukan upang lumipat sa ibabaw ng pader na iyon, ngunit Mayroon akong isang pagkakataon ng hindi pagtupad. Ang mga uri ng laro ay nakakakuha ng mas malapit at mas malapit sa mga uri ng mga controllers na bumuo kami sa robotics. Sa robotics, kami ay may sa ipalagay na kami ay may limitadong impormasyon. Mayroon kaming mga sensor na sabihin sa amin ang tungkol sa mundo. Kami ay may isang laging-bagong, dynamic na kapaligiran. Kami ay may isang mundo kung saan ang space ay tuloy-tuloy, sa halip na hiwalay. At ang aming mga pagkilos, kapag sinubukan namin ang mga ito, magkakaroon ng isang pagkakataon ng mga kamalian. At sa katunayan, modernong laro controllers para sa iyong Halo kalaban, o para sa mga NPCs sa Skyrim, talaga magpatakbo ng maliit na robotics architectures. Pakiramdam nila sa mundo. Bumuo sila ng isang modelo ng mundo. Sila compute batay sa isang hanay ng mga mga layunin na nais nilang makamit. Plano nila aksyon batay sa kung ano ang alam nila. At ang mga ito ay eksaktong kapareho ng uri ng mga sistema na bumuo namin sa robotics. Kaya ang mga ito architecture, upang magkasama dalhin ito pabalik, ay madalas na lubos ang parehong. Kaya sabihin makita kung maaari naming makita na. Bumalik tayo sa ating Halimbawa tac-tic-daliri. At ako pagpunta sa humingi ng isang pares ng aking post-docs na pumanhik at makakatulong sa akin. Kaya Chen Ming, at Alessandro, at Olivier, kung ikaw guys ay dumating up. At ako pagpunta sa kailangan isang pares ng mga volunteers OK, nakita ko ang isang kamay hanggang sa kanan doon sa gitna. Hayaan akong kumuha ng isa pang, ang isang tao karagdagang sa likod siguro. Lahat ng karapatan, banda roon. Lumapit sa up. Lahat tama. Kaya sabihin na pabalat down. At kung ikaw guys ay dumating karapatan bumalik sa paligid dito para sa akin, hindi kapani-paniwala. Kaya ito ay isang robot na tinatawag Baxter. And Baxter ay isang robot na ang isang commercial platform, na idinisenyo sa pamamagitan ng isang kumpanya na tinatawag na umisip na muli. At ito robot ay dinisenyo para sa mga maliliit na-scale manufacturing. Ngunit ngayon kami ay pagpunta sa gamitin ito upang i-play tic-tac-daliri sa paa. Ngayon, robot na ito ay din ng isang bagay iyan ay medyo kakaiba. Dahil kung ako ay nakatayo sa kahit saan malapit sa isang karaniwang factory automation system, gusto kong maging sa tunay na libingan panganib ng pagiging nasugatan. Gayunpaman, Baxter, ay idinisenyo upang maging medyo ligtas upang makipag-ugnay sa. At sa gayon maaari kong itulak sa mga ito robot. At makikita mo ito ay isang maliit na bit flexible na ito ay lilipat sa paligid. At maaari ko ba itong muling iposisyon kung saan gusto ko ito upang pumunta. Ngayon sa isang normal robotic system, gusto naming magkaroon ng isang hanay ng mga kasukasuan dito na magiging direkta pagtugon sa mga utos na posisyon. At hindi nila kinakailangang pag-aalaga kung sila ay gumagalaw sa pamamagitan ng bukas na hangin, o kung ang mga ito ay gumagalaw sa pamamagitan ng aking ribcage. SIGE. At kadalasan, kung kayo ay dito sa isang pang-industriya na sistema, Gusto mong pumunta wala na malapit dito. May ay magiging dilaw kaligtasan tape ang lahat sa paligid nito. Ang system na ito ay may isang bahagyang naiiba disenyo na maging friendlier at mas madali para sa mga tao upang makipag-ugnayan, in na sa bawat joint, may isang spring. At sa halip na pagkontrol isang eksaktong posisyon, kontrolin namin ang isang tiyak na halaga ng torque, ang isang tiyak na halaga ng puwersa, na kami ay nais na maging sa na spring. Lahat ng karapatan, kaya hayaan mo akong kumuha ng aming mga volunteers dito. Hi anong pangalan mo? Madla: Louis. Tagapagsalita: Louis. Nice upang makita ka. At? Madla: David. Tagapagsalita: David. Masaya akong makilala kayo. Kung ikaw guys ay maghintay karapatan dito para sa isang segundo, Pupunta ako upang bigyan ka ng isang pagkakataon na gawin ito. Kaya ito robot, kung ikaw ay magkaroon ng at kung ikaw itulak malumanay sa mga ito, ikaw ay pagpunta upang makita na gumagalaw ito nang kaunti. At kung sunggaban mo na ito ng tama dito sa pulso lamang sa itaas kung saan ang mga pindutan ay, ito Mukhang dapat mong mang-agaw ng mga pindutan, ngunit sa halip grab karapatan sa itaas nito, makikita mo maaaring napaka malumanay manipulahin ito sa pamamagitan ng puwang. Louis, gusto mong subukan mo ito? Kaya bigyan ito ng isang maliit na itulak sa magsimula sa. At pagkatapos ay kung ikaw ay ilagay ang iyong mga daliri may karapatan at hold na papunta sa mga ito, dahil ito ay ilipat para sa iyo pagkatapos. Lahat ng karapatan, gusto mong subukan mo ito? Lumapit sa up. Kaya bigyan ito ng isang magiliw itulak doon upang magsimula. Maaari mong pakiramdam kung ano ito ay tulad ng. At pagkatapos ay kung sunggaban mo ito doon, Makikita mo na ang pakana sa paligid. SIGE. Kaya kadalasan, ang ganitong uri ng isang robot gagawin gamitin para sa mga maliliit na proporsyon manufacturing. At ako pagpunta upang ilipat ito bisig lamang down na sa labas ng paraan ng kaunti dito. Ngunit ngayon, kami ay pagpunta sa gamitin ang mga parehong tic-tac-daliri sa paglalaro ng system batay sa minimax na aming binuo mas maaga. SIGE? Kaya, ikaw guys ay sa bawat pagpunta sa play ng isang laro. Louis, ikaw ay pagpunta sa maging unang. Hayaan lamang hold up ako dito para sa isang segundo. Pupunta ako sa mayroon kang tumayo karapatan dito, kaya lang ang lahat ng tao ay maaaring makita ka. Ay naka-set up ka ng isang lalaki dito? ROBOT: Welcome. Maglaro ng tic-tac-daliri Hayaan. Huwag hawakang mahigpit ang iyong token bago Sinasabi ko na ito ay ang iyong turn. Sisimulan ko ang laro. Ito ay ang aking turn. Tagapagsalita: Ngayon, kung ikaw ay maaaring tumagal ng isa sa mga ang iyong mga piraso at sige, at ilagay ito. ROBOT: Ito ay ang iyong tira. [Tawa] Ito ay ang aking turn. [Tawa] [Tawa] Ito ay ang iyong tira. Tagapagsalita: Ang sangkatauhan ay pagbibilang sa iyo dito, Louis. ROBOT: Ito ay ang aking turn. Tagapagsalita: So Baxter Matagumpay na naharang dito. ROBOT: Ito ay ang iyong tira. Ito ay ang aking turn. Ito ay ang iyong tira. Ito ay ang aking turn. Tagapagsalita: At kami na ipaalam sa Baxter tapusin ang kanyang huling ilipat dito. [Tawa] ROBOT: Iyan ay isang itali. Ako ay manalo sa susunod na pagkakataon. [Tawa] Tagapagsalita: Lahat ng mga karapatan, salamat talaga, Louis. Salamat. Maaari kang pumunta sa ganitong paraan. ROBOT: Sisimulan ko ang laro. Tagapagsalita: Kaya hayaan mo akong magpaliwanag sa iyo ng isa pang maliit kaunti bago makuha namin ang aming rematch dito. Ano ba talaga ang nangyayari? Kaya may isang top camera up dito ang robot. At ito ay naghahanap down sa board. At ito ay nakakakita man ito ay nakuha ng isang pulang O o isang asul and white X. Bilang mga makakuha ng ilagay sa mga board, iyan ay isa lamang ang parehong input na ay pagbabasa sa kami mula sa aming mga istraktura ng data mula sa aming mga screen. Ito ay tumatakbo sa parehong minimax algorithm upang maging maaaring makahanap ng kung saan sa maglagay ng isang magandang token. At pagkatapos kami ay nagbibigay ng isang command tungkol kung saan nais naming sa isang token na mailagay. Braso ay gumagalaw out. Ito ay ang paggamit ng isang vacuum gripper na mag-aplay ilang higop sa na piraso ng kahoy, pick up na ito, ilipat ito sa kanan lugar, at pagkatapos ay bitawan ang higop at i-drop ito. Lahat ng mga karapatan, kami ay pagpunta upang bigyan ito ng isa pang shot may bahagyang mas matalinong player dito. Handa ka na? Lahat ng mga karapatan, kung nais mong tumayo karapatan up dito at bigyan a-- i-out sa ganitong paraan upang maaari mong makita ang lahat ng tao. At pagkatapos ay [hindi marinig]. ROBOT: Ito ay ang aking turn. Tagapagsalita: Baxter ay magsisimula. Ito ay ang iyong tira. Ito ay ang aking turn. Ito ay ang iyong tira. Ito ay ang aking turn. [Tawa] Tagapagsalita: [WHISPERING] Lamang hayaan siyang magpatuloy at manalo. ROBOT: Ito ay ang iyong tira. Tagapagsalita: Iyon ay OK. ROBOT: Ito ay ang aking turn. [Tawa] Manalo ako. [Tawa] Sisimulan ko ang laro. Tagapagsalita: Sige, salamat sa inyo. Lahat ng mga karapatan, sa tingin ko namin nakuha ng panahon para sa isa pang mahusay na tic-tac-daliri player, isang tao na maaaring ilagay ang bagay na ito sa tumugma sa, na nakakaalam kung ano ang kanilang ginagawa. [Tawa] Sino ang pagpunta sa maging dito sa aming kampeon? Lahat ng mga karapatan, nagboluntaryo mo ang iyong mga kaibigan. Iyan ay mahusay na sapat para sa akin. Sabihin mo sa akin ang iyong pangalan muli. Madla: Tamir. Tagapagsalita: Tamir, nice na makita ka. Lahat ng mga karapatan, muli, kami ay pagpunta sa ilagay mo karapatan dito kaya lahat ay maaaring makita ka. Ikaw ang aming mga kinatawan sa ito tugma ngayon. Baxter ay isa at naku at oh. O sorry, isa oh at isa. At ito ay nasa sa iyo dito. Baxter ay makarating sa unang ilipat, bagaman. So. ROBOT: Ito ay ang aking turn. [Tawa] Ito ay ang iyong tira. Ito ay ang aking turn. Ito ay ang iyong tira. Ito ay ang aking turn. Ito ay ang iyong tira. [Tawa] ROBOT: Ito ay ang aking turn. Tagapagsalita: Ito ay isang pulutong mas mahirap kapag ikaw ay nakatayo up dito, kakailanganin ng mga tao. [Tawa] ROBOT: Ikaw ang tao ay kaya madaling upang matalo. [Tawa AT palakpakan] Tagapagsalita: Maraming salamat. ROBOT: manalo ako. Sisimulan ko ang laro. Tagapagsalita: Lahat ng mga karapatan, kaya thanks very marami na Olivier, at upang Alessandro, at upang Chen Ming. [Palakpakan] Gusto kong gumawa ng isang huling point. Kaya Baxter sa pinakadulo katapusan doon, ginulangan. At iyon ay hindi inaasahang. Isa sa mga kamangha-manghang mga bagay-bagay tungkol sa AI ay na tayo gawin ang trabaho sa AI upang maaari naming bumuo ng talagang kawili-wili at intelligent device. Ngunit din ang ginagawa namin sa trabaho sa AI dahil ito ay nagsasabi sa amin ng isang bagay tungkol sa kung paano ang mga tao ay intelligent. Isa sa mga paborito mga pag-aaral mula sa aking lab ay naghahanap sa kung ano ang mangyayari kapag biglaan impostor machines. Ginawa namin ito hindi orihinal na may Baxter naglalaro tic-tac-daliri, ngunit may isang mas maliit na robot na may pangalang Nao, na nag-play rock-paper-gunting. At kung minsan matapos naglalaro ng maraming at maraming ng panganganak rock-paper-gunting games, ang robot ay ihagis ng isang kilos, mawala, at pagkatapos ay biglang baguhin kanyang kilos at sabihin, manalo ako. [Tawa] Ngayon, kung minsan namin na gusto ring magkaroon ng mga robot, lamang bilang isang control, magtapon ng isang kilos, manalo, at baguhin ang kilos nito upang mawala, itapon ang mga tugma, impostor upang mawala. At iyon ay hindi halos bilang nakakahimok. Ang robot na cheats upang manalo ng mga tao tumugon sa bilang kung ito ay out upang makakuha ng mga ito, tulad ng ito ay aktibong naghahanap ng kanilang pagkalipol. [Tawa] Ito ay nagiging isang ahente. Ito ay tulad ng isang tao. Ito ay may paniniwala at layunin. At ito ay hindi magandang intensyon. At ang mga robot na itinapon sa laro ay lamang umaandar nang tama. Ito ay lamang ng isang putol na aparato. Hayaan akong ipakita sa iyo ng isang pares ng mga halimbawa ng na mula sa ilang sa aming mga kalahok. Kaya dito ang Pandaraya upang mawala. [Playback ng video] - [Hindi marinig] manalo. Maglaro tayo. -Maghintay, Ano? - [Hindi marinig] manalo. Maglaro tayo. [Hindi marinig] manalo. Maglaro tayo. Tagapagsalita: At dito pagdaraya upang manalo. -Oo, Manalo ako. Maglaro tayo. -Hindi Mo maaaring gawin na. [Tawa] -Oo, Manalo ako. -Nandaya ka. Dinaya mo ngayon. -Oo, Manalo ako. -Hey, Ikaw cheater. Lokohin mo, sobrang cheat. [END playback] Tagapagsalita: Ang mga iba't-ibang reaksyon mabilis baguhin ang aming pang-unawa ng mga aparato. Nangangahulugan ba ito na kusa naming bumuo machine na impostor dahil na ang pinakamahusay na engineering na maaari naming gawin? Hindi, ngunit ito ay nagsasabi sa amin ng isang bagay talagang kawili-wiling tungkol sa mga tao. Na bagay na cheats sa iyo at magnanakaw ang iyong tagumpay, na ang isang bagay na buhay, na bigyang-buhay, iyon ang out para makakuha ka. Ito ay may kaisipan ng estado. Ito ay may paniniwala. Ito ay may layunin. Na bagay na iniabot ang laro sa iyo, na hindi. Iyan na lamang umaandar nang tama. Ito ay sa maraming mga paraan kung bakit ito ay madaling magtapon ng mga laro na may mga bata. Ngunit kung susubukan mo upang dayain ang mga ito at ang uri ng mga claim tagumpay kapag, alam mo, sa iklian lamang ang laro, ang mga ito ay mahuli sa iyo kaagad. Ang mga uri ng mga epekto na nakikita namin na lumalabas mula sa AI, sila magturo sa amin ng maraming tungkol sa ating sarili. Lahat ng mga karapatan, na ito para sa araw na ito. Maraming salamat sa David at pangkat ng produksyon Harvard para sa pagdating down. [Palakpakan] Susubukan naming makita mo para sa quiz na isa, at pagkatapos ay para sa isang huling panayam. Magkaroon ng isang magandang araw. [Palakpakan] [MUSIC nagpe-play] DAVID J MALAN: Well, marahil na kailangan namin upang ipakilala ang ilang mga uri ng pag-encrypt, right? Dahil pagkatapos ay ang mga header ng mga kahilingan ng HTTP ay piniritong upang ang kahit sino sinusubukan na umamoy ang iyong trapiko hindi aktwal na magagawang makita ang mga ito. Kaya kung ano ang solusyon sa problemang ito? Well, kailangan namin upang aktwal na kitang ipakilala encryption sa formula, kaya na kapag ang tao ay Ipinapadala ang data mula A hanggang B, Maaari naming ligtas send-- [Tawa] Ang impormasyon sa isang paraan na ang mga kalaban ay hindi maaaring, sa katunayan, makita ito.