[Παίζει μουσική] 

ΟΜΙΛΗΤΗΣ: Καλώς ήρθατε και πάλι, ο καθένας. Αυτό είναι CS50. Και σήμερα, έχουμε πολλά ενδιαφέροντα πράγματα να συζητήσουμε. Πρώτα, όμως, πρέπει να υπενθυμίσω Σας λίγων διοικητικών πράγματα. Αυτή η εβδομάδα είναι ένα κουίζ, Τετάρτη ή για το τμήμα Yale Τρίτη και Πέμπτη, την Πέμπτη. Υπάρχουν σχόλια κουίζ απόψε στο Yale, 5:30 - 7:00. Στο Χάρβαρντ, κατέγραψαν μία χθες. Και ο καθένας μπορεί να παρακολουθήσετε αυτή την online. 

Επίσης, αυτή την εβδομάδα ή στις αρχές της επόμενης εβδομάδας, έχουμε την τελευταία διάλεξη CS50 μας. [Στεναγμοί] Το ξέρω. Ήρθε τόσο σύντομα. Φοιτητές του Yale θα έχουν μια ζωντανή διάλεξη εδώ στο σχολείο του νόμου αμφιθέατρο, την Παρασκευή. Θα υπάρχουν κέικ. Φοιτητές του Χάρβαρντ θα έχει η τελευταία διάλεξη σε Sanders τη Δευτέρα. Θα υπάρξουν επίσης κέικ. 

Επίσης, αυτή την εβδομάδα, την Παρασκευή, για εκείνους από εσάς που έρχονται προς Νιου Χέιβεν, έχουμε το CS50 Expo. Έχουμε πάνω από 30 διαφορετικές ομάδες καταχωρηθεί για να σας δείξει τα πάντα αυτόνομων ιστιοφόρα, σε συστήματα που αναγνωρίζουν ψηφιακά πορτρέτα, στον υπολογιστή μουσική και τον υπολογιστή-που παράγονται μουσική. Επομένως, σας παρακαλώ να μας ενώσουν. Νομίζω ότι πρόκειται να είναι μια μεγάλη στιγμή. 

Σήμερα, όμως, έχουμε την ευκαιρία να συνεχίσουμε να μιλάμε για το AI, σχετικά με την τεχνητή νοημοσύνη. Και ένα από τα πράγματα που θα πάμε για να φτάσουμε στο σήμερα είναι η ιδέα για το πώς να AI χρησιμοποιούν για την επίλυση προβλημάτων. Τώρα, όπως πάντα, ας ξεκινήσουμε με κάτι απλό. Και θα πάμε για να ξεκινήσει με μια απλή ιδέα. Και αυτό είναι χρησιμοποιώντας την αναζήτηση. 

Φανταστείτε λοιπόν για ένα λεπτό ότι εγώ, έχουν μια εργασία που θα πρέπει να εκτελέσει. Και θα ήθελα να έχει αυτό το έργο αυτοματοποιημένη από κάποιο πράκτορα λογισμικού. Φανταστείτε ότι εγώ προσπαθώ να κλείσετε ένα σετ πτήσεων από, ας πούμε, της Βοστώνης στο Σαν Φρανσίσκο. Θα μπορούσα να πάω μέσα και θα μπορούσε να χρησιμοποιήσει ένα από τα υπέροχα online αναζήτησης εργαλεία, τα οποία πρόκειται να κάνει βασικά η ίδια διαδικασία που είμαστε πρόκειται να περπατήσετε έως και σήμερα. Αλλά αν δεν είχατε ότι εργαλείο, τι θα κάνατε; 

Λοιπόν, θα μπορούσαμε να εξετάσουμε και δείτε και να πω, είμαι στη Βοστώνη. Ποιες πτήσεις είναι διαθέσιμες για εμένα; Τώρα, ίσως έχω τρεις πιθανές πτήσεις από Μπόστον ότι θα ταιριάζει το χρόνο όταν έπρεπε να φύγω. Θα μπορούσε να πετάξει στο Σικάγο. Ή θα μπορούσα να πετάξω στο Μαϊάμι. Ή θα μπορούσα να πάω στη Νέα Υόρκη. Θα μπορούσε στη συνέχεια να εξετάσουμε από κάθε μία από αυτές τις πόλεις προορισμού και σκεφτείτε τι θέσεις Θα μπορούσε ενδεχομένως να φθάσει από κάθε μία από τις επιμέρους πόλεις. 

Έτσι ίσως από το Σικάγο, μπορώ να πάρω μια απευθείας πτήση για το Σαν Φρανσίσκο. Αυτό είναι εξαιρετικό. Ή θα μπορούσα να πάρω μια πτήση προς Ντένβερ. Τώρα, ίσως αυτό πτήση προς Σαν Φρανσίσκο Είναι η τέλεια λύση για μένα, αλλά ίσως όχι. Ίσως Ψάχνω για κάτι ότι είναι λίγο φθηνότερο ή λίγο καλύτερα για το πρόγραμμά μου. Και γι 'αυτό θα μπορούσε να αναζητήσει ό, τι άλλο οι δυνατότητες μπορεί να είναι εκεί έξω. Έτσι, θα μπορούσαμε να εξετάσουμε σε Ντένβερ. Και από το Ντένβερ, καλά, ίσως Μπορώ να πάρετε μια πτήση προς Όστιν. Και από Austin, ίσως μπορώ να πάρω ένα πτήσης προς Φοίνιξ, και από το Φοίνιξ στο Σαν Φρανσίσκο. Τώρα, δεν είμαι γίνει ακόμα. Επειδή ίσως υπάρχει μια απευθείας πτήση από τη Νέα Υόρκη στο Σαν Φρανσίσκο που είναι τέλειο για μένα. Ή ίσως υπάρχει μια πτήση από Μαϊάμι μέσω Ντένβερ που είναι πολύ φθηνότερα. Έτσι, έχω ακόμα να πάω. Και έχω ακόμα να δούμε όλες εκείνες πόλεις που δεν έχουν ερευνηθεί ακόμα. Θα πρέπει να ελέγξετε διεξοδικά όλα οι δυνατότητες που μπορεί να έχω. 

Έτσι, από τη Νέα Υόρκη, ίσως μπορώ να πάρω ένα πτήσης προς Νάσβιλ, και από το Νάσβιλ στο Όστιν. Και τότε ξέρω πού είμαι. Και τότε ξέρω από Austin, μπορώ πετάξει στο Φοίνιξ, και από το Φοίνιξ στο Σαν Φρανσίσκο. Αν έχω πετάξει πρώτα στο Μαϊάμι, όμως, ίσως μπορώ να πάρετε μια πτήση από Μαϊάμι σε Νάσβιλ, ή από το Μαϊάμι στο Όστιν. 

Και τώρα έχω δοκιμάσει όλα από τις δυνατότητες. Έχω δημιουργήσει αυτό το γράφημα ότι μου δείχνει όλες τις πιθανές διαδρομές ότι θα μπορούσε να είναι σε θέση να λάβει. Όταν εμείς εκπροσωπούμε αυτά είδη προβλημάτων, εμείς δεν πρόκειται να εκπροσωπήσει τους ρητά ως αυτό το γράφημα, γιατί αυτό διάγραμμα δεν αντιπροσωπεύει Η ιστορία του, όπου έχουμε πάει. Γνωρίζοντας ότι Πέταξα από Φοίνιξ σε Σαν Φρανσίσκο δεν μου πείτε αν ήρθε μέσω Νάσβιλ, είτε μέσω Ντένβερ, είτε μέσω του Μαϊάμι. 

Λοιπόν, τι θα κάνω, αντίθετα, είναι Θα πάρω το ίδιο πρόβλημα, και εγώ θα την εκπροσωπήσει, όπως ένα δέντρο. Και στη ρίζα του δέντρου, κατά τη κορυφή, θα βάλω τη θέση που άρχισα, Βοστώνη. Και από τη Βοστώνη, εγώ θα εξετάσουμε όλες τις πιθανές θέσεις ότι μπορώ να ταξιδέψω. Λοιπόν, σε αυτή την περίπτωση, είχα τρεις, Σικάγο, τη Νέα Υόρκη και το Μαϊάμι. Και τότε εγώ θα εξετάσει κάθε μία από αυτά τα παιδιά στο δέντρο. 

Από το Σικάγο, είδα ότι είχα δύο πτήσεις. Θα μπορούσα να πετούν απευθείας στην Σαν Φρανσίσκο ή Ντένβερ. Τώρα Σαν Φρανσίσκο, αυτός είναι ο στόχος μου. Αυτός είναι ο προορισμός μου. Αυτό πρόκειται να είναι ένα φύλλο από αυτό το δέντρο. Δηλαδή, εγώ ποτέ δεν πρόκειται να πάω κάπου μετά από το Σαν Φρανσίσκο. Από το Ντένβερ, όμως, Μπορώ να πετάξω από το Ντένβερ στο Όστιν, από Όστιν προς Φίνιξ, και από το Φοίνιξ στο Σαν Φρανσίσκο. Και τώρα πάλι, έχω φτάσει σε ένα φύλλο. 

Θα μπορούσε στη συνέχεια να επιστρέψετε στην επόμενη πόλη που δεν έχω διερευνηθεί πλήρως. Αυτό θα ήταν στη Νέα Υόρκη, πηγαίνετε πίσω μέχρι την κορυφή του δέντρου μου, κατέβει στη Νέα Υόρκη. Από τη Νέα Υόρκη, μπορώ να πετάξω να Νάσβιλ, από Νάσβιλ στο Όστιν, από Όστιν στο Φοίνιξ, και από το Φοίνιξ στο Σαν Φρανσίσκο. Και τέλος, μια πόλη που δεν έχουν εξεταστεί ακόμα, Μαϊάμι. 

Λοιπόν, από το Μαϊάμι είπα ότι είχε δύο δυνατότητες, Νάσβιλ ή Ώστιν. Αν ήμουν πετούν προς Νάσβιλ, καλά τότε πετώ από το Νάσβιλ, στο Όστιν, στο Φοίνιξ, στο Σαν Φρανσίσκο. Αν ήμουν πετούν προς Όστιν, πετάω Ώστιν, στο Φοίνιξ, στο Σαν Φρανσίσκο. Και τώρα έχω ένα δέντρο. Είναι ένα πλήρες δένδρο. Είναι όλα σχετικά με τις δυνατότητες και όλα τα μονοπάτια που θα μπορούσα να πάρω. Δηλαδή, αν εγώ ξεκινούν από το ρίζα του δέντρου στην κορυφή και να πάω κάτω σε ένα από τα φύλλα, μου λέει όχι μόνο όπου Πάω να καταλήγουν, Σαν Φρανσίσκο, αλλά μου λέει ότι η διαδρομή Θα πρέπει να ακολουθήσετε για να φτάσετε εκεί. 

Τώρα, ποιο από τα παρακάτω είναι το καλύτερο; Λοιπόν, τίποτα γι 'αυτό πρόβλημα ακόμα μου λέει ποια από αυτές είναι η καλύτερη λύση. Ίσως Νοιάζομαι για την πιο πόσο χρόνο είμαι στον αέρα, ή η απόσταση που πετάω. Σε αυτή την περίπτωση, το Σικάγο στο Σαν Francisco θα μπορούσε να είναι η συντομότερη αριθμός του μιλίου στον αέρα. 

Ίσως να νοιάζονται για το κόστος. Και όλοι γνωρίζουμε απευθείας πτήσεις είναι συνήθως πιο ακριβά. Έτσι, ίσως αν πάρω αυτό το είδος της διαδρομής προς τα πίσω μέσω του Μαϊάμι, Νάσβιλ, Ώστιν, Φοίνιξ, ίσως τότε Παίρνω μια χαμηλότερη τιμή. Αλλά εγώ θα μπορούσε να βελτιστοποιήσει για οποιαδήποτε κριτήρια που νοιάζομαι. Ποιος έχει το καλύτερο Wi-Fi πτήσης, ή τα οποία αεροδρόμια έχουν στη διάθεσή τους το καλύτερο φαγητό. Και κάθε ένα από αυτά θα μπορούσε να μου δώσει μια διαφορετική λύση ότι θεωρώ ως το καλύτερο. 

Αυτά τα είδη των προβλημάτων, όπου θα πάμε να χτίσει αυτό το δέντρο δυνατοτήτων, και στη συνέχεια εξετάσουμε κάθε ένα από αυτά ατομικές διαδρομές, και να εξετάσει ποια από αυτά πληροί ένα κριτήρια για μας, θα πάμε για να καλέσετε αυτά τα προβλήματα αναζήτησης. Και έχουμε πολλά αλγορίθμων, ορισμένες από τις οποίες έχουμε ήδη δει, να πάει και να εξερευνήσετε τα δένδρα. Θα μπορούσε να το κάνει με τον τρόπο που εγώ ακριβώς έκανε, σε βάθος αναζήτηση πρώτα, κατεβαίνοντας όσο μπορούμε μέχρι να χτύπησε ένα φύλλο, και στη συνέχεια επιστρέφουν επάνω, και πηγαίνει δεξιά πίσω κάτω. Ή θα μπορούσαμε να κάνουμε ό, τι είναι που ονομάζεται αναζήτηση πρώτα κατά πλάτος. Θα μπορούσαμε να αυξήσουμε τα πάντα στην κορυφή, και στη συνέχεια πάντα μια γραμμή κάτω από αυτό, και στη συνέχεια πάντα μια γραμμή κάτω από αυτό. Αυτά τα δένδρα αναζήτησης είναι θεμελιώδους σημασίας για την AI. Αλλά δεν παίρνουν αρκετά σωστό όλη την ώρα. Στην πραγματικότητα, σε πολλές από τις περιπτώσεις ότι ενδιαφερόμαστε πραγματικά για την, θέλουμε να οικοδομήσουμε ένα δέντρο, αλλά δεν το κάνουμε πραγματικότητα πάρετε για να κάνει όλες τις αποφάσεις. 

Αυτές είναι καταστάσεις που ονομάζεται αντιμωλία αναζήτησης, επίσης γνωστό όπως το πώς να γράψει παίζοντας το παιχνίδι συστήματα και να πληρώνομαι για αυτό. Αλλά αυτά είναι τα είδη των συστημάτων όπου θα μπορούσε να πάρει για να επιλέξετε όταν πάω από Βοστόνη, ποια πόλη θα πάω στο επόμενο. Αλλά μετά από αυτό, κάποιος άλλος θα μπορούσε να πάρει να πάρει την απόφαση για το πού θα πετάξει. Έτσι για να χτίσει αυτά είδη δομές, είμαστε θα πρέπει να λάβει μια ελαφρώς διαφορετική προσέγγιση σε αυτό. Εμείς δεν πρόκειται να είναι σε θέση να απλά αναζήτηση μέσω του δέντρου πια, γιατί δεν είμαστε αυτός που είναι στον έλεγχο καθενός από αυτά τα σημεία λήψης αποφάσεων. 

Ας φανταστούμε ένα απλό παιχνίδι όπως-tic tac-toe. Θα μπορούσα να ξεκινήσω με μια εντελώς κενό του σκάφους. Και σε tic-tac-toe, Χ παίρνει να παίξει το πρώτο. Και έτσι θα μπορούσα να σκεφτώ για όλα τα πιθανές κινήσεις που θα μπορούσε να κάνει Χ. Και αν εγώ είμαι αυτός παίζει ο Χ, αυτό είναι υπέροχο. Έχω εννιά κινήσεις που μπορώ να κάνω. Θα μπορούσα να βάλω ένα Χ σε κάθε μία αυτών των εννέα θέσεων. 

Και έπειτα από κάθε μία από αυτές, I θα μπορούσε να φανταστεί τι θα συμβεί στη συνέχεια. Λοιπόν, σε αυτή την περίπτωση, το άλλο παίκτης θα πάρει για να πάρει μια στροφή. O θα πάρει για να πάρει μια στροφή. Και από καθένα από αυτά, εκεί θα ήταν οκτώ διαφορετικές θέσεις O ότι θα μπορούσε να πραγματοποιηθεί δείκτη τους. 

Ας πούμε αποφάσισα ότι ήμουν πρόκειται να βάλει ένα Χ στο κέντρο. Αυτό φαίνεται όπως πάντα μια καλή κίνηση ανοίγματος. Θα μπορούσα να δούμε κάτω από αυτό, η οκτώ πιθανές κινήσεις που κάνει O. Τώρα, αν παίζω Χ, αυτό είναι υπέροχο. Παίρνω να επιλέξετε ποια μου πάνε, εκείνο στη μέση. Αλλά τώρα O παίρνει για να διαλέξετε. Και δεν έχω τον έλεγχο πάνω από την εν λόγω απόφαση. 

Όμως, από κάθε ένα από αυτά πιθανές θέσεις του σκάφους, υπάρχει τότε μια άλλη σύνολο των δυνατοτήτων. Όταν πρόκειται να είναι μου γυρίσει και πάλι, θα ήθελα να επιλέξετε και να πείτε, καλά, αν O κινείται μέσα στο, επίσης, το μεσαίο σημείο στα αριστερά, στη συνέχεια, Έχω μια σειρά από δυνατότητες όπου μπορώ να πάρω την επόμενη κίνησή μου. Από εκείνους, θα μπορούσε να εξετάσει το σύνολο των οι δυνατότητες κάτω από αυτά. Και τότε θα πάρει O να επιλέξει μεταξύ αυτών. 

Και θα μπορούσα να κρατήσει αυτό το κτίριο δέντρο έξω μέχρι να φτάσει στο σημείο όπου είτε κάποιος κερδίζει το game-- που είναι πήρε να θεωρηθεί ένα φύλλο node-- ή το διοικητικό συμβούλιο είναι εντελώς πλήρης και κανείς δεν έχει κερδίσει. Και αυτό είναι, επίσης, πρόκειται να είναι ένας κόμβος φύλλο. Αυτό πρόκειται να είναι μια ισοπαλία. 

Αλλά το δύσκολο πράγμα με αυτό είναι αν αυτό ήταν απλά μια κανονική αναζήτηση πρόβλημα, θα ήθελα να είναι σε θέση να ας πούμε, επίσης, το Χ πρέπει να πάτε εδώ. Και πρέπει να πάει O τρόπος εκεί. Και τότε το Χ πρέπει να πάτε εδώ. Και τότε θα πρέπει να πάει O τρόπος εκεί. Και τότε το Χ μπορεί να πάρει τρεις σε μια σειρά, και έχω κερδίσει. Και το παιχνίδι θα τελείωνε σε πέντε κινήσεις, τρία για μένα, δύο για τον αντίπαλό μου. Αλλά δεν είμαι πάντα να επιλέξουν αυτό. 

Έτσι, αντ 'αυτού, τι είμαστε θα πρέπει να κάνετε είναι θα πάμε να έχουν να έχουμε μια νέα στρατηγική. Και η στρατηγική που παιχνίδι-παιχνίδι αλγόριθμοι χρησιμοποιούν συχνά είναι ό, τι λέγεται minimax. Η κεντρική ιδέα της minimax είναι ότι είμαστε πρόκειται να πάρει την κίνηση που δίνει ο αντίπαλός μας το χειρότερο δυνατό σύνολο των κινήσεων που μπορούν να κάνουν. Δεν μου κάνει κανένα καλό για να επιλέξετε μια κίνηση όπου Θα μπορούσε να είναι σε θέση να κερδίσει μετά ότι, επειδή ο αντίπαλός μου δεν είναι πρόκειται να μου δώσει αυτή την ευκαιρία. Θα πάμε για να επιλέξετε κάποια τρομερό αποτέλεσμα για μένα. Έτσι, Πάω να κάνει το κίνηση που αναγκάζει τον αντίπαλό μου να κάνουμε κάτι καλύτερο για μένα. Εντάξει. Ας δούμε πώς αυτό παίζει έξω. Τόσο εδώ είναι ο αλγόριθμος μας σε ψευδοκώδικα. Εμείς πάμε για να δημιουργήσουν ολόκληρο το δέντρο του παιχνιδιού. Εμείς πάμε για να χτίσει ολόκληρη η δομή. Και τότε θα πάμε μέσα. Και στο κάτω μέρος σε κάθε ένα από τα τερματικών κόμβων, σε καθένα από τα φύλλα, θα αξιολογήσει πώς πολύτιμο είναι αυτό για μένα; Και θα πάμε να τα πράγματα αξίας που είναι καλό για μένα ως θετική. Πράγματα που δεν είναι καλό για μένα θα είναι λιγότερο θετική, ή μηδενική, ή ακόμη και αρνητική. 

Έτσι, σε tic-tac-toe, ίσως μια νίκη για μένα είναι καλό. Αυτό είναι ένα. Και μια ισοπαλία είναι μηδέν. Και κάτι που είναι μια απώλεια για μένα, ίσως αυτό είναι αρνητική. Το μόνο που έχει σημασία είναι ότι το καλύτερο είναι για μένα, τόσο μεγαλύτερη είναι η βαθμολογία που λαμβάνει. Από τις δυνατότητες αυτές κατά τη κάτω, τότε εμείς θα φιλτράρει τα πάνω. Και όταν έρθει η ευκαιρία μου για να επιλέξετε ανάμεσα σε μια σειρά από εναλλακτικές λύσεις, Θα επιλέξετε αυτό που είναι πήρε την υψηλότερη βαθμολογία. 

Και κάθε φορά που αυτό είναι μου αντιπάλους γυρίσει για να επιλέξετε, Θα υποθέσουμε ότι πρόκειται να επιλέξετε το ένα με το χαμηλότερο σκορ. Και αν το κάνω αυτό σε όλη τη διαδρομή μέχρι την κορυφή του δέντρου, Θα επιλέξετε ένα μονοπάτι που δίνει μένα το καλύτερο αποτέλεσμα που μπορώ να πάρω, υποθέτοντας ότι ο αντίπαλός μου κάνει όλες τις σωστές κινήσεις. 

Εντάξει, οπότε ας δούμε Αυτό στην πράξη για πρώτη φορά. Και τότε θα είστε πραγματικά δούμε τον κώδικα για αυτό. Φανταστείτε λοιπόν έχω αυτό το μεγάλο δέντρο. Και τώρα είμαι δεν παίζει Tic-Tac-toe. Ήθελα να σας δώσω κάτι λίγο πιο πλούσια. Έτσι έχω κάποιο παιχνίδι όπου υπάρχουν πολλές διαφορετικές βαθμολογίες ότι θα μπορούσα να έχω στο τέλος. Και γι 'αυτό οικοδομήσουμε πλήρες δέντρο. Και έχω να προχωρήσουμε πρώτα. Είμαι στη ρίζα του δέντρου. 

Και έχω να επιλέξετε that-- ώστε να πάρω να μεγιστοποιηθεί σε όλη αυτή την πρώτη κόμβο. Και τότε ο αντίπαλός μου παίρνει για να πάει. Και τότε έχω να πάω για μια ακόμη φορά. Έτσι, κάτω, στο τέλος, έχω ένα σύνολο δυνατότητες που μπορώ να επιλέξουν από, διαφορετικές τερματικές καταστάσεις του παιχνιδιού. Αν είμαι κάτω από το γεγονός ότι άκρα αριστερά γωνία, και βλέπω ότι έχω μια επιλογή μεταξύ οκτώ, επτά, και δύο, καλά, εγώ είμαι αυτός που παίρνει για να διαλέξετε. Έτσι, Πάω να επιλέξετε το καλύτερο ένα από αυτά. Πάω να επιλέξετε το οκτώ. 

Έτσι ξέρω ότι αν έχω ποτέ πιάσουμε αυτό το σημείο, Θα είμαι σε θέση να πάρει ότι οκτώ σημεία. Αν καταλήγω στο επόμενο σημείο πάνω, το επόμενο κόμβο πάνω, εννέα, ένα, ή έξι, καλά, είμαι πρόκειται να επιλέξουν το καλύτερο από αυτούς. Θα επιλέξω το εννέα. Αν έχω μια επιλογή μεταξύ δυο, και τέσσερις, και ένα, Θα επιλέξω το τέσσερα, το υψηλότερο. 

Τώρα, αν εξετάσουμε το επίπεδο ανωτέρω συνάγεται ότι, ο αντίπαλός μου είναι το ένα παίρνει να κάνουμε αυτή την επιλογή. Έτσι, ο αντίπαλός μου παίρνει να επιλέξουν, θέλω να του δώσω το πράγμα που συμβαίνει να τον πάρει οκτώ σημεία, ή μπορώ να του δώσω το πράγμα που είναι πρόκειται να του δώσει εννέα βαθμούς, ή το πράγμα που συμβαίνει να του δώσει τέσσερα σημεία; Και ο αντίπαλός μου, είναι ορθολογική, πρόκειται να επιλέξει το ελάχιστο από αυτά, πρόκειται να επιλέξετε το τέσσερα. 

Και μπορώ να το κάνω αυτό μέσω ολόκληρου του δέντρου. Μπορώ να πάω κάτω σε αυτό μεσαίο σετ των τριών. Και μπορώ να επιλέξω μεταξύ ένα, τρία και πέντε. Και έχω να διαλέξετε. Έτσι μπορώ να επιλέξω πέντε. Μπορώ να επιλέξω τρεις, εννιά, ή δύο. Παίρνω να επιλέξετε, ώστε να μπορώ να επιλέξω το εννέα. Έξι, πέντε, ή δύο, μπορώ να επιλέξω. Παίρνω να επιλέξετε το έξι. Επίπεδο πάνω από αυτό, ποιος θα επιλέξει; Ποιος παίρνει να επιλέξω; Ο άλλος τύπος, ο αντίπαλός μου. Έτσι, επιλέγουν από πέντε, εννέα, ή έξι, ποια; 

Κοινό: Οι πέντε. 

ΟΜΙΛΗΤΗΣ: Μπορούν να επιλέξουν το πέντε. Παίρνουν να επιλέξουν το ελάχιστο. Και στη συνέχεια η τελευταία, επιλέξουν μία, δύο ή τρία. Παίρνω να επιλέξετε, ώστε να μπορώ να επιλέξω τρεις. Εννέα, επτά, ή δύο, μπορώ να επιλέξω εννέα. Και 11, έξι ή τέσσερα, έχω επιλέξει 11. Ο αντίπαλός μου επιλέγει στη συνέχεια, τρεις, εννέα, ή 11, επιλέγει το ελάχιστο. Μου δίνει τρεις. Και στη συνέχεια, τέλος, στην κορυφή του το δέντρο, να πάρω για να επιλέξετε ξανά. Και έχω να επιλέξουν μεταξύ τεσσάρων, πέντε, ή τριών. Γι 'αυτό πάρτε το πέντε. 

Αν έχω να ελέγχει τα πάντα, είχα πάρτε το μονοπάτι που οδηγούσε στο 11. Αλλά δεν έχω να κάνουμε αυτή την επιλογή. Αν πάω σε αυτή την κατεύθυνση. Ο αντίπαλός μου θα με αναγκάσει να η επιλογή που οδηγεί σε τρία. Έτσι, το καλύτερο που μπορώ να κάνω είναι να λάβουν την μέση υποκατάστημα, κάνει αυτή την επιλογή, που είναι τελικά πρόκειται να με οδηγήσει σε πέντε σημεία. Αυτό είναι που κάνει minimax. 

Εντάξει. Ας ρίξουμε μια ματιά σε αυτό. Έτσι, εδώ στο CS50 IDE είναι ένα πρόγραμμα που υλοποιεί minimax να παίξει tic-tac-toe. Εμείς πάμε για να χτίσει μέχρι μια παράσταση. Εμείς πάμε για να έχουμε δύο opponent-- ή δύο παίκτες, ο υπολογιστής μας player και ένα ανθρώπινο παίκτης. Νούμερο ένα παίκτης θα παίζει η O. Αυτό θα είναι ο παίκτης του μηχανήματος. Παίρνουν για να μετακινήσετε το δεύτερο. Και ο άλλος παίκτης, μας ανθρώπινης αναπαραγωγής, θα είναι Χ 

Και για να κάνουν τη ζωή μου λίγο απλό, Πάω να επισημαίνουν ότι η συσκευή αναπαραγωγής αρνητική. Γι 'αυτό μπορεί να πολλαπλασιαστεί μόνο με αρνητικό να ανταλλάξουν μεταξύ ενός παίκτη και το άλλο. Εντάξει, οπότε ας ρίξουμε μια ματιά τι είμαστε πραγματικά πρόκειται να κάνει. Εμείς πάμε για να καθορίσει το γραφείο μας. Είναι πρόκειται να είναι, καλά, θα πάμε να επιτρέπουν να είναι τρία επί τρία, ή μπορούμε να παίξουμε ακόμα πέντε επί πέντε ή επτά από επτά-tic tac-toe, αν θέλετε παρόμοια, με βάση κάποια διάσταση D. 

Και θα έχουμε ένα ζευγάρι των βοηθητικών λειτουργιών ότι θα κάνουμε τα πράγματα όπως προετοιμάσει το screen-- ή συγγνώμη, προετοιμαστεί μεταβλητές μας, καταργήστε την επιλογή οθόνη, καταρτίζει το διοικητικό συμβούλιο στην οθόνη, μία που ελέγχει ένα διοικητικό συμβούλιο για να δούμε εάν ή όχι υπάρχει ένας νικητής, μια που αναλύει μέσω της γραμμής εντολών, απλά για να βοηθήσει, αυτός που διαβάζει εισόδου, και μία λειτουργία που ονομάζεται minimax. Και αυτό είναι το ένα θα ενδιαφέρουν περισσότερο. Αλλά ας δούμε πρώτα το κύριο. 

Τι κάνουμε? Λοιπόν, θα πάμε να αναλύσει γραμμής εντολών μας, απλά διαβάστε και δείτε ό, σκάφους διάσταση θα θέλαμε να έχουμε. Θα προετοιμάσει σκάφους μας. Και τότε θα μπει σε μια μεγάλα άγρια ​​βρόχο, επανειλημμένα αποδεχθεί κινήσεις έως ότου το παιχνίδι είναι κέρδισε, ή είναι να μην υπάρχουν κινήσεις αριστερά. Κάθε φορά που περνάμε ότι βρόχου, θα καθαρίσετε την οθόνη. Θα επιστήσω την πλακέτα πάνω στην οθόνη. Και είμαστε σκόπιμα το είδος του υδροληψίες αυτά τα μακριά ως υπορουτίνες, έτσι ώστε να μην χρειάζεται να ανησυχείτε πάρα πολύ σχετικά με τις λεπτομέρειες για το πώς θα συμβεί. 

Θα έχετε τον κωδικό αργότερα σήμερα. Και αν θέλετε να κοιτάξετε μέσα και να μάθετε, μπορείτε να τα δείτε όλα. Αλλά θα συντάξει έναν πίνακα στην οθόνη. Και τότε θα ελέγξει και Βλέπετε, έχουμε έναν νικητή; Έχει κάποιος κερδίσει αυτό το παιχνίδι; Αν έχουν, θα εκτυπώσετε έξω ένα μήνυμα νίκης. Και θα τελειώσει το παιχνίδι. 

Επίσης, θα ελέγχει και να δούμε αν υπάρχει μια ισοπαλία. Θα είναι εύκολο να δούμε αν υπάρχει ισοπαλία. Αυτό σημαίνει ότι όλοι οι χώροι είναι πλήρεις, αλλά δεν έχει υπάρξει ακόμη ένας νικητής. Μπορούμε να δηλώσουμε μια γραβάτα και να γίνει. Στη συνέχεια, η πραγματική meat-- αν Είναι ένας παίκτης της μηχανής, θα επιτρέψουμε μηχάνημα αναπαραγωγής για αναζήτηση μέσω της χρήσης αυτόν τον αλγόριθμο minimax, να βρούμε την καλύτερη κίνηση που μπορεί. Και τότε θα βάλουμε αυτή τη κίνηση επάνω. 

Διαφορετικά, αν είναι ένα ανθρώπινο παράγοντα, θα διαβάσετε κάποια στοιχεία από τον άνθρωπο. Και στη συνέχεια, αν είναι ο άνθρωπος παίκτης ή ο παίκτης μηχανή, θα κάνουμε μια μικρή ζευγάρι bits έλεγχο σφαλμάτων, βεβαιωθείτε ότι παραμένει εντός των ορίων των πραγματικών διαστάσεων του διοικητικού συμβουλίου ότι έχουμε, βεβαιωθείτε ότι ο χώρος είναι κενός, που βάζουν ένα κανενός κομμάτι εκεί ήδη. Και τότε θα βάλουμε μόνο ένα κομμάτι στο διοικητικό συμβούλιο, αλλάξετε τον παίκτη στο επόμενο επίπεδο, και αυξήσετε πόσες κινήσεις έχουν συμβεί. 

Αυτό είναι το κύριο βρόγχο για μας παιχνίδι tic-tac-toe. Minimax, στη συνέχεια, είναι ακριβώς ο αλγόριθμος που έχουμε πριν. Η μόνη προσαρμογής που κάναμε έτσι ώστε να μπορέσουμε μπορεί να παίξει υψηλότερα διαστάσεων πίνακες είναι έχουμε διατηρείται αυτό το επιπλέον παράμετρο που ονομάζεται βάθος. Και το βάθος ακριβώς λέει, αν είμαι αναζήτηση προς τα κάτω μέσα από εκείνο το δέντρο και παίρνω μέχρι τώρα κάτω πέρα από κάποιο βάθος επίπεδο ότι εγώ απλά δεν θέλουν να προχωρήσουμε περαιτέρω, Πάω να σταματήσει και απλά αξιολογεί το διοικητικό συμβούλιο σε εκείνο το σημείο. Θα ελέγχουν και να δούμε αν υπάρχει ένας νικητής. Αν υπάρχει ένας νικητής, θα τα επιστρέψει. Διαφορετικά, θα πάω μέσα από ένα βρόχο. Και εγώ θα πω, για το σύνολο των οι πιθανές θέσεις ότι θα μπορούσε ενδεχομένως να λαμβάνει ως κίνηση μου, εγώ θα οικοδομήσουμε ένα υποθετικό Διοικητικό Συμβούλιο που περιλαμβάνει την κίνησή μου σε αυτό το συμβούλιο, και στη συνέχεια καλεί αναδρομικά minimax. 

Αν είναι κίνησή μου, να πάρω για να βρείτε το ένα που πήρε το μεγαλύτερο σκορ. Αν είναι κίνηση του αντιπάλου μου, θα βρούμε αυτός που πήρε την ελάχιστη βαθμολογία. Και όλα τα άλλα είναι ακριβώς τήρηση αρχείων. Εντάξει, οπότε ας δούμε αυτήν την κίνηση. Στην πραγματικότητα, ίσως μπορούμε να πάρετε ένα ζευγάρι των εθελοντών να έρθει και να παίξει tic-tac-toe. [Δεν ακούγεται] ένα, και ένα Επιπλέον, δύο, ακριβώς εκεί. Έλα επάνω. 

Ας πάμε μπροστά και να Ξεκινήστε αυτό το εντελώς. Έτσι, γεια. 

Κοινό: Γεια σου. 

ΟΜΙΛΗΤΗΣ: Ποιο είναι το όνομά σου; 

Κοινό: Gorav. ΟΜΙΛΗΤΗΣ: Gorav. 

Κοινό: Είμαι Layla. 

ΟΜΙΛΗΤΗΣ: Και Layla, και Layla, συγγνώμη. Έλα επάνω. Gorav, θα πάμε για να έχετε πάει πρώτα. Και είμαι πρόκειται να σας ζητήσω να είναι όχι τρομερά καλός παίκτης-tic tac-toe. Εντάξει, έτσι ώστε όλη η πίεση είναι μακριά σε σας. Ας δούμε, όμως, ότι το μηχάνημά μας παίκτης μπορεί να κάνει πραγματικά κάτι έξυπνο. Έτσι πάει μπροστά. Θα πάμε για να πληκτρολογήσετε την οποία συντονίζει θα ήθελα να θέσω το Χ σας. A0, εντάξει, και το μηχάνημα έχει πάει αμέσως και να θέσει τη σφραγίδα του στην Α1. 

Βάλτε το O στο διοικητικό συμβούλιο. Εντάξει, τώρα πάμε μπροστά. Πού θα θέλατε να πάτε? C2. Μηχάνημα παίκτης μας έχει λάβει το μεσαίο τετράγωνο, θα μπλοκάρει. Έτσι, αυτό ήταν ένα καλό, έξυπνο πράγμα για να το κάνετε. Έχετε μπλοκάρει. Αυτό είναι εξαιρετικό. Θα εκτελεί το κόρνερ εκεί. 

Και πρόκειται να σας αναγκάσει να να λάβει το ένα τελευταίο διάστημα, B0. Και το παιχνίδι τελειώνει με ισοπαλία. Αλλά έπαιξε ένα εύλογο παιχνίδι εναντίον σας, έτσι δεν είναι; Εντάξει, ευχαριστώ πολύ, Gorav. 

[ΧΕΙΡΟΚΡΟΤΉΜΑΤΑ] 

Εντάξει, Layla, θα πάμε μέχρι το παιχνίδι για εσάς εδώ. 

Κοινό: Ωραία. 

ΟΜΙΛΗΤΗΣ: Εμείς πάμε για να δώσει Σας τέσσερις από τέσσερις-tic tac-toe. Τώρα, σε τέσσερις από τέσσερις, έχετε να κερδίσετε με τέσσερα στη σειρά, όχι τρία στη σειρά. Και είναι όλα δικά σας. Έτσι Layla πήραν Δ1. Αυτή τη στιγμή, πρόκειται να ακολουθήσουν υπολογιστή παίκτης μας εδώ. Τρεις από τρεις-tic tac-toe είναι το είδος πράγμα που είναι εύκολο για όλους μας. Αλλά είναι ωραίο να βλέπεις το υπολογιστή παίκτη που θα κάνει έξυπνες κινήσεις. Τέσσερις από τέσσερις παίρνει να να είναι λίγο πιο περίπλοκη. 

Όμορφα γίνει. Εντάξει, έτσι ώστε Layla τερμάτισε μακριά. Ω, και θα πρέπει να έχουν τελειώσει εκεί. Αλλά ας κάνουμε ένα ακόμη εδώ. Έτσι Layla, σας ευχαριστώ. Όμορφα γίνει. 

[ΧΕΙΡΟΚΡΟΤΉΜΑΤΑ] 

Έτσι,-tic tac-toe μας παίκτης πηγαίνει μέσα και βρίσκει θέσεις, λύνει τους χρήση αυτής της minimax. Και είχα μια ρύθμιση βάθους σε αυτό, έτσι ώστε να Δεν θα τρέξει πολύ γρήγορα, η οποία είναι πιθανώς γιατί Layla ήταν σε θέση να πάει όμορφα μπροστά όπως έκανε και το έκανε πολύ καλά. Αλλά αυτά τα συστήματα που απλά να περάσει και ωμής βίας πάμε βαθύτερα, και πιο βαθιά, και πιο βαθιά, και να κρατήσει την εξεύρεση της λύσης ότι χρειάζεται, αυτά τα είδη των συστημάτων είναι αρκετά επιτυχής σε αυτά, καλά, πρότυπο επιτραπέζια παιχνίδια. 

Και στην πραγματικότητα, αν δούμε μια τρία επί τρία παιχνίδι tic-tac-toe, Αυτό είναι βασικά μια λυθεί το πρόβλημα. Και αυτό είναι ένα υπέροχο διάγραμμα από Randall Munroe σε XKCD, δείχνοντας τα οποία κινούνται θα πρέπει να λάβει, δεδομένου κινήσεις του αντιπάλου σας. Αυτό είναι κάτι που θα μπορούσαμε να εύκολα καθορίσετε μπροστά από το χρόνο. Αλλά τι συμβαίνει και να έχουμε περισσότερες περίπλοκα παιχνίδια, πιο περίπλοκα παιχνίδια, όπου υπάρχουν μεγαλύτερες πίνακες, περισσότερα δυνατότητες, βαθύτερη στρατηγική; 

Αποδεικνύεται ότι αυτό ωμής βίας αναζήτηση ακόμα κάνει αρκετά καλά, με εξαίρεση όταν φτάσετε στο σημείο όπου αυτό το δέντρο είναι τόσο μεγάλο ότι δεν μπορείτε να το εκπροσωπεί όλους. Όταν δεν μπορείτε να υπολογίσετε ολόκληρο το δέντρο, όταν δεν μπορείτε να πάτε προς τα εμπρός και ώθησης τον εαυτό σας με το σημείο όπου έχετε πάρει ολόκληρο το δέντρο στη μνήμη, ή αν μπορείτε να το πάρετε στη μνήμη και θα είναι ακριβώς να σας πάρει πάρα πολύ καιρό να ψάξετε μέσα αυτό, θα πρέπει να κάνουμε κάτι πιο έξυπνο. 

Για να το κάνετε αυτό, Πρέπει να κάνουμε δύο πράγματα. Κατ 'αρχάς, θα πρέπει να βρείτε μερικά τρόπο τον περιορισμό του βάθους σας. Λοιπόν, αυτό είναι εντάξει. Μπορούμε να βρούμε κάποια ωραία, ελάχιστο και να πω, το μόνο που μπορεί να πάει τόσο βαθιά. Αλλά όταν το κάνετε αυτό, θα σημαίνει ότι έχουν αυτά εν μέρει ελλιπείς πίνακες. Και θα πρέπει να επιλέξετε, μου αρέσει Αυτό εν μέρει ελλιπή διατροφή, ή αυτό εν μέρει ατελές σύστημα; 

Και στις τέσσερις από μας τέσσερις παιχνίδι tic-tac-toe, παίκτης του υπολογιστή μας πήρε τα κάτω προς τα κάτω και είπε, Έχω δύο διαφορετικές σανίδες. Ούτε το ένα είναι μια νίκη. Ούτε το ένα είναι μια απώλεια. Ούτε το ένα είναι μια ισοπαλία. Πώς μπορώ να επιλέξω μεταξύ τους; Και δεν έχουν έξυπνος τρόπος για να γίνει αυτό. 

Βλέπουμε αυτό το είδος του αξιολόγηση συμβαίνουν όλη την ώρα όπως έχουμε μπει σε πιο πολύπλοκα παιχνίδια. Το σκάκι είναι ένα μεγάλο παράδειγμα. Στο σκάκι, έχουμε, πρώτο απ 'όλα, ένα μεγαλύτερο πλοίο. Έχουμε πολύ περισσότερα κομμάτια. Και η τοποθέτηση αυτών των τεμαχίων και ο τρόπος που αυτά τα κομμάτια κινούνται είναι εξαιρετικά σημαντική. Έτσι, αν θέλω να χρησιμοποιήσω minimax, Πρέπει να είμαι σε θέση να προσδιορίσει και να πω, το συμβούλιο, όπου κανείς δεν έχει κερδίσει ή χάσει ακόμα, είναι κάπως καλύτερη από αυτή άλλων του σκάφους, όπου κανείς δεν έχει κερδίσει ή χάσει. 

Για να το κάνετε αυτό, θα μπορούσα να κάνω τα πράγματα όπως θα μπορούσε απλώς να μετράνε πόσα κομμάτια έχω και πόσα κομμάτια έχετε; Ή θα μπορούσε να δώσει διαφορετικά κομμάτια διαφορετικά σημεία. Βασίλισσά μου αξίζει 20 πόντους. Πιόνι σας αξίζει ένα σημείο. Ποιος έχει περισσότερους πόντους συνολικά; Ή θα μπορούσε να εξετάσει τα πράγματα όπως, ο οποίος πήρε την καλύτερη θέση του σκάφους; Ποιος έχει σειρά το επόμενο, κάτι που μπορώ να χρειάζεται να αξιολογηθεί με μεγαλύτερη ακρίβεια η οποία από αυτές τις δυνατότητες είναι καλύτερα χωρίς εξετάζει διεξοδικά κάθε κίνηση που θα μπορούσε να έρθει μετά από αυτό. 

Τώρα για να κάνουμε αυτή την εργασία, ένα από τα πράγματα που είναι πρόκειται να γίνει πραγματικά σημαντικό για μας δεν είναι απλά κινείται ευθεία κάτω σε ένα συγκεκριμένο βάθος όριο, αλλά να είναι σε θέση να πει, μία από αυτές τις ιδέες που έχουν είναι τόσο κακή ώστε να είναι Δεν αξίζει να εξεταστεί όλους τους πιθανούς τρόπους ότι τα πράγματα μπορούν να πάνε από το κακό στο χειρότερο. Για να το κάνετε αυτό, θα προσθέσουμε σε minimax μια αρχή που ονομάζεται βήτα-ΑΓΑ. Και άλφα-βήτα, λέει, εάν έχετε μια κακή ιδέα, μην σπαταλάτε το χρόνο σας προσπαθώντας να μάθετε ακριβώς πόσο κακό είναι. 

Τόσο εδώ είναι τι θα πάμε να κάνουμε. Εμείς πάμε για να πάρει το ίδιο αρχές που είχαμε πριν, το ίδιο είδος minimax της αναζήτησης, μόνο είμαστε θα παρακολουθεί, όχι μόνο η πραγματικές τιμές που έχουμε, αλλά θα να παρακολουθείτε τον καλύτερο δυνατό τιμή που θα μπορούσα να πάρω, Και το χειρότερο δυνατό έκβαση θα μπορούσα να έχω. Και κάθε φορά που το χειρότερο δυνατό πράγμα που ψάχνει πιθανό, Θα εγκαταλείψει το μέρος του δέντρου. Και εγώ δεν θα καν στον κόπο κοιτάζοντας αυτό πια. 

Εντάξει, έτσι φαντάζομαι ότι θα αρχίσουμε με την ίδια ακριβώς δέντρο παιχνίδι. Και τώρα θα πάμε για να πάει και πάλι, σε όλη τη διαδρομή προς τα κάτω της εν λόγω κάτω αριστερή γωνία. Και σε αυτή την κάτω αριστερή γωνία, μας εξετάσουμε και να αξιολογήσουμε αυτόν τον πίνακα. Ίσως είναι μια τέσσερις από τέσσερις-tic tac-toe του σκάφους, ή ίσως είναι μια σκακιέρα. Αλλά το δούμε και να αξιολογήσουμε αυτό, και παίρνουμε μια τιμή των οκτώ. 

Σε εκείνο το σημείο, γνωρίζουμε ότι πρόκειται να πάρει τουλάχιστον οκτώ βαθμούς από αυτό το κατώτατο απόφαση. Δεν έχει σημασία τι το άλλο δύο είναι, ότι επτά και δύο. Θα μπορούσαν να είναι οποιεσδήποτε τιμές ήθελαν να είναι. Εμείς πάμε για να πάρει τουλάχιστον οκτώ σημεία. Εντάξει, αλλά θα μπορούσαμε να να προχωρήσει και να ελέγξει. Ίσως ένας από αυτούς είναι καλύτερο από οκτώ. 

Προσβλέπουμε σε επτά. Είναι ότι καλύτερο από οκτώ; Όχι, αυτό δεν αλλάζει τη γνώμη μας σε όλα. Εξετάζουμε δύο. Είναι ότι καλύτερο από οκτώ; Όχι, αυτό δεν αλλάζει τη γνώμη μας σε όλα. Έτσι τώρα ξέρουμε ότι έχουμε εξαντλήσει όλες τις δυνατότητες εκεί. Εμείς δεν πρόκειται να πάρει κάτι καλύτερο από οκτώ. Εμείς πάμε για να πάρει ακριβώς οκτώ. 

Και έτσι να αλλάξουμε αυτόν τον κόμβο και ας πούμε, ότι τώρα είναι μια βεβαιότητα. Εμείς ανεβείτε ένα επίπεδο πάνω από αυτό. Και τώρα ξέρουμε κάτι σχετικά με αυτό το επίπεδο ελαχιστοποίησης. Ξέρουμε ότι δεν πρόκειται ποτέ να πάρει πάνω από οκτώ σημεία, αν πάμε προς τα κάτω ότι κατεύθυνση. Διότι ακόμη και αν αυτοί άλλοι δύο κλάδοι αποδειχθεί να είναι φανταστική και αξίζει χιλιάδες σημεία το καθένα, ο αντίπαλός μας θα μας δώσει το ελάχιστο, και να μας δώσει τις οκτώ. Εντάξει, καλά, ας δούμε. Θα συνεχίσουμε σε αυτή την κατεύθυνση. Κατεβαίνουμε σε αυτή τη μεσαία στα αριστερά. Έχουμε κοιτάξει κάτω και να δούμε ότι υπάρχει μια εννέα. Ξέρουμε ότι θα πάμε για να πάρει τουλάχιστον εννέα σημεία κατεβαίνοντας ότι μέση του δρόμου. Και σε αυτό το σημείο, μπορούμε απλά να διακόψετε. Και μπορούμε να πούμε, κοιτάξτε, εγώ γνωρίζουν το επίπεδο παραπάνω, Πάω να πάρει όχι περισσότερο από οκτώ σημεία με τη μετάβαση προς αυτή την κατεύθυνση. Αλλά αν πήγα κάτω από τη μέση μονοπάτι αντί του αριστερού μονοπάτι, Θα ήθελα να πάρει τουλάχιστον εννέα σημεία. 

Ο αντίπαλός μου δεν πρόκειται ποτέ να επιτρέψτε μου να ακολουθήσουμε αυτή την μέση οδό. Παίρνουν να επιλέξουν. Και θα πάμε για να επιλέξετε το μονοπάτι προς τα αριστερά προς τα οκτώ, και όχι κάτω από τη μέση προς τι είναι τουλάχιστον εννέα σημεία. Έτσι, σε αυτό το σημείο, θα σταματήσω. Και εγώ θα πω, ξέρετε τι; Δεν έχω να εξετάσουμε πιο κάτω προς αυτή την κατεύθυνση. Επειδή ποτέ δεν πρόκειται να φτάσουμε εκεί. 

Μπορώ να υπερπηδήσει αυτό το ένα, και μπορώ να υπερπηδήσει αυτό το έξι, γιατί αυτό δεν πρόκειται να συμβεί. Γι 'αυτό θα πάει κάτω και θα να εξετάσει τη δυνατότητα επόμενη. Πάω εκεί κάτω και λέω, βλέπω ένα δύο. Ξέρω ότι αν έχω να εδώ, είμαι πρόκειται να πάρει τουλάχιστον δύο. ΕΝΤΆΞΕΙ. Συνεχίζω. Βλέπω ένα τέσσερα. Ξέρω ότι πρόκειται να πάρει τουλάχιστον τέσσερις. Υπάρχει ακόμα μια πολύ μεταξύ τεσσάρων και οκτώ, όμως. Γι 'αυτό και συνεχίζω. Κοιτάζω κάτω και βλέπω ότι υπάρχει ένα. Εντάξει, ξέρω ότι αν Έχω πάει σε αυτό το μονοπάτι, Πάω να είναι σε θέση να επιλέγουν τα τέσσερα. Τι αντίπαλός μου πρόκειται να κάνει; Μεταξύ κάτι που μου δίνει οκτώ, κάτι που μου δίνει τέσσερα, και κάτι που μου δίνει τουλάχιστον εννέα, καλά, ότι πρόκειται να μου δώσει το τέσσερα. Και ξέρω τώρα στο κορυφή, Πάω να είναι σε θέση να πάρει τουλάχιστον τέσσερα σημεία έξω από αυτό το παιχνίδι. 

Η όλη ιδέα της άλφα-βήτα είναι να κόψει το δέντρο μέρη έτσι ότι εγώ δεν τα βλέπω πια. Αλλά εξακολουθεί να μοιάζει έχω πάει κοιτάζοντας πολλά δέντρου. Ας συνεχίσουμε προς τα κάτω. Θα πάμε κάτω από το επόμενο τώρα. Κάτω, στο τέλος, να βρω ένα ένα. Ξέρω ότι πρόκειται να πάρει τουλάχιστον ένα. Θα συνεχίσετε να ψάχνετε. 

Θεωρώ τριών. Ξέρω ότι πρόκειται να πάρει τουλάχιστον τρεις. Συνεχίζω. Βρίσκω πέντε. Ξέρω ότι πρόκειται να πάρει πέντε αν πιάσουμε σε αυτό το μονοπάτι. Και ξέρω επίσης, στη συνέχεια, ότι ο αντίπαλός μου, αν μου επιλέξετε το μεσαίο του οι τρεις μεγάλες επιλογές, ότι πρόκειται να μου δώσει κάτι που είναι πέντε ή λιγότερο. 

ΕΝΤΆΞΕΙ. Μπορώ να συνεχίσω εκεί. Μπορώ να κοιτάξει κάτω και εγώ μπορεί να πει, τι θα πάω να πάρει, αν πάω κάτω από τη μέση οδό; Πάω να πάρει, επίσης, τρεις εκεί. Πάω να πάρω κάτι αυτό είναι τουλάχιστον τρεις. Υπάρχουν ακόμα πράγματα μεταξύ τριών και πέντε, γι 'αυτό συνεχίστε να ψάχνετε. Αχ, εννέα, θα είμαι σίγουρα θεωρήσει ότι κατά τη διάρκεια των τριών. Πάω να πάρει τουλάχιστον εννέα αν ακολουθήσουμε αυτή την μέση οδό. 

Τώρα ο αντίπαλός μου σταματάει και λέει, κοιτάξτε, δεν υπάρχει λόγος πια. Ξέρω ότι μου ελαχιστοποίηση του αντιπάλου, αυτός είναι πρόκειται να μου δώσει το πράγμα που είναι μικρότερη ή ίση με πέντε, παρά το πράγμα που είναι μεγαλύτερο από ή ίσο με εννέα. Έχω σταματήσει. Δεν το βλέπω πια σε αυτό. Συνεχίζω. 

Κοιτάζω προς τα κάτω σε αυτό το σημείο. Στο κάτω μέρος, βρίσκω έξι. Ξέρω ότι πρόκειται να πάρει τουλάχιστον έξι. Και τι μπορώ να κάνω; Μπορώ να σταματήσω. Επειδή υπάρχει μια επιλογή μεταξύ κάτι που είναι τουλάχιστον έξι και κάτι που είναι λιγότερο από πέντε, αυτός είναι πρόκειται να μου δώσει το πράγμα Αυτό είναι λιγότερο από πέντε. Και τώρα ξέρω Πάω για να πάρει ακριβώς εκείνη την επιλογή. Πάω να πάρει αυτή την επιλογή πέντε. 

Έχω πάει πίσω μέχρι την κορυφή. Ποια θα πάω να επιλέξετε ανάμεσα σε κάτι που είναι μεγαλύτερο από ή ίσο με τέσσερα, ή κάτι που είναι ίσο με πέντε; Πάω να πάρει κάτι ότι είναι τουλάχιστον πέντε. Έχω πάει κάτω το τελευταίο μονοπάτι, όλα ο τρόπος προς τα κάτω. Υπάρχει ένα. Εντάξει, τουλάχιστον Πάω να πάρετε ένα σημείο. Συνεχίζω. Δύο, OH, ότι είναι καλύτερα από ένα. Πάω να πάρει τουλάχιστον δύο. Θεωρώ τριών. Ξέρω ότι πρόκειται να πάρω τρεις. 

Και το σημείο ανωτέρω συνάγεται ότι, ο αντίπαλός μου θα να μου δώσει κάτι που είναι μικρότερη ή ίση προς τρία. Και τώρα μπορώ να σταματήσω. Επειδή η επιλογή μεταξύ μένα είναι είναι σε θέση να πάρει ένα πέντε και ο αντίπαλός μου που μου έδωσε κάτι λιγότερο από τρεις, Είμαι πάντα πρόκειται να πάρει ότι πέντε. Γι 'αυτό και δεν αξιολογούν ότι κάτω μέρος του δέντρου καθόλου. 

Τώρα, αυτό μπορεί να φαίνεται μικρό. Αλλά όταν μικρά κομμάτια της αριθμητικής, μεγαλύτερο και μικρότερο από, μπορεί να κοπεί μακριά ολόκληρα μέρη του Αυτό εκθετικά αυξανόμενη δέντρο, που οδηγεί σε ένα τεράστιο το ποσό της αποταμίευσης, αποταμίευση που είναι αρκετά μεγάλος ώστε I να αρχίσετε να παίζετε ανταγωνιστικά σε πιο πολύπλοκα παιχνίδια. 

Εντάξει, αν δούμε το μέγεθος και την πολυπλοκότητα των διαφορετικών παιχνιδιών, tic-tac-toe ήταν εύκολο το παράδειγμά μας. Έχουμε ένα μικρό διοικητικό συμβούλιο, τρία επί τρία. Παίρνουμε, το πολύ, κατά μέσο όρο περίπου τέσσερις διαφορετικές επιλογές καθώς περνάμε μέσα από το παιχνίδι. Έχουμε κάπου γύρω στις 10 με το πέμπτο δυνατόν διαφορετικά φύλλα. Και την οικοδόμηση μιας Tic-Tac-toe player, καλά, απλά το έκανε. Ειναι ευκολο. 

Αν πάμε μέχρι κάτι περισσότερο πολύπλοκες, όπως το Connect Four. Θυμάστε αυτό το παιχνίδι όπου ρίχνετε τα μικρά μάρκες μέσα; Είναι ένα από έξι επτά σκάφους, δεν είναι ότι πολύ μεγαλύτερη, ακόμα έχει περίπου την ίδια διακλάδωση παράγοντα-tic tac-toe. Έχω περίπου τέσσερις επιλογές όπου μπορώ να βάλω τα πράγματα στη. Αλλά τώρα, έχω πολλά περισσότερα οδηγεί, από 10 έως 21 ρεύματος. Αυτό είναι κάτι που είναι εύκολο αρκετά ώστε να το λύσουμε αμέσως. 

Ντάμα, τόσο περισσότερο θα complex-- πήρε οκτώ από οκτώ συμβούλιο. Είσαι μόνο για το ήμισυ των οποτεδήποτε, όμως. Έχετε μια διακλάδωση παράγοντα που είναι περίπου 2,8. Λοιπόν, έχουμε ένα ζευγάρι κινήσεις που μπορείτε να πάρετε. Έχετε περίπου 10 έως 31 φύλλα, μεγαλύτερα και μεγαλύτερα, και μεγαλύτερους χώρους. Όπως έχω να ψάξετε μέσα αυτές οι όλο και μεγαλύτερες χώρους, ότι όταν τα πράγματα όπως άλφα-βήτα και να είναι σε θέση να μειώσει μακριά ολόκληρο υποκαταστήματα καθίσταται απαραίτητη. 

Τώρα, πούλια ήταν αρκετά εύκολο, το 1992. Ένα πρόγραμμα υπολογιστή που ονομάζεται Chinook νικήσει τον κόσμο πούλια πρωταθλητής, Μάριον Tinsley. Και από τότε, κανένα ανθρώπινο κύριος παίκτης έχει ήταν σε θέση να νικήσει ο καλύτερος υπολογιστικά συστήματα. Αν κοιτάξουμε κάτι όπως το σκάκι, τώρα και πάλι, έχουμε οκτώ από οκτώ συμβούλιο. Αλλά έχουμε πολύ πιο σύνθετη κομμάτια, πολύ πιο πολύπλοκες κινήσεις. Έχουμε μια παράγοντας διακλάδωσης περίπου 35, 35 πιθανές κινήσεις κατά μέσο όρο ότι μπορώ να πάρω και μια κατάσταση χώρου, ένας αριθμός των φύλλων ότι καλλιεργούνται έως 10 στην 123η δύναμη, τεράστιους αριθμούς των δυνατοτήτων. 

Ακόμα και ακόμα, σύγχρονοι επεξεργαστές είναι σε θέση να το κάνουμε αυτό με επιτυχία. Το 1995 και, στη συνέχεια, το 1997, έναν υπολογιστή πρόγραμμα που ονομάζεται Deep Blue της IBM που χτίστηκε από ότι έτρεξε σε μια γιγαντιαία υπερυπολογιστή κερδίσει το σημερινό παγκόσμιο πρωταθλητή, Γκάρι Κασπάροφ. Αυτό ήταν ένα σημείο καμπής. Σήμερα, όμως, η ίδια επεξεργασία ισχύς βρίσκεται στο MacBook μου. 

Ταχύτητα επεξεργασίας διατηρεί να πάρει όλο και πιο γρήγορα. Μπορούμε να αξιολογήσει όλο και περισσότερο πλακέτες πιο γρήγορα και πιο γρήγορα. Αλλά το πιο σημαντικό, έχουμε την καλύτερη λειτουργίες και καλύτερη αξιολόγηση κλάδεμα μεθόδους. Έτσι, μπορούμε να ψάξουμε το χώρο πιο πολύπλοκα. Το μεγαλύτερο του διοικητικού συμβουλίου παιχνίδια που μπορούμε να σκεφτούμε, κάτι σαν Go που είναι πήρε ένα 19 με 19 του σκάφους, τώρα ξαφνικά, είμαστε πέρα ​​από το σημείο όπου υπολογιστικά συστήματα μπορούν να κερδίσουν. Δεν υπάρχει υπολογιστική σύστημα εκεί έξω ότι μπορεί να νικήσει έναν επαγγελματία παίκτη Go. Τα καλύτερα συστήματα σήμερα είναι περίπου κατάταξη το είδος της καλής ερασιτεχνικό επίπεδο. Έτσι, υπάρχει ακόμα αρκετά ένα κομμάτι από εκεί που δεν μπορείτε να πάρετε ακόμα. 

Εντάξει, αυτά παραδοσιακά επιτραπέζια παιχνίδια, Αυτά τα είδη των συστημάτων όπου οικοδομήσουμε αυτή την minimax, αν έχεις άλφα-βήτα ή όχι, αυτοί οι αλγόριθμοι λειτουργούν επειδή υπάρχουν ορισμένα εμπόδια. Έχουμε τέλεια πληροφόρηση για τον κόσμο. Ξέρουμε πού είναι όλα τα κομμάτια. Ο κόσμος είναι στατικός. Κανείς δεν παίρνει να κινηθεί η κομμάτια γύρω ενώ είμαι κάθεται εκεί σκέψης, λαμβάνοντας σειρά μου. Υπάρχει ένας χώρος δράσης που είναι διακριτές. Μπορώ να βάλω ενέχυρο μου εδώ, ή μπορώ να βάλω ενέχυρο μου εδώ. Δεν είμαι επιτρέπεται να τεθεί σε πιόνι μου η γραμμή μεταξύ των δύο τετραγώνων. 

Και τέλος, οι δράσεις είναι ντετερμινιστική. Ξέρω ότι αν πω, πύργος με τρία ιππότης, πύργος μου πρόκειται να καταλήξουν σε ιππότη τρεις, εφ 'όσον πρόκειται για μια έγκυρη κίνηση. Δεν υπάρχει καμία αβεβαιότητα σχετικά με αυτό. Τώρα, όπως πάω σε πιο διαφορετικά είδη παιχνιδιών, πρέπει να σπάσουμε αυτές τις υποθέσεις. 

Τι θα συμβεί αν πάω σε κάτι όπως κλασικά παιχνίδια βίντεο; Εδώ είναι μια επιλογή από βίντεο παιχνιδιών από το Atari 2600. Τι έχω εκεί πάνω; Έχω Frogger, Διάστημα Εισβολείς, Παγίδα, και Pac-Man. Τι είδους περιβάλλοντα έχω εδώ τώρα; Ποια από αυτές τις υποθέσεις έχω να σπάσει; 

Λοιπόν, αυτό εξαρτάται από το παιχνίδι. Θα μπορούσε να παίξει σκάκι για το 2600, και θα είναι ακριβώς όπως ήταν πριν. Για τα περισσότερα από αυτά τα συστήματα, υπάρχει πλήρη γνώση για τον κόσμο. Υπάρχει πλήρως ντετερμινιστική ενέργειες. Αλλά συνήθως, στον κόσμο δεν είναι πλέον στατική. Δηλαδή, ενώ κάθομαι εκεί αναμονής, κάτι κινείται. Τα φαντάσματα έρχονται να με πάρει. Ο σκορπιός ακολουθεί μου κάτω. Οι εισβολείς χώρο είναι έρχονται όλο και πιο κοντά. Πόσο καλά μπορούμε να κάνουμε από αυτά; 

Πριν από μερικά χρόνια, η Google είχε ένα έργο που ονομάζεται DeepMind, όπου εκπαιδεύονται έναν υπολογιστή πρόγραμμα για να παίξει Atari 2600 παιχνίδια. Και αν νομίζετε ότι αυτό δεν είναι σοβαρό των επιχειρήσεων, τα αποτελέσματα της μελέτης τους δημοσιεύθηκαν στο περιοδικό Nature, έτσι σχεδόν τόσο καλή δημοσίευση όπως μπορείτε ενδεχομένως να πάρετε. Και εδώ είναι το πόσο καλά έκαναν. 

Έχουν έναν αλγόριθμο που καθόταν και παρακολούθησαν μόνο τις εισόδους της οθόνης. Πήρε κανένα απολύτως οδηγίες σχετικά με τους κανόνες του παιχνιδιού. Και έπρεπε να καταλάβω, με βάση βαθμολογία του, το πόσο καλά έκανε. Αυτό ήταν ένα σύστημα το οποίο χρησιμοποιείται κάτι που ονομάζεται ενισχυτική μάθηση. Δηλαδή, κοίταξε βαθμολογία του. Και αν έχεις μια καλή βαθμολογία, είπε, Θα πρέπει να θυμόμαστε αυτά τα πράγματα. Και πρέπει να κάνω εκείνα πάλι. Και αν έχεις μια κακή βαθμολογία, είπε, Δεν πρέπει να κάνουμε και πάλι αυτά τα πράγματα. 

Αυτή είναι η απόδοση των εν λόγω συστημάτων εκπαιδευμένο επιτρέπεται να παίξουν για ένα λίγες ώρες σε κάθε παιχνίδι, συγκρίνεται με επαγγελματίες gamers. Έτσι, για όλα τα παιχνίδια που είναι στην αριστερή πλευρά αυτής της γραμμής, αυτή η αυτο-εκπαιδεύονται πρόγραμμα υπολογιστή ξεπέρασε τα επαγγελματικά gamers. Και για πάντα να το δεξιά, οι επαγγελματίες παίκτες ήταν ακόμα το καλύτερο. Για κάτι που ήξερε τίποτα σχετικά με τους κανόνες, που δεν ήξερε τίποτα για τη δομή του παιχνίδια, αυτό είναι εντυπωσιακές επιδόσεις. Και αυτό είναι ό, τι είμαστε σε θέση να κάνουμε σήμερα. 

Εντάξει, λέτε, αλλά αν εμείς σκεφτείτε AI σε παιχνίδια, συνήθως σκεφτόμαστε για το Πράγματα που μπορούμε πραγματικά να καθίσουν και να παίξει εναντίον. Αν καθίσω και παίζω StarCraft, ή παίζω Δωρεάν κόσκινο, ο αντίπαλος υπολογιστή είναι το πρόσωπο που ελέγχει το Zerg, ή τον έλεγχο της άλλο πολιτισμό. Πώς αυτοί οι παίκτες βρείτε πραγματικά τις κινήσεις τους; 

Λοιπόν, αυτά τα παιχνίδια δομημένο Με τον ίδιο τρόπο, όπως επιτραπέζια παιχνίδια μας, Αυτά τα παιχνίδια ότι θα συλλογικά καλέσει τέσσερα παιχνίδια X, διερευνήσει, expand-- ξεχνάμε αυτά. Τι είναι? Εξερευνήστε, αναπτύξτε, και να σβήσει, Νομίζω ότι είναι η τελευταία. Αλλά είναι βασικά εξερεύνησης και βασίλευε παιχνίδια. Τυπικά, ο αντίπαλος υπολογιστή Έχει υπάρχουν περιορισμένες πληροφορίες. Δεν ξέρω ακριβώς τι είναι συμβαίνει πίσω από αυτή την ομίχλη του πολέμου. Δεν έχετε να δείτε τι έχετε στο απόθεμά σας. 

Υπάρχει ένα περιβάλλον που είναι δυναμική. Τα πάντα αλλάζουν όλη την ώρα. Δεν έχετε να καθίσετε και να περιμένετε να πάρετε την κίνησή σας. Αλλά τα περισσότερα πράγματα εξακολουθούν να είναι διακριτές. Πρέπει να βάλω την πόλη μου εδώ. Ή θα πρέπει να θέσει την πόλη μου εδώ. Και όλα είναι ντετερμινιστική. Όταν λέω, μετακινήστε μονάδα μου εδώ, η μονάδα μου Μεταφέρεται εδώ, εκτός εάν ένα εμπόδιο ξαφνικά μπαίνει στο παιχνίδι. Τώρα, αυτό δεν είναι όλα του υπολογιστή παιχνίδια που είναι εκεί έξω σήμερα. 

Αν πάω και να παίξω έναν πρώτο τύπο προσώπου παιχνίδι, κάτι σαν κλέφτης ή Fallout ή Skyrim, ή το Halo, τώρα Έχω αντιπάλων του υπολογιστή που είναι εκεί έξω που έχουν μια πολύ διαφορετική κατάσταση. Έχουν, πάλι, περιορισμένες πληροφορίες. Το μόνο που μπορεί να δει ένας ορισμένες οπτικό πεδίο. Το περιβάλλον εξακολουθεί να είναι δυναμική. Τα πράγματα αλλάζουν όλη την ώρα. 

Αλλά τώρα έχω ένα πολύ πιο συνεχή χώρο δράσης. Μπορώ να κρυφοκοιτάζει μόνο ένα λίγο έξω από την πόρτα. Και μερικά παιχνίδια, μου δράσεις είναι στοχαστική. Παίρνω να προσπαθήσει να πηδήξει πάνω από το τείχος, αλλά έχω μια πιθανότητα της αποτυχίας. Αυτοί οι τύποι των παιχνιδιών είναι όλο και πιο κοντά και πιο κοντά με τα είδη των ελεγκτών ότι χτίζουμε στη ρομποτική. 

Στη ρομποτική, πρέπει να υποθέσουμε ότι έχουμε περιορισμένες πληροφορίες. Έχουμε αισθητήρες που πείτε μας για τον κόσμο. Έχουμε πάντα μεταβαλλόμενο, δυναμικό περιβάλλον. Έχουμε έναν κόσμο όπου ο χώρος είναι συνεχής, παρά διακριτά. Και τις δράσεις μας, όταν προσπαθούμε τους, έχουν την ευκαιρία της αποτυχίας. Και στην πραγματικότητα, σύγχρονο παιχνίδι ελεγκτές για το Halo αντίπαλό σας, ή για εκείνους τους NPCs στο Skyrim, βασικά τρέχουν μικρές αρχιτεκτονικές ρομποτικής. 

Μπορούν να αισθάνεται τον κόσμο. Χτίζουν ένα μοντέλο του κόσμου. Θα υπολογίσουμε με βάση ένα σύνολο τους στόχους που θέλετε να πετύχετε. Σχεδιάζουν ενέργειες με βάση σε ό, τι ξέρουν. Και αυτά είναι ακριβώς τα ίδια είδη των συστημάτων που έχουμε χτίσει στη ρομποτική. Έτσι αυτές οι αρχιτεκτονικές, να φέρει αυτό πίσω μαζί, είναι συχνά ακριβώς το ίδιο. 

Ας δούμε αν μπορούμε να δούμε ότι. Ας πάμε πίσω στο μας tic-tac-toe παράδειγμα. Και Πάω να κάνω μια-δυο μου μεταδιδακτορικοί να έρθει και να με βοηθήσει. Έτσι Τσεν Μινγκ, και Alessandro, και Olivier, αν εσείς θα καταλήξει. Και Πάω να χρειάζονται ένα ζευγάρι των εθελοντών 

Εντάξει, είδα ένα χέρι επάνω δεξιά εκεί στη μέση. Επιτρέψτε μου να αναφέρω ένα ακόμη, κάποιος περαιτέρω στο πίσω μέρος ίσως. Εντάξει, εκεί πέρα. Έλα επάνω. Εντάξει. Ας πάρουμε λοιπόν αυτό το κάλυμμα προς τα κάτω. Και αν εσείς θα έρθει δεξιά πίσω εδώ γύρω για μένα, φανταστική. 

Έτσι, αυτό είναι ένα ρομπότ που ονομάζεται Baxter. Και Baxter είναι ένα ρομπότ που είναι ένας εμπορική πλατφόρμα, σχεδιασμένη από μια εταιρεία που ονομάζεται επαναπροσδιορισμό. Και αυτό το ρομπότ έχει σχεδιαστεί για την κατασκευή μικρής κλίμακας. Αλλά σήμερα θα πάμε να χρησιμοποιήστε το για να παίξει tic-tac-toe. Τώρα, αυτό το ρομπότ είναι επίσης κάτι ότι είναι σχετικά μοναδικό. Διότι αν ήμουν στέκεται πουθενά κοντά σε μια τυπική αυτοματισμού εργοστασίων σύστημα, θα ήθελα να είναι σε πολύ σοβαρή κίνδυνος να τραυματιστεί. 

Baxter, ωστόσο, έχει σχεδιαστεί ώστε να σχετικά ασφαλές να αλληλεπιδρούν με. Και γι 'αυτό μπορεί να ωθήσει σε αυτό το ρομπότ. Και μπορείτε να δείτε ότι είναι λίγο λίγο ευέλικτο καθώς κινείται γύρω. Και μπορώ να το επανατοποθετήσει όπου θα ήθελα να πάω. Τώρα, σε ένα κανονικό ρομποτικό σύστημα, θα έχουμε μια σειρά από συνδέσμους εδώ ότι θα είναι άμεσα να ανταποκρίνεται στις εντολές θέση. Και δεν θα ήταν απαραιτήτως με νοιάζει αν κινούνταν μέσα από ύπαιθρο, ή εάν κινούνταν μέσω θώρακα μου. 

ΕΝΤΆΞΕΙ. Και συνήθως, αν ήταν εδώ με ένα βιομηχανικό σύστημα, θα πάει πουθενά κοντά σε αυτό. Θα πρέπει να υπάρχουν κίτρινα ταινία ασφαλείας όλα γύρω από αυτό. Αυτό το σύστημα έχει ένα ελαφρώς διαφορετική σχεδίαση να είναι φιλικότερο και πιο για τους ανθρώπους να αλληλεπιδρούν με, από το γεγονός ότι σε κάθε κοινό, υπάρχει ένα ελατήριο. Και αντί να ελέγχει μια ακριβή θέση, ελέγχουμε ένα ορισμένο ποσό των ροπή, ένα ορισμένο ποσό της δύναμης, ότι θα θέλαμε να είναι σε εκείνη την άνοιξη. Εντάξει, οπότε επιτρέψτε μου να λαμβάνουν οι εθελοντές μας εδώ. Γεια πως σε λενε? 

Κοινό: Louis. 

ΟΜΙΛΗΤΗΣ: Louis. Χαίρομαι που σε βλέπω. Και? 

Κοινό: David. 

ΟΜΙΛΗΤΗΣ: David. Χάρηκα για τη γνωριμία. Εάν εσείς θα περιμένετε εδώ για ένα δευτερόλεπτο, Πάω να σας δώσω μια ευκαιρία για να γίνει αυτό. Έτσι, αυτό το ρομπότ, αν καταλήξει και αν πιέσετε απαλά σε αυτό, θα πάμε να δούμε ότι κινείται λίγο. Και αν το πιάσεις σωστά εδώ στον καρπό του χεριού μόνο όταν οι παραπάνω κουμπιά, το Μοιάζει θα πρέπει να αρπάξει τα πλήκτρα, αλλά αρπάξει ακριβώς πάνω από αυτήν Αντίθετα, θα να είναι σε θέση να χειριστούν πολύ προσεκτικά μέσα στο χώρο. Louis, θέλετε να δώσετε μια δοκιμή; Γι 'αυτό δίνουν λίγο πιέστε για να αρχίσει με. Και στη συνέχεια, αν βάλετε τα δάχτυλά σας ακριβώς εκεί και να κρατήσουν σε αυτό, γιατί θα κινηθεί για σας τότε. Εντάξει, θέλετε να δώσετε μια δοκιμή; Έλα επάνω. Γι 'αυτό δώσω ένα απαλό ωθήσει εκεί για να ξεκινήσετε. Μπορείτε να αισθανθείτε τι είναι σαν. Και στη συνέχεια, αν το πιάσεις ακριβώς εκεί, θα είστε σε θέση να κάνω ελιγμούς γύρω. 

ΕΝΤΆΞΕΙ. Έτσι συνήθως, αυτό το είδος ενός ρομπότ θα να χρησιμοποιηθεί για την παραγωγή μικρής κλίμακας,. Και Πάω να μετακινήσετε το όπλο αυτό ακριβώς κάτω από το δρόμο λίγο εδώ. Αλλά σήμερα, θα πάμε να χρησιμοποιήσετε το ίδιο-tic tac-toe παιχνίδι του συστήματος με βάση minimax που φτιάξαμε νωρίτερα. ΕΝΤΆΞΕΙ? Έτσι, εσείς είστε το καθένα Θα παίξουμε ένα παιχνίδι. Louis, εσείς πρόκειται να είναι η πρώτη. Επιτρέψτε μου μόνο να κρατήσει ψηλά εδώ για ένα δευτερόλεπτο. Πάω να έχετε σταθεί σωστά Εδώ, ακριβώς έτσι ο καθένας μπορεί να σας δει. Ρε παιδιά που έχει συσταθεί εδώ; 

ΡΟΜΠΟΤ: Καλώς ήρθατε. Ας παίξουμε-tic tac-toe. Μην αγγίζετε το κουπόνι σας πριν από Λέω ότι είναι η σειρά σας. Έχω ξεκινήσει το παιχνίδι. Είναι η σειρά μου. ΟΜΙΛΗΤΗΣ: Τώρα, αν θα μπορούσατε να πάρετε ένα από τα τα κομμάτια σας και να πάτε μπροστά και να το τοποθετήσετε. ΡΟΜΠΟΤ: Είναι η σειρά σας. [ΓΈΛΙΟ] Είναι η σειρά μου. [ΓΈΛΙΟ] [ΓΈΛΙΟ] Είναι η σειρά σου. ΟΜΙΛΗΤΗΣ: Η ανθρώπινη φυλή είναι Βασιζόμαστε σε σας εδώ, Λούις. 

ΡΟΜΠΟΤ: Είναι η σειρά μου. 

ΟΜΙΛΗΤΗΣ: Έτσι Baxter επιτυχώς μπλοκαριστεί εδώ. 

ΡΟΜΠΟΤ: Είναι η σειρά σας. Είναι η σειρά μου. Είναι η σειρά σου. Είναι η σειρά μου. ΟΜΙΛΗΤΗΣ: Και εμείς θα Baxter τελειώσει τη τελευταία κίνηση του εδώ. 

[ΓΈΛΙΟ] 

ΡΟΜΠΟΤ: Αυτή είναι μια ισοπαλία. Θα κερδίσει την επόμενη φορά. 

[ΓΈΛΙΟ] 

ΟΜΙΛΗΤΗΣ: Εντάξει, Ευχαριστώ πολύ, Λούις. Ευχαριστώ. Μπορείτε να πάτε με αυτόν τον τρόπο. 

ΡΟΜΠΟΤ: Έχω ξεκινήσει το παιχνίδι. ΟΜΙΛΗΤΗΣ: Επιτρέψτε μου λοιπόν να εξηγήσω να σας ένα ακόμη μικρό λίγο πριν φτάσουμε ρεβάνς μας εδώ. Τι ακριβώς συμβαίνει; Έτσι, το ρομπότ διαθέτει κάμερα επάνω στην κορυφή εδώ. Και αυτό είναι κοιτάζοντας προς τα κάτω στο διοικητικό συμβούλιο. Και για να δει αν Έχει μια κόκκινη O ή μπλε και άσπρο X. Όπως εκείνοι να διατίθενται στην αγορά του σκάφους, αυτό είναι βασικά η ίδια είσοδο ότι θα πρέπει να διαβάζετε από δομή δεδομένων μας από την οθόνη μας. Είναι τρέχει το ίδιο αλγόριθμος minimax να είναι είναι σε θέση να βρει πού να Τοποθετήστε μια καλή ένδειξη. 

Και στη συνέχεια, δίνουμε μια εντολή για όπου θα θέλαμε ένα κουπόνι για να τοποθετηθεί. Ο βραχίονας κινείται έξω. Είναι χρησιμοποιώντας μια λαβίδα κενού για την εφαρμογή κάποια αναρρόφησης σε αυτό το ξύλινο κομμάτι, να το παραλάβετε, να το μετακινήσετε προς τα δεξιά τόπου, και στη συνέχεια αφήστε την αναρρόφηση και να πέσει. Εντάξει, θα πάμε για να δώσει μία ακόμη πυροβολισμό με ένα ελαφρώς πιο έξυπνη παίκτης εδώ. Είστε έτοιμοι? Εντάξει, αν θέλετε να σταθεί μέχρι εδώ και να δώσει a-- αποδεικνύονται με αυτόν τον τρόπο ώστε να μπορείτε να δείτε όλους. Και τότε [δεν ακούγεται]. 

ΡΟΜΠΟΤ: Είναι η σειρά μου. 

ΟΜΙΛΗΤΗΣ: Η Baxter θα ξεκινήσει. Είναι η σειρά σου. Είναι η σειρά μου. Είναι η σειρά σου. Είναι η σειρά μου. 

[ΓΈΛΙΟ] 

ΟΜΙΛΗΤΗΣ: [WHISPERING] Ακριβώς αφήστε τον να φύγει μπροστά και να κερδίσει. ΡΟΜΠΟΤ: Είναι η σειρά σας. ΟΜΙΛΗΤΗΣ: Αυτό είναι ΟΚ. 

ΡΟΜΠΟΤ: Είναι η σειρά μου. 

[ΓΈΛΙΟ] 

Κέρδισα. 

[ΓΈΛΙΟ] 

Έχω ξεκινήσει το παιχνίδι. 

ΟΜΙΛΗΤΗΣ: Εντάξει, σας ευχαριστώ πολύ. Εντάξει, νομίζω ότι έχουμε χρόνο για ένα ακόμη εξαιρετικό-tic tac-toe παίκτη, κάποιος που μπορεί να θέσει αυτό το πράγμα που πρέπει να ταιριάζουν, ποιος ξέρει τι κάνουν. 

[ΓΈΛΙΟ] 

Ποιος θα είναι πρωταθλητής μας εδώ; Εντάξει, τους φίλους σας, εθελοντικά. Αυτό είναι αρκετά καλό για μένα. Πες μου το όνομά σας και πάλι. Κοινό: Tamir. ΟΜΙΛΗΤΗΣ: Tamir, χαίρομαι που σας βλέπω. Εντάξει, πάλι, θα πάμε να σας βάλει μέχρι εδώ, ώστε όλοι να μπορούν να σας δουν. Είστε εκπρόσωπος μας σε αυτό το παιχνίδι τώρα. Η Baxter είναι ένα και το OH και ω. Ή συγνώμη, ένα ω και ένα. Και είναι στο χέρι σας εδώ. Η Baxter θα πάρει για να μετακινήσετε την πρώτη, όμως. Έτσι. ΡΟΜΠΟΤ: Είναι η σειρά μου. 

[ΓΈΛΙΟ] 

Είναι η σειρά σου. Είναι η σειρά μου. Είναι η σειρά σου. Είναι η σειρά μου. Είναι η σειρά σου. 

[ΓΈΛΙΟ] ΡΟΜΠΟΤ: Είναι η σειρά μου. ΟΜΙΛΗΤΗΣ: Είναι πολύ πιο δύσκολο όταν στέκεστε εδώ, οι λαοί. [ΓΈΛΙΟ] ΡΟΜΠΟΤ: Εσείς οι άνθρωποι είναι τόσο εύκολο να νικήσει. [Γέλια και χειροκροτήματα] ΟΜΙΛΗΤΗΣ: Ευχαριστώ πολύ. ΡΟΜΠΟΤ: Έχω κερδίσει. Έχω ξεκινήσει το παιχνίδι. 

ΟΜΙΛΗΤΗΣ: Εντάξει, έτσι ευχαριστώ πολύ πολλά να Olivier, και να Alessandro, και να Τσεν Μινγκ. 

[ΧΕΙΡΟΚΡΟΤΉΜΑΤΑ] 

Θέλω να κάνω ένα τελευταίο σημείο. Έτσι Baxter στην ίδια τελειώνει εκεί, εξαπατημένοι. Και αυτό ήταν απροσδόκητη. Ένα από τα φανταστικά πράγματα για AI είναι ότι εμείς κάνει τη δουλειά του ΑΔ, έτσι ώστε να μπορέσουμε να οικοδομήσουμε πραγματικά ενδιαφέρουσα και έξυπνη συσκευές. Αλλά μπορούμε επίσης να κάνουμε την εργασία σε AI γιατί μας λέει κάτι σχετικά με το πώς οι άνθρωποι είναι έξυπνοι. 

Ένα από τα αγαπημένα μελέτες από το εργαστήριο μου είναι εξετάζοντας τι συμβαίνει όταν μηχανές απροσδόκητα εξαπατήσει. Το κάναμε αυτό που αρχικά δεν με Baxter παίζει tic-tac-toe, αλλά με μικρότερο ρομπότ που ονομάζεται Nao, ο οποίος έπαιξε ροκ-χαρτί-ψαλίδι. Και μερικές φορές μετά παίζουν πολλά και πολλά βαρετό ροκ-Ψαλίδι-Χαρτί παιχνίδια, το ρομπότ θα ρίξει μια χειρονομία, χάνουν, και ξαφνικά αλλάζουν χειρονομία του και να πω, μπορώ να κερδίσω. 

[ΓΈΛΙΟ] 

Τώρα, μερικές φορές είχαμε επίσης το ρομπότ, ακριβώς ως μάρτυρας, να ρίξει μια χειρονομία, να κερδίσει, και να αλλάξετε χειρονομία του για να χάσει, να ρίξει τον αγώνα, εξαπατήσει προκειμένου να χάσουν. Και αυτό δεν είναι τόσο συναρπαστικό. Το ρομπότ που απατεώνες προκειμένου να κερδίσει τους ανθρώπους ανταποκρίνονται σε σαν να είναι έξω για να τους πάρει, όπως αυτό επιδιώκει ενεργά την καταστροφή τους. 

[ΓΈΛΙΟ] 

Γίνεται ένας παράγοντας. Είναι σαν ένα άτομο. Έχει την πεποίθηση και την πρόθεση. Και δεν είναι καλή πρόθεση. Και το ρομπότ που κάνει την το παιχνίδι είναι απλά δυσλειτουργεί. Είναι απλά ένα σπασμένο συσκευή. Επιτρέψτε μου να σας δείξω μερικά παραδείγματα του ότι από μερικές των συμμετεχόντων μας. Τόσο εδώ είναι εξαπάτηση, προκειμένου να χάσουν. 

[ΑΝΑΠΑΡΑΓΩΓΗ] - [Δεν ακούγεται] κερδίσει. Ας παίξουμε. 

-ΟΠΑ, τι? 

- [Δεν ακούγεται] κερδίσει. Ας παίξουμε. 

[Δεν ακούγεται] κερδίσει. Ας παίξουμε. 

ΟΜΙΛΗΤΗΣ: Και εδώ είναι εξαπάτηση για να κερδίσει. 

-Ναι, Έχω κερδίσει. Ας παίξουμε. 

-Δεν Μπορεί να το κάνει αυτό. 

[ΓΈΛΙΟ] 

-Ναι, Έχω κερδίσει. -Θα Εξαπατημένοι. Μπορείτε τώρα εξαπατημένοι. 

-Ναι, Έχω κερδίσει. 

-Γεια Σου, θα απατεώνας. Μπορείτε να εξαπατήσει, σούπερ εξαπατήσει. 

[Σταματήσετε την αναπαραγωγή] 

ΟΜΙΛΗΤΗΣ: Αυτές οι διαφορετικές Αντιδράσεις γρήγορα αλλάξει την αντίληψή μας της συσκευής. Μήπως αυτό σημαίνει ότι χτίζουμε σκόπιμα μηχανές που εξαπατούν διότι αυτό είναι το καλύτερο μηχανικής που μπορούμε να κάνουμε; Όχι, αλλά μας λέει κάτι πραγματικά ενδιαφέρον για τους ανθρώπους. Αυτό το πράγμα που και απατεώνες κλέβει τη νίκη σας, αυτό είναι κάτι που είναι ζωντανό, αυτό είναι κίνηση, που είναι έξω για να σας πάρει. Έχει ψυχική κατάσταση. Έχει πίστη. Έχει πρόθεση. 

Αυτό το πράγμα που τα χέρια του παιχνίδι για εσάς, αυτό δεν είναι. Αυτό είναι απλά δυσλειτουργίας. Αυτό είναι με πολλούς τρόπους γι 'αυτό είναι εύκολο να ρίξει το παιχνίδι με τα παιδιά. Αλλά αν προσπαθήσετε να τους εξαπατήσει και το είδος των διεκδικήσει τη νίκη όταν, ξέρεις, απλά για να μειώσει το παιχνίδι, θα σας πιάσει αμέσως. Αυτά τα είδη των επιπτώσεων που βλέπουμε να βγαίνουν της γρίπης των πτηνών, να μας διδάξουν πολλά για τους εαυτούς μας. 

Εντάξει, αυτό είναι όλο για σήμερα. Ευχαριστώ πολύ για τον David και η ομάδα παραγωγής του Χάρβαρντ για να κατεβαίνει. 

[ΧΕΙΡΟΚΡΟΤΉΜΑΤΑ] 

Θα σας δούμε για ένα κουίζ, και, στη συνέχεια, για μια τελευταία διάλεξη. Να έχεις μία υπέροχη μέρα. 

[ΧΕΙΡΟΚΡΟΤΉΜΑΤΑ] 

[Παίζει μουσική] DAVID J Malan: Λοιπόν, θα χρειαστεί κατά πάσα πιθανότητα για την εισαγωγή κάποιου είδους κρυπτογράφηση, δικαίωμα? Γιατί τότε οι κεφαλίδες των Αυτές οι αιτήσεις HTTP θα είναι κωδικοποιημένα έτσι ώστε ο καθένας προσπαθούν να οσφραίνομαι κυκλοφορίας σας δεν θα είναι πράγματι σε θέση να τους δει. Έτσι ποια είναι η λύση σε αυτό το πρόβλημα; Λοιπόν, θα πρέπει πραγματικά να εισαγάγει κρυπτογράφησης στον τύπο, έτσι ώστε όταν το εν λόγω πρόσωπο είναι μετάδοση δεδομένων από το Α στο Β, μπορούμε με ασφάλεια send-- 

[ΓΈΛΙΟ] 

Οι πληροφορίες σε τρόπο ώστε η αντίπαλος δεν μπορεί, στην πραγματικότητα, το βλέπω.