[За възпроизвеждане на музика] SPEAKER: Добре дошли отново на всички. Това е CS50. И днес, ние имаме много интересни неща да говорим. Първо обаче, трябва да напомним ти на няколко административни неща. Тази седмица е една загадка, сряда или за участъка Yale във вторник и четвъртък, в четвъртък. Има мнения викторина Тази вечер в Йейл, 5:30-7:00. В Харвард, те записват един вчера. И всеки може да гледате, че онлайн. Също така, тази седмица или в началото на следващата седмица, имаме последната ни CS50 лекция. [Стонове] Знам. Той дойде толкова скоро. Йейл учениците ще имат на живо лекция тук, в училището право аудитория в петък. Ще има торта. Студенти от Харвард ще имат последната лекция в Sanders в понеделник. Ще има и торта. Също така, тази седмица в петък, за тези, от вас, които идват в Ню Хейвън, имаме CS50 Expo. Ние имаме повече от 30 различни групи регистрирани да ви покажа всичко от автономните платноходки, за системи, които признават, цифрови портрети, към компютър музика и компютърно произведена музика. Така че, моля присъединете се към нас. Мисля, че ще бъде страхотно. Днес, обаче, да стигнем до продължи да говори за AI, за изкуствен интелект. И едно от нещата, които ние ще стигнем до днес е идеята за това как да използвате AI за решаване на проблемите. Сега, както винаги, нека да започнем с нещо по-просто. И ние ще започнем с една проста идея. И това е с помощта на търсене. Така че представете си за момент, че съм има за задача, която ми трябва да изпълни. И бих искал да имам тази задача автоматизиран от някакъв софтуер агент. Представете си, че аз се опитвам да поръчате комплект на полетите от, да речем, Boston в Сан Франциско. Можех да мине през и можех да използвам един от най-прекрасен онлайн търсенето инструменти, които се случва да правя едни и същи процес, който ние сме Ще преминете през днешния ден. Но ако не сте имали, че инструмент, какво бихте направили? Е, можете да погледнете и виж и да кажа, че съм в Бостън. Какво полети са достъпни за мен? Сега, може би имам три възможни полети от Бостън който ще се поберат времето когато имам нужда да си тръгне. Можех да летя до Чикаго. Или можех да летя до Маями. Или мога да лети до Ню Йорк. Тогава можех да погледна от всяка един от тези градове дестинация и мисля за това места Бих могла да достигне от всеки от тези отделни места. Така че може би от Чикаго, мога да получа директен полет до Сан Франциско. Това е отлична. Или мога да получа полет до Денвър. Сега, може би, че полет до Сан Франциско е идеалното решение за мен, но може би не. Може би аз съм гледам за нещо че е малко по-евтино или малко по-добре за моя график. И за да мога да гледам за какви други възможности могат да бъдат там. Така че бих могъл да разгледате Денвър. И от Денвър, добре, може би Мога да получа полет до Остин. И от Остин, може би мога да получа полет до Phoenix, и от Phoenix в Сан Франциско. Сега, аз не съм направено още. Защото може би има по- директен полет от Ню Йорк в Сан Франциско, който е перфектен за мен. Или може би има полет от Маями чрез Denver, че е много по-евтино. Така че аз все още трябва да отида. И аз все още трябва да разгледаме всички тези, градове, които все още не съм разследвани. Трябва да се провери изчерпателно всички възможностите, които биха могли да имат. I Така че от New York, може би мога да получа полет до Нашвил, и от Нешвил до Остин. И тогава аз знам къде съм. И тогава аз знам от Остин, което мога летят до Phoenix, и от Phoenix в Сан Франциско. Ако аз летя първо до Маями, все пак, Може би мога да получа с полет от Маями в Нешвил, или от Маями до Остин. И сега съм пробвал всички на възможностите. Аз бях изградила тази графика, че ми показва всички възможни маршрути за да бъда в състояние да вземе. Когато ние представляваме тях видове проблеми, ние няма да представлява тях изрично като тази графика, защото това не представлява графика историята на където сме отишли. Знаейки, че съм летял от Phoenix в Сан Франциско не ми кажете дали съм дошъл направо Nashville, или чрез Denver, или чрез Маями. Така че това, което аз ще направя, вместо да е Ще взема същия този проблем, и аз ще го представят като едно дърво. И в основата на дървото, в отгоре, аз ще постави на мястото, което започнах, Бостън. И от Бостън, ще разгледаме всички възможни места че мога да пътувам до. Е, в този случай, аз имах три, Чикаго, Ню Йорк и Маями. И тогава аз ще проучи всяка от тези деца в дървото. От Чикаго, видях че имах два полета. Аз може да лети директно до Сан Франциско или в Денвър. Сега Сан Франциско, това е моята цел. Това е моята дестинация. Това ще бъде едно листо от това дърво. Това е, аз никога няма да отида някъде след Сан Франциско. От Денвър, все пак, Аз може да лети от Денвър до Остин, от Austin до Phoenix, и от Финикс до Сан Франциско. И сега отново, аз съм достигнал едно листо. Тогава можех да се върна към следващия град, който аз не съм напълно проучени. Това ще бъде Ню Йорк, отидете обратно нагоре към върха на дървото ми, слезе до Ню Йорк. От Ню Йорк, мога да летя за Nashville, от Нашвил до Остин, от Austin до Phoenix, и от Финикс до Сан Франциско. И накрая, един град I Не сте погледна още, Маями. Е, от Маями Казах, че имаше две възможности, Нешвил или Остин. Ако аз летя за Нешвил, и след това летя от Нешвил, за да Austin, да Phoenix, в Сан Франциско. Ако летите до Остин, летя Остин, да Phoenix, към Сан Франциско. И сега имам едно дърво. Това е пълно дърво. Това е всичко от възможностите и всички пътища, по които мога да взема. Това означава, че ако започна в корена на дървото на върха и аз да се понижат до един от листа, тя ми казва, не само къде отивам да в крайна сметка, Сан Франциско, но тя ми казва, че по маршрута Аз трябва да се вземат, за да стигнем до там. Сега, кой от тях е най-добрият? Е, нищо за това проблем, все още ми казва кой от тях е най-доброто решение. Може би не ми пука много около колко време съм във въздуха, или разстоянието, че летя. В този случай, Чикаго, за да San Francisco може да се окаже най-краткия номер на метри във въздуха. Може би ми пука за разходите. И ние всички знаем директни полети обикновено са по-скъпи. Така че може би, ако аз се възползвам от тази вид назад маршрут чрез Miami, Nashville, Остин, Phoenix, може би тогава Получавам по-ниска цена. Но мога да се оптимизира за всеки критерии, които се грижат за I. Кой има най-добрите в полет Wi-Fi, или които летища имат на разположение най-добрата храна. И всяка от тези сила дай ми едно различно решение който виждам като най-добрия. Тези видове проблеми, къде отиваме да се изгради това дърво на възможности и след това Посетете всяка една от тези индивидуални пътища, и да провери кои от тези Спазва Критерий за нас, ние ще се обадя тези проблеми с търсенето. И ние имаме много алгоритми, някои от които ние вече сме виждали, да отидете и опознаването на тези дървета. Можем да го направим по начина, по който аз Просто направих, първа дълбочина търсене, захождането, доколкото е възможно, докато не удари едно листо, а след това да се върне нагоре, и ще се връщам надолу. Или можем да направим това, което е наречено широчината и първия търсене. Бихме могли да разширим всичко в горната част, и след това всичко един ред че под и след това всичко един ред отдолу това. Тези Вас дървета са от основно значение за AI. Но те съвсем не се получи Правилно ли през цялото време. В действителност, в много от случаите че ние наистина се грижи за, искаме да изградим едно дърво, но ние не правим всъщност получите да направи всички решения. Това са ситуации, наречени състезателна търсене, известен още като как да пиша игра игра системи и се плаща за това. Но това са видовете на системи, където I може да избирате, когато отида от Boston, кой град отивам на следващия. Но след това, някой друг може да получите да вземе решение за това къде летя. Така че, за да се изгради това видове структури, ние сме ще трябва да се вземат леко различен подход към него. Ние няма да бъде в състояние да Просто търся през дървото вече, защото ние не сме този, който е в контрола на всяка една от тези точки на решения. Така че нека да си представим една проста игра като тик-так-палеца. Можех да се започне с абсолютно празни борда. И в тик-так-палеца, X ще играе първи. И така, аз можех да мисля за всички възможни ходове, които биха могли да направят. X И ако аз съм една свиренето Х, това е страхотно. Имам девет възможно се движи, че мога да направя. Можех да се сложи X във всяка една на тези девет позиции. След това от всеки от тези, I можех да си представя какво ще се случи следващата. Е, в този случай, а другият играчите ще стигнем до вземе завой. O ще стигнем до вземе завой. И от всеки от тези, там ще бъде осем различни места O, че би могъл да постави своя маркер. Да кажем, аз реших, че съм ще сложи X в центъра. Това винаги изглежда като добър отваряне ход. Можех да погледнете под това, осем възможни ходове, които прави. O Сега, ако играя X, това е чудесно. Съм се да избере кой I отидете, този в средата. Но сега O получава да избирате. И аз нямам контрол над това решение. Но от всеки от тези възможните позиции за гладене, има после още набор от възможности. Когато става дума за моят ред отново, бих получите, за да изберете и да кажа, добре, ако O движи в, добре, средната място в ляво, след това Имам набор от възможности къде мога да взема следващия си ход. От тези, бих могъл да вземе предвид всички възможностите под тях. И тогава O ще получи да избират сред тези. И аз може да поддържа изграждането на това дърво, докато стигнах до точката когато или някой, печели game-- това е Трябва да се счита за едно листо node-- или на борда се напълни догоре и никой не е спечелил. И това също щеше да бъде едно листо възел. Това ще бъде една вратовръзка. Но трудно нещо, с това е ако това беше просто обикновен търсене проблем, щях да бъда в състояние да да речем, добре, X трябва да отидете тук. И O трябва да отиде начин там. И тогава X трябва да отидете тук. И тогава O трябва да отиде начин там. И тогава X може да получи три в един ред, а аз спечеля. И играта ще бъде над в пет движения, три за мен, два за моя опонент. Но не винаги да избереш това. Така че вместо това, което ние сме Ще трябва да направя се ние ще имаме да има нова стратегия. И стратегията, която игра-игра алгоритми често използват е това, което се нарича Минимакс. Основната идея на Minimax е, че ние сме Ще вземете този ход, който дава нашият противник най-лошия възможен набор от движи, че те могат да направят. Тя не ми направиш някоя добра да изберем движение, при Може и да съм в състояние да спечели след това, защото противникът ми не е ще ми даде този шанс. Те ще изберат някои ужасен резултат за мен. Така че аз отивам да се направи се движат, че силите на моя опонент да се направи нещо по-добро за мен. Всичко е наред. Нека да видим как това се разиграва. Така че тук е алгоритъм ни в Псевдокод. Отиваме да генерира цялата игра дървото. Отиваме да се изгради цялата структура. И тогава ние ще преминеш. И най-долу на всеки един от крайни възли, при всеки от листата, ние ще оцени как ценно е, че на мен? И ние ще стойност неща, които са добри за мен като положителна. Нещата, които не са добре за мен ще бъде по-малко позитивно, или нула, или дори отрицателен. Така че в тик-так-палеца, може би победа за мен е добро. Това е една. И вратовръзка е нула. И нещо, което е загуба за мен, може би това е отрицателен. Всичко, което има значение, е, че по-добре това е за мен, по-голям резултат която получава. От тези възможности в дъното, след което ще се филтрира нагоре. И когато това е моят шанс да изберем сред набор от алтернативи, Ще изберете този, който е получи най-високата оценка. И всеки път, когато това е моята опоненти се обръщат, за да изберете, Ще приемем, че те ще изберете този с най-ниска оценка. И ако аз направя това по целия път до върха на дървото, Аз ще съм избрал пътя, който дава ми най-добрия резултат, че мога да получа, ако се приеме, че противникът ми прави всички правилни действия. Добре, така че нека да видим това в действие първата. И тогава ние ще действителност Посетете кода за него. Така че представете си имам това голямо дърво. И сега аз не играя тик-так-палеца. Исках да ви дам нещо малко по-богати. Така че аз имам някаква игра, в която Има много различни резултати че мога да имам в края. И така, аз се изгради това пълно дърво. И съм се да се премести първата. Аз съм в основата на дървото. И аз да избереш that-- така че да получите да се увеличи през тази първа възел. И тогава противникът ми стане да отида. И тогава съм се да отида още веднъж. Така надолу към дъното, имам набор от възможности, които мога да избирате, различни крайни състояния на играта. Ако аз съм предвидени в това Доколкото ляв ъгъл, и виждам, че имам избор между осем, седем, и две, добре, аз съм този, който получава, за да изберете. Така че аз отивам да изберете най-добрата от тях. Отивам да се избере най-осем. Така че аз знам, че ако някога стигнем до тази точка, Аз ще бъда в състояние да получи това, че осем точки. Ако се окажете в следващата точка над, на следващия възел по, девет, а един, или шест, добре, аз съм ще избере най-добрите от тях. Аз ще избера деветимата. Ако имам избор между две и четири, и един, Аз ще избера четиримата, най-високата. Сега, ако аз гледам на нивото по-горе, че противникът ми е този, който получава да направи този избор. Така опонентът ми да стане избирате, искам да му дам нещо, което се случва да го измъкне осем точки, или мога да му дам нещо, което е Ще му дам девет точки, или това, което се случва за да му даде четири точки? И моят опонент, бидейки рационално, ще да избират минимум на тези, ще избере четири. И мога да го направя през целия дървото. Мога да слизат, че среден сет на три. И аз да избирате между една, три и пет. И аз да избереш. Така че аз се избере пет. Аз може да избере три, девет, или две. Съм се да избера, така че аз избирам деветимата. Шест, пет, или два, аз избирам. Съм се да избере шестимата. Ниво над това, кой да избера? Кой получава да изберем? Другият, противникът ми. Така те избират пет, девет, или шест, коя? АУДИТОРИЯ: Петимата. SPEAKER: Те избират петимата. Те да избереш минимума. И тогава на последната, избере един, два или три. Съм се да изберете, за да мога да избере три. Nine, седем, две, аз избирам девет. И 11, шест, или четири, аз избирам 11. Опонентът ми след това избира трима, девет, или 11, избира минимум. Той ми дава три. И накрая в горната част на дървото, аз да избереш отново. И съм се да избирате между четири, пет, или три. Така че съм на пет. Ако аз трябва да контролира всичко, щях поеме по пътя, който водеше към 11. Но аз не се получи да направи този избор. Ако отида по този път. Опонентът ми ще ме принуди да избора, което води до три. Така че най-доброто, което мога да направя е да вземе, че средната клон, направи този избор е, че в крайна сметка ще ме доведе до пет точки. Това е, което Минимакс прави. Всичко е наред. Нека да разгледаме най-че. Така че тук в CS50 IDE е програма, която изпълнява Минимакс да играе Тик-так-палеца. Отиваме да се изгради създаване на представителство. Отиваме да имат два opponent-- или двама играчи, нашия компютър плейър и човешки плейър. Номер Player един ще се играе на O. Това ще е играч на машината. Те се да се движат на второ място. И на другия играч, ни играч на човека, ще бъде X. И за да ми живот малко проста, аз ще съм да се поставя етикет, че играчите отрицателен. Така че аз може просто да се размножават от отрицателен за размяна между един играч и от друга. Добре, така че нека да разгледаме най- това, което ние всъщност ще направим. Отиваме да се определят нашата борда. Това ще бъде добре, отиваме за да може тя да бъде по три, или дори можем да играем пет от пет или седем от седем тик-так-палеца, ако искате като въз основа на някои измерение D. И ще имаме няколко на помощни функции че ще направя неща, като инициализира screen-- или Съжаляваме, инициализира нашите променливи, изчистете екран, изготвя борда на екрана, един, който проверява на борда да се види дали или не има един победител, който анализира чрез командния ред, Просто, за да помага, една, която чете в вход и една функция, наречена Минимакс. И това е този, ние ще се грижи най-много за. Но нека да погледнем първо на най-главното. И какво ще правим? Е, ние ще разбор на нашия команден ред, що прочетох в и да видим какво измерение борда ние бихме искали да имаме. Ние ще се инициализира нашия борд. И тогава ние ще попадне в едно голяма дива линия, многократно приемам ходове, докато играта е спечели, или че няма останали ходове. Всеки път, когато мине през това линия, ние ще изчистите екрана. Ще се направи на дъската на екрана. И ние сме умишлено нещо абстрахиране тях след като подпрограми, така че ние не трябва да се тревожи твърде много за подробности за това как те се случват. Ще трябва кода по-късно днес. А ако искате да погледнете през и да разберете, можете да видите всички тях. Но ние ще се направи борда на екрана. И тогава ние ще провери и виж, имаме победител? Дали някой е спечелил тази игра? Ако те имат, ще отпечата посочени победа съобщение. И ние ще се сложи край на играта. Ние също така ще проверява и виж, ако има равен брой гласове. Тя ще бъде лесно да се види, ако има равен брой гласове. Това означава, че всички пространства са пълни, но все още не е победител. Ние може да обяви вратовръзка и да се направи. Тогава недвижими meat-- ако това е една машина плейър, ние ще позволим това машина играчите да търсите чрез използването на този Минимакс алгоритъм, да се намери най-добрият ход, който може. И тогава ние ще постави този ход нагоре. В противен случай, ако това е играч на човека, ние ще прочетете някои принос от страна на човека. И след това, дали е човекът плейър или играч на машината, ние ще направим няколко малко бита на проверка за грешки, уверете се, че той остава в границите на действителните размери на дъската че ние имаме, се уверете, че това пространство е празна, че никой не сложи парче там вече. И тогава ние просто ще сложи парче на борда, промяна на играча към следващия слой, и нарастване колко ходове да се случи. Това е основната линия за нашата тик-так-палеца игра. Minimax, а след това, е точно алгоритъм, че преди. Единствената корекция, която сме направили така, че ние може да играе по-висока триизмерни дъски е ние сме съхраняват този допълнителен параметър, наречен дълбочина. И дълбочина просто казва, ако съм търсите надолу през това дърво и аз получавам толкова далеч надолу отвъд някаква дълбочина ниво че аз просто не искам да отиде по-нататък, Отивам да се спре и просто оценка на борда в този момент. Ще проверя и да видим дали има победител. Ако има победител, аз ги върне. В противен случай, ще мине през една линия. И аз ще кажа, за всички възможните места че бих могъл евентуално вземе като моя постъпка, аз ще изгради една хипотетична борда, че включва моя ход от този съвет, и след това рекурсивно призовава Минимакс. Ако това е моята постъпка, аз се да намерите този, който има най-голям резултат. Ако това е ход на опонента ми, ние откриваме този, който има минималния резултат. И всичко останало е просто водене на записи. Добре, така че нека да видим този план. Всъщност, може би можем да получите няколко доброволци да дойде и да играе Тик-так-палеца. [Недоловим] един, и един повече, две, точно там. Хайде нагоре. Така че нека да вървим напред и да рестартирайте това напълно. Така че, здрасти. АУДИТОРИЯ: Здравейте. SPEAKER: Как се казваш? АУДИТОРИЯ: Gorav. SPEAKER: Gorav. АУДИТОРИЯ: Аз съм Лейла. SPEAKER: И Layla и Layla, съжалявам. Хайде нагоре. Gorav, ние ще трябва да отидете на първо място. И аз ще ви помоля да бъде не Ужасно добра тик-так-палеца играч. ОК, така че всичко, налягането е на разстояние от вас. Да видим обаче, че нашата машина играчите могат действително да се направи нещо умно. Така че продължавайте напред. Ти ще се объркат, в който координира бихте искали да сложиш X инча A0, OK, и машината е отишло веднага и сложи своя отпечатък в A1. Поставете O на дъската. Добре, сега вървим напред. Къде бихте искали да отидете? C2. Нашата машина играч е взела средната площада, ви е блокирал. Така че това е един добър, умно нещо, за да се направи. Ти успя да блокира удара. Това е отлична. Това отнема ъгъла там. И това ще ви принуди да вземи един последен пространство, B0. И играта завърши с равен резултат. Но тя играе разумен игра срещу вас, нали? Добре, благодаря много, Gorav. [Аплодисменти] Добре, Layla, отиваме до играта за вас тук. АУДИТОРИЯ: О, страхотно. SPEAKER: Отиваме да даде можете четири от четири тик-так-палеца. Сега, в четири от четири, което трябва да спечели с четири в един ред, а не три поредни. И всичко е ваше. Така Layla взе D1. Сега ще да следват нашия компютър играч тук. Три от три тик-так-палеца е вид на нещо, което е лесно за всички нас. Но тя все още е хубаво да се види на компютър играч прави умни ходове. Четири от четири получава да да бъде малко по-сложни. Добре свършено. Добре, така че Лейла завърши. О, и ние трябва да приключи там. Но нека да направим още една тук. Така Layla, благодаря ви. Добре свършено. [Аплодисменти] Така че нашата тик-так-палеца играч отива чрез и намира места, решава да ги използвате този Минимакс. И аз имах настройка на дълбочина на това, така че тя няма да се кандидатира твърде бързо, което вероятно е защо Layla е в състояние да отидат добре напред като тя го направи, и се справи много добре. Но тези системи, които просто проверете и груба сила навлезем по-дълбоко и по-дълбоко, и по-дълбоко, и поддържа намирането на решение че те се нуждаят, тези видове системи са доста успешни в това, добре, стандартните настолни игри. И всъщност, ако погледнем по- по три тик-так-палеца игра, това е в основата на решен проблем. И това е прекрасно диаграма от Рандал Мънроу в Xkcd, който показва кои движи необходимата взема, като се има ходове на противника си. Това е нещо, което бихме могли да лесно зададени преди време. Но какво се случва, тъй като ние стигнем до по- сложни игри, по-сложни игри, където има по-големи плоскости, по- възможности, по-дълбока стратегия? Оказва се, че това груба сила да търсите още прави доста добре, с изключение на когато стигнем до точката когато това дърво е толкова голям, че не можете да го представляват всички. Когато не може да изчисли цялото дърво, когато не можете да отидете напред и натиснете себе си до точката, където сте намерила цялата дърво в паметта, или дали можете да го получите в паметта и това ще стане само ви отнеме много дълго време, за да се търси чрез това, което трябва да се направи нещо по-умни. За да направите това, вие трябва да направите две неща. Първо, вие трябва да намерите някои начин за ограничаване дълбочината си. Е, това е ОК. Ние можем да намерим някой хубав, абсолютния минимум и да кажа, вие може само да отидете толкова дълбоко. Но когато правиш това, което ти означава, имат тези частично непълни дъски. И вие трябва да изберете, направете ми харесва Това частично непълно борда, или това частично непълно борда? И на нашия четирима от четири тик-так-палеца игра, нашия компютър играч слезе до дъното и да го каза, Имам две различни плоскости. Нито едното е победа. Нито едното е на загуба. Нито едното е вратовръзка. Как да избера между тях? И това не е имало умен начин за правене на това. Виждаме този вид оценка се случи през цялото време като вземем в по-сложни игри. Chess е чудесен пример. В шаха, което имаме, първо от всички, по-голям борд. Ние имаме много повече парчета. И позиционирането на тези парчета и начинът, по който тези парчета се движат е от критично значение. Така че, ако искам да използвам Минимакс, Трябва да бъде в състояние да се уточни и да кажа, този форум, където никой не е печели или губи, все още, е някак си по-добър от този друг дъска, където никой не е печели или губи. За да направите това, мога да направя неща, като бих могъл просто преброим колко парчета трябва да съм, и колко парчета имате? Или мога да дам различен парчета различни гледни точки. Моята кралица е на стойност 20 точки. Вашият пешка е на стойност един момент. Кой има повече точки общо? Или аз да помислите за неща като: който има по-добра позиция на борда? Чий ред е следващата, нещо, което мога да да се оцени по-точно коя от тези възможности е по-добре, без да изчерпателно за това, всеки ход, който може да дойде след това. Сега, за да направи тази работа, едно от нещата, това е ще се превърне в много важен за нас не е просто преместване права до определена дълбочина лимит, но е в състояние да каже, една от тези идеи, които съм имам е толкова лошо, че това е не заслужава да бъде разгледан всички възможни начини че нещата могат да отидат от лошо към по-лошо. За да направите това, ние ще добавим в Минимакс принцип, наречен ALPH-бета. И алфа-бета казва, ако имате лоша идея, не си губете времето да се опитва разберете как точно е зле. Така че тук е това, което ние ще направим. Отиваме да предприемат същите принципи, които сме имали преди, по същия Минимакс типа на търсене, само ние сме Ще следим, не само на действителните стойности, които имаме, но ще следите на най-добрите възможни стойност, която мога да получа, и възможно най-лошата изход мога да имам. И всяко време възможно най-лошата нещо се търси вероятно, Аз ще се откаже от тази част на дървото. И аз дори няма да се занимавам погледнете в него вече. Добре, така че представете си, че ние започваме с този точно същата игра дърво. И сега ние ще отидем отново, по целия път надолу да, че долния ляв ъгъл. И с това, че долния ляв ъгъл, ние Посетете и ние оценяваме този форум. Може би това е една от четирите четири тик-так-палеца борда, или може би това е една шахматна дъска. Но ние гледаме на него, и ние оценяваме той, и ние се стойност от осем. В този момент, ние знаем, че ние ще се получи най-малко осем точки от този отдолу решение. Няма значение какво другият две са, че седем и че две. Те могат да бъдат всякакви ценности те искаха да бъдат. Отиваме, за да получите най- малко осем точки. Добре, но можехме отидете напред и да се провери. Може би един от тях е по-добре от осем. Очакваме в седем. Това ли е по-добре от осем? Не, че не се променя Според нас изобщо. Очакваме в двете. Това ли е по-добре от осем? Не, че не се променя Според нас изобщо. Така че сега ние знаем, ние сме изчерпали всички възможности там. Ние няма да се получи нищо по-добро от осем. Отиваме да получите точно осем. И така, ние се промени, че възела и да речем, че сега е сигурност. Ще отидем до едно ниво над това. И сега ние знаем нещо около това ниво минимизиране. Ние знаем, че ние никога не започваш да се получи повече от осем точки, ако искаме да се понижат тази посока. Защото дори и тези, други два клона се окажат по- да бъде фантастично и си струва хиляди точки за всяка дейност, нашият опонент ще ни даде минимум, и да ни даде осем. Добре, добре, нека да видим. Ние ще продължим по този път. Ние слизат, че средната отляво. Ние погледне надолу и виждаме, че има девет. Ние знаем, че ние ще се получи най-малко девет точки от захождането че средната път. И в този момент, ние можем просто да направите пауза. И ние можем да кажем, вижте, аз знам в по-горното ниво, Отивам да се получи не повече от осем точки от захождането тази посока. Но ако аз отидох в центъра път вместо по левия път, Аз ще получи най-малко девет точки. Опонентът ми никога няма да позволете ми да сляза, че среден път. Те да избереш. И те ще се избере най- път на ляво към осем, отколкото през центъра в посока това, което е най-малко девет точки. Така че в този момент, ще спра. И аз ще кажа, знаеш ли какво? Не е нужно да търсите всеки по-надолу в тази посока. Защото аз никога няма да стигнем до там. Мога да прескачам, че един, и мога да прескочим, че шест, защото това никога няма да се случи. Така че аз ще сляза и ще разгледа следващата възможност. Аз отивам там и ви казвам, аз виждам две. Знам, че ако получа до тук, аз съм Ще получите най-малко две. ДОБРЕ. I продължавай. Виждам четири. Знам, че аз отивам да получите най-малко четири. Все още има много между четири и осем, все пак. Така че аз не спирай. Аз гледам надолу и виждам, че има един. Добре, аз знам, ако Аз отивам по този път, Отивам да бъде в състояние да изберете четиримата. Какво опонентът ми смяташ да правиш? Между нещо, което ми дава осем, нещо, което ми дава четири, и нещо, което ми дава най-малко девет, добре, че ще ми даде четиримата. И сега знам в много отгоре, аз отивам да бъде в състояние да получите най-малко четири точки от тази игра. Цялата идея на алфа-бета е да отреже части на дървото, така че че аз не гледам на тях вече. Но тя все още изглежда като аз съм бил погледнете в много от дървото. Нека да продължим надолу. Ще сляза следващия сега. Най-долу, да намеря една. Знам, че ще се получи най-малко един. I продължавайте да търсите. Да намеря три. Знам, че аз отивам да получите най-малко три. I продължавай. Да намеря пет. Знам, че ще се получи пет ако получа надолу в тази пътека. И аз също знам, след това че опонентът ми, ако аз изберете средата на трите големите решения, той ще ми даде нещо, което е пет или по-малко. ДОБРЕ. Мога да продължа да ходя там. Мога да погледна надолу и аз Може да се каже, какво ще за да получите, ако отида в центъра пътя? Отивам да се получи, добре, три там. Отивам да си взема нещо това е най-малко три. Все още има неща, между три и пет, така че продължавайте да търсите. О, девет, аз определено ще вземе, че в продължение на три. Отивам да получите най-малко девет ако сляза, че среден път. Сега противникът ми спира и казва: Виж, няма смисъл вече. Знам, че моят противника минимизиране, той е ще ми даде това, което е по-малко от или равно на пет, а не това, което е по-голям от или равен на девет. Спра. Аз не гледам повече в това. I продължавай. Аз гледам надолу по този въпрос. Надолу към дъното, да намеря шест. Знам, че аз отивам да получите най-малко шест. И това, което мога да направя? Мога да спра. Защото има възможност за избор между нещо, което е най-малко шест и нещо, което е по-малко от пет, той е ще ми даде нещо това е по-малко от пет. И сега, аз знам, че ще за да получите точно този избор. Отивам да се получи, че петте избор. Се върна на върха. Коя съм аз ще избирате между нещо това е по-голям от или равен на четири, или нещо, което е равно на пет? Отивам да взема нещо това е най-малко пет. Сляза последния път, всички път надолу към дъното. Има една. OK, поне аз ще получите по една точка. I продължавай. Two, о, това е по-добре от една. Отивам да се получи най-малко две. Да намеря три. Знам, че ще се получи три. И най-важното, че по-горе, опонентът ми се случва да ми даде нещо, което е по-малко от или равно на три. И сега мога да спра. Защото при избора между мен е в състояние да получи пет и опонентът ми че ми даде нещо по-малко от три, Аз винаги ще вземе, че пет. Така че аз не се оцени, че долната част на дървото на всички. Сега, това може да изглежда незначително. Но когато парченца аритметика, по-голям от по-малко от, може да изрежете цели части това експоненциално растяща дърво, което води до огромно сума от спестявания, спестявания които са достатъчно големи, че аз да започнете да играете конкурентно при по-сложни игри. Добре, ако погледнем на размера и сложността на различни игри, Тик-так-палеца беше нашият лесен пример. Имаме малък съвет, три от три. Ние получаваме най-много средно около четири различни избори като отидем в играта. Имаме някъде около 10 до пето възможни различни листа. И изграждането на тик-так-палеца плейър, добре, ние просто го е направил. Това е лесно. Ако отидем до нещо по- сложна, като Connect Four. Спомняте ли си тази игра, в която побъркване малките жетоните в? Това е шест от седем борда, Не, че много по-голям, все още има приблизително същото разклонение фактор, тъй като тик-так-палеца. Имам около четири възможности за избор къде мога да постави нещата вътре. Но сега, аз имам много повече води, от 10 до 21-ви власт. Това е нещо, което е лесно достатъчно, че ние го решим веднага. Шашки, още ли complex-- получи осем от осем борда. Ти си само на половината от тях по всяко време, все пак. Имаш разклоняване фактор, който е около 2.8. Е, ние имаме няколко движи можете да вземете. Имаш около 10 до 31 листа, по-големи, и по-големи, и по-големи пространства. Както аз трябва да се търси чрез тези по-големи пространства, това е, когато неща като алфа-бета и е в състояние да изрежете цели отрасли придобива първостепенно значение. Сега, пулове беше достатъчно лесни през 1992. Компютърна програма, наречена Chinook победи световните пуловете шампион, Марион Тинсли. И оттогава не човешкото майстор играч има бил в състояние да победи най-добрия изчислителни системи. Ако се вгледаме в нещо като шах, сега отново, имаме осем от осем борда. Но ние имаме много по-сложна парчета, много по-сложни движения. Имаме разклоняване фактор от около 35, 35 възможни ходове средно че мога да взема и състояние пространство, брой листа който е нараснал до 10 на 123-то силата, огромен брой възможности. Дори все още, модерни процесори са в състояние да направите това успешно. През 1995 г. и след това през 1997 г., с компютър програма, наречена Deep Blue, построен от IBM че се кандидатира с гигантски суперкомпютър победи сегашния световен шампион, Гари Каспаров. Това беше повратен момент. Днес, обаче, че същата обработка мощност седи на моя MacBook. Скорост на обработка запазва все по-бързо и по-бързо. Ние можем да се оцени по- дъски по-бързи и по-бързо. Но по-важното е, ние имаме по-добро функции за оценка и по-добра резитба методи. Така че ние можем да търсите в пространство по-сложно. Най-голямата от дъската игри, които ние можем да се сетиш, нещо като Go това е имам 19 от 19 за гладене, Сега изведнъж, ние сме минали точката където изчислителни системи могат да спечелят. Няма по изчислителна система там че може да победи професионален Go играчите. Най-добрите системи днес тя ранг за сортиране на добро ниво аматьор. Така че все още има доста малко навън там, че не можете да получите, за да все още. Добре, те традиционните настолни игри, тези видове системи, където ние изграждане на тази Минимакс, дали тя има алфа-бета или не, тези алгоритми работят защото има някои ограничения. Ние имаме добра информация за света. Знаем къде всички парчета са. Светът е статична. Никой не получава, за да преместите парчета около докато съм седи там мисля, като мой ред. Има един пространство за действие, който е дискретен. Мога да си сложа пешка тук, или мога да си сложа пешка тук. Не ми е позволено да си сложа пешка линия между двете квадратчета. И накрая, действията са детерминирана. Знам, че ако кажа, топа да рицар три, ми топа ще се окажете в рицар три, толкова дълго, колкото е валиден ход. Няма никаква несигурност относно това. Сега, като отида в по- различни видове игри, ние трябва да се прекъсне тези предположения. Какво става, ако отида в нещо като класически видео игри? Ето селекция от видео игри от Atari 2600. Какво трябва там? Имам Frogger, Space Invaders, Pitfall и Pac-Man. Какви видове среди имам тук сега? Кое от тези предположения трябва ли да се счупи? Е, това зависи от играта. Можех да играе шах на 2600, и че ще бъде точно както беше преди. За повечето от тези системи, има пълно знание за света. Има напълно детерминирани действия. Но обикновено, в света вече не е статична. Това означава, че докато аз съм седи там чака, нещо се движи. Призраците идват да ме вземе. Скорпионът е да ме преследваш отдолу. Нашественици Космическите са идва все по-близо. Колко добре можем да направим срещу тях? Преди няколко години, Google бе нарекъл проект DeepMind, където те обучават компютър програма, за да играете игри Atari 2600. И ако мислите, че това не е сериозно бизнеса, резултатите от тяхното изследване са публикувани в Nature, така че почти толкова добър публикация както можете да получите възможно. И тук е колко добре те изпълняват. Те имат алгоритъм, който седеше и гледах само на входовете на екрана. Тя има каквато не се изискват инструкции за правилата на играта. И това е трябвало да разбера, основава своята оценка, колко добре се справя. Това е система, която използва нещо наречено армировка учене. Тоест, тя погледна към своя резултат. И ако го имам добър резултат, той каза, Аз трябва да се помни тези неща. И аз трябва да направя тези отново. И ако го имам лоша оценка, той каза, Аз не трябва да правите тези неща отново. Това е изпълнението от тези обучени системи позволено да играе за Няколко часа по всяка игра, в сравнение с професионални геймъри. Така че за всички игри, които са от лявата страна на тази линия, това самостоятелно обучени компютърна програма надмина професионалните геймъри. И за всичко до Добре, професионалните геймъри все още са най-добрите. За нещо, което знаеше нищо за правилата, които знаеше нищо за структурата на игри, това е впечатляващо представяне. И това е, което ние сме в състояние да направим днес. OK, което казвате, но ако ние мисля за AI в игри, Обикновено мислим за неща, които можем да всъщност седнем и да играе срещу. Ако аз седна и да играя StarCraft, или играя Free сито, противника на компютъра е лице, контролиращо зергите, или контролиране на друга цивилизация. Как да направя тези играчи всъщност намери своите ходове? Е, тези игри са структурирани по същия начин, както и нашите настолни игри, тези игри, които ще колективно разпит четирима X игри, проучи, expand-- забравяме тези. Какво са те? Запознайте се, разшири и гасят, Мисля, че е последен. Но те са в основата за проучване и завладяване игри. Обикновено, противникът на компютъра там има ограничена информация. Те не знаят какво точно е става зад мъглата на войната. Те не се да видя какво имате в инвентара си. Има една среда, която е динамична. Всичко се променя през цялото време. Вие не получите да седи и да чакам да вземе си ход. Но повечето неща са все още дискретни. Аз трябва да си сложа на града тук. Или аз трябва да си сложа на града тук. И всичко е детерминирана. Когато казвам, преместете ми единица тук, ми блок движи тук, освен ако не е пречка изведнъж влезе в игра. Сега, това не е всичко компютър игри, които са там днес. Ако отида и аз играя първи тип човек игра, нещо като крадец или Fallout или Skyrim, или Halo, сега Имам компютърни опоненти че са там, че да има много по-различна ситуация. Те имат, отново, ограничена информация. Те само могат да видят някои полезрение. Околната среда е все още динамична. Нещата се променят през цялото време. Но сега имам много по- непрекъснато пространство за действие. I може да бъде само един наднича малко от прага. И някои игри, ми действия са стохастични. Съм се да се опита да скочи над тази стена, но аз имам шанс на проблемни. Тези видове игри стават все по-близки и по-близо до вида на контролери че ние изграждаме в роботиката. В роботиката, ние трябва да приемем, че имаме ограничено информация. Имаме сензори, които ни разкаже за света. Имаме постоянно променящата, динамична среда. Ние имаме един свят, в който пространството е непрекъснато, отколкото дискретно. И нашите действия, когато ние се опитваме тях, има вероятност за неизпълнение. И всъщност, модерна игра контролери за вашия опонент Halo, или за тези NPC-та в Skyrim, основно тичам малки роботика архитектури. Те усещат света. Те се изгради модел на света. Те се изчисли въз основа на набор от цели, които искат да се да се изпълни. Те планират действия, основаващи върху това, което знаят. И тези, които са точно същите видове на системи, които изграждаме в роботиката. Така че тези архитектури, за да доведа това отново заедно, доста често са еднакви. Така че нека да видим дали можем да видим, че. Нека се върнем към нашия Тик-так-палеца например. И аз ще задам няколко ми постдокторанти, за да дойдат и да ми помогне. Така Чен Минг и Алесандро, и Olivier, ако вие ще излезе. И аз отивам да се наложи Няколко доброволци OK, видях ръка на полето там в средата. Позволете ми да използвам един по-, някой нататък в гърба може би. Добре, ето там. Хайде нагоре. Всичко е наред. Така че нека да това покритие надолу. И ако вие ще дойдат полето обратно тук за мен, фантастично. Така че това е един робот, наречен Бакстър. И Baxter е робот, който е търговска платформа, предназначена от компания, наречена Премислете. И този робот е проектиран за дребното производство. Но днес ние ще да го използвате, за да играе Тик-так-палеца. Сега, този робот също е нещо, това е относително уникална. Защото, ако аз стояха навсякъде близо до стандартен фабрика автоматизация система, щях да бъда в много тежко опасност от нараняване. Baxter, обаче, е проектиран да бъде относително безопасно да си взаимодействат с. И така, аз може да натиснете върху този робот. И можете да видите, че е малко битов гъвкава тъй като се движи наоколо. И мога да го препозиционира където бих искал да отида. Сега в нормална роботизирана система, ние ще имаме набор от стави тук това ще бъде директно отговаряне на команди за позицията. И те няма непременно да се грижим ако те се движеха през открито, или ако те се движеха чрез моя гръден кош. ДОБРЕ. И обикновено, ако бяхте тук с промишлена система, вие ще отида никъде в близост до него. Няма да има жълта безопасността лента на всички около него. Тази система има малко по-различен дизайн да бъде по-приятелски и по-лесно за хората да взаимодействат с, с това, че във всяка става, има една пружина. И вместо контролиране точна позиция, ние контрол на определен размер на въртящ момент, определено количество сила, че ние бихме искали да бъде на пролетта. Добре, така че ме пусна вземат нашите доброволци тук. Здравей как се казваш? АУДИТОРИЯ: Louis. SPEAKER: Louis. Приятно ми е да те видя. И? АУДИТОРИЯ: Дейвид. SPEAKER: Дейвид. Приятно ми е. Ако вие ще изчакат точно тук, за секунда, Отивам да ви дам шанс да направите това. Така че този робот, ако излезе и ако натиснете леко върху него, започваш да се види, че тя се движи малко. И ако го вземете полето тук на китката просто по-горе, където тези бутони са, тя Изглежда, че трябва да вземете на бутоните, но вземете точно над него Вместо това ще да бъде в състояние да го манипулират много внимателно през пространството. Louis, вие искате да го пробвам? Така че го дам само малко бутнете да се започне с. И след това, ако поставите пръстите си точно там и се задържи на него, защото тя ще се премести за вас след това. Добре, вие искате да го пробвам? Хайде нагоре. Така го дам просто нежно бутнете там, за да започнете. Можете да усетите какво е искал. И тогава, ако го вземете точно там, вие ще бъдете в състояние да маневрира около. ДОБРЕ. Така обикновено, този вид робот би да се използва за производство на малък мащаб. И аз отивам да се премести тази ръка просто надолу от пътя малко тук. Но днес, отиваме за употреба същата система тик-так-палеца игра въз основа на Minimax че изградени по-рано. ДОБРЕ? Така че, момчета са всеки Ще играете игра. Louis, ти започваш да бъде на първо място. Нека само да побере до тук за секунда. Отивам да стоиш прав тук, точно така, всеки може да те види. Възможно ли е, момчета, създадени тук? ROBOT: Добре дошли. Да играем тик-так-палеца. Не хванете вашия знак, преди да Аз казвам, че е твой ред. I започне играта. Мой ред е. SPEAKER: Сега, ако бихте могли да вземе един от си парчета и си отиват напред и да го пускат. ROBOT: Той е ваш ред. [Смях] Мой ред е. [Смях] [Смях] Ваш ред е. SPEAKER: Човешката раса е Разчитам на вас тук, Louis. ROBOT: Това е моят ред. SPEAKER: Така Baxter успешно блокиран тук. ROBOT: Той е ваш ред. Мой ред е. Ваш ред е. Мой ред е. SPEAKER: И ние ще ви позволи Baxter завърши на последния си ход тук. [Смях] ROBOT: Това е една вратовръзка. Аз ще спечели следващия път. [Смях] SPEAKER: Добре, благодаря много, Louis. Благодаря. Можете да отидете по този начин. ROBOT: I започне играта. SPEAKER: Така че нека ти обясня да ви една по-малко битов преди да стигнем нашата реванш тук. Какво точно се случва? Така че роботът има горна камера тук. И това е гледаше надолу към дъската. И това е да се прецени дали тя има червен O или синя и бяло X. Като тези се пуснат на борда, това е в основата на един и същи вход че ние ще се чете в от нашата структура на данните от нашия екран. Това е движение еднакви Минимакс алгоритъм, за да бъде в състояние да намери къде да поставите добър знак. И тогава ние даваме команда за където ние бихме искали символично да бъде поставен. Ръката се движи навън. Тя се използва вакуумна хващач да прилага някои изсмукване на тази дървена парче, го вземете, да го преместите в правото място, а след това съобщение засмукването и да го пуснете. Добре, отиваме да му се даде още един удар с малко по-умен играч тук. Готов ли си? Добре, ако искате стои точно до тук и да даде A-- окаже този начин така че можете да видите всички. И тогава [недоловим]. ROBOT: Това е моят ред. SPEAKER: Baxter ще започне. Ваш ред е. Мой ред е. Ваш ред е. Мой ред е. [Смях] SPEAKER: [шепне] Just нека вървим напред и да спечелим. ROBOT: Той е ваш ред. SPEAKER: Това е добре. ROBOT: Това е моят ред. [Смях] Аз печеля. [Смях] I започне играта. SPEAKER: Добре, благодаря ви много. Добре, аз мисля, че имаме време за още една отлична тик-так-палеца плейър, някой, който може да постави това нещо да съвпадат, кой знае какво правят. [Смях] Кой ще бъде наш шампион тук? Добре, моите приятели можете доброволно. Това е достатъчно добър за мен. Кажи ми името си отново. АУДИТОРИЯ: Тамир. SPEAKER: Тамир, е хубаво да те видя. Добре, отново, ние ще ви постави чак до тук, така че всеки да може да те види. Вие сте наш представител в този мач сега. Baxter е една и о и о. Или Съжалявам, един О, и една. И това е до вас тук. Baxter ще получите да се движат на първо място, все пак. Така. ROBOT: Това е моят ред. [Смях] Ваш ред е. Мой ред е. Ваш ред е. Мой ред е. Ваш ред е. [Смях] ROBOT: Това е моят ред. SPEAKER: Това е много по-трудно, когато стоите тук, приятели. [Смях] ROBOT: Вие хора са толкова лесно да се победи. [Смях и аплодисменти] SPEAKER: Благодаря много. ROBOT: спечеля. I започне играта. Лектор: Добре де, благодарение много много да Olivier и да Alessandro, и да Чен Минг. [Аплодисменти] Искам да направя един последен въпрос. Така Baxter в самото свършва дотук, излъгани. И това беше неочаквано. Един от фантастичното неща за AI е, че ние върши работата в AI, така че ние можем да изградим наистина интересно и интелигентно устройства. Но ние също правим работа в AI защото тя ни казва нещо за това как хората са интелигентни. Един от най-любимите казуси от моята лаборатория е гледаш какво се случва, когато машини неочаквано мамят. Направихме това първоначално не с Baxter играе Тик-так-палеца, но с по-малък робот на име Nao, който играе рок-ножица-хартия. И понякога, след като играе много и много от скучни рок-ножица-хартия игри, роботът ще хвърля един жест, загубят, а след това изведнъж се промени си жест и да кажа, аз спечеля. [Смях] Сега, понякога ние бихме също имат робота, Просто като контрола, хвърли един жест, спечели, и да промени своя жест да губи, хвърли на мача мамят, за да загубим. И това не е толкова убедителна. Роботът, който мами За да спечелите хората отговори, както ако е към тях се, като го активно търси тяхното унищожаване. [Смях] Тя се превръща в средство. Това е като човек. Той има убеждения и намерения. И това не е добро намерение. И на робота, който хвърля Играта е просто неправилно функциониране. Това е просто едно повредено устройство. Нека ви покажа няколко примера на тази от някои от нашите участници. Така че тук е измама, за да загубим. [Възпроизвеждане на видео] - [Недоловим] спечелим. Хайде да играем. -Чакаме какво? - [Недоловим] спечелим. Хайде да играем. [Недоловим] спечелим. Хайде да играем. SPEAKER: И тук е измама, за да спечели. -Да, Аз спечеля. Хайде да играем. -Ти Не може да направи това. [Смях] -Да, Аз спечеля. -Ти Излъгани. Можете изневери сега. -Да, Аз спечеля. -Hey, Можете измамник. Вие мамите, супер измама. [END PLAYBACK] SPEAKER: Това различно бързо реакции променим нашето възприятие на устройството. Означава ли това, че ние умишлено построи машини, които изневеряват, защото това е най-инженеринг, че можем да направим? Не, но тя ни казва нещо наистина интересно за хората. Това нещо, че вие ​​и мами открадне победата си, това е нещо, което е жив, това е анимирате, това е да те хванат. Той има психическо състояние. Той има убеждения. Той има намерение. Това нещо, че ръцете на игра за вас, че не е така. Това е просто неправилно функциониране. Това в много отношения е защо е лесно да се хвърлят на срещата с децата. Но ако се опитате да ги мамят и нещо като претендира за победа когато, знаете ли, просто да се съкрати игра, ще те хване веднага. Тези видове ефекти, които ние виждаме, излизащ от AI, те ни научи много за себе си. Добре, че е всичко за днес. Благодаря много на Давид и производство екипа на Harvard за да слиза. [Аплодисменти] Ще се видим за една викторина, и след това за една последна лекция. Приятен ден. [Аплодисменти] [За възпроизвеждане на музика] DAVID J Malan: Е, може би имаме нужда да се въведе някакъв вид криптиране, нали? Защото тогава заглавията на тези HTTP заявки ще бъдат бъркани, така че всеки опитвайки се да помиришат трафика всъщност няма да бъде в състояние да ги види. И така, какво е решението на този проблем? Е, ние трябва да се въведе реално криптиране във формулата, така че, когато това лице е предаване на данни от точка А до Б, можем шифрована send-- [Смях] Информацията по начин, че противникът не може в действителност, виж това.