[Daqq tal-mużika] SPEAKER: Merħba lura, kulħadd. Dan huwa CS50. U llum, aħna għandna ħafna ta ' affarijiet interessanti li jitkellmu dwar. L-ewwel, għalkemm, għandi biex tfakkar inti ta 'affarijiet amministrattivi ftit. Din il-ġimgħa hija kwizz waħda, l-Erbgħa jew għas-sezzjoni Yale nhar ta 'Tlieta u Ħamis, nhar il-Ħamis. Hemm reviżjonijiet kwizz tonight fil-Yale, 5:30-07:00. Fil-Harvard, huma rreġistrati bieraħ wieħed. U kulħadd jistgħu jaraw dak online. Ukoll, din il-ġimgħa jew ġimgħa d-dieħla kmieni, għandna aħħar lecture CS50 tagħna. [Groans] I know. Daħal hekk malajr. Istudenti Yale se jkollhom live jagħti konferenza hawn fil--iskola liġi sala nhar il-Ġimgħa. Se jkun hemm kejk. Istudenti Harvard se jkollhom l- aħħar lecture fil Sanders nhar it-Tnejn. Se jkun hemm ukoll kejk. Ukoll, din il-ġimgħa nhar il-Ġimgħa, għal dawk minnkom li huma ġejjin lejn New Haven, aħna għandna l-Expo CS50. Għamilna aktar minn 30 gruppi differenti rreġistrati biex turi li inti dak kollu minn sailboats awtonomi, għal sistemi li jirrikonoxxu ritratti diġitali, għall-kompjuter mużika u mużika prodotta bil-kompjuter. Allura jekk jogħġbok jingħaqdu magħna. Naħseb li għaddej biex tkun ħafna ħin. Illum, għalkemm, we biex tkompli jitkellem dwar AI, dwar intelliġenza artifiċjali. U waħda mill-affarijiet li aħna qed tmur biex tikseb llum hija l-idea ta 'kif użu AI sabiex isolvu problemi. Issa, kif dejjem, Nibdew ma 'xi ħaġa sempliċi. U aħna qed tmur biex tibda bi idea sempliċi. U li jużaw search. Allura immaġina għal minuta li I għandhom kompitu li għandi bżonn biex iwettqu. U nixtieq li jkollhom dak il-kompitu awtomatizzat billi xi aġent software. Immaġina li jien tipprova ktieb sett ta 'titjiriet minn, ejja ngħidu, Boston li San Francisco. I tista 'tmur permezz u I jistgħu jużaw wieħed mill-tiftix online isbaħ għodod, li se tagħmel bażikament l-istess proċess li aħna qed ser jimxu permezz llum. Imma jekk inti ma kellhiex dak għodda, dak li għandek tagħmel? Well, inti tista 'tfittex u tara u jgħidu, jien fil Boston. Liema titjiriet huma disponibbli għalija? Issa, forsi għandi tliet titjiriet possibbli minn Boston li se jaqbel l-ħin I meta bżonn leave. I jistgħu jtiru lejn Chicago. Jew I jistgħu jtiru lejn Miami. Jew I jistgħu jtiru lejn New York. I jistgħu mbagħad jidhru minn kull wieħed minn dawk l-ibliet destinazzjoni u jaħsbu dwar dak postijiet I jista 'possibbilment tilħaq minn kull wieħed minn dawk l-ibliet individwali. Allura forsi minn Chicago, I jistgħu jiksbu titjira diretta lejn San Francisco. Li eċċellenti. Jew I jistgħu jiksbu titjira lejn Denver. Issa, forsi dik it-titjira lejn San Francisco huwa s-soluzzjoni perfetta għalija, imma forsi le. Forsi jien tfittex xi ħaġa li l-ftit irħas jew ftit aħjar għall-iskeda tiegħi. U so I tista 'tfittex dak oħra possibbiltajiet jista 'jkun hemmhekk. So I tista 'tħares lejn Denver. U minn Denver, ukoll, forsi I jistgħu jiksbu titjira lejn Austin. U minn Austin, forsi I jistgħu jiksbu titjira lejn Phoenix, u minn Phoenix li San Francisco. Issa, jien ma isir s'issa. Minħabba forsi hemm titjira diretta minn New York li San Francisco li perfett għalija. Jew forsi hemm titjira minn Miami permezz Denver li l-lott orħos. So I għad iridu jgħaddu. U għadni għandek tfittex fil kollha ta 'dawk bliet li jien ma investigati għadhom. I għandhom jiċċekkjaw b'mod eżawrjenti kollha il-possibbiltajiet li I jista 'jkollhom. Allura minn New York, forsi I jistgħu jiksbu titjira lejn Nashville, u minn Nashville li Austin. U allura naf fejn jien. U mbagħad naf minn Austin, nista ' jtiru lejn Phoenix, u minn Phoenix li San Francisco. Jekk I ħallsu għall-ewwel għal Miami, għalkemm, forsi I jistgħu jiksbu titjira minn Miami li Nashville, jew minn Miami għall Austin. U issa stajt ppruvaw kollha dwar il-possibbiltajiet. Stajt mibnija din il-graff li turi me kollha tar-rotot possibbli li I jista 'jkun kapaċi li jieħu. Meta aħna jirrappreżentaw dawn tipi ta 'problemi, aħna mhux qed tmur biex jirrappreżentaw minnhom espliċitament bħala din il-graff, minħabba li graff ma tirrappreżentax l-istorja ta 'fejn konna marret. Jafu li I tellgħu mill Phoenix lejn San Francisco ma tell me jekk I daħal permezz Nashville, jew permezz Denver, jew permezz Miami. Allura dak I ser tagħmel minflok qed I ser tieħu din l-istess problema, u jien ser jirrappreżentaw bħala siġra. U fl-għerq tal-siġra, fil- top, jien ser tpoġġi l-post li bdejt, Boston. U minn Boston, I ser tħares lejn kollha tal-postijiet possibbli li I jistgħu jivjaġġaw lejn. Ukoll, f'dan il-każ, kelli tlieta, Chicago, New York, u Miami. U mbagħad I ser tesplora kull wieħed dawn it-tfal fil-siġra. Minn Chicago, I raw li kelli żewġ titjiriet. I jistgħu jtiru direttament lill San Francisco jew biex Denver. Issa San Francisco, li l-għan tiegħi. C'est destinazzjoni tiegħi. Li għaddej biex tkun werqa ta 'din is-siġra. Dan huwa, jien qatt ma se jmorru x'imkien wara San Francisco. Mill Denver, għalkemm, I jistgħu jtiru minn Denver li Austin, minn Austin għal Phoenix, u minn Phoenix għal San Francisco. U issa għal darb'oħra, stajt laħaq werqa. I tista 'imbagħad mur lura għall-ieħor belt li jien ma esplorati bis-sħiħ. Dan ikun New York, mur lura sa l-quċċata ta 'siġra tiegħi, tinżel għal New York. Minn New York, I jistgħu jtiru lejn Nashville, minn Nashville għal Austin, minn Austin għall Phoenix, u minn Phoenix lejn San Francisco. U fl-aħħarnett, belt waħda I ma jkunux ħarsu lejn għadhom, Miami. Well, minn Miami I said I kellhom żewġ possibbiltajiet, Nashville jew Austin. Jekk I jtiru lejn Nashville, tajjeb allura I fly minn Nashville, Austin, Phoenix, li San Francisco. Jekk I jtiru lejn Austin, I fly Austin, biex Phoenix, li San Francisco. U issa għandi siġra. Huwa siġra komplet. Dan kollu tal-possibbiltajiet u kollha tal-mogħdijiet li I tista 'tieħu. Dan huwa, jekk nibda fil- għerq tal-siġra fil-quċċata u I jinżlu għal wieħed mill- weraq, hija me dice mhux biss fejn jien ser jispiċċaw, San Francisco, iżda jgħidlekx me-rotta li I bżonn tieħu biex naslu s'hemm. Issa, li wieħed minn dawn huwa l-aħjar? Well, xejn dwar dan problema għadhom jgħidlekx me liema minn dawn huwa l-aħjar soluzzjoni. Forsi I kura l-aktar dwar kemm ħin jien fl-arja, jew id-distanza li jien jtajru. F'dak il-każ, Chicago lejn San Francisco jista 'jkun l-iqsar numru ta 'mili fl-arja. Maybe I care about ispiża. U lkoll nafu titjiriet diretti huma ġeneralment aktar għaljin. Hekk forsi jekk I jieħdu din tip ta 'rotta lura permezz Miami, Nashville, Austin, Phoenix, forsi imbagħad I jiksbu prezz aktar baxx. Imma I jistgħu jottimizzaw fuq kwalunkwe kriterji li I jimpurtahom. Li ltqajna l-aħjar fl titjira Wi-Fi, jew li ajruporti jkollhom l-aħjar ikel disponibbli. U kull wieħed minn dawk jista tagħti me soluzzjoni differenti li nara bħala l-aħjar. Dawn it-tipi ta 'problemi, fejn aħna qed tmur biex jibnu din is-siġra tal possibbiltajiet, u mbagħad tħares lejn kull wieħed minn dawk mogħdijiet individwali, u jeżamina liema minn dawk jissodisfa a kriterji għalina, aħna qed tmur biex sejħa dawk il-problemi tat-tiftix. U għandna lottijiet ta ' algoritmi, li wħud minnhom Rajna diġà, li jmorru u jesploraw dawk is-siġar. Stajna nagħmlu dan fil-mod li I biss għamlet, tfittxija-fond ewwel, jinżel 'l isfel safejn nistgħu sakemm aħna hit weraq, u mbagħad jiġu lura up, u jmorru lura d-dritt isfel. Jew nistgħu nagħmlu dak li hu imsejħa tfittxija wisa ewwel. Nistgħu jespandu kollox fil-quċċata, u mbagħad kollox linja waħda taħt dik, u mbagħad kollox linja waħda taħt dak. Dawk is-siġar tat-tiftix huma fundamentali biex AI. Iżda dawn ma pjuttost tikseb dan id-dritt l-ħin kollu. Fil-fatt, fil-lott tal-każijiet li aħna verament jimpurtak, rridu nibnu siġra, imma aħna ma attwalment nikseb biex jagħmlu kollha tad-deċiżjonijiet. Dawn huma sitwazzjonijiet msejħa tfittxija tal-kontradittorju, magħrufa wkoll kif kif jiktbu jilagħbu logħba sistemi u nikseb mħallas għaliha. Iżda dawn huma t-tipi ta 'sistemi fejn I tista 'tikseb li jagħżlu meta mmur minn Boston, li belt mmur jmiss. Iżda wara dan, xi ħadd ieħor tista 'tikseb jieħdu d-deċiżjoni dwar fejn I fly. Allura biex jibnu dawn istrutturi tipi, aħna qed se jkollhom jieħdu xi ftit approċċ differenti lilha. Aħna mhux se tkun tista ' biss tfittex permezz-siġra aktar, għaliex aħna mhux qed il-wieħed li fil-kontroll ta 'kull wieħed minn dawn il-punti deċiżjonijiet. Mela ejja jimmaġina sempliċi logħba bħal tic tac toe. I tista 'tibda bil board kompletament vojta. U fil tic tac toe, X gets jilagħbu l-ewwel. U so I jista 'jaħseb dwar l- jiċċaqlaq possibbli li X tista 'tagħmel. U jekk jien l playing wieħed l-X, li l-kbir. Għandi disa possibbli jiċċaqlaq li I jistgħu jagħmlu. I tista 'tpoġġi X fi kwalunkwe wieħed ta 'dawk disa pożizzjonijiet. U mbagħad minn kull wieħed minn dawn, I jista 'jimmaġina dak li jiġri li jmiss. Ukoll, f'dan il-każ, l-ieħor player se tikseb biex tieħu dawran. O se tikseb biex tieħu dawran. U minn kull wieħed minn dawn, hemm Ikun tmien postijiet differenti li O tista 'tpoġġi markatur tagħhom. Ejja ngħidu I iddeċieda li I kien se timplimenta X fil-ċentru. Li dejjem tidher qisha ftuħ mossa tajba. I tista 'tħares lejn taħtha dan, il- tmien passi possibbli li O jagħmel. Issa, jekk jien playing X, li mill-isbaħ. I nikseb li jagħżel liema waħda I mur, il-wieħed fin-nofs. Imma issa O gets li jagħżlu. U jien ma jkollhom kontroll fuq dik id-deċiżjoni. Iżda minn kull wieħed minn dawk posizzjonijiet possibbli tal-bord, hemm mbagħad ieħor sett ta 'possibbiltajiet. Meta niġu li tkun tiegħi dawran darb'oħra, nixtieq jiksbu toqgħod jgħidu, ukoll, jekk O jiċċaqlaq fil-, ukoll, il-post tan-nofs fuq ix-xellug, imbagħad I ikollhom sett ta 'possibbiltajiet fejn I tista 'tieħu pass li jmiss tiegħi. Minn dawk, I tista 'tikkunsidra li kollha il-possibilitajiet taħthom. U allura O se tikseb jagħżlu fost dawk. UI jistgħu jżommu bini dan siġra out sal I ltqajna sal-punt fejn jew xi ħadd jirbaħ l game-- li l- ltqajna biex jiġu kkunsidrati werqa node-- jew il-bord huwa kompletament sħiħa u l-ebda wieħed rebaħ. U li wkoll se tkun node werqa. Li għaddej biex tkun rabta. Imma l-ħaġa delikata ma 'dan huwa jekk dan kienu biss tfittxija regolari problema, I d jkun kapaċi jiġifieri, ukoll, X għandu mur hawn. U O għandhom imorru mod hemmhekk. U mbagħad X għandhom imorru minn hawn. U mbagħad O għandhom imorru mod hemmhekk. U allura X tista 'tikseb tliet in fila, u nirbaħ. U l-logħba se tkun fuq fil-ħames jiċċaqlaq, tlieta għalija, tnejn għal avversarju tiegħi. Imma jien ma dejjem jiksbu li jagħżlu dan. Allura minflok, dak li aħna qed ser ikollhom jagħmlu huwa aħna qed tmur biex ikollhom li għandhom strateġija ġdida. U l-istrateġija li algoritmi logħba playing spiss jużaw huwa dak li sejjaħ minimax. L-idea ċentrali tar minimax huwa li aħna qed ser pick-mossa li tagħti avversarju tagħna l-agħar sett possibbli ta 'jiċċaqlaq li jistgħu jagħmlu. Huwa ma jagħmel me kwalunkwe tajba li jagħżlu mossa fejn I jista 'jkun kapaċi jirbħu wara li, minħabba avversarju tiegħi mhuwiex ser jagħti lili dak iċ-ċans. Huma qed tmur biex jagħżlu xi riżultat terribbli għalija. Hekk jien ser tagħmel l- jimxu li l-forzi avversarju tiegħi li jagħmel xi ħaġa aħjar għalija. Kull dritt. Ejja naraw kif dan jilgħab barra. Allura hawnhekk algoritmu tagħna fil pseudocode. Aħna qed tmur biex jiġġeneraw l-siġra logħba kollha. Aħna qed tmur biex jibnu l-istruttura sħiħa. U allura aħna ser jgħaddu. U fil-qiegħ nett f'kull tal- lymph terminali, f'kull wieħed mill-weraq, aħna ser tevalwa kif valur huwa li għalija? U aħna qed tmur biex affarijiet ta 'valur li huma tajbin għalija bħala pożittiv. Affarijiet li mhumiex tajbin għalija se jkunu inqas pożittivi, jew żero, jew saħansitra negattiv. Għalhekk fl tic tac toe, forsi rebħa għalija hija tajba. Li l-wieħed. U rabta huwa żero. U xi ħaġa li l-telf għal me, forsi li waħda negattiva. Uniku fatt rilevanti huwa li l-aħjar huwa għalija, l-ogħla punteġġ li tirċievi. Minn dawk il-possibbiltajiet fil- qiegħ, allura aħna ser filtru fuq. U meta huwa ċ-ċans tiegħi biex jagħżlu fost sett ta 'alternattivi, I ser jagħżlu l-waħda li ltqajna l-ogħla punteġġ. U kull meta huwa tiegħi avversarji jduru biex jagħżlu, I ser tassumi li dawn qed tmur biex jagħżlu dik bl-punteġġ aktar baxx. U jekk nagħmel dan it-triq kollha sal-quċċata tas-siġra, I ser għażilt triq li tagħti me l-aħjar riżultat li nista 'nikseb, jekk wieħed jassumi li l-avversarju tiegħi jagħmel l-passi dritt. Kull dritt, so ejja naraw dan fl-azzjoni ewwel. U allura aħna ser fil-fatt tħares lejn il-kodiċi għal dan. Allura immaġina I jkollhom din is-siġra kbira. U issa jien ma playing tic tac toe. Jien ridt li jtik xi ħaġa ftit aktar sinjuri. Allura stajt ltqajna xi logħba fejn hemm punteġġi differenti ħafna li I jista 'jkollhom fl-aħħar. U so I jibnu din is-siġra sħiħa. U jien nikseb li jiċċaqalqu ewwel. Jien l-għerq tal-siġra. U nasal biex jagħżlu that-- so I nikseb biex timmassimizza madwar li l-ewwel node. U mbagħad avversarju tiegħi gets li jmorru. U mbagħad niġi biex tmur darba aktar. Allura stabbiliti fuq il-qiegħ, I ikollhom sett ta ' possibbiltajiet li I jistgħu jagħżlu minn, stati terminali differenti tal-logħba. Jekk jien mill-imsemmi xellug kantuniera idejn, u nara li stajt ltqajna għażla bejn tmienja, seba, u tnejn, ukoll, jien il-wieħed li gets biex jagħżlu. Hekk jien ser jagħżlu l-aħjar waħda minn dawk. Jien ser jagħżlu l-tmienja. So I jafu li jekk jien qatt għonqna dak il-punt, I ser tkun kapaċi tikseb li tmien punti. Jekk I jispiċċaw fil-punt li jmiss fuq, il-node li jmiss fuq, ta 'disa, waħda, jew sitt, ukoll, jien ser jagħżlu l-aħjar ta 'dawk. I ser jagħżlu l-disgħa. Jekk I jkollhom għażla bejn tnejn, u erba, u wieħed, I ser jagħżlu l-erba ', l-ogħla. Issa, jekk I tħares lejn il-livell hawn fuq li, avversarju tiegħi hija dik gets li jagħmlu din l-għażla. Allura avversarju tiegħi gets tagħżel, ma nixtieq li jagħtih il-ħaġa li għaddej tikseb lilu tmien punti, jew għandi jagħtih il-ħaġa li l- ser jagħtih disa 'punti, jew il-ħaġa li għaddej li jagħtih erba 'punti? U l-avversarju tiegħi, li razzjonali, va li jagħżlu l-minimu ta 'dawn, se jagħżlu l-erbgħa. U nista 'tagħmel dan permezz tal-siġra kollu. I tista 'tmur għal dan il sett nofs ta 'tlieta. UI jistgħu jagħżlu bejn wieħed, tlieta, u ħamsa. U nasal biex jagħżlu. So I jagħżlu ħamsa. I jistgħu jagħżlu tlieta, disa ', jew tnejn. I nikseb li jagħżlu, so I jagħżlu l-disgħa. Sitta, ħames, jew tnejn, I jagħżlu. I nikseb li jagħżlu l-sitt. Livell ogħla minn dak, li jottjeni li jagħżlu? Li jottjeni li jagħżlu? Il Guy-oħra, avversarju tiegħi. Allura dawn jagħżlu ħames, disa ', jew sitt, liema waħda? UDJENZA: Il-ħamsa. SPEAKER: Huma jagħżlu l-ħames. Huma jiksbu li jagħżlu l-minimu. U allura l-aħħar wieħed, jagħżlu wieħed, tnejn, jew tlieta. I nikseb li jagħżlu, so I jagħżlu tlieta. Disa ', seba', jew tnejn, I jagħżlu disgħa. U 11, sitta, jew erba ', I jagħżlu 11. Avversarju tiegħi mbagħad jagħżel tlieta, disa ', jew 11, jagħżel il-minimu. Huwa jagħti me a tlieta. U mbagħad finalment fil-quċċata tal l-siġra, nasal biex jagħżlu mill-ġdid. U nasal biex jagħżlu bejn erba, ħames, jew tlieta. So I jieħdu l-ħames. Jekk Sirt kontroll kollox, I d tieħu t-triq li wasslet għall-11. Imma jien ma jsibux li tagħmel din l-għażla. Jekk I jinżlu f'din it-triq. Opponent My se seħħ me fis l-għażla li twassal għal tlieta. Allura l-aħjar li nista 'nagħmlu huwa li jieħdu dik il-fergħa tan-nofs, jagħmlu din l-għażla li l-eventwalment ser iwasslu lili biex ħames punti. Dak hu minimax ma. Kull dritt. Ejja tagħti ħarsa lejn dak. Allura hawn fil-CS50 IDE huwa programm li timplimenta minimax jilagħbu tic tac toe. Aħna qed tmur biex jibnu up rappreżentazzjoni. Aħna ser ikollhom żewġ opponent-- jew żewġ plejers, kompjuter tagħna player u player bniedem. Numru wieħed player se jilagħbu l O. Li ser tkun l-attur magna. Huma jiksbu biex jiċċaqalqu tieni. U l-plejer l-oħra, tagħna player bniedem, se jkun X. U biex jagħmlu l-ħajja tiegħi ftit sempliċi, jien ser twaħħal tikketti li juru waħda negattiva player. So I tista 'biss jimmultiplikaw billi wieħed negattiv li tpartit bejn wieħed player u l-oħra. Kull dritt, so ejja tagħti ħarsa lejn dak li aħna qed attwalment se jagħmlu. Aħna ser jiddefinixxu bord tagħna. Huwa ser tkun, ukoll, aħna qed tmur biex ikun jista 'jkun tliet minn tlieta, jew nistgħu wkoll jilgħab ħamsa minn ħames jew seba minn seba 'tic tac toe jekk youd bħal, ibbażata fuq uħud dimensjoni D. U aħna ser ikollhom koppja tal-funzjonijiet helper li ser tagħmel affarijiet simili initialize l screen-- jew sorry, initialize varjabbli tagħna, ċar l- screen, jiġbed l-bord fuq l-iskrin, wieħed li l-kontrolli bord biex tara jekk jew le hemm rebbieħ, wieħed li parses permezz tal-linja tal-kmand, biss biex jgħinu, wieħed li jaqra fil input, u l-funzjoni wieħed imsejjaħ minimax. U li l-waħda aħna ser kura aktar dwar. Imma ejja nħarsu ewwel fil-prinċipali. X'nagħmlu? Well, aħna qed tmur biex parse linja tal-kmand tagħna, aqra biss fi u ara dak dimensjoni bord aħna tixtieq li jkollha. Aħna ser initialize bord tagħna. U allura aħna ser jidħol wieħed loop selvaġġi kbar, ripetutament jaċċettaw jiċċaqlaq sakemm il-logħba hija rebaħ, jew hemm l-ebda jiċċaqlaq xellug. Kull darba aħna jgħaddu dik loop, aħna ser ċar l-iskrin. Aħna ser jiġbed l-bord fuq l-iskrin. U aħna qed deliberatament tip ta ' abstracting dawn bogħod bħala subroutines, hekk li aħna ma jkollhomx għalfejn tinkwieta wisq dwar id-dettalji ta 'kif jigru. Int ser ikollok l-kodiċi aktar tard illum. U jekk inti tixtieq li tfittex permezz u taf, inti tista 'tarahom kollha. Iżda aħna ser jiġbed bord fuq l-iskrin. U allura aħna ser jiċċekkja u tara, għandna rebbieħ? Has xi ħadd rebaħ il-logħba? Jekk ikollhom, aħna ser jistampaw messaġġ rebħa. U aħna ser itemmu l-logħba. Aħna ser jivverifika wkoll u ara jekk hemm rabta. Dan ser ikun faċli li wieħed jara jekk hemm rabta. Dan ifisser li l-ispazji huma sħiħa, iżda ma kien hemm rebbieħ s'issa. Nistgħu tiddikjara rabta u jsir. Imbagħad il-meat-- reali jekk huwa player magna, aħna ser jippermettu li player magna ta 'tiftix permezz ta 'użu dan algoritmu minimax, biex isibu l-aħjar mossa li jista '. U allura aħna ser iqiegħed dak ningranaw. Inkella, jekk huwa player tal-bniedem, aħna ser taqra xi kontribut mill-bniedem. U allura jekk huwa l-bniedem player jew il-player magna, aħna ser nagħmlu ftit ftit bits ta 'verifika żball, kun żgur li jibqa fil-konfini tad-dimensjonijiet attwali tal-bord li għandna, kun żgur li dan l-ispazju ikun vojt, dik implementata ebda wieħed minn biċċa fil hemm diġà. U allura aħna ser biss jitqiegħed biċċa fuq il-bord, jibdlu l-attur għall-saff li jmiss, u inkrement kemm jiċċaqlaq ġara. Dik hija l-linja prinċipali għall logħba tic tac toe tagħna. MINIMAX, allura, huwa eżattament l-algoritmu li aħna qabel. L-unika aġġustament li ħadna sabiex inkunu tista 'tilgħab ogħla bordijiet dimensjonali hija konna miżmuma dan il-parametru extra imsejħa fond. U l-fond biss jgħid, jekk jien tiftix isfel permezz ta 'dak siġra u I nikseb s'issa isfel lil hinn xi fond livell li jien biss ma jridux li jittieħdu passi oħra, Jien ser tieqaf u biss jevalwa l-bord f'dak il-punt. I ser jiċċekkja u ara jekk hemm rebbieħ. Jekk hemm rebbieħ, I ritorn tagħhom. Inkella, I ser jgħaddu minn linja. U jien ser jgħidu, għal kulħadd ta ' il-postijiet possibbli li I jista 'possibbilment jieħdu bħala pass tiegħi, jien ser jibnu bord ipotetiku li jinkludi jiċċaqilqu tiegħi fuq dak il-bord, u mbagħad recursively jitlob minimax. Jekk huwa pass tiegħi, nasal biex isibu l- wieħed li ltqajna l-akbar punteġġ. Jekk huwa pass avversarju tiegħi, insibu il-wieħed li ltqajna l-punteġġ minimu. U kull ħaġa oħra huwa żamma biss ta 'rekords. Kull dritt, so ejja ara din ir-run. Fil-fatt, forsi nistgħu jiksbu koppja ta 'voluntiera biex toħroġ u play tic tac toe. [Inaudible] waħda, u wieħed aktar, tnejn, hemm dritt. Come fuq up. Mela ejja imorru quddiem u terġa 'tibda dan kompletament. Allura, hi. UDJENZA: Hi. SPEAKER: X'hemm isem tiegħek? UDJENZA: Gorav. SPEAKER: Gorav. UDJENZA: Ninsab Layla. SPEAKER: U Layla, u Layla, sorry. Come fuq up. Gorav, aħna qed tmur li jkunu inti tmur l-ewwel. U jien ser jgħidlek biex tkun mhux terriblement tajba player tic tac toe. OK, hekk l-pressjoni hija off fuqek. Ejja naraw, madankollu, li magna tagħna player jistgħu attwalment jagħmlu xi ħaġa intelliġenti. Allura aqbad. Int ser tip li fihom jikkoordina inti tixtieq li jitqiegħdu X tiegħek fil. A0, OK, u l-magna tkun marret dritt bogħod u mqiegħda trade mark tagħha fil A1. Poġġi l-O fuq il-bord. Kull dritt, issa jimxi 'l quddiem. Fejn kieku inti tixtieq li tmur? C2. Player tagħna magna ħadet l-kwadru tan-nofs, imblukkata inti. Allura li kien tajjeb, ħaġa intelliġenti biex tagħmel. You ħadthom imblukkata dan. Li eċċellenti. Huwa jieħu l-kantuniera hemmhekk. U li għaddej biex seħħ inti jieħdu l-aħħar spazju wieħed, B0. U l-logħba tispiċċa f'voti ndaqs. Iżda hija kellha raġonevoli logħba kontra tiegħek, right? Kull dritt, grazzi ħafna, Gorav. [Applause] Kull dritt, Layla, aħna qed tmur up l-logħba fuq inti hawn. UDJENZA: Oh, kbir. SPEAKER: Aħna ser tagħti inti erbgħa minn erba 'tic tac toe. Issa, f'erba minn erba ', inti għandek biex tirbaħ ma 'erba fir-ringiela, mhux tliet fir-ringiela. U huwa kollha tiegħek. Allura Layla ħa D1. Aħna issa sejra ssegwi player kompjuter tagħna hawn. Tliet minn tliet tic tac toe hu t-tip ta 'ħaġa li hija faċli għalina lkoll. Iżda huwa għadu sabiħ li tara l- player kompjuter jagħmlu jiċċaqlaq intelliġenti. Erbgħa mill-erba gets jkun ftit delikati. Nicely jsir. Dritt kollox, so tal Layla ikkonkluda azzjoni. Oh, u għandna jkunu spiċċaw hemmhekk. Imma ejja jagħmlu waħda aktar up here. Allura Layla, grazie. Nicely jsir. [Applause] Allura player tagħna tic tac toe tmur permezz ta 'u jsib postijiet, issolvi lilhom jużaw dan minimax. U kelli l-issettjar fond fuq li sabiex ma jmur malajr wisq, li hija probabbilment għala Layla kienet kapaċi li jmorru nicely quddiem kif hi ma, u ma tajjeb ħafna. Iżda dawn is-sistemi li biss jgħaddu u forza brutali mur fil-fond, u aktar profonda, u aktar profonda, u jżommu tinstab is-soluzzjoni li għandhom bżonn, dawk it-tipi ta 'sistemi huma pjuttost ta 'suċċess fil dawn, ukoll, logħob standard bord. U fil-fatt, jekk inħarsu lejn tliet minn tliet logħba tic tac toe, dan huwa bażikament problema tissolva. U dan huwa dijagramma isbaħ minn Randall Munroe fil XKCD, turi li jimxu għandek jieħdu, minħabba jiċċaqlaq avversarju tiegħek. Din hija xi ħaġa li nistgħu faċilment tispeċifika qabel iż-żmien. Imma x'jiġri kif aħna nikseb aktar logħob kumplessi, logħob aktar ikkomplikat, fejn hemm bordijiet akbar, aktar possibbiltajiet, l-istrateġija aktar profonda? Jirriżulta li din forza brutali tiftix għadu ma raġonevolment tajjeb, ħlief meta inti jasal sal-punt fejn dik siġra hija tant kbir li inti ma tistax tirrappreżenta dan kollu. Meta inti ma tistax kkalkulata l-siġra kollu, meta inti ma tistax tmur quddiem u push yourself sal-punt fejn inti stajt gotten l-siġra kollu fil-memorja, jew jekk tista 'tikseb fil-memorja u se biss tieħu inti triq twila wisq biex tfittex permezz dan, inti għandek tagħmel xi ħaġa aktar intelliġenti. Sabiex tagħmel dan, inti għandek tagħmel żewġ affarijiet. L-ewwel, inti għandek issib xi mezz biex tiġi limitata fond tiegħek. Ukoll, li OK. Nistgħu nsibu xi sbieħ, minimu indispensabbli u jgħidu, inti tista 'ssir biss tant radikali. Imma meta inti tagħmel dan, dan ifisser li inti jkollhom dawn il-bordijiet parzjalment mhux kompluta. U inti għandek tagħżel, tagħmel I simili dan il-bord parzjalment inkomplet, jew dan il-bord parzjalment inkomplet? U fuq tagħna erbgħa mill erba logħba tic tac toe, player kompjuter tagħna ltqajna isfel għall-qiegħ u qal, Stajt ltqajna żewġ bordijiet differenti. La waħda hija rebħa. La waħda huwa telf. La waħda hija rabta. Kif nista jagħżlu bejniethom? U ma kellhiex mod intelliġenti ta 'kif isir dan. Naraw dan it-tip ta ' evalwazzjoni jiġri l-ħin kollu kif aħna jsibu rwieħhom logħob aktar kumplessi. Chess hija eżempju kbir. Fl-ċess, għandna, l-ewwel ta 'kollha, bord akbar. Għamilna ferm aktar biċċiet. U l-pożizzjoni ta 'dawn il-biċċiet u l-mod li dawn il-biċċiet jiċċaqalqu huwa ta 'importanza kritika. Mela jekk jien tixtieq li tuża minimax, I bżonn biex tkun f'pożizzjoni li tispeċifika u jgħidu, dan il-bord, fejn ebda wieħed rebaħ jew mitlufa għadhom, hija daqsxejn aħjar minn dan ieħor board, fejn l-ebda wieħed rebaħ jew mitlufa. Biex tagħmel dan, I tista 'tagħmel affarijiet simili I jistgħu biss għadd kemm biċċiet ħafna għandi u kemm biċċiet għandek? Jew I jista 'jagħti differenti punti differenti biċċiet. Reġina tiegħi min 20 punt. Pawn tiegħek min punt wieħed. Min għandu aktar punti total? Jew I jistgħu jikkunsidraw affarijiet simili, li ltqajna l-pożizzjoni bord aħjar? Li jkun imissu huwa li jmiss, xi ħaġa li nista ' do biex tevalwa b'mod aktar preċiż liema minn dawn il-possibilitajiet huwa aħjar mingħajr jikkunsidraw b'mod eżawrjenti kull mossa li tista 'tiġi wara dik. Issa li jagħmlu dak ix-xogħol, waħda mill-affarijiet C'est se ssir verament importanti għalina huwa mhux biss miexja dritta isfel għal fond partikolari limitu, imma li tista 'tgħid, wieħed minn dawn l-ideat li I għandhom hija daqshekk ħżiena li huwa mhux min jikkunsidrah kollha tal-modi possibbli li l-affarijiet jistgħu jmorru minn ħażin għall-agħar. Biex tagħmel dan, aħna ser żid in minimax prinċipju msejjaħ alph-beta. U alpha-beta jgħid, jekk għandek idea ħażina, ma jaħlux ħin tiegħek jippruvaw issir taf eżattament kif bad huwa. Allura hawnhekk huwa dak li aħna qed tmur biex tagħmel. Aħna qed tmur biex tieħu l-istess prinċipji li kellna qabel, l-istess tip minimax ta 'tfittxija, biss aħna qed ser iżżomm kont, mhux biss tal- valuri attwali li għandna, iżda aħna ser iżżomm kont ta 'l-aħjar possibbli valur li I jistgħu jiksbu, u l-agħar possibbli eżitu I jista 'jkollhom. U kull darba li l-agħar possibbli Ħaġa qed tfittex probabbli, I ser tabbanduna dik il-parti tas-siġra. U jien mhux se jolqot anki tħares lejn dan aktar. Dritt kollox, hekk jimmaġina li nibdew ma dan l-istess siġra logħba eżatt. U issa aħna qed tmur biex tmur stabbiliti mill-ġdid, it-triq kollha għal dak rokna tax-xellug t'isfel. U f'dak il qiegħ tax-xellug kantuniera, aħna dehra u aħna tevalwa dan il-bord. Forsi huwa ta 'erba minn erba' tic tac toe bord, jew forsi huwa bord taċ-ċess. Iżda aħna nħarsu lejn din, u aħna tevalwa dan, u aħna jiksbu valur ta 'tmienja. F'dak il-punt, aħna nafu li aħna se tikseb mill-inqas tmien punti minn din id-deċiżjoni qiegħ. Ma jimpurtax liema l-oħra tnejn huma, li seba u li tnejn. Huma jistgħu jkunu kwalunkwe valuri huma riedu li jkun. Aħna qed tmur biex tikseb fuq inqas tmien punti. Kull dritt, imma nistgħu imorru quddiem u jiċċekkjaw. Forsi wieħed minnhom huwa aħjar minn tmienja. Aħna nħarsu lejn l-seba '. Hija li aħjar minn tmienja? Le, dan ma jbiddilx opinjoni tagħna fil-livelli kollha. Aħna nħarsu lejn it-tnejn. Hija li aħjar minn tmienja? Le, dan ma jbiddilx opinjoni tagħna fil-livelli kollha. Allura issa nafu konna eżawriti kollha tal-possibilitajiet hemmhekk. Aħna mhux se tikseb xejn aħjar minn tmienja. Aħna qed tmur biex tikseb eżattament tmienja. U hekk aħna bidla li node u jiġifieri, li issa huwa ċertezza. Immorru up livell wieħed aktar minn dak. U issa nafu xi ħaġa dwar dak il-livell minimizzazzjoni. Aħna nafu li aħna qed qatt ser tikseb aktar minn tmien punti jekk aħna jinżlu f'dik id-direzzjoni. Minħabba li, anki jekk dawk żewġ fergħat oħra jispiċċaw li jkun meraviljuż u jiswa eluf ta 'punti kull waħda, opponent tagħna se tagħtina l- minimu, u agħtina l tmienja. Kull dritt, ukoll, ejja ara. Aħna ser iżommu jinżel 'l isfel f'din it-triq. Aħna jinżlu għal dik tan-nofs fuq ix-xellug. Aħna tfittex l isfel u naraw hemm disa. Aħna nafu li aħna qed tmur biex tikseb mill-inqas disa 'punti mill jinżel' l isfel dik it-triq tan-nofs. U f'dan il-punt, nistgħu biss nieqaf. U nistgħu ngħidu, ħarsa, I jafu fil-livell ta 'hawn fuq, Jien ser tikseb mhux aktar minn tmien punti minn jinżel 'l isfel f'din id-direzzjoni. Imma jekk I marru l-nofs triq minflok il-passaġġ tax-xellug, I se tikseb mill-inqas disa 'punti. Avversarju tiegħi huwa qatt ser let me jinżlu f'din it-triq tan-nofs. Huma jiksbu li jagħżlu. U dawn qed tmur biex jagħżlu l- triq lejn ix-xellug lejn il-tmienja, aktar milli l-nofs lejn x'hemm mill-inqas disa 'punti. Allura f'dak il-punt, jien ser tieqaf. U jien ser jgħidu, inti taf liema? I ma jkollhomx biex tfittex xi aktar l isfel f'dik id-direzzjoni. Għaliex jien qatt ma ser naslu s'hemm. I tista 'skip fuq li wieħed, u I tista 'skip fuq dak sitta, minħabba li qatt ma jiġri. So I ser imorru isfel u I ser jikkunsidraw il-possibbiltà li jmiss. I jmorru hemm isfel u I say, I tara tnejn. I know jekk I nikseb hawn, jien se tikseb mill-inqas tnejn. KOLLOX SEW. I jibqgħu għaddejjin. Nara erbgħa. I know jien ser jiksbu mill-inqas erbgħa. Hemm għadu ħafna bejn erba 'u tmien, għalkemm. So I jibqgħu għaddejjin. I tfittex l isfel u nara hemm waħda. Kull dritt, naf jekk I jinżlu din it-triq, Jien ser ikunu jistgħu jagħżlu l-erbgħa. X'hemm avversarju tiegħi se jagħmlu? Bejn xi ħaġa li tagħti me tmienja, xi ħaġa li tagħti me erba, u xi ħaġa li tagħti me-inqas disa ', ukoll, huwa għaddej biex agħtini l-erbgħa. U naf issa fil- ħafna top, jien ser biex ikunu jistgħu jiksbu mill-inqas erba 'punti minn din il-logħba. L-idea kollha ta 'alpha-beta huwa biex jinqata 'partijiet-siġra hekk li jien ma tħares lejn lilhom jibqgħalu. Iżda għadu qisu stajt ġiet tħares lejn ħafna tas-siġra. Ejja jibqgħu għaddejjin isfel. Aħna ser jinżlu dak li jmiss issa. Down fil-qiegħ, I isibu waħda. I know jien ser jiksbu mill-inqas wieħed. I iżommu tfittex. I isibu tlieta. I know jien ser jiksbu mill-inqas tlieta. I jibqgħu għaddejjin. I isibu ħamsa. I know jien ser tikseb ħamsa jekk niġi mill-imsemmi triq. U naf ukoll allura li avversarju tiegħi, jekk I jagħżlu l-nofs ta ' it-tliet għażliet kbar, huwa għaddej biex jagħti me xi ħaġa li ħamsa jew inqas. KOLLOX SEW. I tista 'żżomm għaddej hemmhekk. I tista 'tfittex l isfel u I tista 'tgħid, dak li jien ser tikseb jekk immur fit-triq tan-nofs? Jien ser tikseb, ukoll, tlieta hemm. Jien ser tikseb xi ħaġa dan huwa mill-inqas tlieta. Hemm għadu affarijiet bejn tlieta u ħamsa, so I iżommu tfittex. Oh, ta 'disa, I ser definittivament jieħdu dik fuq tlieta. Jien ser jiksbu mill-inqas disa ' jekk I jinżlu f'din it-triq tan-nofs. Issa avversarju tiegħi waqfiet u jgħid, ħarsa, hemm ebda punt aktar. Naf li tiegħi avversarju minimizzazzjoni, hu ser jagħti lili l-ħaġa li l- inqas minn jew ugwali għal ħamsa, aktar milli l-ħaġa li l- ikbar minn jew ugwali għal disgħa. I stop. I ma nħarsu aktar f'dak. I jibqgħu għaddejjin. I ħarsa stabbiliti fuq dan wieħed. Sal-qiegħ, I isibu sitt. I know jien ser jiksbu mill-inqas sitt. U x'nista 'nagħmel? I tista 'twaqqaf. Għaliex hemm għażla bejn xi ħaġa li mill-inqas sitt u xi ħaġa li inqas minn ħamsa, hu ser jagħti lili l-ħaġa li l-anqas minn ħamsa. U issa naf jien ser tikseb eżattament din l-għażla. Jien ser tikseb dak ħamsa għażla. I jmorru lura sal-quċċata. Li jien ser jagħżlu bejn xi ħaġa li l-ikbar minn jew ugwali għal erbgħa, jew xi ħaġa li ugwali għal ħamsa? Jien ser tieħu xi ħaġa dan huwa mill-inqas ħamsa. I jinżlu l-aħħar triq, Kollha il-mod sal-qiegħ. Hemm wieħed. OK, mill-inqas jien ser tikseb il-punt wieħed. I jibqgħu għaddejjin. Żewġ, oh, li aħjar minn wieħed. Jien ser jiksbu mill-inqas tnejn. I isibu tlieta. I know jien ser tikseb tlieta. U l-punt ta 'hawn fuq li, avversarju tiegħi huwa għaddej li tagħti me xi ħaġa li inqas minn jew ugwali għal tlieta. U issa I tista 'twaqqaf. Minħabba fl-għażla bejni jkunu kapaċi tikseb ħamsa u avversarju tiegħi tajtu lili xi ħaġa inqas minn tlieta, Jien dejjem se jieħdu dik ħamsa. So I ma tevalwa li parti t'isfel tas-siġra fil-livelli kollha. Issa, dan jista 'jidher minuri. Imma meta bits ftit ta 'aritmetika, akbar minn u anqas minn, tista 'tnaqqas bogħod partijiet kollha ta' din is-siġra li jikbru b'mod esponenzali, li twassal għal enormi ammont ta 'tfaddil, tfaddil li huma kbar biżżejjed li I tista 'tibda playing kompetittiv fil aktar logħob kumplessi. Kull dritt, jekk inħarsu lejn id-daqs u l-kumplessità ta 'logħob differenti, tic tac toe kien eżempju faċli tagħna. Imxejna ltqajna bord żgħir, tlieta bi tlieta. Nikbru, bħala massimu, b'medja ta ' madwar erba 'għażliet differenti kif immorru permezz tal-logħba. Għandna x'imkien madwar 10 għall- ħames weraq differenti possibbli. U bini ta 'tic tac toe player, ukoll, aħna biss ma kien. Huwa faċli. Jekk immorru sa xi ħaġa aktar kumpless, bħal Connect Erba. Do you remember din il-logħba fejn inti qatra l-tokens ftit fil-? Huwa sitta minn seba abbord, mhux li ħafna akbar, xorta għandha madwar l-istess fergħat fattur bħala tic tac toe. I jkollhom madwar erba 'għażliet fejn I tista 'tpoġġi l-affarijiet fil. Imma issa, stajt qbilna ħafna aktar twassal, 10 għall-qawwa 21. Dik xi ħaġa li faċli biżżejjed li aħna issolvi dan minnufih. Kontrolluri, aktar complex-- inti ltqajna tmien minn tmien bord. Inti biss fuq nofs magħhom fi kwalunkwe ħin, għalkemm. You ħadthom ltqajna fergħat fattur li dwar 2.8. Well, konna ltqajna koppja jiċċaqlaq inti tista 'tieħu. You ħadthom ltqajna madwar 10-31 weraq, spazji akbar, u akbar, u akbar. Kif għandek tfittex permezz dawk l-ispazji akbar u akbar, dan huwa meta l-affarijiet simili alpha-beta u jkunu jistgħu jaqtgħu fergħat kollha isir essenzjali. Issa, kontrolluri kien faċli biżżejjed fl-1992. Programm tal-kompjuter imsejjaħ Chinook taħbit il-kontrolluri tad-dinja champion, Marion Tinsley. U minn dakinhar, l-ebda player kaptan bniedem għandu kienu kapaċi jegħlbu l-aħjar Sistemi komputazzjoni. Jekk inħarsu lejn xi ħaġa bħal taċ-ċess, issa għal darb'oħra, għandna tmien minn tmien bord. Imma aħna għandna ħafna aktar kumpless biċċiet, ħafna movimenti aktar kumplessi. Għandna fattur fergħat ta 'madwar 35, 35 jiċċaqlaq possibbli fuq medja li I tista 'tieħu, u stat ispazju, numru ta 'weraq li imkabbra għal 10 għall-qawwa 123, numri enormi ta 'possibbiltajiet. Anki xorta, proċessuri moderni huma kapaċi li jagħmlu dan b'suċċess. Fl-1995 u mbagħad fl-1997, kompjuter programm imsejjaħ Deep Blue mibnija mill IBM li dam fuq supercomputer ġgant taħbit il-ċampjin dinja attwali, Garry Kasparov. Dan kien punt ta 'bidla. Illum, madankollu, li istess ipproċessar qawwa tpoġġi fuq MacBook tiegħi. Ipproċessar tal-veloċità jżomm jkollna aktar mgħaġġla u aktar malajr. Aħna tista 'tevalwa aktar u aktar bordijiet aktar mgħaġġla u aktar malajr. Iżda aktar importanti, għandna aħjar funzjonijiet ta 'evalwazzjoni u żbir aħjar Metodi. Allura nistgħu tfittex il- aktar spazju complexly. L-akbar tal-bord logħob li aħna tista 'taħseb, xi ħaġa bħal Mur thats ltqajna 19 minn 19 board, issa f'daqqa waħda, aħna qed passat il-punt fejn is-sistemi komputazzjoni tista 'tirbaħ. M'hemm l-ebda komputazzjoni sistema hemmhekk li jista 'taħbit plejer professjonali Go. L-aħjar sistemi illum rank dan dwar t-tip ta 'livell dilettanti tajba. Allura għad hemm pjuttost ftit out hemm li inti ma tistax tikseb s'issa. Dritt Kollha, dawn logħob abbord tradizzjonali, dawn it-tipi ta 'sistemi fejn aħna jibnu din minimax, kemm jekk huwa ltqajna alpha-beta jew le, dawn algoritmi jaħdmu għaliex hemm ċerti restrizzjonijiet. Aħna informazzjoni perfett dwar id-dinja. Nafu fejn l-biċċiet kollha huma. Id-dinja hija statika. Ħadd gets biex tmexxi l- biċċiet madwar filwaqt li jien seduta hemm ħsieb, tieħu dawran tiegħi. Hemm spazju azzjoni li l diskreta. I tista 'tpoġġi pawn tiegħi hawn, jew I tista 'tpoġġi pawn tiegħi hawn. Jien mhux permess li jitqiegħdu pawn tiegħi fuq il-linja bejn iż-żewġ kwadri. U finalment, l-azzjonijiet huma deterministic. Naf li jekk I say, rook li kavallier tlieta, rook tiegħi se jispiċċaw fil kavallier tlieta, sakemm huwa pass validu. M'hemm l-ebda inċertezza dwar dan. Issa, kif mmur aktar tipi differenti ta 'logħob, aħna jkollhom jiksru dawk is-suppożizzjonijiet. X'jiġri jekk immur xi ħaġa bħal video games klassika? Hawn għażla ta 'video logħob mill-Atari 2600. What do I jkollhom up hemm? Stajt ltqajna Frogger, l-Ispazju Invażuri, iżvantaġġ, u Pac Man. Liema tipi ta 'ambjenti għandi hawn issa? Liema minn dawn is-suppożizzjonijiet għandi jkollhom jiksru? Ukoll, dan jiddependi fuq il-logħba. I jista 'jkollha ċess fuq il 2600, u ikun biss bhalu kien qabel. Għal ħafna minn dawn is-sistemi, hemm għarfien sħiħ dwar id-dinja. Hemm kompletament azzjonijiet deterministic. Iżda ġeneralment, fid-dinja m'għadhomx statika. Dan huwa, filwaqt li jien seduta hemm stennija, xi ħaġa tkun miexja. Il-ghosts huma ġejjin biex nikseb me. Il Skorpjun huwa li ġejjin lili taħt. L-invażuri ispazju huma ġejjin eqreb u eqreb. Kif ukoll nagħmlu kontra dawn? Ftit snin ilu, Google kien proġett imsejjaħ DeepMind, fejn mħarrġa kompjuter programm jilagħbu Atari 2600 logħob. U jekk taħseb li dan ma jkunx serju negozju, ir-riżultati ta 'studju tagħhom ġew ippubblikati fil-Natura, hekk biss dwar kif tajba pubblikazzjoni kif inti tista 'possibilment tinkiseb. U hawnhekk kif ukoll wettaq. Huma għandhom algoritmu li sib u jaraw biss il-inputs iskrin. Hija marret l-ebda struzzjonijiet tkun xi tkun dwar ir-regoli tal-logħba. U kien suppost biex insemmu, ibbażata punteġġ tiegħu, kif ukoll li kien isir. Dan kien sistema li tintuża xi ħaġa imsejħa tagħlim rinfurzar. Jiġifieri, hija ħadet inkunsiderazzjoni score tagħha. U jekk ltqajna punteġġ tajba, huwa qal, I għandhom jiftakru dawk l-affarijiet. U jien tagħmel dawk mill-ġdid. U jekk ltqajna punteġġ ħażina, huwa qal, I ma għandhom jagħmlu dawk l-affarijiet mill-ġdid. Dan huwa l-prestazzjoni ta 'dawk is-sistemi mħarrġa permessi li jkollhom għal ftit sigħat fuq kull logħba, kkumparat ma gamers professjonali. Allura għall kollha tal-logħob li huma naħa tax-xellug ta 'din il-linja, dan awto mħarrġa programm tal-kompjuter issuperati l-gamers professjonali. U għal kollox lill- dritt, l-gamers professjonali kienu għadhom l-aħjar. Għal xi ħaġa li kienet taf xejn dwar ir-regoli, li kien jaf xejn dwar l-istruttura tal- logħob, dan huwa rendiment impressjonanti. U dan huwa dak li aħna qed kapaċi li jagħmlu llum. OK, inti tgħidli, imma jekk irridu jaħsbu dwar AI fil-logħob, normalment naħsbu dwar l- affarijiet li nistgħu attwalment joqogħdu bilqegħda u jilagħbu kontra. Jekk I joqogħdu bilqegħda u I play StarCraft, jew I play Free Għarbel, l-opponent kompjuter huwa l- persuna li tikkontrolla l-Zerg, jew kontroll tar-ċiviltà oħra. Kif dawk il-plejers attwalment issib jiċċaqlaq tagħhom? Ukoll, dawn il-logħob huma strutturati ħafna bl-istess mod bħall logħob bord tagħna, dawn il-logħob li aħna ser kollettivament sejħa erba X logħob, tesplora, expand-- tinsa dawk. X'inhuma? Esplora, jespandu, u jitfu, Naħseb huwa l-aħħar wieħed. Iżda dawn qed bażikament esplorazzjoni u jirbħu logħob. Tipikament, l-opponent kompjuter kien hemm informazzjoni limitata. Huma ma jafux eżattament x'hemm għaddejjin wara li ċpar ta 'gwerra. Huma ma jiksbu biex tara dak li għandek fl-inventarju tiegħek. Hemm ambjent li huwa dinamiku. Kollox qed tinbidel il-ħin kollu. Inti ma tieħux biex ipoġġu u stenna li tieħu pass tiegħek. Iżda ħafna affarijiet għadhom diskreta. I jkollu jpoġġi belt tiegħi hawn. Jew għandi tpoġġi belt tiegħi hawn. U kollox huwa deterministic. Meta I say, jimxu unità tiegħi hawn, l-unità tiegħi jiċċaqlaq hawn, sakemm ostaklu f'daqqa tidħol fis-play. Issa, li mhux kollha kompjuter logħob li huma hemmhekk illum. Jekk immur u I play ewwel persuna tip logħba, xi ħaġa bħal ħalliel jew Fallout jew Skyrim, jew Halo, issa Għandi avversarji kompjuter li huma hemmhekk li jkollhom sitwazzjoni differenti ħafna. Huma għandhom, għal darb'oħra, informazzjoni limitata. Huma biss jista 'jara ċerti kamp ta 'vista. L-ambjent għadu dinamiku. Affarijiet qed jinbidlu l-ħin kollu. Imma issa għandi ħafna aktar ispazju azzjoni kontinwa. I tista 'tiġi biss peeking a ftit mill-bieb. U xi logħob, my azzjonijiet huma stochastic. I nikseb li jippruvaw biex tiżdied fuq dak il-ħajt, imma stajt ltqajna ċans li wieħed jonqos. Dawn it-tipi ta 'logħob huma jersqu qrib u eqreb lejn it-tipi ta 'kontrolluri li nibnu fil-robotika. Fl robotika, aħna għandhom jassumu li għandna informazzjoni limitata. Għandna sensors li tgħidilna dwar id-dinja. Għandna jinbidlu dejjem, ambjent dinamiku. Għandna dinja fejn l-ispazju huwa kontinwu, aktar milli diskreta. U l-azzjonijiet tagħna, meta aħna tipprova minnhom, għandhom ċans li wieħed jonqos. U fil-fatt, il-logħba moderna kontrolluri għall avversarju Halo tiegħek, jew għal dawk NPCs fil Skyrim, bażikament run arkitetturi robotika żgħar. Dawn is-sens id-dinja. Huma jibnu mudell tad-dinja. Huma jikkomputa bbażati fuq sett ta ' għanijiet li huma tixtieq li tlesti. Huma pjan azzjonijiet ibbażati fuq dak li jafu. U dawk huma eżattament l-istess tipi ta 'sistemi li nibnu fil-robotika. Allura dawn arkitetturi, li tressaq dan lura flimkien, spiss huma pjuttost l-istess. Mela ejja ara jekk nistgħu naraw li. Ejja ħa mmorru lura għall tagħna Eżempju tic tac toe. U jien ser jistaqsu ftit tiegħi post-docs biex toħroġ u għinni. Allura Chen Ming, u Alessandro, u Olivier, jekk inti guys se toħroġ. U jien ser bżonn koppja ta 'voluntiera OK, I raw dritt idejn up hemm fin-nofs. Let me tieħu waħda aktar, xi ħadd aktar fid-dahar forsi. Dritt kollox, hemmhekk. Come fuq up. Kull dritt. Mela ejja tagħti dik il-kopertura isfel. U jekk inti guys kien jidħol dritt lura madwar hawn għalija, meraviljuż. Allura dan huwa robot imsejjaħ Baxter. U Baxter huwa robot li l- pjattaforma kummerċjali, imfassla minn kumpanija msejħa Rethink. U dan robot huwa ddisinjat għall-manifattura fuq skala żgħira. Imma llum aħna qed tmur biex jużaha biex jilagħbu tic tac toe. Issa, dan robot huwa wkoll xi ħaġa li relattivament uniku. Għaliex jekk I kienu wieqfa kullimkien qrib ta 'awtomazzjoni fabbrika standard sistema, I d jkun fil ferm gravi periklu li jkunu midruba. Baxter, madankollu, hija mfassla biex tkun relattivament sikur biex jinteraġixxu ma '. U so I jista 'push fuq dan robot. U tista 'tara huwa ftit bit flessibbli kif jiċċaqlaq madwar. U nista 'jerġgħhu jagħtu posizzjoni it fejn I tixtieq li tmur. Issa f'sistema robotiċi normali, rridu naraw sett ta 'ġonot hawn li jkun direttament jirrispondu għall jikkmanda pożizzjoni. U huma mhux bilfors kura jekk dawn kienu jiċċaqilqu permezz arja aperta, jew jekk dawn kienu miexja permezz ribcage tiegħi. KOLLOX SEW. U tipikament, jekk inti kienu hawn ma 'sistema industrijali, inti tmur imkien qrib dan. Ikun hemm isfar tejp kollu ta 'sikurezza madwaru. Din is-sistema għandha disinn kemmxejn differenti li jkun familjari u aktar faċli għall-persuni li jinteraġixxu ma ', f'dak f'kull konġunta, hemm rebbiegħa. U pjuttost milli jikkontrollaw pożizzjoni eżatta, aħna kontroll ċertu ammont ta ' torque, ċertu ammont ta 'forza, li nixtiequ li tkun fuq dik tar-rebbiegħa. Kull dritt, so let me jieħdu voluntiera tagħna hawn. Hi, x'hemm isem tiegħek? UDJENZA: Louis. SPEAKER: Louis. Għandi pjaċir. U? UDJENZA: David. SPEAKER: David. Għandi pjaċir. Jekk inti guys se tistenna dritt hawn għat-tieni, Jien ser jagħtuk iċ-ċans li jagħmlu dan. Allura dan robot, jekk inti toħroġ u jekk inti timbotta bil-mod fuq dan, int ser tara li jiċċaqlaq ftit. U jekk inti grab dan id-dritt hawn fuq il-polz biss hawn fuq meta dawk buttuni huma, huwa qisu għandek grab-buttuni, iżda grab dritt hawn fuq minflok, inti ser tkun tista 'bil-mod ħafna jimmanipulaw permezz ta 'spazju. Louis, inti tixtieq li jipprova hu? Allura tagħtiha biss ftit timbotta biex jibdew bihom. U allura jekk inti tpoġġi swaba tiegħek hemm dritt u żżomm fuq lilha, minħabba li se timxi għalik allura. Kull dritt, inti tixtieq li jipprova hu? Come fuq up. Allura tagħtiha biss ġentili timbotta hemm biex tibda. Tista 'tħossok dak li huwa simili. U allura jekk inti grab hemm dritt, inti ser ikunu jistgħu jimmanuvraw madwar. KOLLOX SEW. Allura tipikament, dan it-tip ta 'robot kieku jintużaw għall-manifattura fuq skala żgħira. U jien ser jimxu din driegħ biss l barra mill-mod ftit hawn. Imma llum, aħna qed tmur biex tuża l- istess tic tac toe sistema playing ibbażata fuq minimax li aħna mibnija qabel. KOLLOX SEW? Allura, inti guys huma kull se tilgħab logħba. Louis, int ser tkun l-ewwel. Let me biss istiva up here għat-tieni. Jien ser ikollhom inti toqgħod dritt hawn, biss hekk kulħadd jista 'jara inti. Huma inti guys twaqqaf hawn? ROBOT: Merħba. Ejja play tic tac toe. Ma jaħtfu token tiegħek qabel Jien ngħid li huwa lilkom. I tibda l-logħba. Huwa min-naħa tiegħi. SPEAKER: Issa, jekk inti tista 'tieħu waħda minn biċċiet tiegħek u jimxi 'l quddiem u poġġiha. ROBOT: Huwa lilkom. [Rires] Huwa min-naħa tiegħi. [Rires] [Rires] Huwa lilkom. SPEAKER: Il-razza umana hi intom hawn, Louis. ROBOT: Huwa dawran tiegħi. SPEAKER: Allura Baxter b'suċċess imblukkata hawn. ROBOT: Huwa lilkom. Huwa min-naħa tiegħi. Huwa lilkom. Huwa min-naħa tiegħi. SPEAKER: U aħna ser let Baxter finitura out aħħar pass tagħha hawn. [Rires] ROBOT: Li rabta. I se jirbaħ ħin li jmiss. [Rires] SPEAKER: Id-dritt, grazzi ħafna, Louis. Grazzi. Inti tista 'tmur il-mod. ROBOT: I tibda l-logħba. SPEAKER: So let me jispjegaw lilek waħda aktar ftit bit qabel nikbru rematch tagħna hawn. X'inhi eżattament jiġri? Allura l-robot kamera top up here. U huwa tħares stabbiliti fuq il-bord. U huwa jaraw jekk huwa ltqajna O aħmar jew blu u X. abjad bħal dawk jiksbu mqiegħda fuq il- board, li bażikament l-istess input li aħna jkollna qari minn istruttura data tagħna mill-iskrin tagħna. Huwa taħdem l-istess algoritmu MINIMAX li jkun tista 'ssib fejn post ta 'token tajba. U allura aħna qed jagħti kmand dwar fejn aħna tixtieq a token li jitqiegħdu. Il-fergħa tkun miexja out. Huwa użu ta 'gripper vakwu biex japplikaw xi ġbid biex dik il-biċċa l-injam, pick it up, jġorrhom lejn il-lemin post, u mbagħad tirrilaxxa l-ġbid u qatra. Kull dritt, aħna qed tmur biex jagħtuh wieħed shot aktar bi player ftit aktar intelliġenti hawn. Inti lest? Kull dritt, jekk youd stand dritt up hawn u jagħtu a-- jispiċċaw dan il-mod sabiex inti tista 'tara kulħadd. U mbagħad [inaudible]. ROBOT: Huwa dawran tiegħi. SPEAKER: Baxter se tibda. Huwa lilkom. Huwa min-naħa tiegħi. Huwa lilkom. Huwa min-naħa tiegħi. [Rires] SPEAKER: [WHISPERING] Just let lilu imorru quddiem u irbaħ. ROBOT: Huwa lilkom. SPEAKER: Li OK. ROBOT: Huwa dawran tiegħi. [Rires] I win. [Rires] I tibda l-logħba. SPEAKER: Kull dritt, nirringrazzjak ħafna. Kull dritt, naħseb konna ltqajna ħin biex wieħed aktar eċċellenti player tic tac toe, xi ħadd li tista 'tpoġġi dan ħaġa li jaqblu, li jaf dak li qed isir. [Rires] Min ser ikun champion tagħna hawn? Kull dritt, ħbieb tiegħek volontarju inti. Li tajjeb biżżejjed għalija. Tell me isem tiegħek mill-ġdid. UDJENZA: Tamir. SPEAKER: Tamir, sbieħ biex tara int. Kull dritt, għal darb'oħra, aħna qed tmur biex tpoġġi lilek dritt up here sabiex kulħadd jista 'jara inti. Inti huma rappreżentattivi tagħna fil din il-logħba issa. Baxter huwa wieħed u oh u oh. Jew sorry, wieħed oh u wieħed. U huwa sa inti hawn. Baxter se tikseb biex jiċċaqalqu l-ewwel, għalkemm. So. ROBOT: Huwa dawran tiegħi. [Rires] Huwa lilkom. Huwa min-naħa tiegħi. Huwa lilkom. Huwa min-naħa tiegħi. Huwa lilkom. [Rires] ROBOT: Huwa dawran tiegħi. SPEAKER: Huwa ħafna aktar diffiċli meta int bil-wieqfa hawn, folks. [Rires] ROBOT: You bnedmin huma tant faċli li tħabbat. [Daħk U applause] SPEAKER: Grazzi ħafna. ROBOT: I win. I tibda l-logħba. SPEAKER: Id-dritt, hekk grazzi ħafna ħafna Olivier, u biex Alessandro, u biex Chen Ming. [Applause] Irrid nagħmel aħħar punt wieħed. Allura Baxter fl-ħafna jieqafx hemm, misruqin. U li kien mhux mistennija. Wieħed mill-meraviljuż affarijiet dwar AI hija li aħna jagħmlu xogħol fil AI sabiex inkunu nistgħu nibnu verament interessanti u intelliġenti apparati. Iżda aħna wkoll jagħmlu xogħol fil AI għaliex tgħidilna xi ħaġa dwar kif il-bnedmin huma intelliġenti. Wieħed mill-favoriti Studji mill lab tiegħi huwa tħares lejn dak li jiġri meta magni għarrieda iqarrqu. Għamilna dan oriġinarjament mhux ma Baxter playing tic tac toe, iżda ma 'robot iżgħar jismu Nao, li lagħab rock-karta imqass. U xi kultant wara playing lottijiet u lottijiet tal boring logħob rock-karta imqass, l-robot se tarmi ġest, jitilfu, u mbagħad bidla f'daqqa ġest tiegħu u jgħidu, I win. [Rires] Issa, xi kultant aħna'd jkollhom ukoll l-robot, biss bħala kontroll, tarmi ġest, win, u l-bidla ġest tiegħu x'titlef, tarmi-partita, iqarrqu sabiex jitilfu. U dan mhux kważi bħala konvinċenti. Il-robot li cheats sabiex tirbaħ nies jirrispondu għall bħallikieku hija biex tikseb minnhom, bhalu qed jippruvaw b'mod attiv qerda tagħhom. [Rires] Dan isir aġent. Huwa bħal persuna. Hija twemmin u l-intenzjoni. U m'humiex intenzjoni tajba. U l-robot li tixħet l logħba hija biss ħsara. Huwa biss mezz imkisser. Let me nuruk ftit eżempji ta 'dik minn ftit ta' parteċipanti tagħna. Allura hawnhekk qerq sabiex jitilfu. [Daqq video] - [Inaudible] tirbaħ. Ejja nilagħbu. -Wait, Liema? - [Inaudible] tirbaħ. Ejja nilagħbu. [Inaudible] tirbaħ. Ejja nilagħbu. SPEAKER: U hawnhekk qerq biex tirbaħ. -Yes, I win. Ejja nilagħbu. 'Inti ma tistax tagħmel dan. [Rires] -Yes, I win. -Inti Misruqin. Inti misruqin issa. -Yes, I win. -Hey, Inti cheater. You iqarrqu, iqarrqu super. [END Daqq] SPEAKER: Dawn differenti Reazzjonijiet malajr bidla fil-perċezzjoni tagħna ta 'l-apparat. Dan ifisser li aħna deliberatament nibnu magni li iqarrqu minħabba li l l-aħjar inġinerija li nistgħu nagħmlu? Le, iżda tgħidilna xi ħaġa verament interessanti dwar in-nies. Li ħaġa li cheats inti u steals rebħa tiegħek, li xi ħaġa li ħaj, li l- janimaw, li barra li inti tikseb. Hija istat mentali. Hija twemmin. Hija għandha l-intenzjoni. Li ħaġa li idejn l- logħba lilek, li mhux. Li jinsab biss ħsara. Dan huwa f'ħafna modi għaliex huwa faċli biex tarmi l-logħba bi tfal. Imma jekk inti tipprova biex iqarrqu lilhom u tip ta 'pretensjoni rebħa meta, inti taf, biss li jitqassar il- logħba, dawn ser qabda tiegħek dritt bogħod. Dawn it-tipi ta 'effetti li naraw li joħorġu ta AI, jgħallmu us ħafna dwar nfusna. Dritt kollox, din hija għal-lum. Grazzi ħafna għall David u it-tim tal-produzzjoni Harvard għall jinżlu. [Applause] Aħna ser tara inti għal kwizz waħda, u mbagħad għall-aħħar lecture wieħed. Il-ġurnata t-tajba. [Applause] [Daqq tal-mużika] DAVID J Malan: Well, we probabilment ikollok bżonn li tintroduċi xi tip ta 'encryption, id-dritt? Għaliex imbagħad l-intestaturi ta ' dawn it-talbiet HTTP se jkun scrambled sabiex kulħadd jippruvaw sniff traffiku tiegħek mhux se attwalment tkun kapaċi li tara minnhom. Allura x'inhu l-soluzzjoni għal din il-problema? Well, għandna bżonn li fil-fatt tintroduċi encryption fil-formula, b'tali mod li meta dik il-persuna trażmissjoni tad-data minn A sa B, nistgħu sikur send-- [Rires] L-informazzjoni b'mod li l avversarju ma tistax, fil-fatt, jarawha.