The aim of this thesis is to design a competitive Artificial Intelligence AI algorithm for Scopone, a famous Italian-card game. In particular, we focused on the Monte Carlo Tree Search (MCTS) algorithms. However, MCTS requires full knowledge of the game state, therefore we also used an extension of the algorithm called Information Set Monte Carlo Tree Search (ISMCTS), that can work with partial knowledge of the game state. We developed different improvements of MCTS and ISMCTS, and we evaluated their playing strength against three rule-based AI encoding rules taken from well-known strategy books of Scopone. Our results showed that the deck team has an advantage over the hand team and the MCTS and ISMCTS algorithms proved to be stronger than the rule-based AI. Finally, we also developed an application to let human players interact with our AI.

Lo scopo di questa tesi è quello di progettare un algoritmo d'Intelligenza Artificiale (IA) competitiva per Scopone, un famoso gioco di carte Italiano. In particolare, ci siamo concentrati sugli algoritmi di Ricerca ad Albero Monte Carlo (o Monte Carlo Tree Search, MCTS). Tuttavia, MCTS richiede la piena conoscenza dello stato di gioco, quindi abbiamo anche usato un'estensione dell'algoritmo chiamata Information Set Monte Carlo Tree Search (ISMCTS), che è pensata per funzionare usando una conoscenza parziale dello stato di gioco. Inoltre, abbiamo sviluppato diverse varianti degli algoritmi MCTS e ISMCTS, valutando il loro livello di gioco contro tre IA a regole, che codificano la conoscenza tratta da famosi libri di strategia di Scopone. I nostri risultati hanno dimostrato che la coppia di mazzo ha un vantaggio rispetto la coppia di mano e gli algoritmi MCTS e ISMCTS sono risultati più forti delle IA a regole. In fine, abbiamo sviluppato un'applicazione che permette ai giocatori umani di misurarsi con le nostre IA.

Monte Carlo tree search algorithms applied to the card game Scopone

Di PALMA, STEFANO
2013/2014

Abstract

The aim of this thesis is to design a competitive Artificial Intelligence AI algorithm for Scopone, a famous Italian-card game. In particular, we focused on the Monte Carlo Tree Search (MCTS) algorithms. However, MCTS requires full knowledge of the game state, therefore we also used an extension of the algorithm called Information Set Monte Carlo Tree Search (ISMCTS), that can work with partial knowledge of the game state. We developed different improvements of MCTS and ISMCTS, and we evaluated their playing strength against three rule-based AI encoding rules taken from well-known strategy books of Scopone. Our results showed that the deck team has an advantage over the hand team and the MCTS and ISMCTS algorithms proved to be stronger than the rule-based AI. Finally, we also developed an application to let human players interact with our AI.
ING - Scuola di Ingegneria Industriale e dell'Informazione
18-dic-2014
2013/2014
Lo scopo di questa tesi è quello di progettare un algoritmo d'Intelligenza Artificiale (IA) competitiva per Scopone, un famoso gioco di carte Italiano. In particolare, ci siamo concentrati sugli algoritmi di Ricerca ad Albero Monte Carlo (o Monte Carlo Tree Search, MCTS). Tuttavia, MCTS richiede la piena conoscenza dello stato di gioco, quindi abbiamo anche usato un'estensione dell'algoritmo chiamata Information Set Monte Carlo Tree Search (ISMCTS), che è pensata per funzionare usando una conoscenza parziale dello stato di gioco. Inoltre, abbiamo sviluppato diverse varianti degli algoritmi MCTS e ISMCTS, valutando il loro livello di gioco contro tre IA a regole, che codificano la conoscenza tratta da famosi libri di strategia di Scopone. I nostri risultati hanno dimostrato che la coppia di mazzo ha un vantaggio rispetto la coppia di mano e gli algoritmi MCTS e ISMCTS sono risultati più forti delle IA a regole. In fine, abbiamo sviluppato un'applicazione che permette ai giocatori umani di misurarsi con le nostre IA.
Tesi di laurea Magistrale
File allegati
File Dimensione Formato  
2014_12_DiPalma.pdf

accessibile in internet per tutti

Descrizione: Testo della tesi
Dimensione 1.02 MB
Formato Adobe PDF
1.02 MB Adobe PDF Visualizza/Apri

I documenti in POLITesi sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10589/102246