Πληροφορική

Πριν από μία δεκαετία, το σκακιστικό πρόγραμμα της IBM, το Deep Blue, νίκησε τον παγκόσμιο πρωταθλητή Γκάρι Κασπάροφ σε έναν αγώνα έξι παρτίδων. Το γεγονός αποτέλεσε ορόσημο, αφού ανάγκασε τους ανθρώπους να παραχωρήσουν την κυριαρχία τους σε ένα ακόμα παιχνίδι στρατηγικής. Έκτοτε, τη μοναδική αχίλλειο πτέρνα της επιστήμης των υπολογιστών φαινόταν να αποτελεί το ασιατικό επιτραπέζιο παιχνίδι Γκο: οι άνθρωποι μπορούσαν να κερδίζουν άνετα τις μηχανές. Ένας νέος αλγόριθμος, όμως, μπορεί πλέον να αντιμετωπίζει δυνατούς ανθρώπους-παίκτες, και να τους κερδίζει.

Το Γκο αποδείχθηκε απίστευτα δύσκολο για τους προγραμματιστές υπολογιστών, εξαιτίας της κρυφής πολυπλοκότητάς του. Ο σκοπός στο Γκο είναι η οριοθέτηση της περιοχής και η περικύκλωση του αντιπάλου με την τοποθέτηση μαύρων ή άσπρων χαλικιών στις διασταυρώσεις ενός πλέγματος γραμμών διαστάσεων 9 x 9 ή 19 x 19. Ιδιαίτερα στον μεγάλο πίνακα, το πλήθος των δυνατών κινήσεων ανά γύρο είναι τεράστιο ―200 κατά μέσο όρο για κάθε θέση στο μέσο του παιχνιδιού, σε σύγκριση με κάποιες δεκάδες πιθανές θέσεις στο σκάκι. Υπάρχουν επίσης τεράστιοι παράγοντες διακλάδωσης. Αν ο πίνακας έχει Ν θέσεις, το συνολικό πλήθος των πιθανών θέσεων του παιχνιδιού είναι 3^Ν, διότι κάθε θέση μπορεί να καταλαμβάνεται από ένα μαύρο ή λευκό κομμάτι, ή να παραμένει κενή. Το συνολικό πλήθος των επιτρεπόμενων κινήσεων στον μικρό πίνακα είναι περίπου 10³⁸, ενώ στον μεγάλο πίνακα 10¹⁷⁰. Επιπλέον, τα περισσότερα χαλίκια δεν εξασφαλίζουν τη νίκη, και οι παίκτες πρέπει να μπορούν να αξιολογούν τοπικές θέσεις και ταυτόχρονα να βλέπουν τον πίνακα ως σύνολο.

Για να αντιμετωπίσουν αυτές τις τεράστιες προκλήσεις, ειδικοί της τεχνητής νοημοσύνης σχεδίασαν αλγορίθμους με σκοπό τον περιορισμό των αναζητήσεων, αλλά τα προγράμματα αυτά δεν κατάφεραν να νικήσουν τους καλύτερους ανθρώπους-παίκτες στον μεγάλο πίνακα. Το περασμένο φθινόπωρο, δύο ούγγροι ερευνητές ανέφεραν ότι ο αλγόριθμός τους ξεπέρασε τα ποσοστά επιτυχίας των καλύτερων προγραμμάτων Γκο κατά ποσοστό 5% και μπορούσε να αντιμετωπίσει επαγγελματίες παίκτες Γκο σε μικρούς πίνακες. Ο αλγόριθμος ονομάζεται UCT (από τη φράση upper confidence bounds applied to trees, που μεταφράζεται «άνω όρια εμπιστοσύνης σε δέντρα») και αναπτύχθηκε από τον Levente Kocsis, του Ινστιτούτου Έρευνας για τους Υπολογιστές και τον Αυτοματισμό της Ουγγρικής Ακαδημίας Επιστημών στη Βουδαπέστη, και τον Csaba Szepesvari, ο οποίος τώρα εργάζεται στο Πανεπιστήμιο της Αλμπέρτα στο Έντμοντον. Ο αλγόριθμος UCT αποτελεί επέκταση της γνωστής μεθόδου Μόντε Κάρλο.

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

Ο αλγόριθμος UCT επεκτείνει τον αλγόριθμο Μόντε Κάρλο εστιάζοντας την αναζήτηση στις κινήσεις με τις καλύτερες προοπτικές. «Η κεντρική ιδέα στην οποία βασίζεται η εν λόγω προσέγγιση είναι η επιλεκτική δειγματοληψία ενεργειών», λέει ο Kocsis. Ο αλγόριθμος πρέπει να πετύχει μια ισορροπία, ελέγχοντας εναλλακτικές λύσεις που προς στιγμήν μοιάζουν βέλτιστες για να εντοπίσει πιθανές αδυναμίες και εξερευνώντας «άλλες λύσεις οι οποίες φαίνονται λιγότερο βέλτιστες, ώστε να εξασφαλιστεί ότι δεν έχουν παραβλεφθεί καλές εναλλακτικές προσεγγίσεις εξαιτίας πρώιμων σφαλμάτων εκτίμησης», όπως εξηγεί.

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

Ο UCT αποφασίζει αν η ολοκληρωμένη τυχαία παρτίδα είναι νίκη ή ήττα, και έπειτα ενημερώνει τα στατιστικά όλων των κινήσεων που πραγματοποιήθηκαν κατά τη διάρκεια του παιχνιδιού. Αν ο αριθμοδείκτης είναι ίσος με το ρυθμό επιτυχιών της κίνησης, ο αλγόριθμος εστιάζεται γρήγορα στην πιο πολλά υποσχόμενη διαδρομή. Τίποτα όμως δεν εγγυάται ότι μια αρχικά επιτυχημένη διαδρομή θα αποδώσει στο τέλος μια νικηφόρα κίνηση. Έτσι, κατά την επιλογή των κινήσεων, ο UCT προσαρμόζει τους ρυθμούς επιτυχιών δίνοντας μεγαλύτερο βάρος στις υποψήφιες κινήσεις με τη μικρότερη επισκεψιμότητα. Οι ερευνητές δανείστηκαν αυτή την ιδέα από προβλήματα που σχετίζονται με τους γνωστούς «κουλοχέρηδες» ―η επιλεκτική στάθμιση αποφέρει το μέγιστο όφελος για έναν παίκτη ο οποίος παίζει ταυτόχρονα σε πολλούς κουλοχέρηδες με άγνωστη μέση ανταπόδοση.

Οι μαθηματικοί Sylvain Gelly και Yizao Wang, οι οποίοι εργάζονται στην Πολυτεχνική Σχολή του Παρισιού, είναι οι πρώτοι που χρησιμοποιούν τον αλγόριθμο UCT σε ένα πρόγραμμα το οποίο ονομάζουν MoGo. Το ποσοστό επιτυχιών του προγράμματος είναι κατά 5% υψηλότερο από εκείνο του προηγούμενου καλύτερου αλγορίθμου επέκτασης της μεθόδου Μόντε Κάρλο. Εξοπλισμένο με τον κορυφαίο πλέον αλγόριθμο Γκο, το MoGo έκανε επίδειξη των δυνατοτήτων του τον Μάρτιο κατά τη διάρκεια ενός τουρνουά, κατατροπώνοντας δυνατούς παίκτες σε πίνακες 9 x 9 και νικώντας πιο αδύναμους παίκτες σε μεγάλους πίνακες. Ο Gelly λέει ότι ο αλγόριθμος UCT είναι απλός στην υλοποίησή του και μπορεί να βελτιωθεί περαιτέρω ―ένας ακόμα λόγος για να περιμένουμε ότι η ανθρώπινη κυριαρχία στο Γκο θα φτάσει τελικά στο τέλος της.

Επιστημονικά Νέα - Ιούνιος, 2007