Search Pathology

Computer games based on the minimax principle usually produce better results when searching deeper. When researchers attempted to explain this formally using mathematical models, they found that under seemingly reasonable conditions minimax behaves unexpectedly: deeper search produced worse results – just the opposite of what happens in practice. This phenomenon was termed minimax pathology.

In my BSc thesis, supervised by Ivan Bratko, Matjaž Gams, and Mitja Luštrek, I investigated conditions using synthetic game trees as well as real game.

Relevant papers:
B. Kaluža. Analysis of pathological models of minimax and Pearl’s game. BSc. Thesis, Faculty of Computer and Information Science, University of Ljubljana. September 2008. In Slovene. [pdf]