>> [Musikwiedergabe]
>> SPRECHER: Willkommen zurück, jeder.
Dies ist CS50.
Und heute haben wir eine Menge von interessante Dinge zu erzählen.
Zunächst jedoch muss ich daran erinnern, Sie ein paar administrative Dinge.
Diese Woche ist ein Quiz, Mittwoch oder für die Yale Schnitt
dienstags und donnerstags, am Donnerstag.
Es gibt Quiz Bewertungen heute Abend an der Yale, von 5.30 bis 07.00 Uhr.
In Harvard, nahmen sie eine gestern.
Und jeder kann diese online zu sehen.
>> Auch in dieser Woche oder Anfang nächster Woche, Wir haben unsere letzte CS50 Vortrag.
[Seufzt] Ich weiß.
Es kam so schnell.
Yale Studenten einen Live haben Vorlesung hier in der juristischen Fakultät
Auditorium am Freitag.
Es gibt Kuchen.
Harvard-Studenten wird das haben letzte Vorlesung in Sanders am Montag.
Es wird auch Kuchen.
>> Auch diese Woche am Freitag, für diejenigen, von Ihnen, die nach New Haven zu kommen,
wir haben den CS50 Expo.
Wir haben mehr als 30 registriert verschiedenen Gruppen
um Ihnen alles zeigen von autonomen Segelboote,
auf Systeme, die erkennen, digitalen Porträts, auf den Computer
Musik und Computer-erzeugten Musik.
Also bitte besuchen Sie uns.
Ich denke, es wird eine tolle Zeit.
>> Heute jedoch, zu bekommen, die wir weiter reden AI,
über künstliche Intelligenz.
Und eines der Dinge, die wir werden heute erhalten
ist die Idee, wie AI verwenden, um Probleme zu lösen.
Nun, wie immer, lass uns anfangen mit etwas einfach.
Und wir werden beginnen mit einer einfachen Idee.
Und das ist mit Suche.
>> So vorstellen, für eine Minute, dass ich eine Aufgabe, die ich brauche, um durchzuführen.
Und ich möchte, um diese Aufgabe haben von einigen Software-Agent automatisiert.
Stellen Sie sich vor, dass ich versuche, um einen Satz zu buchen der Flüge von, sagen wir, Boston
nach San Francisco.
Ich konnte durch zu gehen und ich verwenden könnte Eines der wunderbaren Online-Suche
Werkzeuge, die gehen zu tun, grundsätzlich das gleiche Verfahren, das wir
werde bis heute gehen.
Aber wenn Sie nicht haben, dass Werkzeug, was würden Sie tun?
>> Nun, Sie aussehen könnte und sehen und zu sagen, ich bin in Boston.
Welche Flüge stehen mir zur Verfügung?
Nun, vielleicht habe ich drei haben mögliche Flüge von Boston
das wird die Zeit passen wenn ich brauche, um zu verlassen.
Ich konnte nach Chicago zu fliegen.
Oder ich könnte nach Miami zu fliegen.
Oder ich könnte nach New York zu fliegen.
Ich könnte dann von jedem sehen eine jener Zielstädte
und über das, was Orten denken Ich nur erreichen konnte
von jedem dieser einzelnen Städten.
>> Also vielleicht aus Chicago, die ich bekommen kann ein Direktflug nach San Francisco.
Das ist ausgezeichnet.
Oder ich könnte einen Flug nach Denver zu bekommen.
Nun, vielleicht ist das Flug nach San Francisco ist die perfekte Lösung für mich,
aber vielleicht auch nicht.
Vielleicht bin ich auf der Suche nach etwas, das ist ein bisschen billiger
oder ein bisschen besser für meine Zeitplan.
Und so konnte ich für das, was andere suchen Möglichkeiten könnte da draußen.
So konnte ich in Denver suchen.
Und aus Denver, na ja, vielleicht Ich kann einen Flug nach Austin zu bekommen.
Und aus Austin, vielleicht kann ich einen bekommen Flug nach Phoenix und von Phoenix
nach San Francisco.
Nun, ich bin noch nicht fertig.
Denn vielleicht gibt es eine Direktflug von New York
nach San Francisco, das ist perfekt für mich.
Oder vielleicht gibt es einen Flug von Miami durch Denver, die viel billiger ist.
So habe ich noch zu gehen.
Und ich habe immer noch an alle, die aussehen Städte, die ich noch nicht untersucht.
Ich muss abschließend überprüfen Sie alle die Möglichkeiten, die ich haben könnte.
>> Also aus New York, vielleicht kann ich einen bekommen Flug nach Nashville und von Nashville
nach Austin.
Und dann weiß ich, wo ich bin.
Und dann habe ich von Austin weiß, ich kann Fliegen nach Phoenix und von Phoenix
nach San Francisco.
Wenn ich fliegen zuerst nach Miami, obwohl, vielleicht kann ich einen Flug von Miami zu bekommen
nach Nashville, oder von Miami nach Austin.
>> Und jetzt habe ich alles versucht der Möglichkeiten.
Ich habe mir diese Grafik gebaut, zeigt mir alle möglichen Routen
dass ich vielleicht in der Lage, zu nehmen.
Wenn wir stellen diese Arten von Problemen,
wir werden nicht zu vertreten sie explizit als dieser graphischen
denn das Graphen repräsentieren nicht die Geschichte, wo wir gegangen sind.
Zu wissen, dass ich aus flog Phoenix nach San Francisco
hat mir nicht sagen, ob ich über kam Nashville, oder über Denver, oder über Miami.
>> Also, was ich tun werde, ist stattdessen Ich werde das gleiche Problem zu nehmen,
und ich werde es als Baum darstellen.
Und an der Wurzel des Baums, bei der top, werde ich den Ort, den ich begonnen setzen,
Boston.
Und von Boston, ich werde schauen alle möglichen Orte
dass ich zu reisen.
Nun, in diesem Fall hatte ich drei, Chicago, New York und Miami.
Und dann werde ich jede erkunden diese Kinder im Baum.
>> Von Chicago, sah ich, dass ich zwei Flüge.
Ich konnte direkt zu fliegen San Francisco oder nach Denver.
Jetzt San Francisco, das ist mein Ziel.
Das ist mein Ziel.
Das wird ein Blatt dieses Baumes sein.
Das heißt, ich werde nie gehen irgendwo nach San Francisco.
Von Denver, obwohl, Ich kann von Denver zu fliegen
nach Austin, von Austin nach Phoenix, und von Phoenix nach San Francisco.
Und jetzt wieder, habe ich ein Blatt erreicht.
>> Ich konnte dann gehen Sie zurück zu der nächsten Stadt, die ich noch nicht vollständig erforscht.
Das wäre New York, zu gehen wieder auf der Spitze von meinem Baum,
komm herab nach New York.
Von New York, ich kann fliegen Nashville, von Nashville nach Austin,
von Austin nach Phoenix, und von Phoenix nach San Francisco.
Und schließlich, eine Stadt, die ich wurden nicht betrachtet noch in Miami.
>> Nun, von Miami Ich sagte, ich hatte zwei Möglichkeiten, Nashville und Austin.
Wenn ich fliegen nach Nashville, gut, dann fliege ich aus Nashville, Austin, nach Phoenix,
nach San Francisco.
Wenn ich fliegen nach Austin, fliege ich Austin, nach Phoenix, nach San Francisco.
Und jetzt habe ich einen Baum.
Es ist eine komplette Baum.
Es ist alles über die Möglichkeiten und alle Pfade, die ich nehmen könnte.
Das heißt, wenn ich beginnen bei der Wurzel des Baumes an der Spitze
und ich gehen zu einem der verlässt, es sagt mir, nicht nur
wo ich zu gehen am Ende, San Francisco,
aber es sagt mir, die Route, Ich muss nehmen, um dorthin zu gelangen.
>> Nun, das ist die eine von ihnen die beste?
Nun, nichts davon Problem mir sagt, noch
die von denen, die beste Lösung ist.
Vielleicht habe ich am meisten interessieren wie viel Zeit ich bin in der Luft,
oder die Distanz, die ich fliege.
In diesem Fall Chicago nach San Francisco könnte die kürzeste Zahl sein
von Meilen in der Luft.
>> Vielleicht habe ich kümmern uns um den Kosten.
Und wir alle wissen Direktflüge sind in der Regel teurer.
Vielleicht, wenn ich diese nehmen Art der Rückroute
durch Miami, Nashville, Austin, Phoenix, vielleicht dann
Ich einen niedrigeren Preis erhalten.
Aber ich konnte auf jede Optimierung Kriterien, die mich interessiert.
Wer ist der beste in bekam Flug Wi-Fi oder die
Flughäfen haben das beste Essen zur Verfügung.
Und jeder von denen könnte geben Sie mir eine andere Lösung
dass ich als die beste.
>> Diese Arten von Problemen, wohin wir gehen
zu bauen, diese Baum Möglichkeiten, und dann
Blick auf jede dieser einzelne Pfade, und untersuchen
Welche dieser erfüllt ein Kriterium für uns,
wir werden rufen diese Suchprobleme.
Und wir haben viele Algorithmen, von denen einige
wir bereits gesehen haben, zu gehen und erkunden Sie die Bäume.
Wir könnten es in der Art und Weise zu tun, dass ich gerade tat, eine Tiefensuche,
going down so weit, wie wir können, bis wir schlug ein Blatt, und dann wieder kommen,
und gehen gleich wieder nach unten.
Oder wir könnten tun, was genannt Breitensuche.
Wir konnten alles zu erweitern an der Spitze, und dann
alles eine Zeile darunter das, und dann
alles, was man darunter, dass Zeilen.
Diese Suchbäume sind grundlegend für AI.
Aber sie wissen nicht so recht, es richtig die ganze Zeit.
In der Tat, in vielen Fällen dass wir wirklich über,
wir wollen, um einen Baum zu bauen, aber wir haben nicht wirklich
zu erhalten, um alle Entscheidungen zu treffen.
>> Das sind Situationen, genannt kontradiktorischen suchen, auch bekannt,
wie, wie man Spiele spielen zu schreiben Systeme und dafür bezahlt werden.
Aber das sind die Arten von Systemen, wo ich
möglicherweise erhalten zu wählen, wenn ich aus gehen Boston, die Stadt, die ich gehen Sie zum nächsten.
Aber danach, vielleicht jemand anderes bekommen die Entscheidung darüber, wo ich fliegen zu machen.
Also, diese zu bauen Arten Strukturen sind wir
zu haben, um eine leicht zu nehmen anderen Ansatz, um es.
Wir werden nicht in der Lage zu sein, nur durch den Baum zu suchen
mehr, weil wir nicht die eine, die in der Kontrolle
jedes dieser Entscheidungspunkte.
>> So stellen wir uns ein einfaches Spiel wie tic-tac-toe.
Ich könnte mit einem Start komplett leeren Brett.
Und in tic-tac-toe, X erhält zuerst spielen.
Und so konnte ich über all das denken, möglichen Züge, die X machen könnte.
Und wenn ich das eine Spiel das X, das ist toll.
Ich habe neun möglichen bewegt, dass ich machen kann.
Ich konnte ein X in einem setzen jener neun Positionen.
>> Und dann von jedem von diesen, I konnte sich vorstellen, was als nächstes passiert.
Nun, in diesem Fall, die andere Spieler bekommen würde, eine Wendung nehmen.
O bekommen würde, eine Wendung nehmen.
Und aus jeder dieser gibt würde acht verschiedenen Orten sein
dass O konnten ihre Marker zu platzieren.
>> Nehmen wir an, ich beschlossen, dass ich werde ein X in den Mittelpunkt zu stellen.
Das scheint immer wie eine gute Eröffnungszug.
Ich könnte unter diesem Blick, der acht möglichen Bewegungen, die O macht.
Nun, wenn ich spiele X, das ist wundervoll.
Ich bekomme zu wählen, welche I gehen Sie zu, der einen in der Mitte.
Aber jetzt O bekommt, um zu wählen.
Und ich habe keine Kontrolle über diese Entscheidung.
>> Aber aus jedem der beteiligten möglich Mandate,
es gibt dann eine andere Reihe von Möglichkeiten.
Wenn es um sein kommt Meine wieder zu aktivieren, würde ich
erhalten zu wählen, und sagen, na ja, wenn O in der sich bewegt, auch,
der mittlere Fleck auf der linken Seite, dann Ich habe eine Reihe von Möglichkeiten,
wo ich meinen nächsten Schritt zu nehmen.
Von denen, konnte ich alle betrachten die Möglichkeiten sind unter ihnen.
Und dann O bekommen würde unter denjenigen auszuwählen.
>> Und ich konnte zu halten bauen diese Baum aus, bis ich zu dem Punkt,
in denen entweder jemand gewinnt den game--, das ist
habe, um als Blatt werden node-- oder das Board vollständig gefüllt
und niemand hat gewonnen.
Und das auch gehen, um ein Blattknoten ist.
Das wird ein Unentschieden sein.
>> Aber die heikle Sache mit diesem ist, wenn dies nur eine regelmäßige Suche
Problem, würde ich in der Lage zu sein, sagen wir auch, X soll hier.
Und O sollte Weg dorthin gehen.
Und dann X sollte hier gehen.
Und dann sollte O Weg dorthin gehen.
Und dann kann X drei erhalten in einer Reihe, und ich gewinne.
Und das Spiel wäre vorbei in fünf Züge, drei für mich,
zwei für meinen Gegner.
Aber ich weiß nicht immer, um, dass zu wählen.
>> Anstatt also, was wir tun zu haben,
wird wir gehen zu müssen, um eine neue Strategie haben.
Und die Strategie, Spielerei Algorithmen verwenden oft
ist, was heißt Minimax.
Die zentrale Idee Minimax ist, dass wir
gehen, um die Bewegung, die gibt abholen unser Gegner die denkbar schlechteste Satz
der bewegt, dass sie machen können.
Es macht mir nichts nützen einen Zug, wo wählen
Vielleicht kann ich nach gewinnen dass, weil mein Gegner nicht
werde mir diese Chance geben.
Sie werden einige wählen schrecklichen Ergebnis für mich.
Also werde ich das machen zu bewegen, dass mein Gegner zwingt
etwas Besseres für mich tun.
Gut.
Mal sehen, wie das heraus spielt.
Also hier ist unser Algorithmus in Pseudocode.
Wir werden zu generieren das ganze Spiel Baum.
Wir werden bauen die gesamte Struktur.
Und dann werden wir durch zu gehen.
Und am unteren Ende an jedem der Endknoten, an jedem der Blätter,
wir beurteilen, wie wertvoll ist, dass zu mir?
Und wir sind auf den Wert Dinge, dass sind gut für mich als positiv.
Dinge, die nicht gut für mich sind weniger positiv oder Null ist,
oder sogar negativ.
>> So in tic-tac-toe, vielleicht ein Sieg für mich gut ist.
Das ist eine eins.
Und eine Krawatte ist Null.
Und etwas, das ist ein Verlust für mir, vielleicht ist das eine negative.
Alles was zählt ist, dass die bessere es für mich ist, desto höher die Punktzahl
er empfängt.
Von diesen Möglichkeiten bei der unten, dann werden wir nach oben zu filtern.
Und wenn es meine Chance zu wählen, unter einer Reihe von Alternativen,
Ich werde die, die es wählen erhielt die höchste Punktzahl.
>> Und wann immer es ist mein Gegner drehen, um zu wählen,
Ich gehe davon aus, dass sie zu gehen wählen Sie das mit der niedrigsten Punktzahl.
Und wenn ich das den ganzen Weg bis an die Spitze des Baumes,
Ich werde einen Weg, gibt gewählt haben mich das beste Ergebnis, das ich bekommen kann,
davon aus, dass mein Gegner macht alles richtig.
>> Alles klar, also mal sehen, dies in Aktion zu ersten.
Und dann werden wir tatsächlich Blick auf den Code für sie.
So vorstellen, ich habe diesen großen Baum.
Und jetzt werde ich nicht spielen tic-tac-toe.
Ich wollte Ihnen etwas ein wenig reicher.
Also habe ich etwas Spiel, in dem stand es gibt viele verschiedene Partituren
dass ich am Ende zu haben.
Und so habe ich bauen diese komplette Baum.
Und ich bekomme den ersten zu bewegen.
Ich bin an der Wurzel des Baumes.
>> Und ich bekomme zu wählen dass-- so bekomme ich um über diesen ersten Knoten zu maximieren.
Und dann mein Gegner bekommt, um zu gehen.
Und dann bekomme ich noch einmal zu gehen.
So nach unten am Boden, ich habe eine Reihe von Möglichkeiten, die ich von zu wählen,
verschiedene Endzustände des Spiels.
Wenn ich unten bin, dass Ganz links Ecke,
und ich sehe, dass ich eine andere Wahl zwischen einer acht, ein Sieben und eine zwei,
gut, ich bin derjenige, der zu wählen, erhält.
Also, ich werde wählen am besten einer von denen.
Ich werde die acht zu wählen.
>> So weiß ich, dass wenn ich jemals runter zu diesem Punkt,
Ich werde in der Lage, dass acht Punkte bekommen.
Wenn ich am Ende auf den nächsten Punkt über, den nächsten Knoten über,
neun, eine Eins oder eine Sechs, gut, ich bin gehen, um die besten von denen wählen.
Ich werde die neun zu wählen.
Wenn ich die Wahl zwischen zwei, vier und eins,
Ich werde die vier, die höchste zu wählen.
>> Nun, wenn ich mir die Ebene oben, dass mein Gegner
ist die bekommt man diese Wahl zu treffen.
Also mein Gegner bekommt, wählen, will ich ihm geben
die Sache, die gehen ihm acht Punkte zu bekommen,
oder muss ich ihm die Sache, die ist zu geben geht ihm neun Punkte zu geben,
oder die Sache, die geht ihm vier Punkte zu geben?
Und mein Gegner, wobei rational, wird
um die minimale Anzahl an zu wählen, wird den vier zu wählen.
>> Und ich kann dies tun durch den gesamten Baum.
Ich kann auf das gehen mittleren Satz von drei.
Und ich kann wählen zwischen einem, drei und fünf.
Und ich bekomme, um zu wählen.
So wähle ich ein fünf.
Ich kann drei, neun oder zwei zu wählen.
Ich bekomme zu wählen, so wähle ich die neun.
Sechs, fünf, oder zwei, ich wähle.
Ich bekomme, um die sechs zu wählen.
Niveau über, dass, wer bekommt zu wählen?
Wer bekommt zu wählen?
Der andere Mann, mein Gegner.
So dass sie wählen, fünf, neun oder sechs, welche?
>> Publikum: Die fünf.
>> SPRECHER: Sie wählen die fünf.
Sie bekommen, um die minimale Auswahl.
Und dann der letzte, Wählen Sie ein, zwei, oder drei.
Ich bekomme zu wählen, so dass ich drei zu wählen.
Neun, sieben, oder zwei, wähle ich neun.
Und 11, sechs oder vier, wähle ich 11.
Mein Gegner wählt dann drei, neun oder 11, wählt das Minimum.
Er gibt mir eine Drei.
Und dann schließlich an der Spitze der Baum, bekomme ich wieder wählen.
Und ich bekomme die Wahl zwischen ein Vier, ein Fünf oder eine drei.
Also nehme ich die fünf.
>> Wenn ich habe, alles zu kontrollieren, würde ich nehmen Sie den Weg, der zu den 11 geführt.
Aber ich nicht bekommen, um diese Wahl zu treffen.
Wenn ich auf diesem Weg.
Mein Gegner wird mir in Kraft die Wahl, die zu einem von drei führt.
So ist die beste, die ich tun kann, ist , dass die mittlere Ast zu nehmen,
diese Wahl, die schließlich ist wird mich auf fünf Punkte führen.
Das ist, was Minimax tut.
>> Gut.
Werfen wir einen Blick auf, dass.
Also hier in der CS50 IDE ist ein Programm,
setzt Minimax zu Tic-Tac-Toe zu spielen.
Wir werden bauen up abweichen.
Wir werden zwei opponent-- haben oder zwei Spieler, unsere Computer
Player und einem menschlichen Spieler.
Spieler Nummer eins spielen wird die O. Das wird die Maschine Spieler sein.
Sie lernen Sekunde.
Und der andere Spieler, unsere menschlichen Spieler wird X.
>> Und mein Leben ein zu machen wenig einfach, ich werde
, dass die Spieler negativ zu kennzeichnen.
Also ich kann nur multiplizieren von negativen zu tauschen
zwischen einem Spieler und dem anderen.
Alles klar, also nehmen wir mal einen Blick auf was wir eigentlich tun.
Wir werden in unserem Vorstand zu definieren.
Es wird sein, gut, wir gehen , damit sie drei mal drei ist,
oder wir können sogar spielen Fünf von fünf oder sieben
sieben tic-tac-toe Wenn Sie möchten dergleichen, basierend auf einigen Abmessung D.
>> Und wir werden ein paar haben der Hilfsfunktionen
dass du Dinge wie initialisieren das screen-- oder sorry,
initialisieren unserer Variablen, deaktivieren Sie das Bildschirm, ziehen Sie die Platine auf dem Bildschirm,
eine, die ein Brett überprüft ob oder nicht zu sehen
es ist ein Gewinner, eine, analysiert über die Befehlszeile,
nur, um zu helfen, eine, die in liest Eingang und eine Funktion namens Minimax.
Und das ist die eine wir werden die meisten interessieren.
Aber lassen Sie uns zunächst einen Blick auf den Main.
>> Was machen wir?
Nun, wir gehen, um analysieren unsere Kommandozeile,
gerade lesen und sehen, was Dimension Bord wir gerne hätten.
Wir werden unser Board initialisieren.
Und dann werden wir einen geben Große Wild Schleife wiederholt
akzeptieren, bewegt sich, bis das Spiel gewonnen, oder es gibt keine Züge verlassen.
Jedesmal, wenn wir durchmachen Schleife, werden wir den Bildschirm zu löschen.
Wir werden das Brett auf dem Bildschirm zu zeichnen.
Und wir sind bewusst Art abstrahiert diese weg wie Unterprogramme,
so dass wir nicht zu viel Sorgen über die Einzelheiten, wie sie geschehen.
>> Hier finden Sie den Code haben, im Laufe des Tages.
Und wenn Sie wollen, um durch zu suchen und finden Sie heraus, können Sie sie alle zu sehen.
Aber wir werden ein Brett auf dem Bildschirm zu zeichnen.
Und dann werden wir prüfen und siehe, wir haben einen Gewinner?
Hat jemand gewann das Spiel?
Wenn sie, wir drucken aus einem Sieg Nachricht.
Und wir werden das Spiel zu beenden.
>> Wir werden auch prüfen und sehen, ob es ein Unentschieden.
Es wird leicht zu sehen, wenn es einen Gleichstand zu sein.
Es bedeutet, dass alle Räume gefüllt sind, aber es ist ein Gewinner noch nicht.
Wir können eine Krawatte zu erklären und durchgeführt werden.
Dann wird der reale meat-- wenn es ist eine Maschine-Spieler,
das werden wir erlauben Maschine-Player zur Suche
durch Verwendung dieses Minimax-Algorithmus, zu den besten Zug, dass sie zu finden.
Und dann werden wir diesen Zug aufgestellt.
>> Andernfalls, wenn es ist ein menschlicher Spieler, wir werden einige Eingaben aus dem menschlichen lesen.
Und dann, ob es die Menschen Spieler oder die Maschine-Spieler,
wir werden ein paar wenig tun Bits der Fehlerprüfung,
sicherzustellen, dass es innerhalb der Grenzen bleibt, der tatsächlichen Abmessungen des Boards
dass wir, stellen Sie sicher, dass der Raum leer ist,
dass niemand die Put a Stück schon drin.
Und dann haben wir nur gestellt werden ein Stück auf dem Brett,
ändern Sie den Player an die nächste Schicht, und zu erhöhen, wie viele Züge geschehen.
>> Das ist die Hauptschleife unsere Tic-Tac-Toe-Spiel.
Minimax ist also genau Der Algorithmus, den wir vorher.
Die einzige Anpassung, wir damit gemacht haben wir
können höhere spielen Dimensionsplatten ist wir haben
Diese zusätzlichen Parameter namens Tiefe gehalten.
Und Tiefe sagt nur, wenn ich mich Suche nach unten durch diesen Baum
und ich bekomme so weit nach unten jenseits einer gewissen Ebene Tiefe
dass ich einfach nicht wollen, weiter zu gehen,
Ich werde aufhören, nur das Brett zu bewerten an diesem Punkt.
Ich werde zu überprüfen und sehen, ob es einen Sieger.
Wenn es einen Gewinner, ich sie zurück.
Ansonsten werde ich durch eine Schleife zu gehen.
Und ich werde sagen, für alle die möglichen Standorte
dass ich nur konnte nehmen, wie meinem Umzug, ich werde
eine hypothetische Bord Build, umfasst meinem Umzug auf dieser Platine,
und ruft dann rekursiv Minimax.
>> Wenn es meinem Umzug, bekomme ich zu dem zu finden eine, die die größte Punktzahl bekommen hat.
Wenn er unterwegs meines Gegners ist, finden wir, die eine, die die Mindestpunktzahl bekommen hat.
Und alles andere ist nur Aufzeichnungen.
Alles klar, also mal sehen, diesen Lauf.
Eigentlich können wir vielleicht bekommen ein paar Freiwillige
zu kommen und zu spielen tic-tac-toe.
[Unverständlich] ein, und man mehr, zwei, recht.
Komm auf.
>> Also lassen Sie uns weitermachen und starten Sie diese vollständig.
So, hallo.
>> ZIELGRUPPE: Hallo.
>> SPRECHER: Wie ist dein Name?
>> ZIELGRUPPE: Gorav.
SPRECHER: Gorav.
>> Publikum: Ich bin Layla.
>> SPRECHER: Und Layla und Layla, sorry.
Komm auf.
Gorav, wir gehen zu müssen Sie zuerst gehen.
Und ich werde Sie bitten, eine nicht schrecklich gute tic-tac-toe-Player.
OK, so dass der ganze Druck ist weg auf Sie.
Lassen Sie uns sehen, wenn auch, dass unsere Maschine Spieler kann tatsächlich etwas Smart zu tun.
Also zögern Sie nicht.
Sie gehen zu geben, in dem Koordinaten Sie möchten Ihre X in.
A0, OK, und die Maschine ist gegangen sofort und legte seine Spuren in A1.
>> Setzen Sie den O auf dem Brett.
So, jetzt gehen Sie vor.
Wo würdest du gerne hingehen?
C2.
Unsere Maschine Spieler getroffen hat, das mittlere Quadrat, blockiert sie.
Das war also eine gute, intelligente, was dafür zu tun ist.
Sie haben es blockiert.
Das ist ausgezeichnet.
Es bringt die Ecke gibt.
>> Und es geht um Sie zu zwingen, nehmen Sie die eine letzte Raum, B0.
Und das Spiel endet unentschieden.
Aber es eine vernünftige gespielt Spiel gegen sie, nicht wahr?
Alles klar, vielen Dank, Gorav.
>> [BEIFALL]
>> In Ordnung, Layla, wir gehen bis das Spiel auf Sie hier.
>> ZIELGRUPPE: Oh, großartig.
>> SPRECHER: Wir gehen zu geben, Sie vier mal vier tic-tac-toe.
Jetzt, in vier durch vier, um zu gewinnen müssen Sie mit vier in einer Reihe, nicht die drei in einer Reihe.
Und es ist ganz Ihnen.
So Layla nahm D1.
Wir werden jetzt zu folgen Unsere Computer-Spieler hier.
Drei mal drei tic-tac-toe ist die Art Dinge, die einfach für uns alle ist.
Aber es ist immer noch schön, das zu sehen Computer-Spieler, der Smart-Moves.
Vier mal vier bekommt ist ein wenig komplizierter.
>> Schön gemacht.
In Ordnung, so Layla endete.
Oh, und wir sollten es beendet haben.
Aber lassen Sie uns einen weiteren hier oben.
So Layla, danke.
Schön gemacht.
>> [BEIFALL]
>> Also unsere Tic-Tac-Toe-Spieler geht durch und findet Standorten,
löst sie mit diesen Minimax.
Und ich hatte eine Tiefeneinstellung auf das so, dass es
nicht zu schnell laufen, Das ist wahrscheinlich, warum
Layla konnte gut voran gehen wie sie es tat, und war sehr gut.
Aber diese Systeme, die nur gehen Sie durch und Brute-Force-
tiefer und tiefer und tiefer, und halten Sie die Lösung zu finden
die sie benötigen, diese Arten von Systemen sind recht erfolgreich auf diese, na ja,
Standard-Brettspiele.
>> Und in der Tat, wenn wir uns ein drei mal drei Tic-Tac-Toe-Spiel,
Dies ist im Grunde ein gelöstes Problem.
Und das ist eine wunderbare Bild von Randall Munroe am XKCD,
die zeigen, welche zu bewegen, sollten Sie nehmen, da bewegt sich deines Gegners.
Das ist etwas, dass wir leicht vor der Zeit angeben.
Aber was passiert, wenn wir mehr bekommen komplexe Spiele, kompliziertere Spiele,
wo es größere Bretter, mehr Möglichkeiten, tiefer Strategie?
>> Es stellt sich heraus, dass diese Brute-Force-Suche noch
funktioniert recht gut, mit Ausnahme wenn Sie auf den Punkt
wo dieser Baum ist so groß, dass man nicht zu vertreten sie alle.
Wenn Sie nicht berechnen können den gesamten Baum, wenn Sie sich nicht nach vorn und Push gehen
selbst bis zu dem Punkt, wo Sie haben, bekommen den gesamten Baum im Speicher,
oder ob Sie es bekommen in Erinnerung und es wird nur
nehmen Sie viel zu lange, um durch zu suchen es können, müssen Sie etwas schlauer machen.
>> Um das zu tun, werden Sie haben zwei Dinge tun.
Zuerst müssen Sie einige finden Möglichkeit zur Begrenzung Ihrer Tiefe.
Nun, das ist OK.
Wir können ein paar schöne, absolute Minimum zu finden und zu sagen, man kann nur so tief gehen.
Aber wenn Sie das tun, bedeutet, dass Sie haben diese teilweise unvollständige Boards.
Und man muss sich entscheiden, zu tun Ich mag Diese teilweise unvollständige Pension,
oder diese teilweise unvollständige Bord?
>> Und auf unsere vier durch vier Tic-Tac-Toe-Spiel,
Unsere Computer-Spieler nach unten bekam auf den Boden und sagte, dass es,
Ich habe zwei verschiedene Boards erhielt.
Weder das eine ist ein Gewinn.
Weder das eine ist ein Verlust.
Weder das eine ist eine Krawatte.
Wie kann ich zwischen ihnen wählen?
Und es hatte nicht ein intelligente Art und Weise, das zu tun.
>> Wir sehen diese Art von Auswertung geschieht die ganze Zeit
wie wir in komplexere Spiele.
Schach ist ein gutes Beispiel.
Im Schach, haben wir zuerst von allen, eine größere Bord.
Wir haben weit mehr Stücke.
Und die Positionierung dieser Teile und die Art und Weise, dass diese Stücke bewegen
von entscheidender Bedeutung ist.
Also, wenn ich will Minimax verwenden, Ich muss in der Lage, zu spezifizieren
und sagen, das Brett, wo niemand hat gewonnen oder verloren noch,
irgendwie besser als dieses andere Brett, wo niemand gewonnen oder verloren.
>> Um dies zu erreichen, könnte ich tun, Dinge wie ich könnte nur
zählen, wie viele Stücke habe ich, und wie viele Stücke haben Sie?
Oder ich könnte anders geben Stücke verschiedenen Punkten.
Meine Königin ist 20 Punkte wert.
Ihre Spielfigur zählt einen Punkt.
Wer hat mehr Punkte insgesamt?
Oder ich könnte prüfen, Dinge wie: wer die bessere Brettstellung bekam ist?
Wer ist dran nächsten, Alles, was ich kann,
Sie genauer zu bewerten welche dieser Möglichkeiten
ist besser, ohne erschöpfend Berücksichtigung
jede Bewegung, die danach kommen könnte.
>> Nun, diese Arbeit zu machen, eines der Dinge, die ist
gehen, um wirklich wichtig geworden für uns ist nicht nur Gerade
bis zu einer bestimmten Tiefe Limit, aber in der Lage zu sagen,
eine dieser Ideen, die ich so schlecht, dass es ist,
nicht eine Überlegung wert alle möglichen Weisen
dass die Dinge immer schlechter zu gehen.
Um dies zu erreichen, werden wir in die Minimax hinzufügen ein Prinzip genannt alph-beta.
Und alpha-beta sagt wenn Sie eine schlechte Idee,
Ihre Zeit vergeuden Sie nicht versuchen, genau herauszufinden, wie schlimm es ist.
>> Also hier ist das, was wir tun werden.
Wir werden das gleiche zu nehmen Prinzipien, die wir vorher hatten,
das gleiche Minimax-Typ der Suche, nur wir sind
gehen zu verfolgen, nicht nur die Ist-Werte, die wir haben, aber wir werden
verfolgen die bestmögliche Wert, den ich bekommen konnte,
und das Schlimmste, Resultat, das ich haben könnte.
Und jedes Mal, das Schlimmste, was wahrscheinlich auf der Suche,
Ich werde diesen Teil des Baumes zu verzichten.
Und ich werde nicht einmal die Mühe, Blick auf sie nicht mehr.
>> In Ordnung, so vorstellen, dass wir anfangen, Mit diesem gleichen genauen Spielbaum.
Und jetzt werden wir zu gehen, wieder nach unten, ganz nach unten
in diesem unteren linken Ecke.
Und in diesem unteren linken Ecke, die wir betrachten und bewerten wir dieses Board.
Vielleicht ist es ein vier mal vier tic-tac-toe Brett, oder vielleicht ist es ein Schachbrett.
Aber wir betrachten, und wir bewerten es, und wir bekommen einen Wert von acht Jahren.
>> Zu diesem Zeitpunkt wissen wir, dass wir werden zumindest zu erhalten
acht Punkte aus dieser unteren Entscheidung.
Es ist egal, was die anderen zwei sind, dass sieben und dass zwei.
Sie konnten alle Werte sein sie sein wollte.
Wir werden an erhalten mindestens acht Punkte.
In Ordnung, aber wir konnten gehen Sie vor und überprüfen.
Vielleicht einer von ihnen ist besser als acht.
>> Wir schauen auf die sieben.
Ist das besser als acht?
Nein, das ändert sich nicht, unserer Meinung nach überhaupt.
Wir schauen auf die beiden.
Ist das besser als acht?
Nein, das ändert sich nicht, unserer Meinung nach überhaupt.
So, jetzt wissen wir, dass wir erschöpft habe alle Möglichkeiten gibt.
Wir gehen nicht zu bekommen, nichts besseres als acht.
Wir werden genau acht zu bekommen.
>> Und so haben wir diesen Knoten zu ändern und sagen wir, ist, dass jetzt eine Gewissheit.
Wir gehen eine Ebene darüber.
Und nun etwas wissen wir über diese Minimierung Ebene.
Wir wissen, dass wir nie wieder bekommen mehr als acht Punkte, wenn wir nach unten gehen
diese Richtung.
Denn auch wenn diejenigen, anderen beiden Zweige entpuppen
fantastisch und wert zu sein Tausende von Punkten je,
unser Gegner wird uns die Minimum, und geben uns die acht.
Na gut, na ja, mal sehen.
Wir werden weitermachen auf diesem Weg.
Wir gehen bis zu dieser Mitte auf der linken Seite.
Wir schauen hinunter und wir sehen, gibt es eine neun.
Wir wissen, dass wir gehen, um zu bekommen mindestens neun Punkte, indem Sie unten
dass Mittelweg.
Und an diesem Punkt können wir nur unterbrechen.
Und wir können sagen, schau, ich weiß, in der Ebene über,
Ich werde nicht mehr als acht erhalten Punkte, indem Sie unten in diese Richtung.
Aber wenn ich in der Mitte Pfad anstelle des linken Weg,
Ich würde mindestens neun Punkte zu bekommen.
>> Mein Gegner wird nie Lassen Sie mich diesen mittleren Weg nach unten gehen.
Sie erhalten zu wählen.
Und sie gehen, um das zu wählen Pfad zu dem gegenüber den acht gelassen,
anstatt in der Mitte in Richtung was ist mindestens neun Punkte.
So an diesem Punkt, werde ich aufhören.
Und ich werde sagen, wissen Sie was?
Ich habe nicht nach einem zu suchen mehr in diese Richtung.
Denn ich werde nie dorthin zu gelangen.
>> Ich kann über diesen einen zu überspringen, und ich kann über diese sechs zu überspringen,
denn das wird nie passieren.
Also werde ich nach unten gehen und ich werde Sehen Sie sich die nächste Möglichkeit.
Ich gehe dort unten, und ich sage, ich einen zwei zu sehen.
Ich weiß, wenn ich hierher, ich bin gehen, um mindestens zwei zu bekommen.
OK.
I keep going.
Ich sehe eine vier.
Ich weiß, ich werde mindestens vier zu bekommen.
Es gibt noch eine Menge zwischen vier und acht, though.
So dass ich weitermachen.
Ich schaue nach unten und ich sehe, es ist eine.
Also gut, ich, ob Ich diesen Weg zu gehen,
Ich werde in der Lage, die vier zu wählen.
Was ist mein Gegner tun?
Zwischen etwas, das gibt mir acht, etwas, das gibt mir vier,
und etwas, gibt mir mindestens neun,
na ja, er wird mir die vier.
Und ich weiß, jetzt bei der Ganz oben, ich werde
in der Lage, zumindest zu erhalten vier Punkte aus diesem Spiel.
>> Die ganze Idee der Alpha-Beta- ist abgeschnitten Teile der Baum so
dass ich nicht mehr, sie zu betrachten.
Aber es sieht immer noch wie ich gewesen bin Blick auf eine Menge des Baumes.
Lassen Sie uns hinunter.
Wir werden das nächste nun nach unten gehen.
Unten am Boden, finde ich eine eins.
Ich weiß, ich werde zumindest eine zu bekommen.
Ich suchen Sie weiter.
>> Ich finde eine drei.
Ich weiß, ich werde mindestens drei zu bekommen.
I keep going.
Ich finde eine fünf.
Ich weiß, ich werde bis fünf erhalten wenn ich nach unten in diesem Pfad.
Und ich weiß auch, dann dass mein Gegner, wenn ich
wählen die Mitte die drei großen Auswahl,
er wird mir geben etwas, das fünf oder weniger ist.
>> OK.
Ich kann weitermachen es.
Ich kann nach unten schauen und ich kann sagen, was soll ich nur
zu bekommen, wenn ich in der Mitte Weg zu gehen?
Ich werde dorthin zu gelangen, nun, drei.
Ich werde etwas zu bekommen das ist mindestens drei.
Es gibt immer noch Dinge, zwischen drei und fünf, so dass ich auch in Zukunft.
Oh, eine Neun, werde ich auf jeden Fall nehmen Sie, dass innerhalb von drei.
Ich werde mindestens neun erhalten wenn ich nach unten gehen, dass Mittelweg.
>> Nun mein Gegner stoppt und sagt: aussehen, es hat keinen Sinn mehr.
Ich weiß, dass mein Minimierung Gegner, er ist
werde mir die Sache, die ist zu geben, kleiner als oder gleich fünf ist,
anstatt die Sache, die ist größer als oder gleich neun.
Ich halt.
Ich weiß nicht mehr, sehen Sie, dass.
I keep going.
>> Ich freue mich auf diese ein.
Bis auf den Boden, finde ich eine sechs.
Ich weiß, ich werde mindestens sechs zu bekommen.
Und was kann ich tun?
Ich kann zu stoppen.
Denn es gibt eine Wahl zwischen etwas, das mindestens sechs ist
und etwas, das ist weniger als fünf, er
werde mir die Sache zu geben, das ist weniger als fünf.
Und jetzt weiß ich, ich werde um genau das zu Wahl zu erhalten.
Ich werde diesen fünf Wahl zu erhalten.
>> Ich gehe zurück bis an die Spitze.
Welche soll ich Wahl zwischen etwas,
das ist größer als oder gleich zu vier, oder etwas, das um fünf gleiche ist?
Ich werde etwas zu nehmen das ist, mindestens fünf.
Ich gehen Sie die letzten Weg, alle nach unten auf den Boden.
Es gibt eine eins.
OK, zumindest werde ich einen Punkt zu bekommen.
I keep going.
Zwei, oh, das ist besser als einer.
Ich werde mindestens zwei zu bekommen.
Ich finde eine drei.
Ich weiß, ich werde drei zu bekommen.
>> Und der Punkt über dem, mein Gegner geht
mir etwas, das ist zu geben, weniger als oder gleich drei.
Und jetzt kann ich stoppen.
Denn die Entscheidung zwischen mir als in der Lage, eine Fünf und meine Gegner zu bekommen
Geben Sie mir etwas weniger als drei, Ich werde immer, dass fünf zu nehmen.
So dass ich nicht zu beurteilen, dass unteren Teil des Baumes überhaupt.
>> Jetzt kann diese scheinen gering.
Aber als kleine Stücke von Arithmetik, größer als und kleiner als,
können ganze Teile weggeschnitten Dieses exponentiell wachsenden Baum,
Das führt zu einer enormen Höhe der Einsparungen, Einsparungen
die groß genug ist, dass I kann spielen wettbewerbsfähigen starten
bei komplexeren Spielen.
>> Na gut, wenn wir uns die Größe und die Komplexität der verschiedenen Spielen,
tic-tac-toe war unser einfaches Beispiel.
Wir haben eine kleine Platine, drei mal drei bekam.
Wir bekommen allenfalls durchschnittlich etwa vier unterschiedliche Wahlen
wie gehen wir durch das Spiel.
Wir haben irgendwo um 10 bis die fünften möglichen unterschiedlichen Blättern.
Und den Aufbau einer Tic-Tac-Toe- Spieler, nun ja, wir haben es einfach.
Es ist einfach.
>> Wenn wir nach oben, um etwas mehr Komplex, wie Connect Four.
Wollen Sie dieses Spiel, wo erinnern Sie sehen die kleinen Token in fallen zu lassen?
Es ist ein sechs von sieben Pension, nicht so viel größer, noch
etwa den gleichen Verzweigungs Faktor tic-tac-toe.
Ich habe ungefähr vier Wahlen wo ich kann die Dinge in.
Aber jetzt, ich muss noch viel mehr führt, 10 bis 21. Macht.
Das ist etwas, das einfach genug, dass wir zu lösen Sie es sofort.
>> Checkers, mehr complex-- Sie bekam eine acht mal acht Bord.
Du bist nur auf der Hälfte der sie jederzeit, wenn.
Du hast eine Verzweigung bekam Faktor, der etwa 2,8 ist.
Nun, wir haben ein paar bekam bewegt Sie nehmen können.
Sie haben etwa 10 bis 31. Blättern kam, größere und größere und größere Räume.
Als ich durch zu suchen diese größer und größer Plätze,
das ist, wenn Dinge wie alpha-beta und in der Lage, ganze Zweige wegschneiden
ist unerlässlich.
>> Nun war Kontrolleure leicht genug, im Jahr 1992.
Ein Computerprogramm namens Chinook schlagen Sie die Welt Kontrolleure
Meister, Marion Tinsley.
Und seither keine Menschen Master Spieler
in der Lage, das Beste zu schlagen Rechensysteme.
Wenn wir uns so etwas wie Schach, jetzt wieder, wir haben eine acht mal acht Bord.
Aber wir haben sehr viel komplexer Stücke, viel komplexer Bewegungen.
Wir haben eine Verzweigungsfaktor von etwa 35, 35 möglichen Züge im Durchschnitt
dass ich, und einen Zustand zu nehmen Raum, eine Anzahl der Blätter
das ist um 10 bis 123. Macht gewachsen, enorme Anzahl von Möglichkeiten.
>> Sogar noch, modernen Prozessoren in der Lage, dies gelingt.
Im Jahr 1995 und dann im Jahr 1997 einen Computer Programm namens Deep Blue von IBM gebaut
dass auf einem riesigen Supercomputer lief schlagen die aktuellen Weltmeister,
Garry Kasparov.
Dies war ein Wendepunkt.
Heute aber, dass dieselbe Verarbeitung Macht sitzt auf meinem MacBook.
>> Verarbeitungsgeschwindigkeit hält immer schneller.
Wir können mehr und mehr bewerten Platten schneller und schneller.
Aber noch wichtiger ist, haben wir besser Auswertungsfunktionen und bessere Beschneiden
Methoden.
So können wir die Suche Platz mehr komplex.
Die größte der Platine Spiele, die wir uns vorstellen können,
so etwas wie Go, das ist bekam eine 19 um 19 Pension,
jetzt auf einmal, werden wir über den Punkt sind wo Rechensysteme zu gewinnen.
Es gibt keine rechnerische System da draußen
dass eine professionelle Go-Spieler schlagen kann.
Die besten Systeme heute rank es um die Art von guter Amateurniveau.
Es gibt also noch einiges heraus gibt, die Sie nicht noch bekommen kann.
>> Alle Rechte, diese traditionellen Gesellschaftsspiele,
Diese Arten von Systemen, in denen man bauen diese Minimax, ob es hat
Alpha-Beta oder nicht, diese Algorithmen arbeiten weil es bestimmte Einschränkungen.
Wir haben perfekte Information über die Welt.
Wir wissen, wo all die Stücke sind.
Die Welt ist statisch.
Niemand wird auf den Umzug Stücke um, während ich
dort sitzen zu denken, wobei ich an der Reihe.
Es gibt eine Aktionsraum, die diskrete ist.
Ich kann meinen Bauern hier zu setzen, oder kann ich meinen Bauern hier setzen.
Ich darf nicht zu meinen Bauern setzen auf die Linie zwischen den beiden Plätzen.
>> Und schließlich die Maßnahmen deterministisch sind.
Ich weiß, dass, wenn ich sage, Turm zu drei Ritter,
meinem Turm wird sich auf Ritters am Ende drei, solange es ist eine gültige Bewegung.
Es gibt keine Unsicherheit darüber.
Nun, wie ich gehen, um mehr verschiedene Arten von Spielen,
wir müssen diese Annahmen zu brechen.
>> Was, wenn ich gehen, um etwas wie klassische Videospiele?
Hier ist eine Auswahl von Video- Spiele aus der Atari 2600.
Was muss ich da oben?
Ich habe Frogger, Raum bekam Invaders, Pitfall und Pac-Man.
Welche Arten von Umgebungen muss ich jetzt hier?
Welche dieser Annahmen muss ich brechen?
>> Nun, es hängt von dem Spiel.
Ich konnte Schach auf dem 2600 zu spielen, und es wäre, wie es vorher war.
Bei den meisten dieser Systeme gibt es komplette Wissen über die Welt.
Es ist völlig deterministische Handlungen.
Aber in der Regel, die weltweit nicht mehr statisch.
Das heißt, während ich dort sitzen warten, etwas zu bewegen.
Die Geister kommen, um mich zu bekommen.
Der Skorpion ist mir unter folgenden.
Die Space Invaders sind kommt näher und näher.
Wie gut können wir gegen diese zu tun?
>> Vor ein paar Jahren, Google war ein Projekt mit dem Namen
DeepMind, wobei sie einen Computer ausgebildete Programm zum Atari 2600-Spiele zu spielen.
Und wenn Sie denken, das ist nicht ernst Geschäft werden die Ergebnisse ihrer Studie
wurden in Nature veröffentlicht, so nur ungefähr so ​​gut, eine Publikation
wie Sie vielleicht bekommen.
Und hier ist, wie gut sie durchgeführt wird.
>> Sie haben einen Algorithmus, der saß und sah nur die Bildschirmeingänge.
Es wurde keine Anweisungen auch immer über die Regeln des Spiels.
Und es sollte herausfinden, Auf der Grundlage seiner Partitur, wie gut es tat.
Dies war ein System, das etwas verwendet genannt Reinforcement Learning.
Das heißt, es sah in seiner Partitur.
Und wenn es bekam eine gute Note, hieß es, Ich sollte diese Dinge zu erinnern.
Und ich sollte diejenigen wieder tun.
Und wenn es bekam ein schlechtes Ergebnis, hieß es, Ich sollte die Dinge nicht wieder tun.
>> Dies ist die Leistung jener geschulten Systeme
erlaubt, für ein Spiel wenige Stunden für jedes Spiel,
verglichen professionellen Spielern.
Also für alle die Spiele, die sind auf der linken Seite dieser Linie,
dies selbst ausgebildeten Computerprogramm besser als die professionellen Spielern.
Und für alles, was die Recht, die Profi-Gamer
waren immer noch die besten.
Für etwas, das wusste, nichts über die Regeln, dass
wusste nichts über die Struktur des Spiele, ist dieses beeindruckende Leistung.
Und das ist, was wir in der Lage zu tun heute.
>> OK, Sie sagen, aber wenn wir denke über den AI-in-Spiele,
normalerweise wir über die denken, Dinge, die wir eigentlich
hinsetzen und spielen gegen.
Wenn ich mich hinsetze und ich spiele StarCraft, oder ich spiele Kostenlose Sieve,
die Computer-Gegner ist die Person, die die Zerg,
oder Steuerung der anderen Zivilisation.
Wie jene Spieler ihre Bewegungen tatsächlich finden?
>> Nun, diese Spiele strukturiert sind viel die gleiche Weise, wie unsere Brettspiele,
diese Spiele, die wir kollektiv nennen vier X-Spiele,
zu erforschen, expand-- vergessen diejenigen.
Was sind Sie?
Entdecken Sie, zu erweitern und zu löschen, Ich denke, die letzte ist.
Aber sie sind im Grunde Erforschung und Eroberung Spiele.
Typischerweise wird die Computer-Gegner es hat nur begrenzte Informationen.
Sie wissen nicht genau, was sich hinter diesem Nebel des Krieges.
Sie bekommen nicht, was zu sehen Sie haben in Ihrem Inventar.
>> Es ist eine Umgebung, die dynamisch ist.
Alles verändert sich die ganze Zeit.
Sie erhalten nicht zu sitzen und warten, um Ihren Umzug zu nehmen.
Aber die meisten Dinge sind immer noch diskret.
Ich muss meine Stadt hier setzen.
Oder muss ich meine Stadt hier setzen.
Und alles ist deterministisch.
Wenn ich sage, meine Einheit bewegen sich hier, meiner Einheit bewegt sich hier, es sei denn, ein Hindernis plötzlich
ins Spiel kommt.
Nun, das ist nicht alle Computer Spiele, die da draußen heute.
>> Wenn ich gehe, und ich eine erste Art zu spielen Spiel, so etwas wie Dieb oder Fallout
oder Skyrim oder Halo, jetzt Ich habe Computer-Gegner
, die aus gibt es, dass haben eine ganz andere Situation.
Sie haben wieder begrenzte Informationen.
Sie können nur eine zu sehen bestimmte Sehfeld.
Die Umgebung ist noch dynamischer.
Die Dinge ändern sich die ganze Zeit.
>> Aber jetzt habe ich eine viel kontinuierliche Aktionsraum.
Ich kann einfach späht werden ein etwas aus der Tür.
Und einige Spiele, mein Aktionen sind stochastische.
Ich versuchen, über die Mauer zu springen, aber ich habe eine Chance zu scheitern bekam.
Diese Art von Spielen sind näher und näher an die Art der Steuerungen
dass wir bauen in der Robotik.
>> In der Robotik, müssen wir davon ausgehen, dass wir begrenzte Informationen.
Wir haben Sensoren, erzählen Sie uns von der Welt.
Wir haben einen immer wechselnden, dynamischen Umfeld.
Wir haben eine Welt, in der Raum kontinuierlich, statt diskreter.
Und unser Handeln, wenn wir versuchen, ihnen eine Chance haben, zu scheitern.
Und in der Tat, moderne Spiel Controller für Ihre Halo Gegner,
oder für die NPCs in Skyrim, im Grunde klein Robotik-Architekturen.
>> Sie spüren die Welt.
Sie bauen ein Modell der Welt.
Diese berechnen die auf einer Reihe von der Basis Ziele, die sie gerne erfüllen.
Sie planen Maßnahmen auf der Grundlage auf das, was sie wissen.
Und das sind genau die gleichen Arten von Systemen, die wir in der Robotik zu bauen.
Also diese Architekturen zu zusammen diese zurück zu bringen,
sind häufig ziemlich gleich.
>> Also mal sehen, ob wir das sehen können.
Gehen wir zurück zu unserem Tic-Tac-Toe-Beispiel.
Und ich werde ein paar meiner Fragen Post-Docs zu kommen und mir helfen.
So Chen Ming und Alessandro und Olivier, wenn euch würde kommen.
Und ich werde zu müssen, ein paar Freiwillige
>> OK, eine Hand rechts sah ich, es in der Mitte.
Lassen Sie mich noch einen nehmen, jemand weiter hinten vielleicht.
Alles klar, da drüben.
Komm auf.
Gut.
Werfen wir also, dass die Abdeckung nach unten.
Und wenn euch Recht kommen würde zurück hier in der Gegend für mich fantastisch.
>> Das ist also ein Roboter namens Baxter.
Und Baxter ist ein Roboter, der eine ist Handelsplattform, entworfen,
von einer Firma namens denken.
Und dieser Roboter ist so konzipiert für die Kleinserienfertigung.
Aber heute werden wir zu gehen verwenden, um Tic-Tac-Toe zu spielen.
Nun, das ist auch etwas, dieser Roboter das ist relativ eindeutig.
Denn wenn ich irgendwo stehen nah an einem Standard-Fabrikautomation
System, würde ich in sehr ernst sein, Gefahr, verletzt.
>> Baxter, ist jedoch so konzipiert, dass relativ sicher zu interagieren.
Und so kann ich auf diesem Roboter zu schieben.
Und sehen Sie, es ist ein wenig wenig flexibel, wie es sich bewegt.
Und ich kann es neu zu positionieren wo ich möchte sie zu gehen.
Jetzt in einem normalen Robot-System, wir würden eine Reihe von Gelenken hier
das wäre direkt sein Reaktion auf Positionsbefehle.
Und sie würden nicht unbedingt kümmern wenn sie durch die offene Luft bewegen,
oder wenn sie bewegten durch meinen Brustkorb.
>> OK.
Und in der Regel, wenn Sie waren hier mit einem industriellen System,
Sie nirgendwo in der Nähe es gehen würde.
Es wäre gelb Sicherheitsband alle um ihn herum.
Dieses System hat eine etwas anderes Design
freundlicher und leichter zu sein, für die Menschen zu interagieren,
dadurch gekennzeichnet, dass in jeder Verbindung gibt es eine Feder ist.
Und anstatt Steuern eine genaue Position,
steuern wir einen gewissen Drehmoment eine gewisse Menge an Kraft,
dass wir möchten auf diesem Frühjahr.
In Ordnung, so lassen Sie mich nehmen unsere Freiwilligen hier.
Hallo wie heißt du?
>> ZIELGRUPPE: Louis.
>> SPRECHER: Louis.
Schön, dich zu sehen.
Und?
>> ZIELGRUPPE: David.
>> SPRECHER: David.
Nett, dich zu treffen.
Wenn euch würde warten hier für eine zweite,
Ich werde dir geben eine Möglichkeit, dies zu tun.
Also dieser Roboter, wenn Sie kommen, und wenn Sie drücken Sie vorsichtig darauf
wirst du sehen, dass es bewegt sich ein wenig.
Und wenn Sie es packen rechts Hier am Handgelenk gerade
oben, wo diese Tasten sind, es sieht aus wie Sie sollten die Tasten zu greifen,
sondern greifen direkt darüber Stattdessen werden Sie in der Lage, sehr leicht zu manipulieren
durch den Raum.
Louis, möchten Sie ihm einen Versuch zu geben?
So geben sie nur ein wenig zu drücken, um mit zu beginnen.
Und dann, wenn Sie Ihre Finger setzen genau dort und auf, es zu halten,
denn es wird für Sie bewegen dann.
Na gut, Sie wollen es zu versuchen?
Komm auf.
So gebe es nur eine sanfte schieben es zu starten.
Sie können fühlen, wie es ist.
Und dann, wenn Sie es greifen genau dort, Sie in der Lage, um zu manövrieren sein.
>> OK.
So Typischerweise wird diese Art würde ein Roboter für Kleinserienfertigung eingesetzt werden.
Und ich werde diesen Arm gerade zu bewegen sich aus dem Weg, ein bisschen hier.
Aber heute, wir werden das benutzen gleichen Tic-Tac-Toe-Spielsystem
Auf der Grundlage von Minimax, die wir früher gebaut.
OK?
Also, sind Sie Kerle jedes gehen, um ein Spiel zu spielen.
Louis, du wirst der erste sein.
Lassen Sie mich nur halten Sie hier für eine Sekunde.
Ich werde haben Sie stehen rechts Hier, nur so kann jeder sehen.
Seid ihr hier eingestellt?
>> ROBOT: Willkommen.
Lassen Sie uns spielen tic-tac-toe.
Ihr Token Greifen Sie nicht vor Ich sage, dass Sie an der Reihe ist.
Ich das Spiel starten.
Ich bin am Zug.
SPRECHER: Nun, wenn Sie könnte eine der nehmen Ihre Stücke und gehen Sie vor und legen Sie es.
ROBOT: Es ist an der Reihe.
[LACHEN]
Ich bin am Zug.
[LACHEN]
Du bist dran.
SPRECHER: Die menschliche Rasse ist zähle auf Sie hier, Louis.
>> ROBOT: Es ist meine wiederum.
>> SPRECHER: So Baxter hier erfolgreich blockiert.
>> ROBOT: Es ist an der Reihe.
Ich bin am Zug.
Du bist dran.
Ich bin am Zug.
SPRECHER: Und wir lassen Baxter Abschluss seiner letzten Zug hier.
>> [LACHEN]
>> ROBOT: Das ist eine Krawatte.
Ich werde das nächste Mal zu gewinnen.
>> [LACHEN]
>> SPRECHER: In Ordnung, Dank sehr viel, Louis.
Danke.
Sie können diesen Weg zu gehen.
>> ROBOT: Ich starte das Spiel.
SPRECHER: Also lassen Sie mich erklären, um Ihnen noch eine kleine
bit, bevor wir hier unsere Rückkampf.
Was genau ist passiert?
So der Roboter über eine Kamera bis oben hier.
Und es hat sich auf das Brett suchen.
Und es ist zu sehen, ob Es ist eine rote O oder einen blauen bekam
und weißen X. Wie die, steigen in den platziert Bord, das ist im Grunde das gleiche Eingangs
dass wir werden in aus der Lektüre unseren Datenstruktur unserer Bildschirm.
Es läuft die gleiche Minimax-Algorithmus zu sein
der Lage zu finden, wo man legen ein gutes Zeichen.
>> Und dann geben wir einen Befehl zu wo wir möchten ein Zeichen gesetzt werden.
Der Arm bewegt sich.
Es ist mit einem Vakuumgreifer zur Anwendung einige Saugwirkung auf diesem Holzstück,
holen Sie es, bewegen Sie ihn nach rechts spot, und lassen Sie die Saug-
und legen Sie es.
Na gut, wir gehen es noch eine Chance zu geben
mit einem etwas smarter Player hier.
Bereit?
Na gut, wenn Sie rechts oben stehen würde hier und geben a-- entpuppen sich auf diese Weise
so können Sie sehen, alle.
Und dann [unverständlich].
>> ROBOT: Es ist meine wiederum.
>> SPRECHER: Baxter beginnt.
Du bist dran.
Ich bin am Zug.
Du bist dran.
Ich bin am Zug.
>> [LACHEN]
>> SPRECHER: [WHISPERING] Nur ließ ihn voran gehen und zu gewinnen.
ROBOT: Es ist an der Reihe.
SPRECHER: Das ist OK.
>> ROBOT: Es ist meine wiederum.
>> [LACHEN]
>> Ich gewinne.
>> [LACHEN]
>> Ich das Spiel starten.
>> SPRECHER: In Ordnung, ich danke Ihnen sehr.
Also gut, ich denke, wir haben Zeit für eine weitere ausgezeichnete tic-tac-toe-Player,
jemand, der diese Sache zu setzen kann entsprechen, die weiß, was sie tun.
>> [LACHEN]
>> Wer wird unser Meister hier zu sein?
Alle Rechte, die Sie Ihren Freunden freiwillig.
Das ist gut genug für mich.
Sag mir deinen Namen wieder.
ZIELGRUPPE: Tamir.
SPRECHER: Tamir, schön dich zu sehen.
Also gut, wieder, werden wir an Sie stellen Recht hier oben, so kann jeder sehen.
Sie sind unser Vertreter in dieses Spiel jetzt.
Baxter ist ein und ach ja, und oh.
Oder sorry, man oh und ein.
Und es liegt an Ihnen hier.
Baxter erhalten, um zuerst zu bewegen, wenn.
Also.
ROBOT: Es ist meine wiederum.
>> [LACHEN]
>> Du bist dran.
Ich bin am Zug.
Du bist dran.
Ich bin am Zug.
Du bist dran.
>> [LACHEN]
ROBOT: Es ist meine wiederum.
SPRECHER: Es ist viel schwieriger, wenn Sie stehen hier, Leute.
[LACHEN]
ROBOT: Ihr Menschen sind so leicht zu schlagen.
[Lachen und Beifall]
SPRECHER: Vielen Dank.
ROBOT: ich gewinne.
Ich das Spiel starten.
>> SPRECHER: In Ordnung, also danke sehr viel zu Olivier, und Alessandro,
und Chen Ming.
>> [BEIFALL]
>> Ich möchte einen letzten Punkt zu machen.
So Baxter zumin zu Ende, betrogen.
Und das war unerwartet.
Einer der fantastischen Dinge über AI ist, dass wir
arbeiten in AI, so dass wir aufbauen können wirklich interessant und intelligent
Geräte.
Aber wir haben auch Arbeit in AI zu tun denn es sagt uns etwas
darüber, wie Menschen sind intelligent.
>> Einer der Lieblings Studien aus meinem Labor ist
schauen, was passiert, wenn Maschinen unerwartet zu betrügen.
Wir taten dies ursprünglich nicht mit Baxter spielt Tic-Tac-Toe,
jedoch mit einem kleineren Roboter namens Nao, die Papier-Stein-Schere gespielt.
Und manchmal nach spielen viel, viel
langweilig Papier-Stein-Schere-Spiele, der Roboter wäre eine Geste zu werfen,
zu verlieren, und dann plötzlich ändern ihre Gesten und sagen, ich gewinne.
>> [LACHEN]
>> Nun, manchmal würden wir auch den Roboter, nur als Kontrolle, werfen eine Geste,
zu gewinnen, und ändern Sie seine Geste zu verlieren, werfen Sie das Spiel,
zu betrügen, um zu verlieren.
Und das ist bei weitem nicht so überzeugend.
Der Roboter, der betrügt um Menschen zu gewinnen
zu antworten, als ob es aus, um sie zu erhalten, wie es
aktiv nach ihrer Zerstörung.
>> [LACHEN]
>> Es wird ein Agent.
Es ist wie eine Person.
Es verfügt über Glauben und Absicht.
Und es ist nicht in guter Absicht.
Und der Roboter, wirft die Spiel ist nur eine Fehlfunktion.
Es ist nur ein defektes Gerät.
Lassen Sie mich Ihnen ein paar Beispiele der, dass von einigen unserer Teilnehmer.
Also hier ist Betrug, um zu verlieren.
>> [VIDEO-WIEDERGABE]
- [Unverständlich] zu gewinnen.
Lass uns spielen.
>> -Warte was?
>> - [Unverständlich] zu gewinnen.
Lass uns spielen.
>> [Unverständlich] zu gewinnen.
Lass uns spielen.
>> SPRECHER: Und hier ist Betrug, um zu gewinnen.
>> -Ja, Ich gewinne.
Lass uns spielen.
>> -Sie Können das nicht tun.
>> [LACHEN]
>> -Ja, Ich gewinne.
-Du hast betrogen.
Sie betrogen bekommen.
>> -Ja, Ich gewinne.
>> -Hey, Sie Betrüger.
Sie zu betrügen, super Cheat.
>> [END PLAYBACK]
>> SPRECHER: Diese verschiedenen Reaktionen schnell
verändern unsere Wahrnehmung des Gerätes.
Heißt das, dass wir bewusst bauen
Maschinen, die betrügen, weil das ist, die beste Technik, die wir tun können?
Nein, aber es sagt uns etwas wirklich interessant zu Personen.
Das Ding, das Sie und Cheats stiehlt Ihren Sieg, das ist,
etwas, das noch am Leben ist, das ist, animieren, das ist hinter dir her.
Es hat psychische Verfassung.
Es verfügt über Glauben.
Es hat die Absicht.
>> Das Ding, dass die Hände Spiel, dann ist das nicht.
Das ist nur eine Fehlfunktion.
Dies ist in vielerlei Hinsicht, weshalb es einfach, um das Spiel mit Kindern zu werfen.
Aber wenn Sie versuchen, sie zu betrügen und eine Art Sieg für sich beanspruchen
wenn Sie wissen, nur um die Verkürzung Spiel, sie werden Ihnen sofort zu fangen.
Diese Art von Auswirkungen, sehen wir von AI kommen,
sie lehren uns viel über uns selbst.
>> Alles klar, dass es für heute.
Vielen Dank an David und der Harvard Produktionsteam
für herab.
>> [BEIFALL]
>> Registrieren Sie sich für ein Quiz zu sehen, und dann für einen letzten Vortrag.
Ich wünsche ihnen einen wunderbaren Tag.
>> [BEIFALL]
>> [Musikwiedergabe]
DAVID J MALAN: Nun, wir brauchen wahrscheinlich , eine Art von Verschlüsselung einführen,
Recht?
Weil dann die Header Diese HTTP-Anforderungen werden
verschlüsselt, so dass jeder, versuchen, Ihren Traffic zu schnuppern
wird nicht wirklich in der Lage, sie zu sehen.
Was ist also die Lösung für dieses Problem?
Nun müssen wir uns tatsächlich vorstellen Verschlüsselung in der Formel,
so dass, wenn die betreffende Person ist Übertragen von Daten von A nach B,
wir können sicher send--
>> [LACHEN]
>> Die Informationen in einer Weise, dass die Gegner kann nicht in der Tat, es sehe.