Η μάθηση είναι μία κρίσιμη ικανότητα για πράκτορες που σχεδιάζονται για να λαμβάνουν μέρος σε ανταγωνιστικά παιχνίδια εναλλασσόμενων κινήσεων δύο παικτών όπως το τάβλι, το Othello, το σκάκι, το Hex, κλπ. Η επικρατούσα προσέγγιση της μάθησης σε παιχνίδια αυτού του είδους συνίσταται στην ενημέρωση κάποιας συνάρτησης αξιολόγησης καταστάσεων, συνήθως με την έννοια της χρονικής διαφοράς (TD) είτε υπό το κριτήριο βελτιστοποίησης MiniMax είτε υπό βελτιστοποίηση έναντι συγκεκριμένου αντιπάλου. Ωστόσο, η προσέγγιση αυτή περιορίζεται από διάφορους παράγοντες: (α) οι ενημερώσεις στη συνάρτηση αξιολόγησης είναι σταδιακές, (β) δείγματα από προηγούμενα παιχνίδια δεν μπορούν να αξιοποιηθούν, και (γ) η ποιότητα κάθε ενημέρωσης εξαρτάται από την τρέχουσα συνάρτηση αξιολόγησης. Σε αυτή τη διατριβή, παρουσιάζουμε τέσσερις παραλλαγές μιας προσέγγισης μάθησης βασισμένης στον αλγόριθμο Least-Squares Policy Iteration (LSPI) που εστιάζονται στην εκμάθηση συναρτήσεων αξιολόγησης καταστάσεων-ενεργειών (state-action) και δεν πλήττονται από τους προαναφερθέντες περιορισμούς. Το βασικό πλεονέκτημα των προτεινόμενων προσεγγίσεων είναι ότι ο πράκτορας μπορεί να κάνει μαζικές ενημερώσεις στη συνάρτηση αξιολόγησης με οποιαδήποτε συλλογή δειγμάτων, μπορεί να αξιοποιήσει δείγματα από παρελθόντα παιχνίδια, και μπορεί να κάνει ενημερώσεις που δεν εξαρτώνται από την τρέχουσα συνάρτηση αξιολόγησης. Παρουσιάζουμε την αποτελεσματικότητα και την ανταγωνιστικότητα των LSPI πρακτόρων έναντι του TD πράκτορα και επιλεγμένων ‘δύσκολων’ πρακτόρων στα κλασικά επιτραπέζια παιχνίδια Othello και τάβλι.
(EL)
The ability of learning is critical for agents designed to compete in a variety of two-player, turn-taking, tactical adversarial games, such as Backgammon, Othello/Reversi, Chess, Hex, etc. The mainstream approach to learning in such games consists of updating some state evaluation function usually in a Temporal Difference (TD) sense either under the MiniMax optimality criterion or under optimization against a specific opponent. However, this approach is limited by several factors: (a) updates to the evaluation function are incremental, (b) stored samples from past games cannot be utilized, and (c) the quality of each update depends on the current evaluation function due to bootstrapping. In this thesis, we present four variations of a learning approach based on the Least-Squares Policy Iteration (LSPI) algorithm that overcome these limitations by focusing on learning a state-action evaluation function. The key advantage of the proposed approaches is that the agent can make batch updates to the evaluation function with any collection of samples, can utilize samples from past games, and can make updates that do not depend on the current evaluation function since there is no bootstrapping. We demonstrate the efficiency and the competency of the LSPI agents over the TD agent and selected benchmark opponents in the classical board games of Othello/Reversi and Backgammon.
(EN)
