[Computational Complexity] Whats your Game Mr. Bond? Nim?
- BILL: Clyde is teaching a graduate course titled Games, Game Theory, and the Theory of Games. He tells me that there are basically eight kinds of games governed by three 2-valued parameters. (1) 2-player or multi-player, (2) complete information or incomplete information, (3) luck or no luck. For example Chess or Nim are 2-player, no hidden information, no luck (I won't quibble about the coin toss to see who goes first.) There are natural examples of most of the combinations. The one I have the most trouble with is multiplayer with no hidden information and no luck. (Clyde is NOT as dogmatic as the above indicates. One other aspect I've left out for this post is that some games are impartial and some are not.)
DARLING: Here is a multiplayer game with no luck and no hidden information: pick up sticks.
BILL: For Clyde's class that not a game.
DARLING: Why not? Its alot more fun than NIM!
Help me answer my darling. What makes something a game rather than a sport? Not sure pick-up-sticks is a sport either.
Lets try to get NATURAL examples of each category: One issue- the terms are not that well defined so you may disagree with some of these. We break it into two basic categories (for a better picture of the results goto here.)
1) Complete Information
- 2-player, no luck. Go, Chess, Nim: Nim has had some nice math associated to it. Chess and Go have inspired very nice computer techniques (was alpha-beta pruning developed for chess originally?). There are some recent techniques for GO which I will talk about in a later posting.
- 2-player, some luck: Backgammon, Can't Stop (a natural game but not that well known). Sorry! (that's not be apologizing, that's the game Sorry!). Parcheesi.
- Multiplayer, no luck: Chinese Checkers. I do not know of ANY other examples.
- Multiplayer, luck: Monopoly (and similar games).
- 2-player, no luck. Stratego, Battleship: These are debatable. In fact, it may that that if defined carefully this combination is impossible.
- 2-player, luck: Gin and most 2-player card game.
- Multiplayer, no luck: Clue where each player only moves 5 squares per turn, so dice needed. One of Clyde's students families plays it this way, hence it is a natural game.
- Multiplayer, luck: Poker. Most multiplayer card games.
QUESTION: Many games are hard via complexity theory. For example, GO and CHESS are EXPTIME complete (see here). Do these results tell us things about real games?
Posted By GASARCH to Computational Complexity at 12/10/2009 10:58:00 AM