This work is licensed under a
Creative Commons License.
|
Thursday, December 10, 2009
Whats your Game Mr. Bond? Nim?
Posted by GASARCH
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 Information2) Incomplete 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?10:58 AM
# 17 comments
-
Multiplayer, no luck: Chinese Checkers. I do not know of ANY other examples.
Blokus?
-
Jenga.
Any number of Ravensbruger games.
The Voronoi game: http://home.dti.net/crispy/Voronoi.html
But why is pick-up-sticks not a game? The only objection I can imagine is that executing a perfect strategy is hard for physical reasons. (Also: isn't that true of Chess and Go as well? Aren't brains physical instruments?) On the other hand, there's definitely luck involved in the initial conditions.
-
One-player complete-information no-luck games (i.e. puzzles) tend to be either in P or NP-complete. (Here I mean *natural* examples of games, otherwise languages of arbitrary difficulty can be considered in this category.)
Two-player complete-information no-luck games tend to be either PSPACE-complete or EXP-complete. As complete problems for a class completely determine that class, perhaps it is games that are telling us something about complexity rather than vice versa.
(An interesting example that does not follow this pattern: Go with Chinese rules, where no board pattern can ever be repeated, is suspected to be EXPSPACE-complete -- as you have to keep track of all game positions that have happened so far -- but all we know is that it is in EXPSPACE; its hardness is still open.)
-
You can check a 3 player game with no luck or hidden info:
http://members.optusnet.com.au/cyberite/triad/triad-1.htm
I can also send you info how to play Hex or Go with 3 players, if you like.
João Pedro Neto
-
sLx: YES, post on the web a link about 3-player Go, etc.
-
"Multiplayer, no luck: Chinese Checkers. I do not know of ANY other examples. "
There are quite a few boardgames that are multiplayer and without randomness. An example is steam (see
http://www.boardgamegeek.com/boardgame/27833)
-
So Long Sucker is a curious game in the multiplayer, no luck, complete information category.
Incidentally, Josh's comment is elaborated in detail in Robert Hearn's thesis.
-
so by NATURAL we mean board or card game? Cause that seems kind of wacky. Pick up sticks seems far more natural (sticks are generally considered pretty "natural"). What about cops and robbers? Hide and go seek? Sharks and Minnows is always tons of fun. Rock, Paper Scissors? Cat's Cradle is a game where no one wins. Now there's a concept! There's a whole good list of children's games on wikipedia, many of which seem far more natural to me than board games or card games do.
http://en.wikipedia.org/wiki/Category:Children's_games
-
Multiplayer, no luck, complete information: Dots & Boxes, Pente
-
"2-player, no luck. Battleship"
how is there no luck in Battleship?
serious question.
if you are lucky you hit on the first move. if you are lucky you go in the right direction the right distance and sink the entire ship. repeat luck.
-
Where do you place a game like "Chinatown"?
-
I too don't understand how you can have "incomplete info + no luck". Whenever non-deterministic choice is part of your decision making, there's always luck involved.
-
To address the multi-player, complete information, no luck group (just like everyone else): just about any impartial game can be thought of as a multi-player game without luck. Nim, for example, can be played with more than two players. For the "partisan" feel, one could imagine playing Atropos where each player is assigned one of the three colors (shameless plug: http://cs-people.bu.edu/paithan/atropos/).
To address the battleship question, there are no random elements used in the game rules itself. This does not mean that no luck is involved in the playing of the game; it might be a good idea to use randomness to make (some of) your decisions.
-
Great post !
IMO adding the following 2-valued parameter you can include puzzles in this classification: move-symetric / move-asymetric games.
Puzzles are move-asymetric games where one player (the puzzler) has only one move and the other player (the solver) has usually an indefinite number of moves. If the puzzler had the permission to change the puzzle after each solver move then we would get a game. Fortunately, the nature (puzzler) scientist (solver) game is a move-asymetric game. Nature is given once for all...
On the other hand, for most popular games such as chess, the rules make them move-symetric (but it had not to be necessarily this way). Unfortunately problems such as P versus NP can be modeled as a move-symetric game played by the polynomial-time-algoritmer and the unrestricted-counterexampler. Those who think that P!=NP bet that the later wins...
-
Could computer real time strategy games, called RTS, be considered "games"? I think most RTS are multiplayer, hidden-information (fog of war), no luck games. Some RTS have no fog of war, like Red Alert 3 and Battleforge, so there is no hidden information.
If you think that RTS have luck, well, they don't beyond intial starting positions.
-
>sLx: YES, post on the web a link about 3-player Go, etc.
(sorry for the delay)
You can check at World's of Abstract Games:
http://homepages.di.fc.ul.pt/~jpn/gv/players.htm
Cheers, João
-
"Incidentally, Josh's comment is elaborated in detail in Robert Hearn's thesis."
FWIW I categorize games and puzzles along two dimensions: 0-, 1-, 2-, or more players, and of polynomially bounded or unbounded length. A 0-player game is a simulation (Life, other CAs); a 1-player game is a puzzle. Each of the 8 categories yields a natural complexity class. To get a distinct complexity result for multiplayer games, it's necessary to consider team games with imperfect information. In fact, such games (when not of bounded length) are undecidable in general, even though they are played in bounded space.
BTW the thesis is now a book from A.K. Peters, with Erik Demaine -- "Games, Puzzles, and Computation". We did not treat games with luck involved.
Links to this post:
Weblog Home
Archives
