Εβδομάδα 4: Παίγνια δύο αντιπάλων

Σημειώσεις μελέτης βασισμένες στη Διάλεξη 4 του μαθήματος και στο εργαστήριο «MATLAB Basics, συνέχεια». Οι διαφάνειες βρίσκονται στο Moodle.

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

Παίγνια δύο αντιπάλων

Στα παίγνια δύο αντιπάλων (adversary ή two-person games) δύο παίκτες παίζουν εναλλάξ, ο καθένας με τις δικές του επιτρεπτές κινήσεις, δηλαδή με δικό του σύνολο τελεστών μετάβασης.

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

Ασχολούμαστε με παίγνια που έχουν τρεις ιδιότητες:

Το πρόβλημα με όρους αναζήτησης

Όπως στις προηγούμενες εβδομάδες, περιγράφουμε το παιχνίδι με καταστάσεις:

• κατάσταση είναι η διάταξη του ταμπλό σε μια στιγμή·
• χώρος καταστάσεων είναι όλες οι επιτρεπτές διατάξεις·
• τελεστές μετάβασης είναι οι επιτρεπτές κινήσεις·
• τελικές καταστάσεις είναι όσες τερματίζουν το παιχνίδι (π.χ. ματ, τρεις στη σειρά, ισοπαλία).

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

Το δένδρο παιχνιδιού

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

Γιατί δεν χτίζουμε όλο το δένδρο;

Αν μπορούσαμε να χτίσουμε όλο το δένδρο ως το τέλος του παιχνιδιού, το πρόγραμμα δεν θα έχανε ποτέ. Στην πράξη αυτό είναι αδύνατο λόγω της συνδυαστικής έκρηξης. Στο σκάκι, με περίπου 10 κινήσεις σε κάθε θέση και περίπου 40 κινήσεις ως το τέλος, το δένδρο έχει περίπου 10⁴⁰ φύλλα. Ακόμη και με ένα φύλλο ανά νανοδευτερόλεπτο (10⁻⁹ s), θα χρειαζόταν 10³¹ δευτερόλεπτα, δηλαδή περίπου 3 · 10²³ χρόνια: δεκάδες τρισεκατομμύρια φορές η ηλικία του σύμπαντος.

Πώς βγαίνουν αυτοί οι αριθμοί;

Πόσα φύλλα. Σε κάθε επίπεδο κάθε θέση «σπάει» σε περίπου 10 νέες θέσεις. Μετά από μία κίνηση έχουμε 10 θέσεις, μετά από δύο 10 · 10 = 100, και μετά από 40 κινήσεις, δηλαδή 40 φορές το 10, παίρνουμε τον αριθμό των φύλλων:

$$\underbrace{10 \cdot 10 \cdots 10}_{40} = 10^{40}$$

Πόσος χρόνος. Αν κάθε φύλλο θέλει 10⁻⁹ δευτερόλεπτα, πολλαπλασιάζουμε· οι εκθέτες προστίθενται:

$$10^{40} \cdot 10^{-9}\ \text{s} = 10^{40-9}\ \text{s} = 10^{31}\ \text{s}$$

Σε χρόνια. Ένα έτος έχει περίπου 365,25 · 24 · 3.600 ≈ 3,16 · 10⁷ δευτερόλεπτα, άρα τα χρόνια είναι:

$$\begin{aligned} \frac{10^{31}}{3{,}16 \cdot 10^{7}} &\approx 0{,}32 \cdot 10^{24} \\ &= 3{,}2 \cdot 10^{23} \end{aligned}$$

Σε σύγκριση με το σύμπαν, που είναι περίπου 1,38 · 10¹⁰ χρόνων:

$$\frac{3{,}2 \cdot 10^{23}}{1{,}38 \cdot 10^{10}} \approx 2{,}3 \cdot 10^{13}$$

Δηλαδή περίπου 23 τρισεκατομμύρια φορές η ηλικία του σύμπαντος.

Γι’ αυτό το δένδρο χτίζεται ως ένα μικρό βάθος, όσο επιτρέπει ο χρόνος που έχει το πρόγραμμα για κάθε κίνηση. Αντίθετα, η τρίλιζα είναι αρκετά μικρή (λιγότερες από 9! = 362.880 σειρές κινήσεων) ώστε ένα πρόγραμμα να την εξετάσει ολόκληρη και να μη χάνει ποτέ.

Γιατί 9!;

Η πρώτη κίνηση έχει 9 ελεύθερα τετράγωνα, η δεύτερη 8, η τρίτη 7, κ.ο.κ. Οι δυνατές σειρές κινήσεων είναι το γινόμενο:

$$\begin{aligned} 9! &= 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \\ &= 362.880 \end{aligned}$$

Είναι ανώτατο όριο: πολλές παρτίδες τελειώνουν νωρίτερα, όταν κάποιος κάνει τρίλιζα, οπότε οι πραγματικές παρτίδες είναι λιγότερες.

Συνάρτηση αξιολόγησης

Αφού το δένδρο σταματά πριν από το τέλος του παιχνιδιού, χρειαζόμαστε έναν τρόπο να βαθμολογήσουμε μια θέση «στη μέση». Αυτό κάνει η συνάρτηση αξιολόγησης (evaluation function): μια ευριστική συνάρτηση, όπως εκείνες της Εβδομάδας 3, που δίνει έναν αριθμό σε κάθε φύλλο. Μεγάλος αριθμός σημαίνει καλή θέση για τον MAX.

Στο σκάκι, μια απλή συνάρτηση αξιολόγησης συνδυάζει:

• υλικό: αθροίζεις την αξία των κομματιών σου και αφαιρείς του αντιπάλου (π.χ. πιόνι 1, ίππος ή αξιωματικός 3, πύργος 5, βασίλισσα 9)·
• θέση: πόντοι για κομμάτια που ελέγχουν το κέντρο της σκακιέρας·
• απειλές: πόντοι για κάθε κομμάτι του αντιπάλου που απειλείς, πολλοί περισσότεροι αν απειλείς τον βασιλιά.

Ο αλγόριθμος Minimax

Ο Minimax (ελαχίστου-μεγίστου) ονομάζει τους δύο παίκτες MAX και MIN. Ο MAX, συνήθως η ρίζα, θέλει τη μεγαλύτερη δυνατή τιμή· ο MIN τη μικρότερη.

1. Χτίσε το δένδρο ως κάποιο βάθος και βαθμολόγησε τα φύλλα με τη συνάρτηση αξιολόγησης.
2. Από κάτω προς τα πάνω, δώσε σε κάθε κόμβο:
   • σε κόμβο MAX, τη μέγιστη τιμή των παιδιών του·
   • σε κόμβο MIN, την ελάχιστη τιμή των παιδιών του.
3. Παίξε την κίνηση που οδηγεί στο παιδί της ρίζας με την καλύτερη τιμή.

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

Παράδειγμα

Ο MAX έχει τρεις κινήσεις, προς τις καταστάσεις A, B και C. Σε καθεμία ο MIN έχει τρεις απαντήσεις, και η συνάρτηση αξιολόγησης δίνει τις τιμές:

Σε κάθε κόμβο ο MIN διαλέγει τη μικρότερη τιμή, γιατί αυτή είναι η χειρότερη για τον MAX:

Στη ρίζα ο MAX διαλέγει τη μεγαλύτερη από αυτές:

άρα παίζει C και εξασφαλίζει τουλάχιστον 5. Πρόσεξε ότι το B έχει το μεγαλύτερο φύλλο (11), αλλά ο MIN δεν θα τον αφήσει ποτέ να φτάσει εκεί.

Τα τρίγωνα με τη μύτη προς τα πάνω είναι κόμβοι MAX και τα ανάποδα κόμβοι MIN: είναι η συνηθισμένη σύμβαση στα βιβλία.

Minimax στην τρίλιζα

Στην τρίλιζα το δένδρο είναι αρκετά μικρό για να φτάσει ως το τέλος του παιχνιδιού, οπότε δεν χρειάζεται εκτίμηση: κάθε φύλλο είναι νίκη (+1), ισοπαλία (0) ή ήττα (−1) για τον X. Στη θέση παρακάτω παίζει ο X (MAX) και έχει τρία ελεύθερα τετράγωνα:

• Γραμμή 3, στήλη 2: ο X κάνει τρίλιζα στη μεσαία στήλη. Τιμή +1.
• Γραμμή 2, στήλη 3: τώρα ο O πρέπει να κλείσει τη μεσαία στήλη, και μετά ο X παίρνει το τελευταίο τετράγωνο χωρίς να κερδίσει κανείς. Τιμή 0.
• Γραμμή 3, στήλη 1: ο O παίζει στη γραμμή 2, στήλη 3 και κάνει τρίλιζα στην τρίτη στήλη. Τιμή −1.

Ο X παίρνει τη μέγιστη τιμή, max(0, −1, +1) = +1, και κερδίζει. Οι τιμές υπολογίστηκαν με πλήρη αναζήτηση Minimax ως το τέλος κάθε παρτίδας.

Ο αλγόριθμος Alpha-Beta

Ο Minimax βαθμολογεί κάθε φύλλο. Ο Alpha-Beta δίνει πάντα το ίδιο αποτέλεσμα, αλλά παραλείπει («κλαδεύει») κλαδιά που αποδεδειγμένα δεν μπορούν να αλλάξουν την απόφαση. Το κλάδεμα αυτό δεν είναι ευριστικό: δεν στηρίζεται σε εκτίμηση, αλλά σε τιμές που έχουν ήδη υπολογιστεί.

Κρατά δύο όρια καθώς ψάχνει σε βάθος:

• α: η καλύτερη τιμή που έχει ήδη εξασφαλίσει ο MAX σε αυτή τη διαδρομή. Ξεκινά από −∞.
• β: η καλύτερη τιμή που έχει ήδη εξασφαλίσει ο MIN. Ξεκινά από +∞.

Όταν σε κάποιον κόμβο ισχύσει α ≥ β, τα υπόλοιπα παιδιά του δεν χρειάζεται να εξεταστούν.

• Ένας κόμβος MAX ανεβάζει το α όταν βρει παιδί με μεγαλύτερη τιμή.
• Ένας κόμβος MIN κατεβάζει το β όταν βρει παιδί με μικρότερη τιμή.

Το ίδιο παράδειγμα με Alpha-Beta

1. A: ο Alpha-Beta εξετάζει τα 6, 8, 4. Ο κόμβος A παίρνει τιμή 4, άρα ο MAX έχει εξασφαλίσει τουλάχιστον 4: α = 4.
2. B: το πρώτο φύλλο είναι 3. Ο MIN μπορεί λοιπόν να κρατήσει τον B στο 3 ή και χαμηλότερα (β = 3). Ο MAX όμως έχει ήδη το 4 από το A, άρα δεν θα διαλέξει ποτέ τον B. Αφού α = 4 ≥ β = 3, τα 11 και 7 δεν εξετάζονται καθόλου.
3. C: εξετάζει τα 9, 5, 10· η τιμή του C είναι 5 > 4, άρα α = 5.

Το αποτέλεσμα είναι το ίδιο με του Minimax (παίζει C, τιμή 5), αλλά με 7 αντί για 9 φύλλα. Σε μεγάλα δένδρα η εξοικονόμηση είναι τεράστια.

Γιατί έχει σημασία η σειρά; Ο Alpha-Beta κλαδεύει περισσότερο όταν εξετάζει πρώτα τις καλύτερες κινήσεις. Στην καλύτερη περίπτωση βαθμολογεί περίπου √N φύλλα αντί για τα N του Minimax. Στον ίδιο χρόνο, αυτό του επιτρέπει να ψάξει περίπου διπλάσιο βάθος.

Πώς βγαίνει το √N και το «διπλάσιο βάθος»;

Έστω ότι κάθε θέση έχει $b$ κινήσεις και ψάχνουμε σε βάθος $d$. Ο Minimax αξιολογεί όλα τα φύλλα:

$$N = b^{d}$$

Με τέλεια σειρά κινήσεων, ο Alpha-Beta χρειάζεται να «αποδείξει» την τιμή μόνο σε περίπου τα μισά επίπεδα, άρα αξιολογεί περίπου:

$$b^{d/2} = \sqrt{b^{d}} = \sqrt{N}$$

Γιατί διπλάσιο βάθος; Αν στον ίδιο χρόνο ο Minimax φτάνει σε βάθος $d$ (δηλαδή αξιολογεί $b^{d}$ φύλλα), ο Alpha-Beta με τον ίδιο αριθμό φύλλων φτάνει σε βάθος $d'$ τέτοιο ώστε οι δύο αριθμοί φύλλων να είναι ίσοι. Αφού έχουν την ίδια βάση $b$, εξισώνουμε τους εκθέτες:

$$\begin{aligned} b^{d'/2} &= b^{d} \\ \frac{d'}{2} &= d \\ d' &= 2d \end{aligned}$$

Η ακριβής τιμή. Οι Knuth και Moore (1975) έδειξαν ότι με τέλεια σειρά ο Alpha-Beta αξιολογεί ακριβώς:

$$b^{\lceil d/2 \rceil} + b^{\lfloor d/2 \rfloor} - 1$$

φύλλα. Στο δένδρο μας, με $b = 3$ και $d = 2$, αυτό δίνει 3 + 3 − 1 = 5: είναι ακριβώς η περίπτωση της ερώτησης 4 παρακάτω. Για $b = 10$ και $d = 4$ δίνει 100 + 100 − 1 = 199 φύλλα αντί για 10.000.

Πώς γίνονται ακόμα πιο γρήγοροι

• Ευριστικό κλάδεμα: κόβεις κινήσεις που μοιάζουν προφανώς κακές, με τον κίνδυνο να κόψεις και κάποια καλή.
• Δυναμική συνάρτηση αξιολόγησης, που αλλάζει ανάλογα με τη φάση του παιχνιδιού.
• Πίνακες μετάθεσης (transposition tables): αποθηκεύεις την τιμή κάθε θέσης που έχεις ήδη αξιολογήσει, γιατί η ίδια θέση μπορεί να προκύψει με διαφορετική σειρά κινήσεων.
• Έτοιμες κινήσεις για το άνοιγμα και το τέλος της παρτίδας (openings, endgames), χωρίς αναζήτηση.

Για να δεις τον Minimax να παίζει τρίλιζα βήμα βήμα, δοκίμασε το Elements of AI, στα ελληνικά.

Εργαστήριο: while, continue και break στο MATLAB

Ο βρόχος for τρέχει για προκαθορισμένες τιμές. Όταν δεν ξέρεις από πριν πόσες επαναλήψεις θα χρειαστούν, χρησιμοποιείς το while, που επαναλαμβάνει όσο ισχύει μια συνθήκη:

total = 0;
k = 0;
while total <= 100        % σταματά μόλις το άθροισμα ξεπεράσει το 100
    k = k + 1;
    total = total + k;
end
disp(k)                   % 14, γιατί 1 + 2 + … + 14 = 105

Μέσα στον βρόχο πρέπει κάτι να αλλάζει, ώστε η συνθήκη κάποτε να πάψει να ισχύει· αλλιώς ο βρόχος δεν τελειώνει ποτέ.

Δύο εντολές αλλάζουν τη ροή ενός βρόχου for ή while:

• continue: παραλείπει τις υπόλοιπες εντολές αυτού του κύκλου και περνά στον επόμενο.
• break: βγαίνει αμέσως από τον βρόχο.

v = [4 -2 7 0 9 3];
s = 0;
for k = 1:length(v)
    if v(k) < 0
        continue          % αγνόησε τους αρνητικούς
    end
    if v(k) == 0
        break             % σταμάτα στο πρώτο μηδέν
    end
    s = s + v(k);
end
disp(s)                   % 11 (4 + 7)

Ερωτήσεις αυτοαξιολόγησης

1. Γιατί το τάβλι δεν είναι ντετερμινιστικό παίγνιο, ενώ το σκάκι είναι;

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

2. Στο παράδειγμα, ο B έχει το μεγαλύτερο φύλλο (11). Γιατί ο MAX δεν τον διαλέγει;

Γιατί στον B παίζει μετά ο MIN, που θα διαλέξει το 3, τη χειρότερη τιμή για τον MAX. Ο Minimax υποθέτει ότι ο αντίπαλος παίζει πάντα την καλύτερη κίνηση για εκείνον.

3. Μπορεί ο Alpha-Beta να διαλέξει διαφορετική κίνηση από τον Minimax;

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

4. Ας πούμε ότι ο C εξετάζεται πρώτος και ότι στον A το 4 είναι το πρώτο φύλλο (4, 6, 8). Πόσα φύλλα βαθμολογεί τώρα ο Alpha-Beta;

Πέντε αντί για επτά. Μετά τον C (9, 5, 10) είναι α = 5. Στον A, το πρώτο φύλλο (4) δίνει β = 4 ≤ 5, άρα κόβονται τα 6 και 8. Στον B, το 3 κόβει τα 11 και 7. Όταν οι καλύτερες κινήσεις εξετάζονται πρώτες, ο Alpha-Beta κλαδεύει πολύ περισσότερο.

5. Τι κάνει μια συνάρτηση αξιολόγησης και γιατί τη χρειάζεται ο Minimax;

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

---

Πηγές: Διάλεξη 4 του μαθήματος· «MATLAB Basics, συνέχεια» του εργαστηρίου· Ι. Βλαχάβας, Π. Κεφαλάς, Ν. Βασιλειάδης, Φ. Κόκκορας, Η. Σακελλαρίου, Τεχνητή Νοημοσύνη (4η έκδοση)· Elements of AI.