Talk:Game complexity

From Wikipedia, the free encyclopedia

Knight chess piece This article is within the scope of WikiProject Strategy games, an effort by several users to improve Wikipedia articles on strategy games. For more information, visit the project page, where you can join the project and/or contribute to the discussion.
B This article has been rated as B-Class on the assessment scale.
Mid This article is on a subject of mid priority within strategy games for inclusion in Wikipedia 1.0.
Strategy games To-do:

Contents

[edit] Connect6 game-tree complexity

I've added a comment to Talk:Connect6 and have modified Connect6. The number 140 for the log game-tree complexity of Connect6 given on that page is uncited and based on a questionable assumption. If one makes a different (and perhaps more reasonable) assumption one gets 70 (in other words, the same as that for Gomoku). I'll update this page to say "70-140?" for Connect6, but perhaps it should simply be left as "?". kfgauss (talk) 20:57, 13 January 2008 (UTC)

The game length on this page, which was listed as 200 and uncited, made no sense (note that the entire board would be filled by that point). I've updated it to 15-30?, which is what is mentioned on Connect6, based on analogy with published numbers for Gomoku. A quick check of some games by top players on Little Golem suggests this range is at least in the right ballpark. kfgauss (talk) 21:09, 13 January 2008 (UTC)

[edit] Move-sequence complexity bogus?

I cut this section from the article because (a) I couldn't find anything on the web that indicates that this is a real term in game complexity research; and (b) as far as I can tell from this somewhat confusing definition it's the same thing as game tree complexity. Gdr 12:19, 2004 Jul 8 (UTC)

A "move-sequence" is the succession of moves from the "game start" to the "game end". A "move" (Go term) is the action of a player performed during his turn and thereby transforming one "game state" to its successor, its next "game state". The "number of move-sequences" is the total number of move-sequences that might occur legally according to a game's rules. It is expressed as a function in a parameter. A typical parameter is the number of objects that form the board of a game. E.g., N = 64 squares in Chess or N = 361 intersections in Go. Since determining a "number of move-sequences" M(N) is a difficult mathematical problem for many interesting games, one uses bounds to limit the unknown, precise functions: a "lower bound" L(N) or an "upper bound" U(N). The following holds: L(N) < M(N) < U(N). E.g., for Go (with simple rules) trivial bounds are: L(N) = N! and U(N) = N^(3^N). So for the precise "computational complexity" M(N) of Go we can say: N! < M(N) < N^(3^N).

[edit] Legal Positions In Tick-Tack-Toe

I have written a program which counts the legal positions in tick-tack-toe and I get 5890.

[edit] Other board games

What about Arimaa? Does anybody have a clue about that one? 132.231.54.1 21:15, 1 Feb 2005 (UTC)

[edit] Where the numbers in the table come from

I would like to see a reference to the numbers in the complexity table, i did some calculations for the othello game and i'm getting lower values that the ones show in the table.

[edit] Average Branching Factors and Average Moves Per Game

I think it would be most clarifying to make the complexity of various board games directly comparable by adding columns to the table for the average branching factors and average moves per game (for a rationally played game). It may not be easy to retrieve this information for some entries, however. --BadSanta

I agree. Anyone know any numbers/calculations? Give me formulas and I can calculate. 70.111.251.203 19:09, 21 February 2006 (UTC)

[edit] Can someone update the table with the added games?

Various cells in the table are blank. I don't think that FischerRandomChess would have the same values as regular chess.

Well, only one starting position in FRC would return EXACTLY the same values as in standard chess. [Guess which one?] The rest of the 960 starting positions possible for a game would return slightly different values, higher or lower, with the average of all for a game randomly chosen being very close to that of standard chess. After all, we are dealing with exactly the same pieces on the same board, just differently placed at the beginning of the game. --AceVentura

[edit] Complexity class for Connect6

An editor suggested that generalized Connect6 might be EXPTIME-complete. I removed this, because it's almost certainly false: if I understand the rules of Connect6 correctly, since pieces never move or capture once placed, a game can last no more moves than there are spaces on the board, and that's a polynomial function of the board size. It may well be PSPACE-complete, using similar methods to those used to show that generalized Gomoku is PSPACE-complete, but I think we need a reference. Gdr 01:16, 3 January 2006 (UTC)

[edit] Under which category?

Shouldn't this article be under combinatorial game theory and not just regular game theory?70.111.251.203 03:05, 7 February 2006 (UTC)

Sure. I've changed it, but in future, Be bold. ··gracefool |☺ 04:35, 7 February 2006 (UTC)

[edit] Chart of Complexities

Although certain game exceed other games in complexity by state space and/or game tree, this is largely do to the size of the boards, numbers of pieces, etc. Thus the table is misleading; the game of Chess has a board size of 8x8, thus 64 squares, Go has a 19x19 board, with 361 intersections. Go is over 5 times as large, while the game complexity is comparatively only approximately 3 times as complex (4 if you're generous, doesn't matter). {correction - the numbers for Go were horrendously wrong when you were looking at the comparison. The actual numbers for Go are 10 to the 172 for state space and 10 to the 766 for game tree.} Because of the lack of a 1:1 ratio, the games can't be compared on equal ground. The game of chess is actually more complex for it's size. I'm not sure how pieces play into this. Here is a table:


Game log(State space) log(Game tree) Complexity class of suitable generalized game Board size (number of squares/intersections for a piece)
Tic-tac-toe 3 5 PSPACE-complete 9
Nine Men's Morris 10 50 ? ?
Awari 12 32 ? ?
Pentominoes 12 18 ? ?
Connect Four 14 21 ? 42
American checkers 21 31 EXPTIME-complete 64 or 32?
Lines of Action 24 56 ? 64?
Othello 28 58 PSPACE-complete 64
Backgammon 20 144 ? 24?
Chess 46 123 EXPTIME-complete 64
Chess960 46 123 EXPTIME-complete 64
Xiangqi 75 150 EXPTIME-complete 90
Shogi 71 226 EXPTIME-complete 81
Go 172 360 EXPTIME-complete 361
Connect6 172? 140? ? any size depending on board size, but if on 19x19, then 361, can be larger though
Arimaa 54 440 ? 64

This chart actually shows how Shogi and Arimaa are the most complex games per space. Shogi because of both numbers, and Arimaa only because of the Game Tree. Does anyone know where that 440 number for Arimaa's Game Tree came from? It doesn't make much since considering how you can choose the initial setup of pieces, but there are superior setups, and almost always people put all their rabbits in the back row.

70.111.251.203 14:08, 7 February 2006 (UTC)

Maybe there is a relationship that should be made between the state space and the game tree too. 70.111.251.203 13:34, 9 February 2006 (UTC)

[edit] Poker

There are a lot of different variants of poker, and the complexities vary depending on the number of players; maybe we should create a separate page just for the poker variants? Ben Standeven 20:31, 9 March 2006 (UTC)

If you have the numbers, put them on here for now. No point in making a seperate page if there is very little information on it. 128.6.175.59 21:09, 13 April 2006 (UTC)

[edit] Moves per game in Arimaa

I removed the question mark from the Arimaa average game length of 35. That is in fact the average length of rated games between humans on arimaa.com, as calculated from the publicly available database of games played there. Games involving two computers are slightly longer on average because sometimes neither computer can come up with a plan. Games between expert humans (rated over 1900) are also longer on average, about 45 moves per game. However, compared to chess, top-level Arimaa is intrinsically a slightly shorter game. The greater length of Arimaa games occurs because agreed draws are forbidden and resignation is highly discouraged on arimaa.com. If resignation and agreed draws were forbidden in chess, the average expert game of chess would probably be well over 45 moves. --Fritzlein 17:53, 19 June 2006 (UTC)

Also, how was the game-tree complexity of 190 calculated for Arimaa? With an average branching factor of 15000, and 35 moves per game (70 half-moves) I calculate log(15000^70) = 292. --Fritzlein 18:00, 19 June 2006 (UTC)

[edit] E[a^b] != E[a]^E[b]

The article defines game-tree complexity to be "the total number of possible games that can be played". It then says "a reasonable estimate can be made by raising the game's average branching factor to the power of the number of plies in an average game" but this is completely wrong. For example in chess the estimate seems to be 30^(2*40) = 1e+118, but even if only 1% of games are 60 moves long instead of 40 moves, those account for 0.01*30^(2*60) = 1e+175 games. So on for even rarer, but longer games. In other words to estimate the total number of possible games by computing a^b, one cannot use averages for a and b, instead one should use values closer to the maximum possible.

I conclude that either game-tree complexity is NOT "the total number of possible games that can be played" (but something else), or pretty much every number in the table is grossly underestimating the game-tree complexity. Which one is it? 69.109.189.208 02:10, 19 February 2007 (UTC)

The numbers for tic-tac-toe are exact. The others are lower bounds (or really, estimates of lower bounds). Gdr 17:00, 3 May 2007 (UTC)
The exact number of chess games is infinite (or more precisely, Aleph-one) because infinite games are possible (see comment on http://www.research.att.com/~njas/sequences/A048987 ). So if you're sure that game-tree complexity is the total number of possible games, then the value of log(games) for Chess should simply read "infinite". 69.109.171.115 21:34, 11 May 2007 (UTC)
I'm pretty sure that these estimates are based on applying the 50-move rule as soon as it becomes available: certainly Shannon's 1950 paper notes "The end must occur, by the rules of the games after a finite number of moves (remembering the 50 move drawing rule)".
Anyway, you have a valid nitpick, so I wrote it up in a note on the Shannon number page.
Also, you're right that the article has the wrong definition of game-tree complexity, or at least it doesn't match the definition in Victor Allis's thesis. Gdr 17:18, 14 May 2007 (UTC)

[edit] Example tic-tac-toe

It is not true that

"When rotations and reflections of positions are considered the same, there are only 26,830 possible games."

Proof: Firstly, no game is symmetrical with respect to rotations or reflections. That is because each game has at least five moves, and a symmetry can be preserved only for at most three moves. Please note that we are talking about game-tree complexity, where the order of the moves is relevant, see article. Secondly, the order of the symmetry group of rotations and reflections is eight. Therefore, there are 255168/8 = 31896, not 26830, different games up to rotations and reflections. --80.129.78.128 15:26, 19 March 2007 (UTC)

You've missed a crucial point. For two games A and B to be identified in each count, we demand that each position reached in game A is symmetric to the corresponding position in game B. But we don't demand that the symmetry is the same for each position. So no such simple division is going to give the right answer. There's really no substitute for computing all the game trees.
I restored the correct figure to the article and to the tic-tac-toe article.
Here's an example to demonstrate this point. Number the squares 1-9 starting at the top left. Now consider the (partial) games A=6584 and B=8564. The positions reached after move 2 in the two games are related by a reflection in the line 1-5-9. But the positions reached after move 4 are not related by this reflection (in fact they are identical). Gdr 16:46, 3 May 2007 (UTC)
I see, but then one should correct the definition given in the article: "The game tree is typically vastly larger than the state space because the same positions can occur in many games by making moves in a different order". And this is exactly what happened in your example: The same position occured, but the moves were made in a different order. If the cited phrase means anything, then that the two (partial) games should be considered different. --80.129.118.249 12:07, 4 May 2007 (UTC)
You're confusing the two situations (symmetrical positions identified or not). In the case where symmetrical positions are not identified, the two games are different. In the case where symmetrical positions are identified, the two games are identical. The fact that we number the moves differently is a red herring — when symmetrical positions are identified, the initial move 6 is the same as the initial move 8. Gdr 13:35, 7 May 2007 (UTC)
P.S. It's not hard to compute these numbers. You can see some Python code at Talk:Game complexity/ttt.py that agrees with the numbers in the article. You might want to compare and contrast the implementation of the functions count_games_2 (which identifies symmetric positions) and count_games (which doesn't). Gdr 16:31, 7 May 2007 (UTC)
Yes, I understand. I should have mentioned that you explained it very well above, and your example is neat. However, though you can say that the initial moves are the same, because one transforms into the other through a symmetry, the same is not true for the final moves: In one case a space diagonally adjacent to the previously marked space is marked, but not in the other case. You actually don’t identify moves in this way, just positions. But the article talks about "making moves in a different order". --80.129.76.170 07:36, 11 May 2007 (UTC)

[edit] Tidying

I added references to the article, then removed claims about complexity classes that I couldn't find a reference for (magic fingers, xiangqi, connect6) and then removed entries from the table where no information was being provided (magic fingers, seven-card stud poker, contract bridge, mahjong). I also took removed Chess960 since from a complexity point of view it's much the same as ordinary chess.

I was slightly surprised that I couldn't find a proof that xiangqi is EXPTIME-complete. Am I missing it? Gdr 17:19, 3 May 2007 (UTC)

Almothough many of the numbers in the table are verifiable (e.g. straight out of Allis 1994) I've been unable to find citations for many others. These were mostly added or updated by anonymous users so I can't ask them for sources. I can compute some of them myself; for example I verified that the log of the state space complexity of Arimaa is between 41 and 42. However, that's original research and WP:NOR. Other numbers in the table seem rather unlikely when I've checked them: the average branching factor for Arimaa is over 17,000 [1] and the average game lasts 60 ply [2] suggesting that the log of the game-tree complexity is more like 250 than 190. So where did these numbers in the table come from? Gdr 17:16, 23 May 2007 (UTC)

The 766 value for go seemed to be based on 361!×0.012 (the proportion of board setups that are legal go positions). I replaced it with the figure from Allis 1994. Gdr 19:26, 23 May 2007 (UTC)

[edit] The first sentence

This article starts Game complexity is a measure of the complexity of a game. Does this sentence say anything at all. Also, does complexity here have anything to do with the everyday meaning of the word? --Apoc2400 06:56, 29 June 2007 (UTC)

"Complexity" is being used in two different technical meanings in this article. Firstly, in "state complexity" and "tree complexity" it's just a fancy way of saying "size" or "count". Second, in "computational complexity" it has the meaning from the field of complexity theory, which means, very roughly, "the asymptotic rate at which computational resources need to increase as problem instances grow in size". Gdr 12:43, 30 November 2007 (UTC)

[edit] chinese checkers

I corrected the figures for the state space complexity for Chinese Checkers, which were too high. There are 121 cells, and there may be 20 to 60 pieces on board, as the number of players varies from 2 through 6. For 2 players, the maximum number of positions possible is 121C20 = (121!)/(101!.20!) = 3.5e22. For 6 players, 121C60 = (121!)/(60!.61!) = 1.9e35. -- Brhaspati\talk/contribs 06:54, 2 December 2007 (UTC)

[edit] Amazons

I've added a table entry for Amazons, which is PSPACE-complete (reference provided in the Amazons article). I could not find the true state space complexity of the game anywhere, but I have upper-bounded it as follows: 100 squares on the board, of which 4 are white queens, 4 are black queens and 92 are free of queens. This can be done in (100!)/(92!4!4!) ways. Each of the 92 queen-free squares can either have an arrow or be empty, causing another factor 2^92. The upper bound is the product of these two numbers, evaluating to 6.45e40. Some of these positions may not be achievable in the course of a game, hence the number is an upper bound on the real state space complexity. If someone gets a real reference, please update the entry. -- Brhaspati\talk/contribs 07:03, 2 December 2007 (UTC)

You ought to divide by 8 for the symmetries of the board. Gdr 12:18, 2 December 2007 (UTC)
Yup, you're right. New upper bound is 8.06e39. Updating article. -- Brhaspati\talk/contribs 14:48, 2 December 2007 (UTC)

[edit] Irensei

An anonymous editor added an entry for Irensei, assigning it a state-space complexity of "?171", a game-tree complexity of "360", and an average game length of "80". No reference was given, so I removed it for now. We could put it back if there were a reference. Gdr 12:18, 2 December 2007 (UTC)

[edit] Dots

I'm surprised Dots is not on here. Does anyone have any info on this, regardless of grid size? you know that 2x2 grid is won by 1st player. So thats a start. —Preceding unsigned comment added by Doedicurus (talk • contribs) 05:17, 25 January 2008 (UTC)

You mean dots and boxes, right? Winning Ways shows that it is NP-hard. No completeness result is known (I would guess it's PSPACE-complete, but that's only a guess). Gdr 14:14, 26 April 2008 (UTC)