Algorithmic explorations of a well known wargame

Kriegspiel was a serious game played on three identical boards representing an actual territory. Two (groups of) generals fought a virtual war coordinated by an umpire, the only one knowing the full state of the game. The players would issue orders to their units, and the umpire would carry them out, revealing to each player what their units could see, and no more. He would also resolve combat based on tables, rules and personal experience. Kriegspiel is thought to have been an important training tool for the armies that used it until the XX century. The Japanese navy used Kriegspiel in the Russo-Japanese war (1905), which resulted in the Rising Sun's unexpected major victory. The modern descendants of Kriegspiel are computer games, especially the real-time and turn-based strategy genres, which owe everything to this original idea. So-called "wargames" are still widespread, mostly fought with toy soldiers and miniatures, though they eschew imperfect information due to practical difficulties in maintaining three boards. Instead, uncertainty derives from a random factor (dice) and estimating distances between units without using tools. This paper is about Kriegspiel, though not the Kriegspiel that the Prussians played for training the officers of their armies. It is about a chess variant of the same name, designed around the same spirit, in hopes of making Chess closer to a modern wargame, including a concept of {em fog of war}. It was described by vonNeumann and Morgestern in their classic book {em Theory of Games and Economic Behavior} under the name {em blind chess}. Players only see their own pieces and submit move attempts to a neutral umpire who can accept or reject them. Kriegspiel is like chess in that it follows the same rules, yet it is very different. For one, computers have a lot of trouble playing Kriegspiel compared to regular chess, whereas human players can adapt fairly quickly to the concept of an invisible opponent. Information is scarce, changes all the time and can be misleading, but every little bit of it can decide the outcome of the game. In a way, many Kriegspiel tactics could be likened to the ever elusive common sense that remains one of the most difficult things for computers to grasp. We study algorithms for playing Kriegspiel because it is a difficult game that does not seem to fall completely into any one category, which makes it very much like a real-world simulation. Playing a game of Kriegspiel forces you to reason about the past, present and future, to reason about your goals and your opponents' ones, to decide what you know and what you choose to believe. Except in limited endgame scenarios, there is no ultimate perfection that a computer can discover by trying a number of combinations. Poker is a complex game that meets most of these criteria; even so, Texas Hold'em merely requires the player to select one of three strategies (check, fold or raise) through a handful of betting rounds. Imagine a game of poker with 40 options to choose from through 50 betting rounds in which your opponent may keep his strategy secret most of the time. Yet, maybe surprisingly, the best human players can win consistently this game. Computers are only starting to make some progress. Within the context of this work, much of this progress will be discussed and analyzed.