[Мусиц плаиинг] ГОВОРИ: Добродошао назад, свима. Ово је ЦС50. И данас, имамо доста интересантне ствари да разговарамо. Прво, мада, морам да подсетим ти од неколико административних ствари. Ове недеље је квиз један, у среду или за секцију Иале уторком и четвртком, у четвртак. Постоје квиз коментара вечерас на Јејлу, 5:30 до 7:00. На Харварду, они су једно јуче забележен. И сви могу да гледам тај онлине. Такође, ове недеље или почетком следеће недеље, имамо нашу последњу ЦС50 предавање. [Гроанс] Знам. То је тако брзо. Иале студенти ће имати уживо предавања овде на Правном факултету дворана у петак. Биће торте. Харвард студенти ће имати Последње предавање у Сандерс у понедељак. Такође ће бити торта. Такође, ове недеље у петак, за оне који од вас који долазе у Нев Хавен, имамо ЦС50 Екпо. Имамо више од 30 различите групе регистровани да ти покажем све од аутономних једрилица, на системе који препознају дигитални портрети, на рачунало музика и компјутерски произведена музика. Дакле, молимо вас да нам се придружите. Мислим да ће то бити сјајно време. Данас, међутим, долазимо до наставити говоримо о АИ, о вештачкој интелигенцији. А једна од ствари која ћемо доћи до данас је идеја како да користити АИ за решавање проблема. Сада, као и увек, почнимо са нечим једноставним. И ми ћемо да почне са једноставној идеји. И то је користећи претрагу. Замислите на тренутак да сам имају задатак да морам да обавља. И ја бих волео да се то задатак аутоматизован неки софтверски агент. Замислите да ја покушавам да резервишете сет летова из, рецимо, Бостон у Сан Франциско. Могао бих и ја кроз могу користити Једна од дивних онлине сеарцх алати, који ће да уради у суштини исти процес који смо да хода до данас. Али, ако нисте имали да алат, шта би ти урадио? Па, можете да погледате и види и кажем, ја сам у Бостону. Који летови су доступни за мене? Сада, можда имам три Могући летови из Бостона који ће се уклопити време када треба да оду. Могао бих да летим у Чикаго. Или бих могла да одлетим у Мајами. Или може да лети до Њујорка. Тада сам могао гледати једни од један од оних градова дестинације и размислите о којим локацијама Могао бих евентуално доћи из сваке од тих појединачних градова. Можда из Чикага, могу добити директан лет за Сан Франциско. То је одлично. Или бих могао да добијем лет за Денвер. Сада, можда је лет за Сан Францисцо је савршено решење за мене, али можда и не. Можда сам у потрази за нечим То је мало јефтиније или мало боље за мој распоред. И тако сам могао тражити оно што други могућности може бити тамо. Тако да сам могао гледати у Денверу. И из Денвера, па, можда Могу да добијем лет за Аустин. И од Аустин, можда могу добити лет за Пхоеник, и из Феникса у Сан Франциско. Сада, нисам још готов. Зато што можда постоји директан лет из Њујорка до Сан Франциска који је савршен за мене. Или можда има лет из Мајамија кроз Денверу то је много јефтиније. Тако да увек морам да идем. И даље морам да гледам све оне градови који још нисам истражити. Морам да проверим све исцрпно могућности да бих могао имати. Дакле, из Њујорка, можда могу добити лет за Насхвилле, а од Насхвилле у Аустин. И онда знам где сам. И онда ја знам из Остина, не могу лете у Пхоеник, и из Феникса у Сан Франциско. Ако сам први пут летим у Мајами, међутим, можда могу добити лет из Мајамија у Насхвилле, или из Мајамија у Аустин. И сад сам пробао све од могућности. Ја сам изградио овај графикон који ми показује све могуће путева да бих могао бити у стању да преузме. Када смо представљају ови врсте проблема, нећемо представљати их експлицитно као овог графикона, јер то графикон не представља историја где смо отишли. Знајући да сам летео од Феникс у Сан Франциско не ми рећи да ли сам дошао преко Насхвилле, или преко Денверу, или преко Мајамију. Дакле, шта ћу да урадим уместо је Ја ћу искористити ову исти проблем, и ја ћу га представљају као дрво. И у корену дрвета, на Топ, Ставићу место које сам започео, Бостон. И из Бостона, ја ћу погледати све могућих локација да могу да путују у. Па, у овом случају, имао сам три, Чикаго, Њујорк, Мајами и. И онда ћу истражити сваку од ова деца у стаблу. Из Чикага, видио сам да сам имао два лета. Ја могу директно да лете Сан Франциско или у Денвер. Сада Сан Франциско, то је мој циљ. То је моја дестинација. То ће бити листа овог дрвета. То је, никада нећу отићи негде после Сан Франциску. Из Денвера, ипак, И цан фли из Денвера у Аустин, из Остина у Пхоеник, и од Феникса до Сан Франциска. И сад опет, ја сам достигао лист. Тада сам могао да се вратим на следећи град који нисам у потпуности истражена. То би било Њујорк, иди назад на врх јелке, сиђе у Њујорк. Из Њујорка, могу летјети до Насхвилле, у Насхвилле у Аустин, од Аустин у Пхоеник, и из Феникса до Сан Франциска. И на крају, један град и нису погледао још, Миами. Па, из Мајамија сам рекао да имам два могућности, Насхвилле, или Аустин. Ако летим у Насхвилле, па онда летим у Насхвилле, у Аустин, у Пхоеник, у Сан Франциско. Ако летим у Аустин, летим Аустин, у Феникс, у Сан Франциску. И сада имам дрво. То је потпуна дрво. То је све могућности и све стазама које сам могао узети. То јест, ако сам почети на корен дрвета на врху и ја одемо до једног од напусти, то ми говори не само где ћу завршити, Сан Франциско, али ми говори пут којим Морам да се тамо. Сада, што један од њих је најбољи? Па, ништа о томе Проблем ми је ипак говори који од њих је најбоље решење. Можда ми је стало највише о колико сам у ваздуху, или удаљеност да летим. У том случају, Чикаго за Сан Франциско може бити најкраћи број миља у ваздуху. Можда ми је стало цени. И сви знамо директне летове су обично скупљи. Па можда ако узмем ово врста уназад трасе кроз Мајамију, Насхвилле, Остин, Феникс, можда тада Ја се нижу цијену. Али бих могао да оптимизира на било критеријуми које ми је стало. Ко има најбоље у лет, Ви-Фи, или који аеродроми имају најбољу храну на располагању. И сваки од њих би могао дај ми другачије решење да видим као најбољи. Ове врсте проблема, где идемо да се изгради овај дрво могућности, а затим погледамо сваки од њих појединачне стазе, и испитати која од тих испуњава критеријум за нас, ћемо звати ти проблеми претраге. И имамо много алгоритми, од којих неке смо већ видели, да одем и истражују оно дрвеће. Можемо то урадити на начин на који сам Управо јесам, а дубина првог претрагу, иде доле колико год можемо док не погодио лист, а затим се враћа горе, и иде враћам. Или би могли да урадимо оно што је зове ширина првог претрагу. Могли смо да проширимо све на врху, а затим све једна линија испод, а онда све једна линија испод тога. Ти претраге дрвеће су од фундаменталног значаја за АИ. Али они не разумем да у праву све време. У ствари, у многим случајева да смо заиста стало, желимо да изградимо дрво, али ми не стварно да да све одлуке. То су ситуације се зову контрадикторно претрага, такође познат како да пишу Гаме Плаиинг системи и бити плаћени за то. Али ово су врсте система где сам Можда могу да бирам када одем из Бостон ком граду идем у следећи. Али после тога, неко други могао добити да донесе одлуку о томе где летим. Тако да се изгради ово киндс структуре, ми смо морати да предузме нешто другачији приступ њу. Нећемо бити у стању да само тражи кроз дрво више, јер ми нисмо онај који је под контролом сваког од тих доношења тачака. Дакле, хајде да замислимо једноставан игра као Тиц-Тац-пете. Могао бих почети са потпуно празно одбор. А у Тиц-Тац-пете, Кс добија прво да свирам. И тако сам могао да размишљам о свим Могући потези да је Кс могла да уради. И ако сам онај игру Кс, то је сјајно. Имам девет могуће креће да могу направити. Могао бих ставио Кс у једном од тих девет позиција. А онда из сваке од њих, И могу да замислим шта ће се десити следеће. Па, у овом случају, друга играч ће добити да се ред. О би добили да се ред. А из сваке од њих, тамо ће бити осам различитих места да је О могао да стави свој маркер. Рецимо одлучио сам да сам био ће ставити Кс у центру. То увек изгледа као добар потез отварање. Могао бих да погледамо испод тога, осам могућих потеза да је О чини. Сада, ако играм Кс, то је дивно. Ја бирам које Оне И идите на, онај у средини. Али сада о стигне до изабрати. И немам контролу над том одлуком. Али од свакој од ових могуће позиције боард, ту је затим још сет могућности. Када је у питању било Моји поново укључите, ја бих могу да бирају и рећи, добро, ако о усељења у, добро, средњи место на левој страни, а затим Имам сет могућности где могу узети мој следећи потез. Од оних сам могао размотрити све могућности испод њих. И онда о ће добити да бирају између њих. И могао задржати гради ово дрво све док сам до тачке где било неко осваја игру-- који је Мора да се сматра лист ноде-- или одбор је потпуно пуна а нико није победио. И то је такође ће бити листа чвор. То ће бити нерешено. Али незгодно ствар са овим је ако је ово обичан претрага Проблем је, ја бих могао да рецимо, и Кс треба да иде овде. И о треба да иде тако тамо. И онда Кс да идем тамо. А онда треба да иде о начин тамо. А онда Кс може добити три у реду, и ја сам победио. И игра ће бити готова у пет потеза, три за мене, две за мој противник. Али не увек да изабере да. Дакле, уместо тога, оно што смо морати да урадите се да ћемо имати да има нову стратегију. А стратегија која Гаме-плаиинг алгоритми често користе је оно што се зове Минимак. Централна идеја Минимак је да смо да изаберемо потез који даје наш противник најгора могућа скуп потеза који могу да направе. То ме не ништа добро изабрати потез где Можда ћу моћи да победи после да, јер је мој противник није ће ми дати ту шансу. Они ће одабрати неку страшно исход за мене. Зато ћу да чине покрет који приморава свог противника да уради нешто боље за мене. У реду. Хајде да видимо како се то игра се. Дакле, овде је наш алгоритам у псеудокоду. Идемо да генерише цела игра дрво. Идемо да се изгради цела структура. А онда ћемо проћи. И на самом дну у свакој од терминал нодова, у сваком од лишћа, ми ћемо проценити колико вредно је то за мене? И ми ћемо вредности ствари које добри су за мене као позитивно. Ствари које нису добре за мене ће бити мање позитивна, или нула, или чак негативан. Дакле, у Тиц-Тац-пете, можда победа за мене је добро. То је један. И кравата је нула. И нешто што је губитак за ја, можда је негативан. Све што је битно је да је боље то је за мене, то је већи скор прима. Из тих могућности на дно, онда ћемо филтрирати према горе. И кад је моја шанса да изаберете међу скуп алтернатива, Ја ћу одабрати онај који је добио највишу оцену. И кад год је то моја противници окренути да изаберете, Ја ћу претпоставити да ће они изабрати онај са најнижим резултатом. И ако ово урадили скроз до врха стабла, Ја ћу изабрао пут који даје ми најбољи исход који могу да добијем, под претпоставком да мој противник чини Алл Тхе Ригхт Мовес. У реду, да видимо ово акција први пут. И онда смо стварно ћу погледај кода за њега. Замислите имам велику дрво. И сада не играм Тиц-тац-тое. Хтео сам да ти дам нешто мало богатији. Дакле, имам неке игра у којој постоји много различитих бодова да сам могао имати на крају. И тако сам изградити овај комплетан дрво. И доћи до првог потеза. Ја сам у корену дрвета. И ја бирам то-- па сам се како би се повећала преко тог првог чвора. И онда је мој противник добија да иде. И онда се још једном да оде. Дакле, доле на дну, имам сет могућности које могу да бирају из, различита терминал стања игре. Ако сам доле у ​​томе далеко левом углу, и видим да имам избор између осам, а седам, и два, Па, ја сам онај који добија да бира. Зато ћу да изаберете најбољи од њих. Ја ћу изабрати осам. Тако да знам да ли сам икада Иди до те тачке, Моћи ћу да се јавим осам бодова. Ако завршим на следећу тачку над, следећи чвор заврши, девет, један, или шест, добро, ја сам ће изабрати најбоље од њих. Ја ћу изабрати девет. Ако имам избор између два и четири, и један, Ја ћу изабрати четири, највиша. Дакле, ако погледамо ниво изнад тога, мој противник је један добија да тај избор. Дакле, мој противник стигне до изабрати, желим да му дам ствар која се дешава да му се осам бодова, или да му дам ствар која је да му девет бодова, или ствар која се дешава да му дам четири бода? И мој противник, што рационалан, иде изабрати минимум оних, ће одабрати четири. И могу да радим ово кроз цело стабло. Могу да одем доле на то средњи сет три. И могу бирати између један, три и пет. И ја бирам. Зато сам одабрати пет. Ја могу да бирају три, девет, или два. Ја могу да бирам, па сам изабрати девет. Шест, пет, или два, бирам. Могу да изабере шест. Ниво изнад тога, ко добија одабрати? Ко може да се изабере? Други момак, мој противник. Дакле, они бирају пет, девет, односно шест, које? ПУБЛИКА: Пет. ГОВОРИ: Они бирају пет. Они могу да бирам минимум. А онда последњи, изабрати једну, две или три. Ја могу да бирам, тако да бирам три. Девет, седам, или два, бирам девет. И 11, шест или четири, бирам 11. Мој противник онда бира три, девет или 11, бира минимум. Он ми даје три. И на крају на врху дрво, могу да опет ће изабрати. И ја бирам између четири, пет, или три. Дакле, узмем пет. Ако морам да контролише све, ја бих идемо путем који је водио до 11. Али ја не разумем да тај избор. Ако одем доле том путу. Мој противник ће ме отерати у избор који води до три. Дакле, најбоље што могу учинити је да ту грану средњи, да тај избор који је на крају да ме доведе до пет поена. То је оно што Минимак ради. У реду. Хајде да погледамо то. Дакле, овде у ЦС50 ИДЕ је програм који Минимак спроводи да игра Тиц-тац-тое. Идемо да се изгради до представљање. Ми ћемо имати два оппонент-- или два играча, наш рачунар играч и човек играч. Број играча један ће играти Тхе О. То ће бити машина играч. Они се уселити други. И други играч, наш људски играч, ће бити Кс. А да би мој живот мало једноставно, ја идем да означи да играча негативни. Тако сам се може размножавати негативним један да мењате између једног и другог играча. У реду, хајде да погледамо шта ћемо заправо радити. Идемо да дефинишемо нашу одбор. То ће бити добро, идемо како би се омогућило да буде три са три, или да чак могу да играју пет од пет или седам од седам Тиц-Тац-пете ако бих као, заснована на некој димензији Д. И ми ћемо имати пар помажућих функција то ће учинити ствари као што су покрене сцреен-- или је, инитиализе наше променљиве, опозовите избор екран, повуците плочу на екрану, онај који проверава одбор да видимо да ли или не ту је победник, који парсес кроз командне линије, само да помогне, онај који чита у улаз, а једна функција зове Минимак. И то је један ћемо стало највише о томе. Али хајде да прво погледамо главни. Шта да радимо? Па, идемо у анализирати нашу командну линију, само читати и видети шта димензија одбор бисмо волели да имамо. Ми ћемо иницијализујте нашу одбор. А онда ћемо ући један велика дивља петље, у више наврата прихвати потезе док се игра победио, или да нема потеза остало. Сваки пут кад пролазим кроз то петља, ми ћемо обрисали екран. Ми ћемо извући плочу на екрану. И ми смо на неки начин намјерно вађење они далеко као потпрограма, тако да не морате да бринете превише о детаљима како се дешавају. Имаћете код касније данас. А ако желите да погледате кроз и сазнајте, можете их све видети. Али ми ћемо извући одбор на екрану. И онда ћемо проверити и види, да имамо победника? Да ли је неко добио ову игру? Ако имају, ми ћемо штампати од победу поруке. И ми ћемо завршити игру. Такође ћемо провјерити и види да ли је кравата. То ће бити лако да видим да ли је кравата. То значи да су сви простори су пуни, али још увек није побједник. Можемо да прогласи кравату и да се уради. Онда је право једем месо, ако То је машина играч, ћемо дозволити да машина за претраживање играч кроз коришћење овог минимак алгоритам, пронаћи најбољи потез да се може. А онда ћемо ставити ту Мове уп. У супротном, ако је човек играч, ћемо читати неку улаз из људског. И онда да ли је људски плејер или машина играч, ћемо мало направити пар бита провере грешке, уверите се да остане у границама од стварних димензија одбора да имамо, уверите се да тај простор је празан, То нико не ставимо комад у већ тамо. И онда ћемо ставити комад на плочи, промените плаиер до следећег слоја, и инкрементирање колико потези догодило. То је главна петља за наш Тиц-Тац-Тое игра. Минимакс, онда, управо алгоритам који смо раније. Једини подешавање да смо направили тако да смо могу да играју више дименсионал плоче је имамо задржао тај додатни параметар који се зове дубина. И дубина само каже, ако сам претраживање надоле кроз тог дрвета и ја тако да сада доле изван неке дубине нивоа да ја једноставно не желим ићи даље, Ја ћу зауставити и само оцени одбора у том тренутку. Ја ћу да проверим и видим да ли је победник. Ако је победник, ја их врате. Иначе, ја ћу ићи кроз петљу. А ја ћу рећи, за све могућих локација да сам могао узети као мој потез, ја ћу изгради хипотетички одбор који укључује мој потез на тој табли, а затим рекурзивно позива МИНИМАКС. Ако је мој потез, и да би пронашли онај који има највећи резултат. Ако је мој противник потез, налазимо онај који има минималну оцену. И све остало је Само евиденција. У реду, хајде да видимо ову серију. Заправо, можда можемо добити неколико волонтера да дођу до и плаи Тиц-тац-тое. [Неразумљиво] једног, један више, два, тамо. Хајде горе. Дакле, идемо напред и рестарт ово потпуно. Дакле, здраво. ПУБЛИКА: Здраво. ГОВОРИ: Како се зовеш? ПУБЛИКА: Горав. ГОВОРИ: Горав. ПУБЛИКА: Ја сам Лаила. ГОВОРИ: и Лаила, и Лаила, жао ми је. Хајде горе. Горав, идемо да ти први. И ја ћу да вас замолим да будем не Страшно добра Тиц-Тац-Тое играч. У реду, тако да све је притисак на вас. Да видимо, међутим, да је наша машина играч заиста може да уради нешто паметно. Дакле, само напред. Идеш да унесете у којима координира желите да ставите Кс у. А0, ОК, и машина је отишао одмах и ставио свој печат на А1. Ставите О на табли. У реду, сад иди. Gde bi ste voleli da idete? Ц2. Наша машина играч узима средњи квадрат, блокирао. Тако да је био добар, паметна ствар за да уради. Ви сте га блокирали. То је одлично. Потребно је иза угла тамо. И то ће вас натерати да узети последњи простор, Б0. А игра се завршава у кравату. Али играо разуман игра против вас, зар не? У реду, хвала пуно, Горав. [АППЛАУСЕ] У реду, Лаила, идемо до игре на тебе овде. ПУБЛИКА: Сјајно. ГОВОРИ: Идемо дати сте четири од четири Тиц-Тац-пете. Сада, у четири од четири, морате да победи са четири заредом, а не три за редом. И то је све твоје. Дакле, Лаила је Д1. Сада ћемо пратити наш рачунар играч овде. Три од три Тиц-Тац-пете је врста ствари које је лако за све нас. Али ипак је лепо да виде рачунар плејер који паметне потезе. Четири од четири стигне до бити мало компликованије. Лепо урађено. У реду, Лаила је завршио. Ох, и требали смо тамо завршио. Али хајде да урадимо још један овде. Дакле, Лаила, хвала. Лепо урађено. [АППЛАУСЕ] Дакле, наш Тиц-Тац-Тое играч одлази кроз и проналази локације, решава их користећи овај МИНИМАКС. И ја сам имао подешавање дубине о томе тако да Не бих покренути пребрзо, што је вероватно разлог зашто Лаила је био у стању да иде напред лепо као она, и то веома добро. Али ови системи који само пролазе кроз и брутална сила дубље, и дубље, и дубље, и задржати проналажење решења да им је потребно, оне врсте система су прилично успешни у њих, добро, стандардне друштвене игре. У ствари, ако посматрамо три од три тик-Тац-Тое игре, ово је у основи решен проблем. И ово је дивно дијаграм од Рандалл Мунрое на КСКЦД, Показано који крећу да би требало се, с обзиром на ваш противник потези. То је нешто што смо могли лако одредити унапред. Али шта се дешава као што смо доћи до више сложене игре, сложеније игре, где постоје веће одбори више, могућности, дубље стратегија? Испоставило се да је ово бруте форце сеарцхинг даље ради прилично добро, осим када дођете до тачке где је то дрво је толико велика да не можете све представља. Када не можете израчунати целог стабла, када не можете ићи напред и гурај се до тачке где сте стечен целог стабла у меморији, или да ли можете га добити у меморији и то ће само да сте превише дуго да претражујете то, морате да урадите нешто паметније. Да би се то урадило, хвала морам да урадим две ствари. Прво, морате да нађете неки начин ограничавања на дубину. Па, то је ОК. Можемо наћи неку фину, само минимум и рећи, можете само ићи тако дубоко. Али када то урадите, да си то ти имају ове делимично непотпуне даске. И морате да изаберете, ја волим ово делимично непотпуни одбор, или ово делимично непотпуни плоча? И на наша четири стране четири Тиц-Тац-Тое игра, наш рачунар играч добио доле до дна и рекао, Имам два различита даске. Ни једна је победа. Нити један је губитак. Нити један је кравата. Како да изаберете између њих? И није имао паметан начин да то чине. Ми видимо ову врсту евалуација десити све време као што смо се у сложеније игре. Шах је одличан пример. У шаху, имамо, прво свега, већи одбора. Имамо много више комада. И позиционирање ових комада и начин на који су ови комади крећу је од суштинске важности. Дакле, ако желим да користим Минимак, Морам да будем у стању да одредите и кажу, ова плоча, где нико није победио или изгубио још, је некако боље него ова друга одбор, где нико није победио или изгубио. Да бисте то урадили, могао бих да урадим ствари као што бих могао само рачунати колико комада морам и колико комада имате? Или можда дати другачији комада различите тачке. Моја краљица вреди 20 поена. Ваш пешак вреди један поен. Ко има више бодова укупно? Или размислите ствари воле, ко има бољу позицију одбора? Чији је следеће скретање, све што ја могу не да прецизније проценимо која од ових могућности је боље без исцрпно разматра сваки потез који би могао доћи после тога. Сада да тај рад, једна од ствари које је ће постати заиста важно за нас није само креће равно до посебне дубине граница, али у стању да каже, једна од тих идеја које сам има је толико лоше да је не вреди с обзиром све могућих начина да ствари могу да иду од лошег ка горем. Да бисте то урадили, ми ћемо додати у Минимак принцип назван АЛПХ бета. И алфа-бета каже, ако имате лошу идеју, не губите време покушавајући да сазнати тачно колико је лоше. Ево шта ћемо да урадимо. Идемо да се исти принципи које смо раније имали, исти тип минимак потраге, само смо ће пратити, не само од стварне вриједности које имамо, али ми ћемо пратити најбоље могуће вредност да сам могао добити, и најгора могућа исход могао сам. И сваки пут најгора могућа ствар је у потрази вероватно, Ја ћу напустити тај део дрвета. И нећу труди више гледам. У реду, тако да претпостављам да почнемо са истом тачним игра дрвета. А сада ћемо да идемо опет доле, скроз доле у том доњем левом углу. И у том доњем левом углу, ми изгледају и да процени овај форум. Можда је четири од четири Тиц-Тац-Тое плоча, или можда шаховској табли. Али, гледамо и оцењујемо да, и добијамо вредност од осам. У том тренутку, ми знамо да је ћемо добити најмање осам бодова овог доњег одлуке. Није битно шта друго два су, да је седам и да су двојица. Они могу бити било које вредности они желе да буду. Ми ћемо добити у Најмање осам бодова. У реду, али смо могли иди и провери. Можда једна од њих је бољи од осам. Гледамо на седам. Да ли је то боље од осам? Не, то не мења наше мишљење уопште. Гледамо на два. Да ли је то боље од осам? Не, то не мења наше мишљење уопште. Дакле, сада знамо да смо исцрпили све могућности тамо. Нећемо добити ништа боље од осам. Ми ћемо добити тачно осам. И тако смо промијенити ту чвор и рецимо, да је сада сигурно. Идемо горе за један ниво изнад тога. И сада знамо нешто о том нивоу минимизације. Ми знамо да никада нећемо добити више од осам бодова ако идемо доле том правцу. Јер, чак и ако они Друге две гране испало да се фантастично и вреди хиљаде поена, наш противник ће нам дају минимална, и дај нам осам. Добро, добро, хајде да видимо. Ми ћемо наставити тим путем. Идемо до те средини са леве стране. Гледамо се и видимо тамо је девет. Знамо да ћемо добити најмање девет тачака по гоинг довн да средњи пут. И у овом тренутку, можемо да паузу. И можемо рећи, види, знате на нивоу горе, Идем да се не више од осам поене иде доле у ​​овом правцу. Али, ако сам по средини пут уместо левог стазе, Ја бих се најмање девет бодова. Мој противник никада неће допусти ми да одем то средњи пут. Они могу да бирам. И они ће изабрати Пут на лево ка осам, уместо по средини према шта је најмање девет бодова. Дакле, у том тренутку, ја ћу престати. А ја ћу рећи, знаш шта? Ја не морам да гледам било више доле у ​​том правцу. Зато што никада нећу тамо. Ја могу да прескочим тај, и ја могу да прескочим да је шест, зато што се никад неће десити. Дакле, ја ћу отићи и ја ћу размотрити следеће могућности. Идем тамо и кажем, видим два. Ја знам да дођем до овде, ја сам ће добити најмање две. ОК. Ја кееп гоинг. Видим четири. Знам да ћу добити најмање четири. Има још доста између четири и осам, мада. Тако да наставим. Гледам доле и видим да је једна. У реду, знам да Идем доле том путу, Ја ћу бити у могућности да бирају четири. Шта мој противник да уради? Између нешто што ми даје осам, нешто што ми даје четири, и нешто што даје ми барем девет, добро, он ће ми дати четири. И сада знам да су у самом врху, ја ћу бити у стању да се барем четири бода из ове утакмице. Цела идеја алфа-бета је одсекао део стабло тако да ја више не гледај их. Али и даље изгледа као да сам био гледајући много дрвета. Идемо даље доле. Идемо низ следећи сада. Доле на дну, ја нађем један. Знам да ћу добити барем један. Стално тражим. Мислим да је три. Знам да ћу добити најмање три. Ја кееп гоинг. Мислим да је пет. Знам да ћу добити пет ако доле у ​​том путу. Такође знам онда да је мој противник, ако И изабрати средину три велике избора, Он ће ми дати нешто што је пет или мање. ОК. Ја могу да наставим тамо. Ја Можете погледати доле и ја може се рећи, шта ћу да ако одем доле у ​​средини путу? Идем да, добро, три тамо. Идем да узмем нешто то је најмање три. Има још ствари између три и пет, тако да сам стално у потрази. Ох, девет, дефинитивно ћу узети преко три. Идем да најмање девет ако иду тим средњи пут. Сада мој противник зауставља и каже: види, више нема смисла. Знам да је мој минимизирање противник, он је ће ми дати ствар која је мање или једнако до пет, а не ствар која веће од или једнако до девет. Престанем. Ја не гледам више ово. Ја кееп гоинг. Гледам доле на овом једном. Доле на дну, ја наћи шест. Знам да ћу добити најмање шест. А шта да радим? Ја могу да престанем. Зато што је избор између нешто што је најмање шест и нешто што је мање од пет, он је ће ми дати ствар То је мање од пет. И сад знам да ћу да се тачно тај избор. Идем да да пет избора. Ја се вратим до врха. Што ћу изабрати између нечега то је већи или једнак до четири, или нешто што је једнако пет? Ја ћу узети нешто То је најмање пет. Идем доле последњи пут, све пут до дна. Постоји једна. У реду, барем ћу добити један поен. Ја кееп гоинг. Два, ох, то је боље од једне. Идем да најмање два. Мислим да је три. Знам да ћу добити три. Поента изнад тога, мој противник ће да ми нешто што је мање од или једнако до три. И сада могу да престанем. Јер у избор између мене бити могао да добије пет и мој противник да ми нешто мање од три, Увек ћу узети да је пет. Тако да не оцењују да доњи део дрвета уопште. Сада, ово може изгледати мања. Али када мали комадићи аритметике, веће од и мање од, могу одсећи читаве делове ово експоненцијално расте дрво, који води до огромна износ штедње, штедње који су довољно велики да може почети играти конкурентних у сложенијим игара. У реду, ако погледамо величину и сложеност различитих игара, Тиц-Тац-Тое био наш лако пример. Имамо малу таблу, три по три. Ми се, у најбољем случају, у просеку око четири различите опције док идемо кроз игру. Ми имамо негде око 10 до Пети могући различити листови. И изградњу Тиц-Тац-Тое играч, па смо то урадили. То је лако. Ако одемо до нешто више комплекс, као и повежи четири. Да ли се сећате овог игра у којој испустите мале токена у? То је шест од седам одбор, није много већи, и даље отприлике исте гранања фактор као Тиц-тац-тое. Имам око четири изборе где могу ставити ствари у. Али сада, имам много више води, од 10 до 21. власт. То је нешто што је лако Довољно да га решимо одмах. Даме, више вас цомплек-- Добио осам од осам одбора. Ти си само на половини да у било ком тренутку, ипак. Имаш гранање фактор који је око 2,8. Па, имамо пар помера можете узети. Мораш око 10 до 31. лишћа, веће и веће, и веће просторе. Као што морам да претражујете те већи и већи простори, то је када ствари као што су алфа-бета и бити у стању да смањи далеко читаве гране постаје од суштинске важности. Сада, даме било лако 1992. године. Компјутерски програм под називом Цхиноок Беат тхе Ворлд даме шампион, Марион тинслеи. И од тада, нема људско мајстор Играч био у стању да победи најбоље рачунарске системе. Ако погледамо нешто слично шаху, сада Опет, имамо осам од осам одбора. Али имамо много комплекснији комада, много сложенији покрети. Имамо гранања фактор од око 35, 35 могућих потеза у просеку да могу узети и државу простор, број листова који је нарастао на 10 до 123. власт, Огромни број могућности. Цак и модерни процесори су способни да то урадили успешно. У 1995. и затим 1997. године, са рачунаром Програм се зове Дееп Блуе саградио ИБМ које су објавиле на огромном суперкомпјутер победила актуелног светског првака, Гари Каспаров. То је била прекретница. Данас, међутим, та иста обрада снага седи на мом МацБоок. Брзина обраде чува све брже и брже. Можемо проценити све више и више одбори све брже и брже. Али што је још важније, ми имамо боље Функције евалуације и боље орезивање методе. Дакле, можемо сеарцх простор више комплексно. Највећи одбора игре које можемо замислити, нешто слично Го то Има 19 од 19 одбора, Сада одједном, ми смо поред тачке где рачунарске системе могу да победе. Нема рачунске Систем тамо да може да победи професионални Го плаиер. Најбољи системи данас је место за врста добром нивоу аматера. Дакле, још увек постоји доста од нема да не можете доћи до још. У реду, то традиционалне друштвене игре, овакве системе где смо изградњу овог Минимак, да ли има алфа-бета или не, те алгоритми раде јер постоје одређене препреке. Имамо савршене информације о свету. Знамо где су сви комади су. Свет је статичан. Нико не добија за померање комада око док сам ја седи тамо размишљање, узимајући мој ред. Ту је акција простор који је дискретна. Ја могу да ставим пешака овде, или могу ставити свој пешака овде. Ја не смем да ставим пешака на линија између два квадрата. И на крају, акције су детерминистички. Знам да ако кажем, Топ на витеза три, мој топ ће се завршити у витеза три, док је валидан потез. Нема неизвесности око тога. Сада, као што сам ићи на више различите врсте игара, морамо да се пробије те претпоставке. Шта ако одем на нешто као класичне видео игре? Ево избор видео игрице са Атари 2600. Шта ја имам тамо? Имам Фроггер, Спаце Инвадерс, Капан, и Пац-Ман. Какве окружења ја овде сада? Који од ових претпоставки морам да се пробије? Па, то зависи од саме игре. Могао бих да играм шах на 2600, и то би било исто као што је било раније. За већину ових система, ту је потпуно знање о свету. Ту је потпуно детерминистички акције. Али обично, у свету не статична. То је, док сам седео тамо чекања, нешто се креће. Духови долазе по мене. Шкорпион ме прати испод. Тхе освајачи су простор долазе ближе и ближе. Колико добро можемо да урадимо против њих? Пре неколико година Гоогле је пројекат под називом ДеепМинд, где су обучени компјутер програм за играње Атари 2600 игара. А ако мислите да ово није озбиљно посао, резултати њиховог истраживања објављени су у природи, тако исто тако и добра публикација као што евентуално могу добити. А ево како добро су извели. Они имају алгоритам који сат и гледао само на екрану улаза. Постало је уопште нема инструкције о правилима игре. И то је требало да схватим, базирао своју оцену, колико добро ради. То је систем који се користи нешто позвао појачање учење. То јест, изгледало је на свом резултату. И ако имам добре оцене, наводи се, Требало би да се тих ствари. И треба ли они поново. И ако је добио лошу оцену, да је рекао: Не би требало да те ствари поново. То су перформансе тих обучених система дозвољено да играју на Неколико сати на свакој утакмици, у односу према професионалним играчима. Дакле, за све игара које су на левој страни ове линије, ово само обучени компјутерски програм надмашила професионалне играче. А за све до десно, професионални играчи су и даље најбољи. За нешто што је знао ништа о правилима, која не зна ништа о структури игре, ово је импресивне перформансе. И то је оно што смо у стању да урадимо данас. У реду, ви кажете, али ако размислите о АИ у играма, нормално мислимо о Ствари које ми заправо можемо сјести и играти против. Ако седнем и ја играм Старцрафт, или играм Фрее сито, компјутер противник је Особа контролу Зерг, или контролише другу цивилизацију. Како ти играчи заправо пронађу своје потезе? Па, ове игре су структурирани много на исти начин као наши друштвене игре, Ове игре да ћемо колективно зову четири Кс Гамес, истражују, екпанд-- заборављају оне. Шта су они? Истражите, проширити и гаси, Мислим да је последња. Али они су у основи истраживања и Цонкуер игре. Типично, компјутер противник ту има ограничене информације. Они не знају тачно шта је дешава иза магли рата. Они не виде оно што имате у инвентару. Ту је окружење које је динамичан. Све се мења све време. Ти не да седимо и чекати да свој потез. Али већина ствари су и даље дискретни. Морам да ставим овде мој град. Или морам да ставим овде мој град. И све је детерминистички. Када кажем, доселити своју јединицу, моју јединицу сели овде, осим ако препрека изненада долази до изражаја. Сада, то није све рачунар игре које су тамо данас. Ако одем и ја играм први тип особе игра, нешто као лопов или Фаллоут ор Скирим, или хало, сад Имам компјутерске противнике да су тамо који имају веома другачија ситуација. Имају, опет, ограничене информације. Они само могу да видим сигурно видно поље. Окружење је и даље динамичан. Ствари се мењају све време. Али сада имам много више континуирана акција простор. Могу бити само вире мало из врата. И неке игре, мој акције су стохастички. Могу да покушам да прескочим тај зид, али имам шансу од неуспеха. Ове врсте игара су све ближе и ближе врсте контролера да градимо у роботици. У роботике, морамо да претпоставимо да имамо ограничену информације. Имамо сензоре који Реците нам о свету. Имамо увек мењају, динамично окружење. Имамо свет у коме је простор цонтинуоус, пре него дискретна. И наше акције, када покушамо их, имају шансу од неуспеха. И у ствари, модерна игра контролери за ваш Хало противника, или за оне НПЦ у Скирим, у суштини имају мала роботике архитектуре. Они осете свет. Они граде модел света. Они Цомпуте заснован на сету циљеви који би они желели да постигну. Они планирају акције засноване на шта знају. И они су потпуно исти врсте система који градимо у роботици. Дакле, те архитектуре, да вратим назад заједно, су често исти. Дакле, хајде да видимо да ли можемо да видимо то. Хајде да се вратимо на нашу Тиц-Тац-Тое пример. И ја ћу да поставим пар мојих пост-доцс да дођу до и помози ми. Тако Чен Минг и Алессандро, и Оливије, ако ви доћи до. И ја ћу требати неколико волонтера У реду, видела сам десну руку до тамо у средини. Дозволите ми да још једну, неко даље у позади можда. Добро, тамо. Хајде горе. У реду. Дакле, хајде да узмемо ту поклопац доле. И ако ви доћи у праву назад овде за мене, фантастично. Дакле, ово је робот назван Бакстер. И Бакстер је робот који је комерцијални платформа, дизајнирана од стране компаније под називом Размисли. И овај робот је дизајниран за производњу малог обима. Али данас ћемо користите га да игра Тиц-тац-тое. Сада, овај робот је такође нешто То је релативно јединствен. Јер ако се било где стојим близу стандардне фабрике аутоматизације систем, ја бих био у самом гробу опасност од повређивања. Бактер, међутим, дизајниран да буде релативно безбедно за интеракцију са. И тако ја могу гурати на овом робота. И можете да видите да је мало мало флексибилан као што се креће около. И могу да позиционирати где бих га да оде. Сада у нормалном роботског система, бисмо имали низ зглобова овде то би било директно одговара на положај команди. И они не би нужно брига ако су се кретали кроз отвореном, или ако су се кретали кроз грудни кош. ОК. И обично, ако сте били овде са индустријским системима, ти би нигде ићи код њега. Било би жута Безбедност трака око њега. Овај систем има мало другачији дизајн бити пријатније и лакше за људе да комуницирају са, у томе у сваком зглобу, са опругом. И уместо да контролишу егзактна положај, ми контролишемо одређену количину обртни момент, одређена количина силе, да желимо да будемо на том пролеће. У реду, тако да ме пусти узме наше волонтере овде. Здраво, како се зовеш? ПУБЛИКА: Луис. ГОВОРИ: Луис. Драго ми је да Вас видим. И? ПУБЛИКА: Дејвид. ГОВОРИ: Дејвид. Драго ми је да смо се упознали. Ако ви би ваит овде на секунд, Ја ћу да ти дам шансе за то. Дакле, овај робот, ако дођеш до и ако лагано гурните на њему, ћеш видјети да помера мало. А ако га ухватите у праву овде на зглобу само изнад места где су та дугмад, то Изгледа да треба да узмем дугмад, али зграби тачно изнад њега уместо тога, ви ћете бити у прилици да лагано га манипулишу кроз простор. Луис, хоћеш да му дати прилику? Тако се дају само мало пусх за почетак. И онда ако ставите прсте тамо и задржати на њега, јер ће се кретати за тебе. У реду, желите да га пробамо? Хајде горе. Тако се дају само нежни пусх ту да почне. Можете осетити како је то. И онда ако га ухватите тамо, ћете моћи да маневрише око. ОК. Тако типично, ова врста робота би могу користити за производњу малог обима. И ја ћу да се овај руку само сишао с пута мало овде. Али данас, ми ћемо користити Исто Тиц-Тац-Тое игру систем на основу Минимак које смо раније изградили. ОК? Дакле, ви сте једни да играју игру. Луис, ти ћеш бити први. Дозволите ми да држите овде на тренутак. Идем да стојите у реду овде, само да свако може да те види. Да ли ви поставили овде? Робот: Добро. Хајде да се играмо Тиц-тац-тое. Немојте схватити ваш знак пре Ја кажем да је твој ред. Ја почети утакмицу. То је мој ред. ГОВОРИ: Сада, ако би могао узети један од Ваши комада и само напред и поставите га. Робот: То је твој ред. [СМЕХ] То је мој ред. [СМЕХ] [СМЕХ] То је твој ред. ГОВОРИ: Људска раса је Рачунам на тебе, Лоуис. Робот: То је мој ред. ГОВОРИ: Па Бакстер Овде блокиран. Робот: То је твој ред. То је мој ред. То је твој ред. То је мој ред. ГОВОРИ: И ми ћемо пустити Бакстер завршити своју последњу потез овде. [СМЕХ] Робот: То је кравата. Ја ћу победити следећи пут. [СМЕХ] ГОВОРИ: У реду, Хвала пуно, Луис. Хвала вам. Можете ићи на овај начин. Робот сам почети утакмицу. ГОВОРИ: Дакле, дозволите ми да објасним да вас један мали Мало пре него што добијемо реванс овде. Шта се тачно дешава? Дакле, робот има овде камере одозго. И то гледа доле на табли. И то се видело да ли то је добио црвени О или плави и бела Кс. Као они се ставља на плоча, то је у основи исти улаз да ћемо читати из Наша структура података са нашим екранима. То ради исто Минимак алгоритам да буде у стању да пронађу где поставите добар знак. И онда ми даје команду о где бисмо желели жетон да се стави. Рука се исељавају. То је користећи вакуум гриппер да се пријаве нека усисна том дрвеном комаду, покупи га, преместите га на десно место, а затим отпустите усисавање и пустите га. У реду, идемо да му дати још једну прилику са мало паметније играча овде. Ste spremni? У реду, ако би стојим усправно и дај је-- испало овако тако да можете видети све. А онда [неразумљиво]. Робот: То је мој ред. ГОВОРИ: Бактер ће почети. То је твој ред. То је мој ред. То је твој ред. То је мој ред. [СМЕХ] ГОВОРИ: [Вхисперинг] Само нека изволи и победи. Робот: То је твој ред. ГОВОРИ: То је у реду. Робот: То је мој ред. [СМЕХ] Победио сам. [СМЕХ] Ја почети утакмицу. ГОВОРИ: У реду, хвала вам пуно. У реду, мислим да имамо времена за још један одличан Тиц-Тац-Тое играч, неко ко може да ставим ово у матцх, ко зна шта они раде. [СМЕХ] Ко ће бити наш шампион овде? У реду, ваши пријатељи добровољно. То је довољно добро за мене. Реци ми своје име поново. ПУБЛИКА: Тамир. ГОВОРИ: Тамир, драго ми је да те видим. У реду, опет, ми ћемо вас управо овде, тако да сви могу да те видим. Ви сте наш представник у овом мечу сада. Бактер је један и ох и ох. Или је, један О и један. И то је на вама овде. Бактер ће доћи до први корак, мада. Prema tome. Робот: То је мој ред. [СМЕХ] То је твој ред. То је мој ред. То је твој ред. То је мој ред. То је твој ред. [СМЕХ] Робот: То је мој ред. ГОВОРИ: Много је теже када стојите овде, народе. [СМЕХ] Робот Ви људи сте тако лако победити. [Смех и аплауз] ГОВОРИ: Хвала пуно. Робот ја победим. Ја почети утакмицу. Спеакер: У реду, хвала вам много Оливиер, и Алессандро, и Чен Минг. [АППЛАУСЕ] Желим да направим један последњи поен. Дакле, Бактер на самом завршити, варао. И то је било неочекивано. Један од фантастично ствари о АИ је да смо раде у АИ, тако да можемо изградити заиста занимљиво и интелигентан уређаји. Али ми такође раде у АИ јер нам говори нешто о томе како су људи интелигентни. Један од омиљених студије из моје лабораторије је гледајући шта се дешава када машине неочекивано цхеат. Ми смо ово урадили првобитно није са Бакстер играју Тиц-Тац-ножни прст, али са мањим роботом по имену Нао, који је играо Роцк-Папер-маказе. А понекад после играју много и много досадан роцк-папер-сциссорс игре, робот ће бацити гест, изгубити, а онда одједном променити његов гест и рећи, ја сам победио. [СМЕХ] Сада, понекад бисмо такође имају робота, само као контролу, баци гест, победити, а његов гест промени да изгуби, баци меч, цхеат како би се изгуби. А то није ни приближно толико убедљив. Робот који вара како да освоји људе реагују на као да се како би их, као тим активно тражи њихово уништавање. [СМЕХ] То постаје агент. То је као особа. Она има веру и намеру. И то није добра намера. А робот који баца игра је у квару. То је само сломљена уређај. Дозволите ми да вам покажем пар примера то из неколико наших учесника. Дакле, овде је варање у циљу изгубили. [ВИДЕО РЕПРОДУКЦИЈА] - [Неразумљиво] победити. Заиграјмо. -Stani šta? - [Неразумљиво] победити. Заиграјмо. [Неразумљиво] победити. Заиграјмо. ГОВОРИ: И овде је варање да победи. Да, ја сам победио. Заиграјмо. -Не Могу то да урадим. [СМЕХ] Да, ја сам победио. Ти варао. Сада је преварио. Да, ја сам победио. Хеј, ти варалица. Вараш, супер цхеат. [Крај репродукције] ГОВОРИ: Ово другачији реакције убрзано мењају нашу перцепцију уређаја. Да ли то значи да смо намерно буилд машине које цхеат јер је то најбољи инжењеринг што можемо да учинимо? Не, али то нам говори нешто заиста занимљиво о људима. Та ствар која вас вара и краде ваша победа, то је нешто што је жив, то је анимирају, то је од вас добити. То је ментално стање. Она има веру. Она има намеру. Та ствар која руке игра за вас, то није. То је само у квару. Ово је на много начина зашто је то лако баци игру са децом. Али ако покушате да их варају и некако тврде победу када, знаш, само да скрате игра, они ће те ухватити одмах. Овакве ефектима који видимо излази из АИ, Они нас уче много о нама самима. У реду, то је то за данас. Хвала пуно на Давида и продукцијски тим Харварда што сте дошли. [АППЛАУСЕ] Видимо се за квиз један, а затим на последње предавање. Желим ти леп дан. [АППЛАУСЕ] [Мусиц плаиинг] Давид Ј Малан: Па, вероватно треба да уведу неку врсту шифровања, jel tako? Јер тада заглавља ови ХТТП захтеви ће бити кајгану тако да свако покушавајући да их мирише ваш саобраћај неће заиста бити у стању да их види. Дакле, шта је решење за овај проблем? Па, морамо да заиста увести енкрипција у формулу, тако да када та особа преноса података од А до Б, можемо сигурно сенд-- [СМЕХ] Информације у начин да противник не може, у ствари, то видим.