Asymmetric Game Trees using Dynamic Bayesian Networks
Author
Pedersen, Esben Skov
Term
2. term
Education
Publication year
2008
Abstract
This project improves minimax search by predicting which move an opponent is most likely to make. The prediction uses a dynamic Bayesian network, a probabilistic model that links game features over time. The network’s nodes represent abstract features extracted from the game. We train the network with EM learning (an iterative training method) using data from matches between computer players. These computer players are defined as weighted sums of the same features, and the weights are found with a genetic approach (an optimization method inspired by evolution). The system improves the performance of the weakest strategies without increasing the search space, meaning it does not need to examine more possible moves.
Dette projekt forbedrer minimax-søgning ved at forudsige, hvilket træk modstanderen sandsynligvis vil vælge. Forudsigelsen laves med et dynamisk Bayes-netværk, altså en sandsynlighedsmodel, der forbinder spillets træk (features) over tid. Netværkets noder repræsenterer abstrakte træk udtrukket fra spillet. Vi træner netværket med EM-læring (en iterativ træningsmetode) på data fra kampe mellem computer-spillere. Disse computer-spillere er defineret som vægtede summer af de samme træk, og vægtene findes med en genetisk metode (en optimering inspireret af evolution). Systemet kan forbedre ydeevnen for de svageste strategier uden at øge søgerummet, dvs. uden at skulle undersøge flere mulige træk.
[This apstract has been rewritten with the help of AI based on the project's original abstract]