Correspondence Chess II - Σκακιστικές Μηχανές Ι

I - Εισαγωγικά

Ο Claude Shannon ήταν ένας Αμερικανός μαθηματικός, ηλεκτρονικός και κρυπτογράφος που γεννήθηκε το 1916 στο Μίσιγκαν και πέθανε το 2001 στη Μασαχουσέτη. Το διδακτορικό του πάνω στη δυαδική άλγεβρα το 1937 αποτέλεσε τη βάση πάνω στην οποία λειτουργεί κάθε ψηφιακό κύκλωμα. Απέδειξε ουσιαστικά πως οποιαδήποτε ηλεκτρονική υλοποίηση της δυαδικής άλγεβρας μπορεί να κατασκευάσει και να επιλύσει κάθε λογική και αριθμητική πράξη. Το γνωστό κλισέ "όλα στον υπολογιστή είναι 0 και 1" στηρίζεται πάνω στη δουλειά του. Στα καθ' ημάς η μελέτη του "Προγραμματίζοντας έναν υπολογιστή να παίζει σκάκι" που δημοσιεύτηκε το 1950,  καθόρισε τη βασική δομή μιας σκακιστικής μηχανής, ενώ όρισε δύο διακριτές οικογένειες σκακιστικών μηχανών, τη μηχανή τύπου Α και τη μηχανή τύπου Β. Το 99% των σκακιστικών μηχανών που έχουν υλοποιηθεί από τότε μέχρι σήμερα συμφωνεί με αυτή τη δομή και ταιριάζει σε αυτήν την ταξινόμηση, είτε μιλάμε για hardware μηχανές όπως τα θρυλικά Memphisto αλλά και ο Deep Blue, είτε μιλάμε για το λογισμικό που χρησιμοποιούμε  κατά κόρον σήμερα, τα Stockfish, Houdini, Fritz, Komodo, Rybka κλπ.

Οι μηχανές τύπου Α παίρνουν με τη σειρά όλες τις κινήσεις σε μία θέση και τις αναλύουν μία-μία διαδοχικά σε κάποιο βάθος δημιουργώντας ένα εικονικό δέντρο με όλες τις βαριάντες που είναι πιθανόν να προκύψουν μέχρι αυτό το ορισμένο βάθος κινήσεων - το περιβόητο Depth που βλέπουμε στις οθόνες μας. Κάθε σημείο διακλάδωσης αυτού του δένδρου που προκύπτει είναι στην πραγματικότητα μία σκακιστική θέση P. Για κάθε τέτοιο P η μηχανή καλεί μια συνάρτηση εκτίμησης Ε(P) που επιστρέφει ένα σκορ. Η μηχανή συνεχώς συγκρίνει αυτά τα σκορ που λαμβάνει για κάθε θέση μεταξύ τους και τελικά σχεδιάζει μία διαδρομή μέσα σε αυτό το δέντρο που μας δείχνει την αλληλουχία των κινήσεων που συνιστούν το καλύτερο παιχνίδι και των δύο πλευρών της παρτίδας. Βήμα προς βήμα, κίνηση προς κίνηση, όταν είναι να παίξει ο λευκός στη διάρκεια αυτής της διαδρομής η μηχανή επιλέγει την κίνηση εκείνη που οδηγεί σε μεγαλύτερο σκορ και όταν παίζει ο μαύρος αυτή που οδηγεί σε μικρότερο. Για οποιοδήποτε Depth του ορίσουμε - ή οποιοδήποτε Depth έχουμε την υπομονή να περιμένουμε να φτάσει - μας επιστρέφει την αλληλουχία των καλύτερων κινήσεων - την Principal Variation - και το τελικό σκορ του "φύλλου" του δένδρου στο οποίο αυτή η αλληλουχία οδηγεί. Αυτός ο αριθμός - το σκορ - είναι που βλέπουμε τελικά στις οθόνες μας ως εκτίμηση της αρχικής θέσης στο συγκεκριμένο Depth. Το σκορ δηλαδή δεν αφορά τη θέση που βλέπουμε μπροστά μας αλλά τη θέση στην οποία καταλήγει η βαριάντα που μας δίνει ως τη σωστότερη.

Οι μηχανές τύπου Β κάνουν ακριβώς το ίδιο πράγμα με μια σημαντική διαφορά. Αντί να αναλύουν μία προς μία διαδοχικά όλες τις κινήσεις από την αρχική θέση και όλες τις κινήσεις σε κάθε διακλάδωση του δέντρου, επιλέγουν μόνο ένα υποσύνολο αυτών - και μάλιστα μικρό υποσύνολο - και έτσι το δένδρο τελικά που εξετάζουν είναι πολύ μικρότερο σε πλάτος και περιέχει πολύ λιγότερους κόμβους, πολύ λιγότερες δηλαδή σε αριθμό θέσεις P για τις οποίες καλείται η συνάρτηση εκτίμησης Ε(P). Οι τεχνικές με τις οποίες επιλέγεται κάθε φορά αυτό το υποσύνολο  κινήσεων προς διερεύνηση ποικίλουν αλλά η αρχική ιδέα ήταν να προσομοιάζουν τον τρόπο με τον οποίον προσεγγίζει το πρόβλημα ο ανθρώπινος εγκέφαλος, και πιο συγκεκριμένα ο ανθρώπινος εγκέφαλος ενός σκακιστή, όπως για παράδειγμα τεχνικές που στηρίζονται σε αναγνώριση προτύπων (pattern recognition). Ο διασημότερος υποστηρικτής των μηχανών τύπου Β ήταν o Mikhail Botvinnik - γιατί απλώς πίστευε πως θα αποτελούσε μεγάλη παραχώρηση το να μη χρησιμοποιηθεί η σκακιστική ευφυΐα ενός ισχυρού μαιτρ στην επιλογή των πιθανών κινήσεων και να χάνει άδικα χρόνο ο υπολογιστής "μετρώντας" κάθε χαζή κίνηση. Και ο ίδιος ο Shannon θεωρούσε ουτοπικό το να φτιαχτεί μια μηχανή τύπου Α, αυτός για τεχνολογικούς λόγους διότι πίστευε πως η ισχύς των επεξεργαστών υπολογιστών δε θα είναι ποτέ αρκετή για να επιτρέψει τη δημιουργία ενός ισχυρού σκακιστικού προγράμματος που θα αναλύει όλες τις πιθανές κινήσεις κάθε θέσης. Περιττό να πούμε το ότι και οι δύο έκαναν λάθος και πως σήμερα όλες οι μηχανές και τα προγράμματα που χρησιμοποιούμε ανήκουν στην οικογένεια των μηχανών τύπου Α.

Το μεγάλο - και ανυπέρβλητο - πρόβλημα στην εξέλιξη των μηχανών τύπου Β ήταν πως αποδείχτηκε αδύνατον να μεταγραφεί σε κώδικα ο τρόπος με τον οποίον επιλέγουν οι ισχυροί παίκτες το ποιες κινήσεις πρέπει να αναλύσουν. Το 90% των κινήσεων που "κρεμάνε" υλικό ο άνθρωπος δεν τις αναλύει καθόλου. Το άλλο 10% όμως αποτελείται από θυσίες που κερδίζουν φορσέ ή - το δυσκολότερο - από στρατηγικές θυσίες με αντάλλαγμα κάποιο δομικό χαρακτηριστικό της θέσης (π.χ. Benko Gambit) και θυσίες για την πρωτοβουλία. Το όραμα πολλών να μετατρέψουν σε λογισμικό την προσέγγιση στη θέση που προτείνει ο Kotov στο Think Like a Grandmaster αποδείχτηκε ουτοπικό. Για να βρει ο υπολογιστής μία Κασπαροβική θυσία πιονιού στο κέντρο με αντάλλαγμα την πρωτοβουλία, πρέπει να αναλύσει σε βάθος όλες τις θυσίες πιονιού που βλέπει. Το να εντοπίσει μόνος του την ενδιαφέρουσα και να αναλύσει μόνον αυτή αποδείχτηκε αδύνατο. Ενώ ο άνθρωπος δυσκολεύεται στο να θυμάται τί έχει μετρήσει και να οργανώσει τα συμπεράσματα αυτών των αναλύσεών του νοερά πριν αποφασίσει, ο υπολογιστής αποδείχτηκε πως παρόλο που μπορεί να θυμάται τα πάντα που έχει αναλύσει, δεν μπορούσε να επιλέξει το τί θα έπρεπε να αναλύσει εξ αρχής και πόσο. Έτσι καταλήξαμε στο να αναλύει τα πάντα μέχρι να τον σταματήσει κάποιος ή να του αλλάξει τη θέση. Ή για να είμαστε ακριβείς, σχεδόν τα πάντα.

Πάρα πολύ νωρίς στην ιστορία της πληροφορικής, από το 1928 ακόμα στο τομέα της θεωρίας των παιγνίων - της τόσο κατασυκοφαντημένης στη χώρα μας το τελευταίο διάστημα - εισήχθη από τον John Von Neumann το θεώρημα της εκτίμησης MiniMax. Ξεφεύγει από τους σκοπούς του άρθρου αυτού - και του μπλογκ γενικότερα - το να εξηγήσει αυτό το θεώρημα. Η πιο απλή εξήγησή του με παραδείγματα που γνωρίζω αφορά το παιχνίδι της τρίλιζας και βρίσκεται εδώ. Σε ότι μας αφορά, η ουσία του MiniMax αλγορίθμου βρίσκεται στην εξής ιδέα: Αν σε μία θέση P μία κίνηση οδηγεί σε σκορ 5 και μία σε -10, τότε το κλαδί του δέντρου που αρχίζει με την κίνηση που οδηγεί σε -10 δε χρειάζεται να το αναλύσουμε ολόκληρο. Θα προχωρήσουμε ελέγχοντας όλα τα φαγώματα, τα σαχ, τις προαγωγές κ.ο.κ. αλλά κάποια στιγμή όταν θα φτάσουμε σε ήσυχη θέση θα σταματήσουμε να ασχολούμαστε αν το σκορ παραμένει σχετικά χαμηλό. Ως τελευταία δοκιμή, μπορούμε να δώσουμε δύο φορές την κίνηση στον αδύναμο παίχτη και αν και πάλι δε δούμε σοβαρή μεταβολή προς τα πάνω, θα κόψουμε εντελώς το κλαδί. Αυτή η κάπως εκλαϊκευμένη περιγραφή εξηγεί τη βασική λειτουργία του περιβόητου Pruning (κλαδέματος). Το δε κολπάκι με τη διπλή κίνηση του αδύναμου παίχτη είναι γνωστό στο σκακιστικό προγραμματισμό - και γενικότερα στον προγραμματισμό παιγνίων, ως Null Move Euristic και χρησιμοποιείται στον αλγόριθμο αναζήτησης Alpha-Beta, έναν αλγόριθμο υλοποίησης του MiniMax θεωρήματος. Ο αλγόριθμος Alpha-Beta αποτελεί σήμερα το σκελετό πάνω στο οποίον γράφονται όλα τα σκακιστικά προγράμματα. Όποιος θέλει μπορεί να δει το παρακάτω εισαγωγικό βίντεο:

Μπορεί λοιπόν οι απόπειρες να οριστούν από τα πριν υποσύνολα κινήσεων που έχουν νόημα να αναλυθούν να απέτυχαν παταγωδώς - και οι μηχανές τύπου Β να έχουν ουσιαστικά εκλείψει -, όμως τα δέντρα που παράγουν οι μηχανές τύπου Α κλαδεύονται με διάφορους τρόπους και έτσι ο αριθμός των θέσεων για τις οποίες καλείται η συνάρτηση εκτίμησης είναι πολύ μικρότερος από το συνολικό αριθμό των πιθανών θέσεων (Nodes) που μπορούν να προκύψουν από την αρχική θέση. Έτσι ουσιαστικά έχουμε ένα υβριδικό σύστημα. Συμπερασματικά, μετά από όλα τα προαναφερθέντα, μπορούμε ήδη να ορίσουμε δύο τρόπους με τους οποίους ο άνθρωπος - στο θέμα μας, ένας Corr παίκτης - μπορεί να βοηθήσει μία σκακιστική μηχανή.

1ον) Στη αρχική θέση ανάλυσης να σπρώξει τη μηχανή προς συγκεκριμένες κινήσεις. Ας πούμε η κίνηση 8.e4 στη βασική θέση της βαριάντας Panno της Ινδικής του Βασιλιά είναι γνωστό πως δεν είναι καλή. Αντίθετα η ιδέα 8.Bf4,9.Rc1 που εμποδίζει το θεματικό b5 του μαύρου είναι πολύ ενδιαφέρουσα.  Ενδεικτικά το Stockfish 5 σε Depth 20 τις δίνει περίπου ισοδύναμες. Με το να σπρώξουμε τη μηχανή προς το 8.Bf4, μετατρέπουμε τη μηχανή μας σε μια απίστευτα έξυπνη εκδοχή της μηχανής τύπου Β που περιγράψαμε πιο πάνω. Αυτό προσπαθούσε να κάνει ο Botvinnik για 3 δεκαετίες χωρίς επιτυχία - χωρίς ανθρώπινο χέρι. Αντιστοίχως στην πιονοδομή της Γαλλικής όλοι οι καλοί Corr παίκτες αλλά και όλοι οι αναλυτές και συγγραφείς βιβλίων δοκιμάζουν σχεδόν σε κάθε θέση το f6 του μαύρου.  Σχεδόν πάντα οι μηχανές δεν ενθουσιάζονται με αυτή την ιδέα. Κάποιες φορές είναι η καλύτερη κίνηση και σχεδόν πάντα μία από τις καλές υποψήφιες.

2ον) Να εντοπιστούν οι περιπτώσεις λανθασμένου κλαδέματος της Alpha-Beta. Εδώ έχουμε τη γενική περίπτωση στην οποία λέμε ότι ο υπολογιστής δε βρίσκει το σωστό σχέδιο - αυτά που προτείνει δεν οδηγούν σε πρόοδο. Η συχνότερη περίπτωση είναι όταν δεν μπορούν να βελτιωθούν οι θέσεις των κομματιών, ενώ όλα τα breaks πιονιών βραχυπρόθεσμα οδηγούν σε μείωση του σκορ για τον παίκτη που τα παίζει, με αποτέλεσμα να κλαδεύονται από τον αλγόριθμο. Ας δούμε τη θέση-παράδειγμα από το πρώτο μέρος της σειράς.

Θέση Corr #1
Litvinov-Sarakenidis,EU/WS/O/090

Παίζει ο μαύρος. SF5/d38/35...Kh7/-1.14

Ο υπολογιστής παίζει Kh7 και δύο κινήσεις μετά Kg7. Στην Principal Variation του μεταφέρει τη ντάμα από το b4 στο e7 και πάλι πίσω στο b4. Κάποια στιγμή παίζει f5 με τον ίππο στο d4. Ο λευκός βάζει τη ντάμα στο g5 και σχεδόν ισοφαρίζει. Όταν έβαλα την τελική θέση της Principal Variation ως αρχική νέας ανάλυσης, η εκτίμηση σύντομα έπεσε στο -0.31. Έπαιξα 35...Nf4 - η μοναδική κίνηση που κάποιος μπορεί να ισχυριστεί πως αποτελεί βελτίωση κομματιού και μετά από 36.Ne1 είδα και πάλι πως οι προτάσεις του υπολογιστή δεν οδηγούν πουθενά. Πρώτη επιλογή σε μεγάλα Depth έδινε την υποχώρηση 36...Ne6.  Μετά από 37.Nf3 ο αντίπαλος μου πρότεινε ισοπαλία.




Ο υπολογιστής δεν καταλαβαίνει ποιό είναι το πρόβλημα με αυτά που προτείνει. Δε δίνει δεκάρα για το αν θα κερδηθεί η παρτίδα. Όσο βλέπει τις καλύτερες θέσεις των μαύρων κομματιών, το καθυστερημένο d3 πιόνι και την εδαφική υπεροχή του μαύρου, συνεχίζει ικανοποιημένος να τα κουνάει πέρα-δώθε. Δε θα προτείνει ποτέ την αλλαγή της πιονοδομής. Ο άνθρωπος αν ασχοληθεί 10-15 λεπτά με τη θέση θα καταλάβει πως μόνο με αλλαγή της πιονοδομής μπορεί να επιτευχθεί πρόοδος. Δοκίμασα να κάνω να "δουλέψει" το g5, ακολούθως το f5 (φαίνεται άσχημο, αλλά στο Corr οι δοκιμές είναι τζάμπα αν έχεις διαθέσιμο χρόνο) και τελικά κατέληξα στο c6-b5.

37...Qe7 38.Qd1 Nf4 39.Ne3 c6 40.Nc4 Qb4 41.Qc2 b5 42.Nb2 Qd6 43.g3 Ne6 44.Rd1?! (Επιταχύνει το τέλος, 44.Qc1 ήταν πιο ανθεκτικό) g5! 45.hg5 fg5 -+

Αυτή τη θέση το Stockfish τη δίνει σε Depth 33/-.1.14 όπως και αυτή του προηγούμενου διαγράμματος δηλαδή. Όμως, το κρίσιμο στοιχείο που με οδήγησε στο να στοχεύω σε αυτή τη θέση, ήταν το γεγονός πως δίνει ως φορσέ το 46.d4 και όλες τις άλλες κινήσεις του λευκού πάνω από -2.00. Κάθε πιθανότητα φρουρίου, κάθε πιθανότητα να προκύψει θέση που δεν έχει πρόοδο ο μαύρος έχει εκλείψει αν ο λευκός είναι υποχρεωμένος να βάλει d4. Η θέση θα ανοίξει και όλα τα στρατηγικά πλεονεκτήματα του μαύρου θα μετρήσουν στην ανοικτή θέση. Η συγκεκριμένη παρτίδα ήταν η 2η μου παρτίδα στο ICCF - ή τουλάχιστον η 2η στην οποία έβαλα engine. 46...ed4 47.Rcd3 (φορσέ) Qe7 48.Ne5 (επίσης φορσέ) Rc7 49.Rf3 Qc5 50.Qxc5 Nxc5 51.Rc1 Nxe4 52.ab5 Rd5! 53.b6 Re7 54.Nec4

Όλες οι κινήσεις του λευκού από το 44...g5! μέχρι αυτή τη θέση ήταν φορσέ. Οτιδήποτε άλλο και να έπαιζε το σκορ του χειροτέρευε απότομα. Αυτό το είχα εντοπίσει και όταν έπαιξα 44...g5 είχα ήδη αφήσει μία νύχτα τη θέση μετά από 54.Nec4. Το πρωί είδα πως έχω ξεφύγει πια από το "εφιαλτικό" -1.14. Ήδη σε Depth 32 το σκορ ήταν -1.78. Αυτό είναι ένα παράδειγμα αυτού που ονομάζουμε Tunnel Variation. Στην αρχή του Tunnel ο υπολογιστής δίνει ένα σκορ αλλά συνεχίζει και αναλύει διάφορες κινήσεις οι οποίες δε θα παιχτούν ποτέ. Υποχρεώνοντάς τον να αναλύσει τη θέση στο τέλος του τούνελ - αφού όλα τα ενδιάμεσα βήματα για τον ένα παίχτη είναι φορσέ - κάνουμε με το χέρι αυτό που ήθελαν να κάνουν οι μηχανές τύπου Β, να μετρούν δηλαδή μόνο ό,τι έχει νόημα να μετρηθεί.





Ο εντοπισμός τέτοιων φορσέ βαριαντών είναι μια πολύ βασική ικανότητα στο Corr. Αν ο αντίπαλος δεν έχει βρει το Tunnel ή το βρει αφού μπει σε αυτό, πολλές φορές η παρτίδα έχει τελειώσει. Εδώ βέβαια ξεκινήσαμε από μία ήδη πολύ πλεονεκτική θέση, αυτό όμως μπορεί να συμβεί και σε ισόπαλες θέσεις. Η παρτίδα κράτησε άλλες 20 κινήσεις ξεκινώντας με το 54...g4 αλλά είχε ήδη κριθεί. Το μόνο που χρειαζόταν στη συνέχεια ήταν λίγη υπομονή. Litvinov-Sarakenidis.

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

Θέση Corr #2

Παίζει ο λευκός. Έχει παιχτεί το φινάλε του Βερολίνου στην Ισπανική. Ψάχνουμε και πάλι πρόοδο για τα λευκά.