Linguistic Geometry Lecture

Boris StilmanUniversity of Colorado, Denver, and STILMAN Advanced Strategies
No-search approach: Discovering mysteries of the state space in opposing games

Friday, September 26, 2014 - 2:45pm
Malott 224

I will explain briefly foundations of Linguistic Geometry (LG), a theory for solving abstract board games (ABG). The rest of the talk will be devoted to the so-called No-Search Approach in LG, the major theoretical result showing that LG generates optimal solutions for a class of opposing games without search. It is based on decomposing the entire state space into subspaces. This decomposition called the State Space Chart could serve as a strategic "geographical map" of the state space by providing guidelines for travel from state to state. The Chart permits to construct classes of potential strategies for all the opposing sides and to prune those classes that cannot be implemented for a given problem. Subsequent application of the non-pruned potential strategies leads to construction of the optimal solution – the only real strategy existing in this problem.

Rescheduled from Thursday, this is expected to be a 2-hour talk with a short break in the middle.