Είναι η ντάμα υπολογιστικά λυμένη; Πώς 18 χρόνια υπολογισμών απέδειξαν την αναπόφευκτη ισοπαλία

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

Τον Ιούλιο του 2007, μια ιστορική επιστημονική δημοσίευση στο κορυφαίο περιοδικό Science έδωσε οριστική απάντηση^[1]. Ερευνητική ομάδα του Πανεπιστημίου της Αλμπέρτα στον Καναδά υπό τον καθηγητή επιστήμης υπολογιστών Τζόναθαν Σέφερ ανακοίνωσε ότι η αγγλική ντάμα (διεθνώς γνωστή ως checkers ή draughts) λύθηκε υπολογιστικά. Μετά από ένα τιτάνιο υπολογιστικό εγχείρημα που διήρκεσε 18 χρόνια και είχε ξεκινήσει το 1989, το πρόγραμμα Chinook απέδειξε με αδιάσειστα μαθηματικά στοιχεία ότι το τέλειο παιχνίδι και από τους δύο αντιπάλους οδηγεί αναγκαστικά σε ισοπαλία.

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

Τα τρία επίπεδα λύσης στη θεωρία παιγνίων

Στην καθημερινή γλώσσα λέμε συχνά ότι λύσαμε έναν γρίφο μόλις εντοπίσουμε το τέχνασμα που τον απλοποιεί. Στα διακριτά μαθηματικά και στην τεχνητή νοημοσύνη, ο όρος υπακούει σε έναν αυστηρό ορισμό που διατύπωσε το 1994 ο ερευνητής Βίκτορ Άλις^[2]. Ο Άλις διέκρινε 3 επίσημες κατηγορίες λύσης για τα συνδυαστικά παίγνια πλήρους πληροφόρησης:

1. Υπερασθενής λύση (Ultra-weakly solved). Μια μαθηματική απόδειξη καθορίζει το θεωρητικό αποτέλεσμα της αρχικής θέσης (νίκη του πρώτου, νίκη του δεύτερου ή ισοπαλία), χωρίς ωστόσο να παρέχει έναν συγκεκριμένο αλγόριθμο ή πρακτική ακολουθία κινήσεων για την επίτευξή του. Κλασικό παράδειγμα αποτελεί το παιχνίδι Hex, όπου η θεωρία παιγνίων αποδεικνύει ότι ο πρώτος παίκτης έχει θεωρητική νίκη μέσω κλοπής στρατηγικής, χωρίς να μπορεί να υποδείξει τις νικηφόρες κινήσεις σε μεγάλα ταμπλό.
2. Ασθενής λύση (Weakly solved). Ένας αλγόριθμος ή ένα επαληθευμένο δέντρο απόδειξης προσφέρει μια πλήρη στρατηγική που εγγυάται τουλάχιστον ισοπαλία ή νίκη από την αρχική διάταξη απέναντι σε οποιαδήποτε πιθανή απάντηση του αντιπάλου. Το πρόγραμμα μπορεί να μη γνωρίζει την αξία παράδοξων θέσεων που προκύπτουν μετά από αλλεπάλληλα λάθη, αλλά από την αφετηρία είναι ανίκητο. Σε αυτήν ακριβώς την κατηγορία ανήκει η ντάμα^[1].
3. Ισχυρή λύση (Strongly solved). Ένας αλγόριθμος υπολογίζει σε πραγματικό χρόνο την ακριβή τιμή και τη βέλτιστη κίνηση για κάθε νόμιμη θέση που μπορεί να εμφανιστεί στο ταμπλό, ανεξάρτητα από τα προηγούμενα σφάλματα. Το παιχνίδι Connect Four λύθηκε ισχυρά το 1988: ο πρώτος παίκτης κερδίζει αναγκαστικά με σωστό παιχνίδι από οποιαδήποτε κατάσταση^[2].

Η αγγλική ντάμα λύθηκε ασθενώς και όχι ισχυρά, διότι η αποθήκευση κάθε απίθανης θέσης θα απαιτούσε εξωπραγματική χωρητικότητα μνήμης. Η ομάδα του Σέφερ εστίασε στην απόδειξη του αποτελέσματος από την επίσημη αρχική θέση. Στην εκκίνηση, 12 σκούρα πούλια αντιμετωπίζουν 12 ανοιχτόχρωμα πούλια πάνω στα 32 σκούρα τετράγωνα, σχηματίζοντας συνολικά 24 κομμάτια στο ταμπλό^[3].

Δεκαοκτώ χρόνια υπολογισμών: πώς το Chinook έλυσε την ντάμα

Το σύμπαν των δυνατών θέσεων στην ντάμα ξεπερνά κατά πολύ ό,τι φαντάζονται οι απλοί παίκτες. Σε ένα ταμπλό 8×8, ο αριθμός των νόμιμων διατάξεων υπολογίζεται σε περίπου 5 × 10^20 θέσεις^[1]. Ο αριθμός αυτός αντιστοιχεί σε περίπου μισό πεντάκις εκατομμύριο θέσεις. Αν ένας συμβατικός υπολογιστής εξέταζε αυτές τις θέσεις διαδοχικά, η διαδικασία θα απαιτούσε χιλιάδες χρόνια.

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

Ανάδρομη ανάλυση και η βάση δεδομένων των 39 τρισεκατομμυρίων θέσεων

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

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

Από το 1989 έως το 2007, η ομάδα ολοκλήρωσε τις βάσεις για όλες τις θέσεις με 10 ή λιγότερα πούλια στο ταμπλό^[1]. Αυτή η γιγαντιαία βάση περιλαμβάνει 39 τρισεκατομμύρια μοναδικές θέσεις. Μόλις μια παρτίδα φτάσει στα 10 πούλια, το Chinook δεν υπολογίζει πλέον: διαβάζει την απόλυτη αλήθεια απευθείας από τη μνήμη.

Η γέφυρα από το άνοιγμα στη βάση των φινάλε

Με την ολοκλήρωση της βάσης των 10 πουλιών, το εναπομείναν έργο ήταν η κατασκευή μιας αδιάσειστης γέφυρας που θα συνέδεε την αρχική θέση των 24 πουλιών με αυτό το όριο^[1].

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

Η παράλληλη επεξεργασία σε εκατοντάδες διακομιστές διήρκεσε χρόνια. Δισεκατομμύρια περιττές παραλλαγές εξαλείφθηκαν για να χτιστεί ένα επαληθευμένο δέντρο απόδειξης δεκάδων εκατομμυρίων κρίσιμων θέσεων. Κάθε βασική γραμμή από το άνοιγμα κατέληγε είτε σε αδιαπέραστο αμυντικό φρούριο είτε απευθείας σε θέση ισοπαλίας της βάσης των 39 τρισεκατομμυρίων. Το 2007 η απόδειξη ολοκληρώθηκε: η ντάμα είναι μαθηματικά ισόπαλη^[1].

Μάριον Τίνσλεϊ: η ανθρώπινη διάνοια απέναντι στον αλγόριθμο

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

Τα αγωνιστικά επιτεύγματα του Τίνσλεϊ μοιάζουν απίστευτα. Σε μια σταδιοδρομία 45 ετών σε κορυφαία τουρνουά, ο Τίνσλεϊ ηττήθηκε σε μόλις 9 παρτίδες ανάμεσα σε χιλιάδες αγώνες που έδωσε^[1]. Κράτησε τον παγκόσμιο τίτλο για δεκαετίες, αποχωρώντας μόνο όταν εξασθενούσε το αγωνιστικό του κίνητρο.

Για να δοκιμάσει το Chinook απέναντι στο απόλυτο μέτρο της ανθρώπινης ικανότητας, ο Τζόναθαν Σέφερ οργάνωσε έναν επίσημο αγώνα παγκόσμιου τίτλου το 1992 εναντίον του Τίνσλεϊ.

Η αναμέτρηση του 1992 αποτέλεσε ιστορικό ορόσημο. Σε 39 εξαντλητικές παρτίδες, ο Τίνσλεϊ επέδειξε εκπληκτική στρατηγική αντίληψη και νίκησε το Chinook με 4 νίκες, 2 ήττες και 33 ισοπαλίες^[1]. Ήταν η πρώτη φορά στην ιστορία που ένα λογισμικό διεκδίκησε επίσημο παγκόσμιο τίτλο απέναντι σε εν ενεργεία παγκόσμιο πρωταθλητή σε κλασικό επιτραπέζιο παιχνίδι.

Το 1994 διεξήχθη η πολυαναμενόμενη ρεβάνς. Μετά από 6 συνεχόμενες ισοπαλίες, ο Τίνσλεϊ αναγκάστηκε να αποσυρθεί λόγω σοβαρής ασθένειας και απεβίωσε το 1995^[1]. Το Chinook ανακηρύχθηκε τότε παγκόσμιος πρωταθλητής ανθρώπου-μηχανής. Μεταγενέστερες αναλύσεις των παρτίδων του Τίνσλεϊ έδειξαν ότι οι κινήσεις του ταυτίζονταν σχεδόν απόλυτα με τις υποδείξεις των βάσεων φινάλε. Το μυαλό του είχε συλλάβει τη μαθηματική γεωμετρία του παιχνιδιού μέσω της καθαρής διαίσθησης.

Η κλίμακα πολυπλοκότητας: από το Connect Four στο σκάκι

Για να αποτιμήσουμε το μέγεθος του επιτεύγματος στην ντάμα, είναι χρήσιμο να τη συγκρίνουμε με άλλα γνωστά παιχνίδια.

Ήδη από το 1950, ο μαθηματικός Κλοντ Σάνον ανέλυσε την πολυπλοκότητα του σκακιού σε ιστορική μελέτη του για τον προγραμματισμό^[4]. Ο Σάνον υπολόγισε ότι το σκάκι περιλαμβάνει περίπου 10^44 νόμιμες θέσεις και πολυπλοκότητα δέντρου τουλάχιστον 10^120 πιθανών παρτίδων, μέγεθος γνωστό σήμερα ως Αριθμός του Σάνον^[4].

Ας δούμε τη σύγκριση αυτών των παιχνιδιών:

• Connect Four: Λύθηκε ισχυρά το 1988^[2]. Με τρισεκατομμύρια καταστάσεις, επιλύεται σήμερα σε φορητό υπολογιστή μέσα σε λίγα δευτερόλεπτα.
• Αγγλική ντάμα 8×8: Λύθηκε ασθενώς το 2007 σε έναν χώρο περίπου 5 × 10^20 θέσεων^[1]. Χρειάστηκαν 18 χρόνια κατανεμημένης επεξεργασίας και μια βάση 39 τρισεκατομμυρίων θέσεων φινάλε.
• Σκάκι: Εντελώς άλυτο. Με 10^44 θέσεις και 10^120 διαδρομές^[4], υπερβαίνει κάθε σημερινή υπολογιστική ισχύ πλήρους εξάντλησης. Σήμερα οι βάσεις φινάλε στο σκάκι καλύπτουν θέσεις μέχρι 7 κομμάτια. Η επέκταση στα 8 κομμάτια απαιτεί τεράστιους αποθηκευτικούς χώρους, ενώ η πλήρης λύση των 32 κομματιών παραμένει ανέφικτη για τους κλασικούς υπολογιστές.
• Διεθνής ντάμα 10×10: Άλυτη. Παίζεται σε εκατό τετράγωνα με είκοσι πούλια ανά πλευρά, με εκτιμώμενο χώρο καταστάσεων κοντά στις 10^30 θέσεις. Οι ιπτάμενες ντάμες και το υποχρεωτικό χτύπημα των περισσότερων κομματιών αυξάνουν εκθετικά το δέντρο αναζήτησης.

Γιατί η μαθηματική λύση δεν αφαίρεσε τη μαγεία της ντάμας

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

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

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

Στην πράξη, 3 παράγοντες κρίνουν το αποτέλεσμα:

1. Ακρίβεια στο άνοιγμα. Αν και η βέλτιστη γραμμή οδηγεί σε ισότητα, οι διακλαδώσεις κρύβουν θανάσιμες παγίδες. Ένα απρόσεκτο βήμα στην αρχή μπορεί να οδηγήσει σε κατάρρευση μέσα σε ελάχιστες κινήσεις.
2. Στρατηγικοί ελιγμοί. Ο έλεγχος του κέντρου, η θωράκιση της πίσω γραμμής και η εκμετάλλευση των αδυναμιών απαιτούν βαθιά κατανόηση. Οι παίκτες που μελετούν τη στρατηγική στην ντάμα επικρατούν σταθερά των αντιπάλων που βασίζονται μόνο σε επιφανειακούς υπολογισμούς.
3. Τεχνική στο φινάλε. Σε ισόπαλα φινάλε, η έννοια της εναντίωσης (opposition) καθορίζει τη νίκη. Ένα λανθασμένο πάτημα μπορεί να στερήσει μια σίγουρη νίκη, όπως εξηγούμε αναλυτικά στον οδηγό μας για το φινάλε της ντάμας.

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

Η γοητεία της τακτικής αναμέτρησης

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

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

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

Συχνές ερωτήσεις

Είναι η ντάμα λυμένη για οποιοδήποτε απίθανο σφάλμα;

Όχι, η αγγλική ντάμα είναι ασθενώς λυμένη και όχι ισχυρά. Η απόδειξη εγγυάται ιδανική στρατηγική ισοπαλίας από την επίσημη αρχική θέση των 24 πουλιών σε 32 σκούρα τετράγωνα^[1]. Επίσης, όλες οι θέσεις με 10 ή λιγότερα πούλια είναι πλήρως λυμένες στη βάση των 39 τρισεκατομμυρίων καταστάσεων. Ωστόσο, περίεργες θέσεις μετά από αμοιβαία χονδροειδή λάθη με πολλά πούλια δεν έχουν καταγραφεί όλες.

Μπορεί ένας άνθρωπος να νικήσει το Chinook σήμερα;

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

Έχουν πλεονέκτημα τα μαύρα ή τα λευκά στην ντάμα;

Στην αγγλική ντάμα τα μαύρα παίζουν πρώτα. Αν και η πρώτη κίνηση δίνει την πρωτοβουλία για τη διεκδίκηση των κεντρικών τετραγώνων, η απόδειξη του Σέφερ επιβεβαίωσε ότι αυτό το πλεονέκτημα δεν επαρκεί για να εξαναγκάσει νίκη απέναντι σε σωστή άμυνα^[1]. Με τέλειο παιχνίδι και από τις δύο πλευρές, η πρωτοβουλία εξανεμίζεται και η παρτίδα επισφραγίζεται με ισοπαλία.

Πηγές

1. Schaeffer, J., Burch, N., Björnsson, Y., Kishimoto, A., Müller, M., Lake, R., Lu, P., & Sutphen, S. (2007). Checkers Is Solved. Science, 317(5844), 1518–1522.
2. Allis, L. V. (1994). Searching for Solutions in Games and Artificial Intelligence. Ph.D. thesis, University of Limburg, Maastricht.
3. Boardgammon. “Checkers Rules: How to Play, Movement, and Captures.”
4. Shannon, C. E. (1950). Programming a Computer for Playing Chess. Philosophical Magazine, Ser. 7, 41(314), 256–275.
5. Boardgammon. “Checkers Crown: Play Online Checkers and Regional Draughts Variants.”
6. Boardgammon. “Play Checkers Online: Free Browser and Mobile Draughts.”
7. Boardgammon. “Checkers Variants: The Kinds of Draughts Played Around the World.”

Βρήκες λάθος ή κάποια φράση που δεν στέκει; Γράψε μας