RL Game – Τεχνητή νοημοσύνη


RL Game
Τεχνητή νοημοσύνη

Μέθοδος μέγιστης άμεσης ανταμοιβής (“Shortsighted”)

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

Για να αποτιμηθούν τα πιθανά σενάρια χρησιμοποιείται ο ακόλουθος τρόπος μέτρησης:

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

Για παράδειγμα, σε παιχνίδι με 10 πιόνια αρχικά, αν κάποια κίνηση εξαφανίζει 3 αντίπαλα πιόνια αποτιμάται με +30. Αν με κάποια κίνηση χάνονται 2 πιόνια του παίκτη που παίζει, τότε η κίνηση αυτή αποτιμάται με -20. Σε περίπτωση που με μια κίνηση εξαφανίζονται πιόνια και των δύο παικτών, τότε η κίνηση αυτή αποτιμάται με το αλγεβρικό άθροισμα των επιμέρους εξαφανίσεων. Για παράδειγμα, αν εξαφανιστούν 3 πιόνια του αντιπάλου και 2 πιόνια του παίκτη που παίζει, τότε η τελική αποτίμηση είναι (30 – 20 =) 10 πόντοι. Στην περίπτωση που η παρτίδα ξεκινάει με π.χ. 5 πιόνια, όλοι οι παραπάνω αριθμοί διπλασιάζονται λόγω του ότι είναι ανηγμένοι σε εκατονταβάθμια κλίμακα.

Η μέθοδος “Shortsighted” καταγράφει όλες τις δυνατές κινήσεις και επιλέγει αυτή με τη μεγαλύτερη ανταμοιβή. Σε περίπτωση που αυτήν τη μέγιστη ανταμοιβή τη δίνουν περισσότερες της μίας κινήσεις, τότε επιλέγεται κάποια από αυτές στην τύχη.

Μέθοδος ελαχιστοποίησης μεγίστου αρνητικού σεναρίου (“Minimax”)

Η μεθοδολογία του “Minimax” είναι ένας ευρύτατα γνωστός αλγόριθμος στον τομέα της θεωρίας παιγνίων.

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

Σε αυτήν την έκδοση του RL Game o Minimax υλοποιείται με την αναδρομική ανάπτυξη ενός δυναμικού δέντρου, η “ρίζα” του οποίου είναι η τρέχουσα κατάσταση, ενώ οι κόμβοι του είναι δομές δεδομένων που αναπαριστούν πιθανές μελλοντικές καταστάσεις του παιχνιδιού. Το “ύψος” αυτού του δέντρου εξαρτάται από το “βάθος” του Minimax που έχει επιλέξει ο χρήστης στο παράθυρο ρυθμίσεων. Η αύξηση αυτής της τιμής βελτιώνει δραστικά την αποτελεσματικότητα του αλγορίθμου. Επειδή όμως έτσι αυξάνονται με εκθετικό ρυθμό τα πιθανά σενάρια που πρέπει να αναλυθούν, αυξάνεται δραματικά η απαιτούμενη υπολογιστή ισχύς και ο αντίστοιχος χρόνος απόκρισης.

Κάθε κατάσταση του παιχνιδιού αποτιμάται με μία “αξία” που κυμαίνεται μεταξύ των τιμών -100 και 100. Η τιμή αυτή υπολογίζεται ως η διαφορά του αριθμού των πιονιών των δύο παικτών, ανηγμένη στην εκατονταβάθμια κλίμακα. Για παράδειγμα, έστω ότι σε παρτίδα με αρχικά 10 πιόνια, το παιχνίδι καταλήγει σε μια κατάσταση στην οποία ο μπλε παίκτης έχει 8 πιόνια ενώ ο κόκκινος 5. Η κατάσταση αυτή έχει αξία +30 [= (8 – 5)100/10] για τον μπλε παίκτη και -30 [= (5 – 8)100/10] για τον κόκκινο.

Όσον αφορά τις κινήσεις, η αξία τους υπολογίζεται ως η διαφορά της αξίας της τελικής κατάστασης (αυτής δηλαδή μετά την κίνηση) μείον την αξία της αρχικής κατάστασης (αυτής δηλαδή πριν την κίνηση). Σε περίπτωση που οι υποψήφιες βέλτιστες κινήσεις είναι περισσότερες από μία, επιλέγεται κάποια από αυτές στην τύχη.

Μέθοδος Ενισχυτικής Μάθησης (“Reinforcement Learning”)

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

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

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

  1. Καταγράφονται όλες οι δυνατές άμεσες κινήσεις.
  2. Για κάθε μία από αυτές καταγράφονται όλες οι δυνατές επόμενες κινήσεις.
  3. Η διαδικασία επαναλαμβάνεται όσες φορές ορίζει το “βάθος” του αλγορίθμου Minimax, σύμφωνα με την τιμή που έχει επιλέξει ο χρήστης στο παράθυρο ρυθμίσεων του παιχνιδιού.
  4. Με τα παραπάνω βήματα κατασκευάζεται ένα δυναμικό δέντρο με κόμβους δομές δεδομένων, που η κάθε μία αναπαριστά μια πιθανή κατάσταση του παιχνιδιού.
  5. Αποτιμάται κάθε δυνατή διαδρομή μέσα σε αυτό το δέντρο και η αξία της συνδέεται με την αρχική κίνηση από την οποία ξεκινά.
  6. Με βάση τη θεωρία του αλγορίθμου Minimax γίνεται επιλογή της βέλτιστης άμεσης κίνησης.
  7. Σε περίπτωση που οι βέλτιστες κινήσεις είναι περισσότερες από μία, τότε αποστέλλεται αίτημα στο διακομιστή της γνωσιακής βάσης. Το αίτημα αυτό ζητάει την αξία η οποία έχει αποδοθεί σε κάθε μία από τις καταστάσεις στις οποίες οδηγείται το παιχνίδι αν επιλεχθούν οι παραπάνω βέλτιστες κινήσεις.
  8. Γίνεται επιλογή της κίνησης που οδηγεί στην κατάσταση με τη μεγαλύτερη αξία.
  9. Αν η μέγιστη αξία που λήφθηκε από τη ΒΔ αντιστοιχεί σε περισσότερες από μία κινήσεις, τότε επιλέγεται κάποια από αυτές στην τύχη.
  10. Μετά την πραγματοποίηση της κίνησης, γίνεται ενημέρωση της γνωσιακής βάσης, με σκοπό της διόρθωση της αξίας της τρέχουσας αλλά και των προηγούμενων αυτής καταστάσεων, σύμφωνα με τα τρέχοντα πραγματικά δεδομένα του παιχνιδιού. Συνοπτικά ο ψευδοκώδικας του αλγορίθμου που πραγματοποιεί αυτήν την αναπροσαρμογή είναι ο ακόλουθος:
< Προηγούμενο: Κανόνες παιχνιδιού
RL Game – Τεχνητή νοημοσύνη
Επόμενο: Παιχνίδι! >