Talk:Game complexity

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)

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).

Legal Positions In Tick-Tack-Toe

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

Other board games

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

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.

Abulmo (talk) 14:29, 25 November 2013 (UTC) The number for Othello came from Victor Allis' Thesis, who considers the average move number being 10 and the game length 58, hence a game tree size of 10^58. Of course this is a very crude approximation. Much more accurate computation can be done using MonteCarlo simulation. A good coverage of the technique was done by D. Knuth in his article "Estimating the efficiency of backtrack programs" published in 1975. For Othello, on an 8x8 board, the game tree size is 2.08 10^55.

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)

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

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)

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)

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)

not sure where Arimaa gets a mention in that discussion but a key feature is to look at the strength of computer playing programs the single critical piece makes chess a lot simpler strategically.Tetron76 (talk) 23:05, 27 February 2011 (UTC)

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)

Problem is, I've tried repeatedly to add a small texas hold'em poker section, but a certain activist editor keeps removing it without explanation. After three thwarted attempts I've given up. I'm not going to waste my life on endless edit wars. Oh well, it's wikipedia's loss. People will have to go to other websites for the info. 21 August 2010 —Preceding unsigned comment added by 98.216.12.97 (talk) 17:15, 21 August 2010 (UTC)

I believe the scope of the table is combinatorial games, and most are games of perfect information. Poker is an interesting game, but I don't believe it is a combinatorial game (or if so, would pose problems if mapped out on a game tree). It is also not a game of perfect information (although some other games in the list aren't either, such as backgammon). Can we define a scope of the table, and add it either before the table, or in the article's introduction?—LithiumFlash (talk) 15:42, 7 April 2017 (UTC)

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)

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)

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)

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)

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)

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)

• Don't the pieces have colors? Ben Standeven (talk) 08:48, 1 January 2008 (UTC)

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)

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)

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)

Question about Game Tree Complexity

The article says that game tree complexity is the smallest full-width decision tree, which is a sub-tree of the game tree. However, the game tree article says that game tree complexity is the number of leaf nodes of the entire game tree. Are they saying the same thing? It seems like this article says that game tree complexity concerns only a sub-tree while the game tree article says game tree complexity concerns the entire game tree. —Preceding unsigned comment added by MengTzu622 (talk • contribs) 00:31, 4 August 2008 (UTC)

The definition in this article (the smallest full-width decision tree) is the one given in Victor Allis's thesis. The definition in game tree is wrong. It's my mistake, so I will fix it. Gdr 02:02, 26 September 2008 (UTC)

Question about Game Tree Complexity

"The game tree size is total number of possible games that can be played: it's the number of leaf nodes in the game tree"

These are not the same. 217.229.13.214 (talk) —Preceding undated comment added 12:04, 15 August 2010 (UTC).

NOTE: This appears to have since been answered in the above section (at a date after both this post and the original post of the previous section). -SColombo (talk) 06:38, 28 March 2012 (UTC)

"These are not the same." Can anyone explain why total number of possible games that can be played is different than number of entire game tree leaf nodes? — Preceding unsigned comment added by Mogadit (talk • contribs) 10:44, 26 April 2012 (UTC)

International Draughts

The claimed complexity for International Draughts, EXPTIME-complete, is incorrect. Or rather, the cited paper is not about International Draughts; it is about Checkers. The rules are sufficiently different that the results do not apply to International Draughts. As an unbounded 2-player game, it ought to be EXPTIME-complete as well, but I know of no proof. The only result I know of is that determining whether an individual move is legal is NP-complete: is-it-np-hard-to-play-international-draughts-correctly Bobhearn (talk) 06:51, 17 January 2011 (UTC)

Average branching factor

What do people think of adding average branching factor as a column in the table? I think it says a lot about the complexity of a Game Tree beyond just what comes out in the final number of game tree complexity. (Granted, the table is a bit crowded, so it might take a little wikitext-juggling to make it fit).
Thoughts?
-SColombo (talk) 06:40, 28 March 2012 (UTC)

Single Ref column

There should be a single ref. column to include all references per row. Of course, this ref. column would be to the far right of the complexity table, as the references would apply to the entire row. Having multiple ref. columns down the middle of the table is clutter. KyuuA4 (Talk:キュウ) 15:23, 29 March 2012 (UTC)

tic-tac-toe not PSPACE complete

contrary to claim in Game_complexity#Complexities_of_some_well-known_games section, 3 by 3 tic-tac-toe is not PSPACE-complete. As per the associated link, it is more complex similar "first n in a row" games like gomoku that might be pspace complete. 76.119.30.87 (talk) 06:34, 12 February 2015 (UTC)

You did read the "suitable generalized game" in the heading of the column that gives the complexity, right? —David Eppstein (talk) 06:37, 12 February 2015 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified 2 external links on Game complexity. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive http://www.webcitation.org/5oFLE7Mgx?url=http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf to http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf
• Added archive https://web.archive.org/web/20120315192840/http://hyperion.cs.washington.edu/attachments/15/glendenning_ugrad_thesis.pdf to http://hyperion.cs.washington.edu/attachments/15/glendenning_ugrad_thesis.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 15:30, 7 January 2017 (UTC)

Game tree complexity for Hex

The citation failed verification - I can find no complexity data in that source. The branching factor cannot possibly be 280 asstated - the board only has 121 playable spaces, so I've corrected that to reflact the 40 ply game: the average number of vacant spaces is (121+(121-81))=101. Now the game tree size is 121!*120!*...82! = 121!/81! = 1.6*10⁸⁰, so I've also substituted that number. If anyone can cite a source for the 40 ply average game length, we're home. In my experience, games are a little longer, maybe 40-50 ply, but my games are not a valid source.Sbalfour (talk) 02:19, 19 January 2017 (UTC)

Hearthstone

Has anybody scrutinized the complexity of Hearthstone already?--Powerlts (talk) 19:11, 26 May 2017 (UTC)

In a manner of speaking, yes - Programming a Hearthstone agent using Monte Carlo Tree Search Jelleecat (talk) 20:34, 12 January 2019 (UTC)

I actually thought I was including this, so I'll do so now - Monte Carlo Tree Search experiments in Hearthstone the point is still valid! Jelleecat (talk) 20:49, 12 January 2019 (UTC)

@Jelleecat: Wikicoding hint: for external links a single pair of square brackets is enough. --CiaPan (talk) 06:42, 14 January 2019 (UTC)

@CiaPan: You're a doll, thank you! Am I allowed to edit those into single square brackets? ;) Jelleecat (talk) 02:09, 18 January 2019 (UTC)

@Jelleecat: Well done! :) --CiaPan (talk) 11:44, 18 January 2019 (UTC)

Bejeweled and Candy Crush

I'm kinda surprised to see Beheweled and Candy Crush in the page. However I wonder if the following differences between the two games have been considered:

1. Bejeweled is the one that uses 8x8 grids. Candy Crush uses 9x9 (royalgames.com version).

2. Bejeweled uses 7 colors (except diamond mine mode in Bejeweled 3), while Candy Crush uses up to 6 colors.

User670839245 (talk) 23:28, 7 July 2017 (UTC)

These differences are irrelevant to the analysis on this page, because they are abstracted away as variables. Stellaathena (talk) 06:08, 20 November 2021 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Game complexity. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20070614111609/http://www.csie.ndhu.edu.tw/~sjyen/Papers/2004CCC.pdf to http://www.csie.ndhu.edu.tw/~sjyen/Papers/2004CCC.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

Y An editor has reviewed this edit and fixed any errors that were found.

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 14:43, 10 October 2017 (UTC)

International Draughts much more complex than the listed 10^54 value?

Schaeffer released a correction to an older estimation of Checker's/English draughts' game tree complexity at 10^31 and established that the true value was ~10^40. I corrected that in the game-tree complexity table with the source here:

https://icga.org/icga/journal/contents/Schaeffer07-01-08.pdf

There's some indication however that the same is true of International draughts and that the game-tree complexity is actually much higher. As high as 10^92.

Has anyone done anymore research on this, and is there newer literature on the subject either acknowledging or "debunking" the error?

source:

https://laatste.info/bb3/viewtopic.php?t=7817

archived source:

https://archive.is/GkfT1

T0afer (talk) 14:44, 30 August 2021 (UTC)

Magic The Gathering - sketchy claims regarding gametree size

Currently the specific games table contains estimates for various games including Magic the Gathering at the bottom. The claim that Magic the Gathering has infinite/unbounded state-space or gametree complexity is unfounded, obviously incorrect (with a finite number of cards each with finite numbers of targets, the decision-space is obviously finite - except in the sense that repetitions may be allowed, but in this sense a game like chess should also then be called 'infinite'; even videogames, with a much larger decision-space than Magic the Gathering, still have finite though enormous gametrees simply by discretization of time into frames and of space into pixels), and not supported or claimed by the research linked. The papers linked analyse the computational complexity of generalizing Magic the Gathering (which they find to be as hard as arithmetic), not the size of the game in practice as it exists in the real-world (which is clearly finite as the number of cards is finite). — Preceding unsigned comment added by 2A00:23C8:218D:FA01:1D9A:1ADE:E33D:6 (talk) 20:17, 12 February 2022 (UTC)

Why is there no Scrabble in the main table?

Hello. The article seems quite perfect to me, but I have a minor question regarding adding Scrabble to the table.

"The game [of Scrabble] is sold in 121 countries and is available in more than 30 languages; approximately 150 million sets have been sold worldwide, and roughly one-third of American and half of British homes have a Scrabble set."

So it is really popular.

However, this article tells us nothing about Scrabble, and nobody noticed Scrabble even on the discussion page.

I just wonder if there are some specific reasons for that. Maybe it's huge amount of legal board positions, or total number of possible games, or the number of possible words which can be formed at every move etc. 2A00:1858:1047:9BEF:74A6:7DAD:2EB6:38AD (talk) 13:43, 15 July 2023 (UTC)

Wordle?

The claim that Wordle has a state space of 10^12,972, meaning that its state-space complexity dwarfs the complexity of the other games with finite complexity listed, does not make sense to me. That number doesn't appear anywhere in the cited paper, but I don't know enough about math to understand that paper, so I'm not confident enough to edit out the number from the page. I'm not sure what counts as a specific game position in Wordle (merely your choice of word, or the word plus the information – grey, yellow, or green – about each letter?) but there definitely are not 10^12,972 possible ones. — Preceding unsigned comment added by 96.241.231.20 (talk) 04:25, 28 November 2024 (UTC)