Connect Four AI — Παίξτε Ενάντια σε Μηχανή Minimax

Αυτή η AI για το Connect Four είναι ένας γνήσιος αντίπαλος βασισμένος σε αναζήτηση, όχι ένα scripted ή τυχαίο bot. Επιλέξτε να παίξετε ως κόκκινος ή κίτρινος (ο κόκκινος ξεκινά πάντα, όπως στο κλασικό Connect Four), διαλέξτε επίπεδο δυσκολίας και αρχίστε να ρίχνετε δίσκους κάνοντας κλικ σε μια στήλη ή στο βέλος πάνω της. Ο δίσκος κατεβαίνει με κίνηση στη σειρά προσγείωσής του, η τετράδα ανιχνεύεται άμεσα προς κάθε κατεύθυνση — οριζόντια, κάθετα και στις δύο διαγωνίους — και μια σύντομη γραμμή κατάστασης σας λέει πάντα ποιανού είναι η σειρά ή ανακοινώνει τον νικητή.

Η μηχανή πίσω από την AI είναι μια αναζήτηση negamax με κλάδεμα alpha-beta, η ίδια οικογένεια αλγορίθμων που χρησιμοποιούν οι κλασικές μηχανές επιτραπέζιων παιχνιδιών: εξερευνά το δέντρο των πιθανών μελλοντικών κινήσεων, κάθε πλευρά προσπαθεί να μεγιστοποιήσει το δικό της αποτέλεσμα υποθέτοντας ότι και ο αντίπαλος παίζει καλά, και κλαδεύει κλάδους που δεν μπορούν να αλλάξουν το αποτέλεσμα αφού έχει ήδη βρεθεί μια καλύτερη γραμμή. Επειδή το Connect Four έχει μόνο επτά στήλες για να διαλέξετε, αυτή η αναζήτηση μπορεί να κοιτάξει αρκετές κινήσεις μπροστά γρήγορα. Εκτελείται με επαναληπτική εμβάθυνση — ψάχνοντας ένα επίπεδο, μετά δύο, μετά τρία κ.ο.κ. — μέσα σε ένα σύντομο χρονικό περιθώριο ανά κίνηση (περίπου ένα τέταρτο του δευτερολέπτου στο Εύκολο έως περίπου ενάμιση δευτερόλεπτο στο Δύσκολο), οπότε ο browser δεν κολλάει ποτέ περιμένοντας μια κίνηση.

Όταν η αναζήτηση δεν μπορεί να φτάσει στο τέλος του παιχνιδιού μέσα στο βάθος της, οι κινήσεις κρίνονται από μια πραγματική ευρετική αξιολόγησης θέσης αντί για εικασία: κάθε πιθανό παράθυρο τεσσάρων στη σειρά πάνω στο ταμπλό βαθμολογείται με βάση το πόσοι δίσκοι κάθε χρώματος το καταλαμβάνουν ήδη (ένα άδειο παράθυρο αξίζει μηδέν, ένα παράθυρο με μόνο δικούς σας δίσκους αξίζει περισσότερο όσο γεμίζει, ένα παράθυρο μπλοκαρισμένο και από τα δύο χρώματα αξίζει μηδέν) και τα κελιά στις κεντρικές στήλες μετρούν περισσότερο επειδή συμμετέχουν σε περισσότερες πιθανές γραμμές. Το Εύκολο και το Μέτριο προσθέτουν λίγη ελεγχόμενη τυχαιότητα ανάμεσα σε κινήσεις που βαθμολογούνται σχεδόν το ίδιο, ώστε η AI να μοιάζει πιο ανθρώπινη και να μπορεί να νικηθεί· το Δύσκολο παίζει πάντα την ισχυρότερη κίνηση που έχει βρει. Αυτός είναι ένας ειλικρινά δυνατός αντίπαλος minimax χτισμένος από πραγματική αναζήτηση και αξιολόγηση — όχι ένας ισχυρισμός για αήττητο ή τέλειο παιχνίδι, ούτε προσομοίωση οτιδήποτε: κάθε κίνηση είναι το πραγματικό αποτέλεσμα του παραπάνω αλγορίθμου.