Πώς να κάνετε το παιχνίδι Tic Tac Toe ασυναγώνιστο χρησιμοποιώντας τον αλγόριθμο minimax

Δυσκολεύτηκα για ώρες κυλιόμενα σε μαθήματα, παρακολουθώντας βίντεο και χτύπησα το κεφάλι μου στο γραφείο προσπαθώντας να δημιουργήσω ένα ασυναγώνιστο παιχνίδι Tic Tac Toe με μια αξιόπιστη Τεχνητή Νοημοσύνη. Αν λοιπόν περνάτε από παρόμοιο ταξίδι, θα ήθελα να σας συστήσω τον αλγόριθμο Minimax.

Όπως ένας επαγγελματίας παίκτης σκακιού, αυτός ο αλγόριθμος βλέπει μερικά βήματα μπροστά και μπαίνει στα παπούτσια του αντιπάλου του. Συνεχίζει να παίζει μπροστά μέχρι να φτάσει σε μια τερματική διάταξη του πίνακα ( κατάσταση τερματικού ) με αποτέλεσμα ισοπαλία, νίκη ή ήττα. Μόλις βρίσκεται σε τερματική κατάσταση, το AI θα εκχωρήσει ένα αυθαίρετο θετικό σκορ (+10) για μια νίκη, ένα αρνητικό σκορ (-10) για μια ήττα, ή ένα ουδέτερο σκορ (0) για ισοπαλία.

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

Δοκιμάστε το μόνοι σας στο επόμενο παιχνίδι χρησιμοποιώντας κατά προτίμηση πρόγραμμα περιήγησης Chrom.

Ένας αλγόριθμος Minimax μπορεί να οριστεί καλύτερα ως μια αναδρομική συνάρτηση που κάνει τα ακόλουθα πράγματα:

  1. επιστρέψτε μια τιμή εάν βρεθεί μια κατάσταση τερματικού (+10, 0, -10)
  2. περάστε από διαθέσιμα σημεία στον πίνακα
  3. καλέστε τη συνάρτηση minimax σε κάθε διαθέσιμο σημείο (επανάληψη)
  4. αξιολογήστε τις τιμές επιστροφής από κλήσεις συνάρτησης
  5. και επιστρέψτε την καλύτερη τιμή

Εάν είστε νέοι στην ιδέα της επανάληψης, σας συνιστώ να παρακολουθήσετε αυτό το βίντεο από το CS50 του Harvard.

Για να κατανοήσουμε πλήρως τη διαδικασία σκέψης του Minimax, ας την εφαρμόσουμε σε κώδικα και να τη δούμε σε δράση στις ακόλουθες δύο ενότητες.

Ελάχιστα στον Κώδικα

Για αυτό το σεμινάριο θα εργαστείτε σε μια κατάσταση κοντινής λήξης του παιχνιδιού που φαίνεται στο σχήμα 2 παρακάτω. Δεδομένου ότι το minimax αξιολογεί κάθε κατάσταση του παιχνιδιού (εκατοντάδες χιλιάδες), μια κατάσταση κοντά στο τέλος σάς επιτρέπει να παρακολουθείτε ευκολότερα τις αναδρομικές κλήσεις του minimax (9).

Για το παρακάτω σχήμα, υποθέστε ότι το AI είναι X και το ανθρώπινο πρόγραμμα αναπαραγωγής είναι O.

Για να δουλέψετε πιο εύκολα με την πλακέτα Ti Tac Toe, πρέπει να το ορίσετε ως πίνακα με 9 αντικείμενα. Κάθε στοιχείο θα έχει το ευρετήριό του ως τιμή. Αυτό θα είναι χρήσιμο αργότερα. Επειδή ο παραπάνω πίνακας έχει ήδη συμπληρωθεί με κάποιες κινήσεις X και Y, ας ορίσουμε τον πίνακα με τις κινήσεις X και Y ήδη σε αυτό ( origBoard ).

var origBoard = ["O",1,"X","X",4,"X",6,"O","O"];

Στη συνέχεια δηλώστε τις μεταβλητές aiPlayer και huPlayer και ορίστε τις σε "X" και "O" αντίστοιχα .

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

/* the original board O | | X --------- X | | X --------- | O | O */ var origBoard = [“O”,1 ,”X”,”X”,4 ,”X”, 6 ,”O”,”O”]; // human var huPlayer = “O”; // ai var aiPlayer = “X”; // returns list of the indexes of empty spots on the board function emptyIndexies(board){ return board.filter(s => s != "O" && s != "X"); } // winning combinations using the board indexies function winning(board, player){ if ( (board[0] == player && board[1] == player && board[2] == player) || (board[3] == player && board[4] == player && board[5] == player) || (board[6] == player && board[7] == player && board[8] == player) || (board[0] == player && board[3] == player && board[6] == player) || (board[1] == player && board[4] == player && board[7] == player) || (board[2] == player && board[5] == player && board[8] == player) || (board[0] == player && board[4] == player && board[8] == player) || (board[2] == player && board[4] == player && board[6] == player) ) { return true; } else { return false; } }

Τώρα ας δούμε τα καλά μέρη ορίζοντας τη συνάρτηση Minimax με δύο επιχειρήματα newBoard και player . Στη συνέχεια, πρέπει να βρείτε τα ευρετήρια των διαθέσιμων σημείων στον πίνακα και να τα ορίσετε σε μια μεταβλητή που ονομάζεται availSpots .

// the main minimax function function minimax(newBoard, player){ //available spots var availSpots = emptyIndexies(newBoard);

Επίσης, πρέπει να ελέγξετε για καταστάσεις τερματικού και να επιστρέψετε μια τιμή ανάλογα. Εάν κερδίσει το O θα πρέπει να επιστρέψετε -10, εάν το X κερδίσει θα πρέπει να επιστρέψετε +10. Επιπλέον, εάν το μήκος του διαθέσιμου πίνακα Spots είναι μηδέν, αυτό σημαίνει ότι δεν υπάρχει πλέον χώρος για παιχνίδι, το παιχνίδι είχε ως αποτέλεσμα ισοπαλία και θα πρέπει να επιστρέψετε το μηδέν.

 // checks for the terminal states such as win, lose, and tie //and returning a value accordingly if (winning(newBoard, huPlayer)){ return {score:-10}; } else if (winning(newBoard, aiPlayer)){ return {score:10}; } else if (availSpots.length === 0){ return {score:0}; }

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

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

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

Τέλος, το Minimax επαναφέρει το newBoard σε αυτό που ήταν πριν και ωθεί το αντικείμενο μετακίνησης στον πίνακα μετακινήσεων .

// an array to collect all the objects var moves = []; // loop through available spots for (var i = 0; i < availSpots.length; i++){ //create an object for each and store the index of that spot var move = {}; move.index = newBoard[availSpots[i]]; // set the empty spot to the current player newBoard[availSpots[i]] = player; /*collect the score resulted from calling minimax on the opponent of the current player*/ if (player == aiPlayer){ var result = minimax(newBoard, huPlayer); move.score = result.score; } else{ var result = minimax(newBoard, aiPlayer); move.score = result.score; } // reset the spot to empty newBoard[availSpots[i]] = move.index; // push the object to the array moves.push(move); }

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

Η ίδια διαδικασία αξιολόγησης συμβαίνει όταν ο παίκτης είναι huPlayer , αλλά αυτή τη φορά το bestScore θα οριστεί σε υψηλό αριθμό και το Minimax αναζητά μια κίνηση με το χαμηλότερο σκορ για αποθήκευση.

Στο τέλος, το Minimax επιστρέφει το αντικείμενο που είναι αποθηκευμένο στο bestMove .

// if it is the computer's turn loop over the moves and choose the move with the highest score var bestMove; if(player === aiPlayer){ var bestScore = -10000; for(var i = 0; i  bestScore){ bestScore = moves[i].score; bestMove = i; } } }else{ // else loop over the moves and choose the move with the lowest score var bestScore = 10000; for(var i = 0; i < moves.length; i++){ if(moves[i].score < bestScore){ bestScore = moves[i].score; bestMove = i; } } } // return the chosen move (object) from the moves array return moves[bestMove]; }
Αυτό είναι για τη συνάρτηση minimax. :) μπορείτε να βρείτε τον παραπάνω αλγόριθμο στο github και το codepen. Παίξτε με διαφορετικούς πίνακες και ελέγξτε τα αποτελέσματα στην κονσόλα.

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

Ελάχιστο σε δράση

Χρησιμοποιώντας το παρακάτω σχήμα, ας ακολουθήσουμε τις κλήσεις συνάρτησης ( FC ) του αλγορίθμου μία προς μία.

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

1. Το origBoard και το aiPlayer τροφοδοτούνται στον αλγόριθμο. Ο αλγόριθμος δημιουργεί μια λίστα με τα τρία κενά σημεία που βρίσκει, ελέγχει για καταστάσεις τερματικών και βγαίνει σε κάθε κενό σημείο ξεκινώντας από το πρώτο. Στη συνέχεια, αλλάζει το newBoard τοποθετώντας το aiPlayer στο πρώτο κενό σημείο.Μετά από αυτό,καλείται με το newBoard και το huPlayer και περιμένει να επιστρέψει η FC μια τιμή.

2. While the first FC is still running, the second one starts by making a list of the two empty spots it finds, checks for terminal states, and loops through the empty spot starting from the first one. Then, it changes the newBoard by placing the huPlayer in the first empty spot.After thatit calls itself with newBoard and the aiPlayer and waits for the FC to return a value.

3. Finally the algorithm makes a list of the empty spots, and finds a win for the human player after checking for terminal states. Therefore, it returns an object with a score property and value of -10.

Δεδομένου ότι η δεύτερη FC παρουσίασε δύο κενά σημεία, το Minimax αλλάζει το newBoard τοποθετώντας το huPlayer στο δεύτερο κενό σημείο. Στη συνέχεια, αποκαλείται με τον νέο πίνακα και το aiPlayer .

4. Ο αλγόριθμος κάνει μια λίστα με τα κενά σημεία και βρίσκει μια νίκη για τον ανθρώπινο παίκτη αφού ελέγξει τις καταστάσεις τερματικών. Επομένως, επιστρέφει ένα αντικείμενο με ιδιότητα βαθμολογίας και τιμή -10.

Στο δεύτερο FC, ο αλγόριθμος συλλέγει τις τιμές που προέρχονται από χαμηλότερα επίπεδα (3η και 4η FC). Δεδομένου ότι η σειρά του huPlayer είχε ως αποτέλεσμα τις δύο τιμές, ο αλγόριθμος επιλέγει τη χαμηλότερη από τις δύο τιμές. Επειδή και οι δύο τιμές είναι παρόμοιες, επιλέγει την πρώτη και την επιστρέφει στην πρώτη FC. Σε αυτό το σημείο η πρώτη FC έχει αξιολογήσει το σκορ της μετακίνησης aiPlayer στο πρώτο κενό σημείο. Στη συνέχεια, αλλάζει το newBoard τοποθετώντας το aiPlayer στο δεύτερο κενό σημείο. Στη συνέχεια, καλείται με το newBoard και το huPlayer .

5. Στην πέμπτη FC, ο αλγόριθμος κάνει μια λίστα με τα κενά σημεία και βρίσκει μια νίκη για τον ανθρώπινο παίκτη μετά από έλεγχο για καταστάσεις τερματικών. Επομένως, επιστρέφει ένα αντικείμενο με ιδιότητα βαθμολογίας και τιμή +10.

Μετά από αυτό, το πρώτο FC συνεχίζει αλλάζοντας το νέοBoard και τοποθετώντας το aiPlayer στο τρίτο κενό σημείο Στη συνέχεια, αποκαλείται με τον νέο πίνακα και το huPlayer .

6. Το 6ο FC ξεκινά κάνοντας μια λίστα με δύο κενά σημεία που βρίσκει, ελέγχει για καταστάσεις τερματικών και βρόχους μέσω των δύο κενών σημείων ξεκινώντας από το πρώτο. Στη συνέχεια, αλλάζει το newBoard τοποθετώντας το huPlayer στο πρώτο κενό σημείο.Μετά από αυτό,it calls itself with newBoard and the aiPlayer and waits for the FC to return a score.

7. Now the algorithm is two level deep into the recursion. It makes a list of the one empty spot it finds, checks for terminal states, and changes the newBoard by placing the aiPlayer in the empty spot.After that,it calls itself with newBoard and the huPlayer and waits for the FC to return a score so it can evaluate it.

8. On the 8th FC,ο αλγόριθμος δημιουργεί μια κενή λίστα με κενά σημεία και βρίσκει μια νίκη για το aiPlayer αφού ελέγξει για καταστάσεις τερματικού. Επομένως, επιστρέφει ένα αντικείμενο με ιδιότητα βαθμολογίας και τιμή +10 ένα επίπεδο πάνω (7ο FC).

Η 7η FC έλαβε μόνο μία θετική αξία από τα χαμηλότερα επίπεδα (8η FC). Επειδή η σειρά του aiPlayer είχε ως αποτέλεσμα αυτήν την τιμή, ο αλγόριθμος πρέπει να επιστρέψει την υψηλότερη τιμή που έχει λάβει από χαμηλότερα επίπεδα. Επομένως, επιστρέφει τη μοναδική θετική τιμή (+10) κατά ένα επίπεδο πάνω (6ο FC). Δεδομένου ότι η 6η FC παρουσίασε δύο κενά σημεία, το Minimax αλλάζει το newBoard τοποθετώντας το huPlayer στο δεύτερο κενό σημείο. Στη συνέχεια, καλείται με τον νέο πίνακα και το aiPlayer .

9. Next, the algorithm makes a list of the empty spots, and finds a win for the aiPlayer after checking for terminal states. Therefore, it returns an object with score properties and value of +10.

Σε αυτό το σημείο, το 6 FC πρέπει να επιλέξει ανάμεσα στο σκορ (+10) που στάλθηκε από το 7ο FC (επέστρεψε αρχικά από το 8 FC) και το σκορ (-10) επέστρεψε από το 9ο FC. Δεδομένου ότι η σειρά του huPlayer είχε ως αποτέλεσμα αυτές τις δύο επιστρεφόμενες τιμές, ο αλγόριθμος βρίσκει την ελάχιστη βαθμολογία (-10) και την επιστρέφει προς τα πάνω ως αντικείμενο που περιέχει ιδιότητες βαθμολογίας και ευρετηρίου. Τέλος, και οι τρεις κλάδοι του πρώτου FC έχουν αξιολογηθεί (-10, +10, -10). Αλλά επειδή η σειρά του aiPlayer είχε ως αποτέλεσμα αυτές τις τιμές, ο αλγόριθμος επιστρέφει ένα αντικείμενο που περιέχει την υψηλότερη βαθμολογία (+10) και το ευρετήριό του (4).

Στο παραπάνω σενάριο, η Minimax καταλήγει στο συμπέρασμα ότι η μετακίνηση του X στο μέσο του πίνακα οδηγεί στο καλύτερο αποτέλεσμα. :)

Το τέλος!

Μέχρι τώρα θα πρέπει να καταλάβετε τη λογική πίσω από τον αλγόριθμο Minimax. Χρησιμοποιώντας αυτήν τη λογική προσπαθήστε να εφαρμόσετε τον αλγόριθμο Minimax μόνοι σας ή να βρείτε το παραπάνω δείγμαgithub ή codepen και βελτιστοποιήστε το.

Ευχαριστώ για την ανάγνωση! Εάν σας άρεσε αυτή η ιστορία, μην ξεχάσετε να τη μοιραστείτε στα κοινωνικά μέσα.

Ιδιαίτερες ευχαριστίες στους Tuba Yilmaz, Rick McGavin και Javid Askerov για την αναθεώρηση αυτού του άρθρου.