Linguistic Geometry, A New Paradigm for Adversarial Games
Research on new game theory started in 1972 in Moscow, Russia. For 16 years (since his graduation with an MS in mathematics from Moscow State University) Dr. Boris Stilman was involved in the advanced research project PIONEER led by a former World Chess Champion Professor Mikhail Botvinnik. The goal of the project was, at first, to discover and mathematically formalize methodology utilized by the most advanced chess experts (including Botvinnik himself) in solving chess problems almost without search. The following development showed that the power of this approach goes far beyond original chess problem domain. The next step was to actually apply this new theory to complex search problems from various problem domains. In the 80s, in Moscow, Dr. Stilman developed the foundations of the new approach. Some of these results were included in his PhD thesis, defended in 1984 in Moscow. In 1991, while doing research as visiting professor at McGill University, Montreal, Canada, Dr. Stilman coined the term Linguistic Geometry (LG) as a name for the new theory for solving abstract board games (ABG).
LG is a type of game theory that allows us to solve classes of adversarial games of practical scale and complexity. It is ideally suited for problems that can be represented as ABG, for example, military decision aids, intelligent control of unmanned vehicles, simulation-based acquisition, high-level sensor fusion, cyberwar, robotic manufacturing, etc. Its advantage is that, unlike any other known approach, it provides extraordinarily fast and scalable algorithms finding best strategies for concurrent multi-agent systems. Also, unlike other gaming approaches, the LG algorithms permit modeling a truly intelligent enemy. LG is applicable to the non-zero-sum games and to the games with incomplete information (i.e., imperfect sensors, weather, enemy deception, etc.). The word linguistic refers to the model of strategies formalized as a hierarchy of formal languages. The word geometry refers to the geometry of the game board, i.e., chess board, battlefield terrain, sea surface, air space, etc., as well as the geometry of abstract relations (trajectories, networks of trajectories) defining the movements of the game pieces (chess pieces, tanks, aircraft, etc.), their actions and application of sensors.
More than 180 papers on LG have been published. Dr. Stilman has written the first scholarly book on LG, Linguistic Geometry: From Search to Construction, published by Kluwer (now Springer) in February 2000. Since 2000, major theoretical advancement was made in the LG-based representation and solution of the real world defense problems.
More details about LG and Dr. Stilman, including demonstration movies and brochures, can be found at the STILMAN Advanced Strategies Web site.
A number of draft papers on LG and information on Dr Stilman’s research and teaching can be found at www.stilman-strategies.com/bstilman.
Theory and Applications of Linguistic Geometry (LG)
LG is a new type of game theory, which allows us to solve classes of adversarial games of practical scale and complexity. As every new theory it has a lot of topics that require experimental and theoretical research.
Dr. Boris Stilman has shown that LG is applicable to a wide class of games with concurrently moving agents. Later, he has proven that for several classes of games, LG generates optimal strategies in polynomial time. This groundbreaking result also suggests that for much wider class of games LG strategies are also optimal or close to optimal.
The latest version of LG is dispensing with tree search altogether by defining explicit game states, the so-called game boards. Such game boards must sufficiently reach structure so that a "projection" of the game tree on the board could be defined. If considered in its entirety, this projection essentially forms the graph of the game, such that each node in the graph represents multiple nodes of the game tree. However, although the resultant graph is much smaller than the game tree, it could still be too large for a meaningful analysis.
Within the LG approach only portions of the projected game tree are constructed, and only those portions represent meaningful flow of events, the so-called trajectories. Moreover, such "flows" are not constructed in isolation, but are intertwined together as action-reaction-counteraction constructs, the so-called zones. Essentially, in LG search is replaced by construction of strategies out of several types of constructs or blocks, an attack zone, a domination zone, a retreat zone, etc., whose combinations reflect the entire set of winning strategies in abstract board games. Informally, we can say that LG reveals the "genetic structure" of the abstract board games.
Boris Stilman, PhD
Professor Stilman received an MS in mathematics from Moscow State University in 1972; a PhD in computer science and a PhD in electrical engineering from the National Research Institute for electrical engineering, Moscow, in 1984.
1200 Larimer Street
North Classroom, room 2404B
Mailing Address: Campus Box 109, P.O. Box 173364, Denver, CO80217-3364
In 1972-1988, in Moscow, USSR, Dr. Stilman was involved in the advanced research project PIONEER, led by a former World Chess Champion Professor Mikhail Botvinnik. The goal of the project was to discover and formalize an approach utilized by the most advanced chess experts in solving chess problems almost without search. Dr. Stilman developed experimental and mathematical foundations of the new approach to search problems in artificial intelligence (AI). In 1990-91, while at McGill University, Montreal, Canada, based on this approach.
Dr. Stilman originated linguistic geometry (LG), a new theory for solving abstract board games. LG allows us to overcome combinatorial explosion. It is scalable to solving complex real-world problems that are considered intractable by conventional approaches.
Since 1991, Dr. Stilman was developing the theory and applications of LG at the University of Colorado Denver as professor of computer science. A leap in the development LG was made in 1999 when Dr. Stilman, with a group of scientists and engineers, founded STILMAN Advanced Strategies, LLC (STILMAN). Since then, he combines his professorship at UC Denver with his leadership role of chairman and CEO at STILMAN. Dr. Stilman led a number of national projects in the former Soviet Union (until 1990), several government-funded projects at UC Denver and all the projects developed at STILMAN. A number of applications of LG developed at STILMAN passed comprehensive testing and are considered vital for U.S. national defense. They are currently being transitioned to the U.S. Armed Forces.
Dr. Stilman has published several books and contributions to books, and more than 200 research papers. He was a recipient of numerous R&D awards, including the top research awards at UC Denver, grants from the former USSR Academy of Sciences, substantial grants from the U.S. Department of Defense (such as major awards from DARPA, U.S. Army, U.S. Air Force, etc.), Ministry of Defence of UK, from the world leading defense contractors such as Boeing (USA), Rockwell (USA), BAE Systems (UK), Finmeccanica (Italy-UK) ans Fujitsu (Japan). A complete resume of Dr. Stilman is available online.
Computer science and engineering courses related to research in artificial intelligence and linguistic geometry include:
- CSCI 4630 — Linguistic Geometry
- CSCI 5582 — Artificial Intelligence
- CSCI 7582 — Artificial Intelligence
For complete, up-to-date course descriptions, visit the CU Denver academic catalog and search for the course numbers listed above.