Algorithm to find the equilibrium point in missile-ship simulator-based game

In this work we are studying the situation in which a warship is attacked by an infra-red missile. We will use the concepts of Game Theory to tackle this problem and, in particular, since the game is known only through the simulations, we will use the Simulation Based Game Theory, a branch of Game Theory used when the game is not known analytically. The goal of this work will be creating and testing an algorithm that allows us to find the best strategies to follow for both the players of the game: the warship and the missile. First of all, we formally formulate the game in order to be able to do some strategical reasoning on it. After that we will study the complexity of the problem and we will realize that is too complex to be tackled as it is, so we will introduce some simplifications over it. Secondly, we will start to develop a new algorithm that allows us to find the equilibrium point of the game using few simulations possible. Once we have developed it we will test it experimentally in a simpler game than the boat-missile one, showing that it can perform up to 30% better than some other state of the art approaches. In the end we will propose the algorithm to solve the boat-missile problem, showing that, even with few simulations in comparison to the size of the problem, we are able to find strategies that allow the boat to escape the missile.

In questo lavoro studieremo la situazione in cui una nave militare è attaccata da un missile a guida infra-rossa. Useremo concetti della Teoria dei Giochi per afforntare questo problema e in particolare, siccome il gioco è noto solo attraverso delle simulazioni, useremo la Teoria dei Giochi Simulativa, una branca della Teoria dei Giochi usata quando non è disponibile una descrizione analitica del gioco. L'obbiettivo di questo lavoro è quello di creare e testare un algoritmo che permetta di trovare le migliori strategie da seguire per entrambi i giocatori. Prima di tutto daremo una formulazione del gioco formale che ci permetta di ragionare strategicamente su di esso. Dopo di che ne studieremo la complessità e ci accorgeremo che il problema è troppo complesso per essere affrontato così com'è, quindi introdurremo delle semplificazioni. In seguito, cominceremo a sviluppare un nuovo algoritmo che ci permetta di trovare il punto di equilibrio del gioco usando il minor numero di simulazioni possibile. Una volta sviluppato, lo testeremo sperimentalmente in un gioco più semplice di quello nave-missile, mostrando che può performare fino al 30% meglio di altri approcci che rappresentano lo stato dell'arte attuale. Alla fine useremo il nuovo algoritmo per risolvere il problema nave-missile, mostrando che, utilizzando poche simulazioni rispetto alla taglia del problema, siamo in grado di trovare strategie che permettano alla barca di evadere il missile