Human vs Machine

Ανέκαθεν το σκάκι θεωρούνταν ιδανικό πεδίο για την εφαρμογή των υπολογιστών.Ο σκοπός του είναι ξεκάθαρα ορισμένος και η πρόοδος σε αυτό μπορεί εύκολα να μετρηθεί με το σύστημα elo.Σύμφωνα με την λογική είναι ένα στοιχειώδες παιχνίδι :σε κάθε κίνηση ,απλά επιλέγεις από μια σειρά συνεχειών μέχρι να υπάρξει μάτ ή κάποια ισόπαλη θέση.Βέβαια πρακτικά αυτή η στρατηγική δεν είναι εφαρμόσιμη ,μιάς και ένας αστρονομικός αριθμός κινήσεων πρέπει να εξεταστεί.Γιαυτό το λόγο τόσο ο άνθρωπος όσο και οι υπολογιστές βασίζονται σε απλοποιήσεις προκειμένου να φτιάξουν ένα όσο το δυνατό πιο ακριβές μοντέλο του σκακιού.Οι άνθρωποι βασίζονται σε αιώνες παράδοσής και στα 200 χρόνια της σκακιστικής βιβλιογραφίας ενώ οι υπολογιστές στις εξελίξεις στην υπολογιστική νοημοσύνη στα τελευταία 50 χρόνια
ΙΣΤΟΡΙΚΗ ΑΝΑΔΡΟΜΗ

Η ιδέα της σκακιστικής μηχανής έχει τις ρίζες της στα 1760, όταν ο Βαρώνος Wolfgang von Kempelen επειδίκνυε το Chess Automaton στην Ευρώπη .Η μηχανή χαιδευτικά ονομαζόταν ο Τούρκος μιας και έπαιζε τις κινήσεις μέσω μιας μαριονέττας που φορούσε τουρμπάνι και ο χειρισμός της γινόταν, απο ένα πολύπλοκο μηχανισμό.Το επίπεδο της ήταν αρκετά καλό τόσο ώστε να έχει νικήσει τον Ναπολέωντα σε μόλις 19 κινήσεις.Το πρόβλημα υπήρξε όταν αποκαλύφθηκε ότι η μηχανή δεν ήταν τίποτα άλλο απο ένα ισχυρό σκακιστή ο οποίος ήταν στριμωγμένος μέσα της..

Ο Alan Turing ,o Άγγλος μαθηματικός,πρωτοπόρος της επιστήμης των υπολογιστών και της κρυπτογραφίας,ήταν ανάμεσα στους πρώτους που ασχολήθηκε με το πρόβλημα της λειτουργίας μιάς σκακιστικής μηχανής.Ήταν ευκολότερο για αυτόν να φτιάξει ένα θεωρητικό μοντέλο ενός προγράμματος . Την σημαντικότερη εργασία όμως ο Shannon o οποίος ήταν ο πρώτος που ουσιαστικά θεμελίωσε τον αλγόριθμο minmax(τον σημαντικότερο αλγόριθμο στην λειτουργία ενός σκακιστικού προγράμματος).

Το 1958 για πρώτη φορά σκακιστικό πρόγραμμα κερδίζει άνθρωπο.Όμως εδώ πρέπει να σημειωθεί ότι ο αντίπαλος, ήταν ο γραμματέας της εταιρίας που ανέπτυξε το πρόγραμμα και η γνώση της για το σκάκι περιοριζόταν σε ένα μάθημα 30 λεπτών πριν τον αγώνα..

Το 1966 για πρώτη φορά υπολογιστής συμμετέχει σε τουρνουά ανθρώπων.Ο MacHack VI (PDP-6) που αναπτύχθηκε απο το ΜΙΤ έλαβε μέρος στο τουρνουά αρχαρίων της Μασσαχουσέτης πετυχαίνοντας 1 ισοπαλία και 4 ήττες.

Το 1968 συμφωνείται το πιο γνωστό στοίχημα στην ιστορία του υπολογιστικού σκακιού.Ο διεθνής μαίτρ David Levy στοιχηματίζει 3.000$ ότι δεν θα χάσει απο υπολογιστή στα επόμενα 10 χρόνια.Το στοίχημα αποδέχεται ο John McCarthy ένας διακεκριμένος μελετητής της τεχνητής νοημοσύνης.

Το 1975 ο David Bronstein χρησιμοποιεί γαι πρώτη φορά υπολογιστή για να κερδίσει μια παρτίδα που έχει αναβληθεί σε ένα τουρνουά στο Vilnious.Πρόκειται για την Καϊσσα τον παγκόσμιο πρωταθλητή των υπολογιστών για το 1974 που αναπτύχθηκε σε ερευνητικό κέντρο της Μόσχας

Το 1978 ο David Levy κερδίζει το στοίχημα του 1968 νικώντας το σκακιστικό πρόγραμμα Chess 4.7 στο Τορόντο με 3.5-0.5.Είναι η πρώτη φορά που σκακιστικό πρόγραμμα καταφέρνει να πάρει ισοπαλία απο διεθνή μαίτρ

Το 1981 ο Cray Blitz κερδίζει το Πρωτάθλημα του Μισσισίπι με 5 νίκες επιτυγχάνοντας απόδοση 2258 elo.

Το 1988 ο Deep Thought και ο GM Tony Miles μοιράζονται την πρώτη θέση στο U.S Open.Η απόδοση του Deep Thought φτάνει τα 2485 elo

Στις αρχές της δεκαετίας του 90 οι νίκες σκακιστικών προγραμμάτων επί γνωστών GM έιναι κάτι το συνηθισμένο.Στα θύματα των υπολογιστών οι Huebner,Polgar, Karpov ,Kasparov.Ακόμα όμως, τα υπολογιστικά προγράμματα σε παρτίδες με κανονικό χρόνο σκέψης, έχουν αρκετά προβλήματα.

Το 1996 όμως ο Deep Blue παρά την ήττα απο το Kasparov με 4-2 ,είναι ο πρώτος υπολογιστής που καταφέρνει να νικήσει τον παγκόσμιο πρωταθλητή σε παρτίδα με επίσημο χρόνο σκέψης.

Το 1997 έρχεται η μεγάλη έκπληξη.Ο Deep Blue καταφέρνει να κερδίσει τον Kasparov με 3.5-2.5.Ο Deep Blue βασίζεται στον IBM RS/600.Αποτελείται απο 256 επεξεργαστές σε παράλληλη σύνδεση ικάνους να υπολογίζουν 200 εκατομμύρια κινήσεις το δευτερόλεπτο.

Σήμερα τα τουρνουά με την συμμετοχή σκακιστικών προγραμμάτων είναι θεσμός.Ο Deep Junior στο τουρνουά της Φρανκφούρτης κατέλαβε την 6ή θέση με απόδοση 2652 ξεπερνώντας ακόμα και τον παγκόσμιο πρωταθλητή της FIDE Alexander Khalifman.

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

Δύο είναι οι κύριες στρατηγικές που ακολουθούν οι προγραμματιστές σκακιστικών προγραμμάτων.Η πρώτη που ονομάζεται Shannon type A λαμβάνει υπόψη όλες τις δυνατές κινήσεις μέχρι ένα συγκεκριμένο βάθος.Προκειμένου να καταφέρει να εκτιμήσει την θέση που θα προκύψει μετα απο κάποιες συγκεκριμένες κινήσεις,ο υπολογιστής ,χρησιμοποιεί την λεγόμενη συνάρτηση εκτίμησης.Έτσι με την βοήθεια κάποιων στατικών και δυναμικών χαρακτηριστικών όπως το υλικό ,η ανάπτυξη η θέση του βασιλιά κ.α ο υπολογιστής αντιστοιχεί σε κάθε θέση ένα θετικό η αρνητικό αρθμό που εκφράζει μαθηματικά την κατάσταση της θέσης.

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

           Ρε4, Ια1, Ρθ8			
         /   /  |     \   \				
            Παίζει ο Λευκός   
     /     /    |       \     \				
   /      /     |        \      \				
 Ρε5    Ρε3    Ρδ4 ..... Ιγ2    Ιβ3			
 /|\    /|\    /|\       /|\    /|\				
/ | \  / | \  / | \     / | \  / | \			
  Παίζει ο μαύρος

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

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

Γενικα η πρώτη προσέγγιση χρησιμοποιείται σε συστήματα με μεγάλη επεξεργαστική ισχύ (παράλληλα συστήματα) ενώ η δεύτερη σε προγράμματα που τρέχουν σε μονοεπεξεργαστικά συστήματα όπως τα PC.Tα σημερινά εμπορικά προγράμματα ανήκουν στην δεύτρη κατηγορια.

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

Ανάμεσα σε αυτές οι πιο γνωστές είναι οι εξής

Σήμερα η εξέλιξη είναι διαρκής στα σκακιστικά προγράμματα.Κάθε χρόνο διοργανώνεται παγκόσμιο πρωτάθλημα υπολογιστών και κάθε τρίμηνο ανακoiνώνεται η κατάταξη των εμπορικών σκακιστικών προγραμμάτων απο την SSDF.Στην τελευταία λίστα προηγείται ο Fritz 6 με ένα elo που προσεγγίζει το 2600.Βέβαια δεν υπάρχει αντιστοιχία με το ανθρώπινο elo μιας και η λίστα βασίζεται μόνο σε αγώνες μεταξυ σκακιστικών προγραμμάτων.