Exploring exploitation and exploration algorithms in Ms. Pac-Man
Bibliographic record
Abstract
Video game technology has grown to include the development of more sophisticated game play by including computer controlled agents or Non-Player Characters (NPCs). Moreover, game environments provide ideal benchmarking tools to examine new and more sophisticated game related algorithms. Ideal testbeds are games like Pac-Man and Ms. Pac-Man. Ms. Pac-Man is a stochastic game played in a complex maze environment. In this thesis, a novel probabilistic tree search algorithm loosely based on the simulated annealing algorithm is used by the ghost agents that pursue Ms. Pac-Man in order to minimize the score of Ms. Pac-Man (the opponent). In general, simulated annealing is a non-deterministic search optimization algorithm to search for a global maximum/minimum in a non-convex discrete search space. A major advantage of simulated annealing over the tree search models used in past research (Ant Colony Optimization and Monte Carlo Tree Search) as applied to the ghost agents in Ms. Pac-Man is the time and memory complexity. Although simulated annealing is still computationally intensive, it is less so in comparison to the search algorithms mentioned above. Simulated annealing and variants are also excellent sources of easy-to-understand analogs. This thesis investigates the trade-off between exploration and exploitation phases of search algorithms used by ghost agents as they attempt to contain or constrain the movements of Ms. Pac-Man. New algorithms are developed and presented to better control the NPCs within Ms. Pac-Man. The proposed models or algorithms are evaluated on two different experimental setups; 1) maze navigation to test the convergence efficiency with respect to the number of iterations, and 2) within the game of Ms. Pac-Man itself to determine the effectiveness of attacking strategies such as flanking and blocking. These new algorithms may have application within similar types of problems.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.000 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.001 | 0.000 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.003 |
| Open science | 0.001 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one teacher head, not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".