Asymmetric Game Tree using a Dynamic Bayesian Network
Author
Pedersen, Esben Skov
Term
4. term
Education
Publication year
2008
Abstract
Minimax-søgning er en standardmetode til at vælge træk i tospillerspil, men den bruger ofte tid på at undersøge usandsynlige modtræk. Dette projekt forbedrer minimax ved at forudsige, hvilket træk modstanderen sandsynligvis vil vælge, og prioritere søgningen derefter. Vi opbygger et dynamisk Bayesiansk netværk (DBN), hvor noderne repræsenterer abstrakte egenskaber (features) udtrukket fra spillets tilstand. DBN'et trænes med EM (Expectation–Maximization) på data fra kampe mellem computerspillere. Hver computerspiller vælger træk ud fra en vægtet sum af de samme features; vægtene findes med en genetisk tilgang. Ved at bruge DBN'ets forudsigelser til at styre rækkefølgen af træk forbedrer systemet de svageste strategiers præstation uden at øge søgerummet.
Minimax search is a standard way to choose moves in two-player games, but it often spends time exploring unlikely responses. This project improves minimax by predicting which move the opponent is most likely to make and then prioritizing the search accordingly. We build a dynamic Bayesian network (DBN) whose nodes represent abstract features extracted from the game state. The DBN is trained with EM (Expectation–Maximization) on data from matches between computer players. Each computer player selects moves using a weighted sum of the same features; the feature weights are found with a genetic approach. Using the DBN’s predictions to guide move ordering allows the system to improve the performance of the weakest strategies without increasing the search space.
[This abstract was generated with the help of AI]
Documents