Επιτραπέζιο παιχνίδι Τεχνητή Νοημοσύνη: ο αλγόριθμος Minimax: 8 βήματα

2024 Συγγραφέας: John Day | [email protected]. Τελευταία τροποποίηση: 2024-01-30 08:34

Αναρωτηθήκατε ποτέ πώς κατασκευάζονται οι υπολογιστές με τους οποίους παίζετε στο σκάκι ή στα πούλια; Λοιπόν, μην κοιτάξετε πέρα από αυτό το Instructable γιατί θα σας δείξει πώς να φτιάξετε μια απλή αλλά αποτελεσματική τεχνητή νοημοσύνη (AI) χρησιμοποιώντας τον αλγόριθμο Minimax! Χρησιμοποιώντας τον αλγόριθμο Minimax, η τεχνητή νοημοσύνη κάνει καλά προγραμματισμένες και μελετημένες κινήσεις (ή τουλάχιστον μιμείται μια διαδικασία σκέψης). Τώρα, θα μπορούσα να σας δώσω τον κωδικό για την AI που έφτιαξα, αλλά αυτό δεν θα ήταν διασκεδαστικό. Θα εξηγήσω τη λογική πίσω από τις επιλογές του υπολογιστή.

Σε αυτό το Instructable, θα σας καθοδηγήσω στα βήματα για το πώς να δημιουργήσετε AI για τον Othello (AKA Reversi) σε python. Θα πρέπει να έχετε μια ενδιάμεση κατανόηση του τρόπου κωδικοποίησης σε python πριν αντιμετωπίσετε αυτό το έργο. Ακολουθούν μερικοί καλοί ιστότοποι για να κοιτάξετε για να σας προετοιμάσουν για αυτό το Instructable: w3schools ή learnpython. Στο τέλος αυτού του Instructable, θα πρέπει να έχετε μια AI που θα κάνει υπολογισμένες κινήσεις και θα πρέπει να είναι σε θέση να νικήσει τους περισσότερους ανθρώπους.

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

Έμαθα πώς να δημιουργώ αυτό το AI μέσω ενός καλοκαιρινού προγράμματος στο Columbia SHAPE. Πέρασα καλά εκεί, ρίξτε μια ματιά στον ιστότοπό τους για να δείτε αν θα σας ενδιέφερε.

Τώρα που βγάλαμε τα logistics εκτός δρόμου, ας ξεκινήσουμε την κωδικοποίηση!

(Έβαλα μερικές σημειώσεις στις εικόνες, οπότε φροντίστε να τις κοιτάξετε)

Προμήθειες

Αυτό είναι εύκολο:

1) Υπολογιστής με περιβάλλον python όπως το Spyder ή το IDLE

2) Κατεβάστε τα αρχεία για το παιχνίδι Othello από το GitHub μου

3) Εγκατεστημένος ο εγκέφαλός σας με υπομονή

Βήμα 1: Κατεβάστε τα απαραίτητα αρχεία

Όταν πηγαίνετε στο GitHub μου, θα πρέπει να δείτε 5 αρχεία. Κατεβάστε και τα 5 και τοποθετήστε τα όλα στον ίδιο φάκελο. Πριν ξεκινήσουμε το παιχνίδι, ανοίγουμε όλα τα αρχεία στο περιβάλλον spyder.

Εδώ είναι τι κάνουν τα αρχεία:

1) othello_gui.py αυτό το αρχείο δημιουργεί τον πίνακα παιχνιδιών για να παίξουν οι παίκτες (είτε πρόκειται για άνθρωπο είτε για υπολογιστή)

2) othello_game.py αυτό το αρχείο παίζει δύο υπολογιστές μεταξύ τους χωρίς τον πίνακα παιχνιδιών και εμφανίζει μόνο τη βαθμολογία και τις θέσεις μετακίνησης

3) ai_template.py εδώ θα τοποθετήσετε όλο τον κώδικα για να δημιουργήσετε την τεχνητή νοημοσύνη σας

4) randy_ai.py αυτό είναι ένα premade AI που επιλέγει τις κινήσεις του τυχαία

5) othello_shared.y

6) Τα άλλα τρία αρχεία: Puma.py, erika_5.py και nathan.py, φτιαγμένα από εμένα, την Erika και τον Nathan αντίστοιχα από το πρόγραμμα SHAPE, αυτά είναι τρία διαφορετικά AI με μοναδικούς κωδικούς

Βήμα 2: Πώς να ανοίξετε και να παίξετε Python Othello

Μόλις ανοίξετε όλα τα αρχεία, στην κάτω δεξιά γωνία της οθόνης, πληκτρολογήστε "run othello_gui.py" και πατήστε enter στο IPython Console. Or στο τερματικό Mac, πληκτρολογήστε "python othello_gui.py" (αφού είστε στο σωστό φάκελο φυσικά). Στη συνέχεια, θα εμφανιστεί ένας πίνακας στην οθόνη σας. Αυτή η λειτουργία είναι η λειτουργία ανθρώπου έναντι ανθρώπου. Το φως γίνεται δεύτερο και το σκοτάδι πρώτο. Δείτε το βίντεο μου αν μπερδευτήκατε. Στην κορυφή, υπάρχει η βαθμολογία κάθε πλακιδίου χρώματος. Για να παίξετε, κάντε κλικ σε έναν έγκυρο χώρο μετακίνησης για να τοποθετήσετε ένα πλακάκι εκεί και, στη συνέχεια, δώστε τον υπολογιστή στον αντίπαλό σας που θα κάνει το ίδιο και θα επαναλάβει.

Εάν δεν ξέρετε πώς να παίζετε Othello, διαβάστε αυτούς τους κανόνες από τον ιστότοπο των ultra boards:

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

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

Τώρα που μπορείτε να παίξετε το παιχνίδι με έναν φίλο, ας δημιουργήσουμε μια τεχνητή νοημοσύνη με την οποία μπορείτε να παίξετε.

Βήμα 3: Αλγόριθμος Minimax: Δημιουργία σεναρίων

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

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

Το ονόμασα αλγόριθμο οπισθοδρόμησης, επειδή ξεκινά με τη δημιουργία και την αξιολόγηση όλων των μελλοντικών καταστάσεων του πίνακα με τις αντίστοιχες τιμές τους. Αυτό σημαίνει ότι ο αλγόριθμος θα παίξει το παιχνίδι όσες χρειάζεται (κάνοντας τις κινήσεις για τον εαυτό του και τον αντίπαλο) μέχρι να παίξει κάθε σενάριο του παιχνιδιού. Για να παρακολουθούμε όλες τις καταστάσεις του πίνακα (σενάρια), μπορούμε να σχεδιάσουμε ένα δέντρο (κοιτάξτε τις εικόνες). Το δέντρο στην παραπάνω εικόνα είναι ένα απλό παράδειγμα ενός παιχνιδιού Connect 4. Κάθε διαμόρφωση πίνακα ονομάζεται κατάσταση πίνακα και η θέση του στο δέντρο ονομάζεται κόμβος. Όλοι οι κόμβοι στο κάτω μέρος του δέντρου είναι οι τελικές καταστάσεις του πίνακα αφού κάνετε όλες τις κινήσεις. Προφανώς, ορισμένες καταστάσεις είναι καλύτερες για τον έναν παίκτη από τον άλλο. Έτσι, τώρα πρέπει να κάνουμε το AI να επιλέξει σε ποια κατάσταση πίνακα θέλει να φτάσει.

Βήμα 4: Minimax: Αξιολόγηση διαμορφώσεων πίνακα

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

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

Υπάρχουν πολλοί τρόποι για να γίνει αυτό, και έχω τρεις διαφορετικές ευρετικές για να αξιολογήσω τα κομμάτια του πίνακα. Σας ενθαρρύνω να φτιάξετε τον δικό σας τύπο ευρετικής. Ανέβασα τρία διαφορετικά AI στο github μου από τρεις διαφορετικούς κατασκευαστές, με τρεις διαφορετικές ευρετικές: Puma.py, erika5.py, nathanh.py.

Βήμα 5: Αλγόριθμος Minimax: Επιλέγοντας την καλύτερη κίνηση

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

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

Ορισμοί: μητρικός κόμβος - ένας κόμβος που προκύπτει ή δημιουργεί κόμβους κάτω από αυτόν. η προέλευση των παιδικών κόμβων - οι κόμβοι που προέρχονται από τον ίδιο γονικό κόμβο

Οι άδειοι κόμβοι αντιπροσωπεύουν ποια κίνηση θα κάνει το AI για να φτάσει στην καλύτερη κατάσταση πίνακα. Ξεκινά με τη σύγκριση των παιδιών του αριστερότερου κόμβου: 10, -3, 5. Δεδομένου ότι ο παίκτης μεγιστοποίησης θα έκανε την κίνηση, θα επέλεγε την κίνηση που θα του έδινε τους περισσότερους πόντους: 10. Έτσι, επιλέγουμε και αποθηκεύουμε αυτόν μετακινηθείτε με τη βαθμολογία του πίνακα και γράψτε το στον γονικό κόμβο. Τώρα που το 10 είναι στον γονικό κόμβο, τώρα είναι η σειρά ελαχιστοποίησης των παικτών. Ωστόσο, ο κόμβος με τον οποίο θα συγκρίναμε το 10 είναι κενός, οπότε πρέπει πρώτα να αξιολογήσουμε αυτόν τον κόμβο προτού επιλέξει ο παίκτης ελαχιστοποίησης. Επιστρέφουμε λοιπόν στη σειρά μεγιστοποίησης του παίκτη και συγκρίνουμε τα παιδιά του παρακείμενου κόμβου: 8, -2. Το Maximizing θα επιλέξει 8 και το γράφουμε στον κενό γονικό κόμβο. Τώρα που ο αλγόριθμος έχει ολοκληρώσει τη συμπλήρωση των κενών χώρων για τα παιδιά ενός κόμβου πάνω του, ο παίκτης ελαχιστοποίησης μπορεί να συγκρίνει αυτά τα παιδιά - 10 και 8 και να επιλέξει 8. Ο αλγόριθμος στη συνέχεια επαναλαμβάνει αυτήν τη διαδικασία μέχρι να γεμίσει ολόκληρο το δέντρο. Στο τέλος αυτού του παραδείγματος, έχουμε τη βαθμολογία 8. Αυτή είναι η υψηλότερη κατάσταση πίνακα που μπορεί να παίξει η τεχνητή νοημοσύνη υποθέτοντας ότι ο αντίπαλος παίζει το βέλτιστο. Έτσι, η AI θα επιλέξει την πρώτη κίνηση που οδηγεί στην κατάσταση 8 σανίδων και αν ο αντίπαλος παίξει βέλτιστα, η AI θα πρέπει να παίξει όλες τις κινήσεις για να φτάσει στην κατάσταση του πίνακα 8. (Ακολουθήστε τις σημειώσεις στις εικόνες μου)

Ξέρω ότι ήταν πολλά. Εάν είστε ένας από εκείνους τους τύπους που χρειάζονται κάποιον να σας μιλήσει για να καταλάβει κάτι, εδώ είναι μερικά βίντεο που παρακολούθησα για να με βοηθήσουν να κατανοήσω την ιδέα πίσω από αυτό: 1, 2, 3.

Βήμα 6: Αλγόριθμος Minimax: udευδοκώδικας

Αφού καταλάβετε τη λογική πίσω από τον αλγόριθμο minimax, ρίξτε μια ματιά σε αυτόν τον ψευδοκώδικα (οι λειτουργίες που είναι καθολικές για όλους τους κώδικες) από τη wikipedia:

συνάρτηση minimax (κόμβος, βάθος, maximizingPlayer) είναι

αν βάθος = 0 ή κόμβος είναι ένας τερματικός κόμβος τότε

επιστρέφει την ευρετική τιμή του κόμβου

εάν maximizingPlayer τότε

τιμή: = −∞

για κάθε παιδί του κόμβου κάνει

τιμή: = μέγ. (τιμή, ελάχιστο (παιδί, βάθος - 1, ΛΑΘΟΣ))

επιστρεφόμενη τιμή

else (* ελαχιστοποίηση του παίκτη *)

τιμή: = +∞

για κάθε παιδί του κόμβου κάνει

τιμή: = min (τιμή, ελάχιστο (παιδί, βάθος - 1, ΑΛΗΘΙΝΟ))

επιστρεφόμενη τιμή

Αυτή είναι μια αναδρομική συνάρτηση, που σημαίνει ότι καλείται ξανά και ξανά μέχρι να φτάσει σε ένα σημείο στάσης. Πρώτον, η συνάρτηση λαμβάνει τρεις τιμές, τον κόμβο, το βάθος και τη σειρά της οποίας είναι. Η τιμή κόμβου είναι το μέρος όπου θέλετε να ξεκινήσει η αναζήτηση το πρόγραμμα. Το βάθος είναι το πόσο μακριά θέλετε να αναζητήσει το πρόγραμμα. Για παράδειγμα, στο παράδειγμα του δέντρου μου έχει βάθος 3, επειδή έψαξε όλες τις καταστάσεις του πίνακα μετά από 3 κινήσεις. Φυσικά, θα θέλαμε η τεχνητή νοημοσύνη να ελέγξει κάθε κατάσταση πίνακα και να επιλέξει μια νικηφόρα νίκη, αλλά στα περισσότερα παιχνίδια όπου υπάρχουν χιλιάδες, αν όχι εκατομμύρια διαμορφώσεις πίνακα, ο φορητός υπολογιστής σας στο σπίτι δεν θα μπορεί να επεξεργαστεί όλες αυτές τις διαμορφώσεις. Έτσι, περιορίζουμε το βάθος αναζήτησης του AI και το πάμε στην καλύτερη κατάσταση πίνακα.

Αυτός ο ψευδοκώδικας αναπαράγει τη διαδικασία που εξήγησα στα δύο προηγούμενα βήματα. Τώρα ας κάνουμε αυτό ένα βήμα παραπέρα και σωστά αυτό σε κώδικα python.

Βήμα 7: Δημιουργία της τεχνητής νοημοσύνης σας με Ai_template.py

Πριν ρίξετε μια ματιά στον κώδικα AI Minimax, προσπαθήστε να δημιουργήσετε το δικό σας AI με το αρχείο ai_template.py και τον ψευδοκώδικα για τον οποίο μιλήσαμε στο τελευταίο βήμα. Υπάρχουν δύο λειτουργίες στο πρότυπο ai που ονομάζονται: def minimax_min_node (πίνακας, χρώμα) και def minimax_max_node (πίνακας, χρώμα). Αντί να έχουμε την ίδια τη συνάρτηση minimax να ανακαλέσει αναδρομικά, έχουμε δύο διαφορετικές λειτουργίες, οι οποίες καλούν η μία την άλλη. Για να δημιουργήσετε την ευρετική για την αξιολόγηση καταστάσεων πίνακα, θα πρέπει να δημιουργήσετε τη δική σας συνάρτηση. Υπάρχει μια προκατασκευασμένη λειτουργία στο αρχείο othello_shared.py που μπορείτε να χρησιμοποιήσετε για τη δημιουργία της τεχνητής νοημοσύνης σας.

Μόλις αποκτήσετε την τεχνητή νοημοσύνη σας, δοκιμάστε να το εκτελέσετε, randy_ai.py. Για να εκτελέσετε δύο ais μεταξύ τους, πληκτρολογήστε "python othello_gui.py (εισαγάγετε όνομα αρχείου ai).py (εισαγάγετε όνομα αρχείου).py" στο τερματικό Mac ή πληκτρολογήστε "run othello_gui.py (εισαγάγετε όνομα αρχείου ai).py (εισαγάγετε όνομα αρχείου).py "και βεβαιωθείτε ότι βρίσκεστε στον σωστό κατάλογο. Επίσης, δείτε το βίντεό μου για τα ακριβή βήματα.

Βήμα 8: Timeρα να κάνετε AI Fight

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