Talk:Solved game

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:

This is the talk page for discussing improvements to the Solved game article.
Article policies

Contents

[edit] Scrabble

Does it make sense to include Scrabble as unsolved game, due to the random draw of the tiles? My hunch is that even if it were "solved" in some sense, there would be no useful way to articulate the solution other than, for example, "The first player makes the best available play.".

I'm not sure, as you say it clearly has a random factor, however there does theoretically exist an algorithm which does play perfectly (i.e chooses the best position for words, calculating the probabilites of what letters the opponent has,etc.). Also significantly good computer players do exist, IIRC the best is currently Maven who has remained unbeaten (by human or computer) since 1987.
Something about randomness should be added to the article I think. I'll do it myself if no-one with better understanding jumps in first. Bagpuss
You could (theoretically) examine all the possibilities of scrabble (eg. first tile is an a, second is a b, etc). Therefore it is solveable, but not easily articulated. You could put it in probabilistic terms: x% of the time the first person wins, (1-x)% of the time the second person wins. It's not going to be solved anytime in our lifetimes though.

[edit] Solved puzzles

Might I suggest a an article devoted to solved puzzles? I'm thinking of things like the Eternity puzzle.

[edit] Useful article

An article that might be useful:

Games solved: Now and in the future by van den Herik HJ, Uiterwijk JWHM, van Rjiswijck J In the journal ARTIFICIAL INTELLIGENCE

[edit] Article name

This article seems to be more about abstract games than board games, particularly now Nim has been added. Matthew Woodcraft

Well under the classic definition and that used in Computer Science/Maths of the term "board game" virtually all board games are abstract games. Moreover as most "commercial" board games are more or less based upon chance so attract very little academic attention. While there are a few exception (for instance Scrabble) virtually all board games which are solved or coming close to be solved are abstract.
Maybe the article should be moved to solved games but I don't really see much of a problem with its current title. --Imran
I wasn't thinking so much about board games which aren't abstract games, as abstract games which aren't board games (I don't think I've ever seen a Nim board, for example). But as you point out, there are many commercial board games which aren't likely to be covered by this page, which is another good reason to retitle it. Matthew Woodcraft
I think the current title is fine, a single exception (Nim) is OK. IMHO, conveying the spirit of the article in the title is more important than being technically 100% correct. Board games are only a small subset of abstract games, so this article is more about the latter than the former. -- Arvindn

[edit] Go solved

I removed this bit to avoid clutter:

  • Go is, of course, trivially solved in the ultra-weak sense when auction komi is employed.

I think we should only list game variants here if either they are popular or the solution has some interest in its own right. Matthew Woodcraft

[edit] Games with a finite number of positions

The comment in the 3rd definition for "solved" says:

"For a game with a finite number of positions, this is always possible with a powerful enough computer, by checking all the positions. However, there is the question of finding an efficient algorithm, or an algorithm that works on computers currently available."

This seems to imply a powerful enough computer will someday be available, but of course many games (even with finite states)are 'intractable', and will probably never be solved in this manner. Therefore I would like to suggest a minor rewrite to reflect this. - Russell Jones

[edit] The definition of "strong solving"

The definition of "strong solving" makes no sense. What is the definition of 'mistake'? The intuitive meaning is a move that lowers your chances of winning. But if there exists an algorithm that allows you to win even when "mistakes have been made by one or both players" (as the article states), then clearly those are not mistakes at all. The definition seems to be self-contradictory. Anyone care to shed some light on this? —The preceding unsigned comment was added by Hikaru79 (talk • contribs) 03:27, 19 April 2006 (UTC2)

I don't see the contradiciton in the definition. Each position is either a win, loss, or draw for the player to move. If the position is a win for the player to move, but that player moves so as to make it a draw or a win for the other player, it's a mistake. Probabilities or "chances of winning" don't seem relevant when we're talking about perfect play in a two-player game of perfect information.
Suppose that a game is a forced win for Player1, but at some point Player1 makes a move which results in a position that is a forced win for Player2. That's a mistake. Suppose Player2, a few moves later, makes a move which results in a position that is again a forced win for Player1. That's another mistake. Furthermore, the position that arises might be one that would never arise unless the players had made mistakes. If you are able to play perfectly from any such position, then you have solved a game in the strongest sense. --Fritzlein 21:39, 19 April 2006 (UTC)
I'm still not seeing it. The definition of "strong solving" is that a player can win even after he has made a mistake. You just defined a mistake as a move such that the player 'cannot win'. That is a contradiction! If there exists an algorithm (the one that supposedly has been found after a game is strong-solved) that will win a game even after a "mistake" has been made, then there was no mistake because there is still a way to force a win -- the way that the algorithm gives you? Am I being clear? -- Hikaru79 21:20, 20 April 2006 (UTC)
Yes, you are being clear. I understand your objection now. The definition of strong solving is not that one can win from any position. Rather it is that one still knows how to play perfectly from any position. If the position is a forced loss for you, then even with perfect play you will lose, assuming your opponent makes no mistakes.
The confusion probably arises from the dissonance between "perfect" and "lose". In what sense can one play perfectly and still lose? In real life, the best play from a lost position is the play that has a greatest chance of confusing the opponent and inducing an error. A mathematical perspective, however, erases that distinction. A loss is a loss, and all moves from a lost position are equally good/bad, because none will be able to confuse a perfect opponent. In other words, all moves from a lost position are part of perfect play.
A weak solution includes enough information for both sides to play perfectly from the starting position to the end of the game, assuming no mistakes are made. If the game is a forced win for one player, the other player can do anything and still be playing perfectly. Only the player with the forced win can make a mistake in a mathematical sense. Yet even though "playing perfectly" constrains only one player and not the other, most legal positions can never arise with perfect play.
A strong solution, in contrast, includes enough information for both sides to play perfectly from any position that can be legally attained. With a strong solution in hand, I can't necessarily win from any position, but I will know which side can win, and I will know how that win can be attained against any opposing play. --Fritzlein 22:16, 20 April 2006 (UTC)

[edit] Reversi Nearly Solved

Why does wikipedia say Reversi nearly solved on 8×8 board? Is someone working on it and they are close to finding the solution? – — … ° ≈ ± − × ÷ ← → · § Mark Schreiber: Mschribr 17:56, 11 August 2006 (UTC)

[edit] Maharajah and the Sepoys

It is said:

...a weakly solved game may lose its attraction if the winning strategy is simple
enough to remember (e.g Maharajah and the Sepoys).

Unfortunately, there is no information on this statement neither in this article, nor on that game's page, so this statement seems a bit doubtful: If the strategy was so easy to remember, why isn't it explained somewhere? — MFH:Talk 12:25, 24 October 2006 (UTC)

Full details of the winning strategy are now given in that game's article. Robin S 21:52, 4 February 2007 (UTC)

[edit] Checkers

All endgames up to ten pieces are solved, not only some of them. Also, some of the endgames with 11 pieces have been solved: http://web.cs.ualberta.ca/~mmueller/ps/ijcai05checkers.pdf

Checkers has now been solved by the Chinook program.

[edit] Magic Fingers

The second player does not necessarily win; rather it is the player who doesn't tap the opponent first that wins - see my post the the discussion page for Magic Fingers. 12.206.235.170 22:22, 3 April 2007 (UTC)

Thank you for your suggestion! When you feel an article needs improvement, please feel free to make those changes. Wikipedia is a wiki, so anyone can edit almost any article by simply following the Edit this page link at the top. You don't even need to log in (although there are many reasons why you might want to). The Wikipedia community encourages you to be bold in updating pages. Don't worry too much about making honest mistakes — they're likely to be found and corrected quickly. If you're not sure how editing works, check out how to edit a page, or use the sandbox to try out your editing skills. New contributors are always welcome. —ptk✰fgs 23:28, 3 April 2007 (UTC)

[edit] Hex Contradiction

From the solved status of Hex:

  • If Hex is played on an N × N+1 board then the player who has the shorter distance to connect can always win by a simple pairing strategy, even with the disadvantage of playing second.
  • John Nash showed that all board sizes are won for the first player using the strategy-stealing argument (definition #1).

Aren't these contradictory? The first says that if the second player has the shorter distance to connect, they can win. However, the first says that the first player can always win on any board size (which includes N × N+1 sizes). Is there something I'm missing, or was there some restriction on Nash's finding? --Infophile (Talk) (Contribs) 20:58, 26 June 2007 (UTC)

You may have worked this out already, but the second point should only apply to N by N boards. 70.242.137.81 00:42, 17 August 2007 (UTC)

[edit] Checkers proof

This proof was done through a retrograde analysis involving 2 to 10 pieces on the board. (These are endgame positions.) Solutions involving more than 10 pieces were irrelevant to the proof. There are some search tree roots for which positions involving more than 10 pieces have been proven, but not all positions have been followed back to the beginning of the game. The simplification to 10 or less is what has allowed it to be proven in only 18 years. This is why it is defined as a weak solution. It could be proven back to starting positions of the game but would require years more work which are irrelevant to the proof. By all means, if there is a reference showing the proof back to starting positions, put it in, but all of the references I've seen lately specifically show a subset from the endgame. Aspenocean 04:08, 21 July 2007 (UTC)

What I don't understand from the articles is that they claim that the computer can always achieve at least a draw if there are at most ten checkers on the board. What if one side has nine checkers and the other just one? Seven versus three? Six versus four? Surely the side with more checkers would win? --ZeroOne (talk | @) 04:23, 21 July 2007 (UTC)
Maybe somebody else can do a better explanation than I can. It's a very valid question. More or less what happens when working back from 2 to 10 pieces is that you have to make legal moves and not make any mistakes. In such a case you won't wind up with a situation as skewed as 1 against 9. The possibilities will allow for potential situations other than 5 on 5, but in those cases you would also have to consider the board placement of those pieces to see how they could be used to fight to a draw. (Are your inferior numbers already past capture danger and heading towards the opposing baseline? Will you capture on your next move/ have opponents pieces trapped?) Hope that helps at all. Aspenocean 08:30, 21 July 2007 (UTC)
You are incorrect. As of 29 April 2007, Checkers has been solved from the starting position. Here is the text from the researcher's page in the University of Alberta:
On April 29, 2007, we were pleased to announce that checkers is now solved. From the standard starting position, Black (who moves first) is guaranteed a draw with perfect play. White (moving second) is also guaranteed a draw, regardless of what Black plays as the opening move.[1]
My original description in the article was correct; please check your sources. Owen× ☎ 18:48, 21 July 2007 (UTC)
Thanks, that clears it up. So, to sum it up, there are ten piece positions where one side does have a forced win but given perfect play from both sides no such ten piece position can be reached. If either side makes any mistakes the other side may achieve a position where it has a forced win. --ZeroOne (talk | @) 19:20, 21 July 2007 (UTC)
That's right. In fact, most of the 39 trillion positions with 10 or fewer pieces are a win to one side, but none of these non-draw positions will be reached in a perfect game. Owen× ☎ 19:39, 21 July 2007 (UTC)
  • You need to read the same sources and read the actual proof. The proof was not solved from the starting position. There is no "full search-tree""built from the starting position." Where is this stated? There is a proof tree that covers positions involving 2 back to 10 pieces. The longest line of the front-end proof tree is, to quote the proof, 67 ply. Yes, the proof taken as a whole, and including the "White Doctor opening," shows that from the starting position a draw can be had by either side by perfect play, but you are incorrect to assume that the proof was made from the beginning of the game or that all positions were proven back to the start of the game. If you read the proof as it was published you'll see that all pieces past 10 were irrelevant and only a few positions were followed past 10. I think you're mis-understanding the wording of some of the articles. Just because you prove the draw is possible from the beginning of the game doesn't mean you have worked out the possibilities from the beginning. Again, it was specifically stated in all the references and the proof itself that this was not the case and that it would take years more work to do that and turn this into a strong proof. To further clarify, read the reference you quoted. "From the standard starting position, Black (who moves first) is guaranteed a draw with perfect play." It doesn't say anywhere in that statement that the proof was based on positions from the beginning of the game. It merely says that from the starting position you can play to a draw. You need to read further to see how it was actually proven. It doesn't say "solved from the starting position." It says "solved." You need to read the proof. This, and every other reference in the article, I have read, and they all prove the point as I have described it. For example, the New Scientist Tech article says "Schaeffer was able to get his result by searching only a subset of board positions rather than all of them, since some of them can be considered equivalent." In another paper, not cited for this article, but co-authored by Jonathan Schaeffer, called Partial Information Endgame Databases the following is stated: "A completed 11-piece checkers database would encompass 259 trillion positions, over six times larger than all existing checkers databases, which already took many years to build. The complete 6-piece versus 5-piece subset (all combinations of checkers and kings) is a large portion of this, 118 trillion positions. Unfortunately, most of the computation is practically irrelevant for furthering the checkers proof." I hope this helps further clarify the article. My regrets if this explanation is taken as too harsh, or if the dispute arises from a difference in interpretation by a non-native English speaker. In a lot of the talk pages I've read lately this was the case. I'll state here that I'm more than willing to believe somebody could follow all possibilities back to the start of the game, and maybe by creating some massive distributed computing project in the future it will be (but it has taken 18 years of continuous computing along with improvements in computers in the meantime to get to this point). I have not yet seen much evidence of such a project however, and am unconvinced that it is necessary given the proof that currently exists. As an end note I would add that I think this proof is still being vetted. Aspenocean 00:19, 22 July 2007 (UTC)
I am confused. How is solving only the ten piece endgames enough to "solve" the whole game? Could it have been done with just the nine piece endings? If I setup some random 20 piece position on a board, can the machine now immediately tell me the result? --ZeroOne (talk | @) 04:07, 22 July 2007 (UTC)
  • I wish a good teacher would show up and give a succinct and easily understood description of why it is "solved" with 10 piece end games. I'm certainly not that teacher, but consider this: it doesn't matter what choices have been made to get to the final 10 pieces given perfect play. All endgame databases up to 10 pieces have been computed, thus all perfect play possibilities are known past that point and they are known to lead to draws. If by "the machine" you mean "Chinook", it can't tell you the result from 20 random pieces. It does "know" the database of 10 piece or less positions though and can show the results of all possibilities. (Even the 1 on 9 scenario you mentioned in a previous post.) Whatever mistakes you make in the front end game, Chinook will need only to compare board positions at 10 pieces to its database to know exactly what your possible moves are in the endgame. If you haven't played perfectly up to that point you lose. Aspenocean 04:58, 22 July 2007 (UTC)
  • Just for reference, the USA Today article cited states:"Schaeffer's proof is what is called a "weakly solved" result. It calculates the result from an initial position — 10 pieces on the board — rather than from the beginning of the game.Could Schaeffer's team produce a "strong solution" by calculating every position from the beginning of a game? Maybe, but there is not enough computer power available, he said. It took more than 18 years to get where they are now." Aspenocean 04:58, 22 July 2007 (UTC)
The USA Today article is incorrect. It is clear that the journalist has zero understanding of Game Theory, and, regrettably, it seems that neither do you. I'm not saying this to disparage you or your opinion; this is a highly technical subject, and the USA Today article only serves to confuse things. However, I'm not going to get into an edit war with you. Please read the material on the UoAlb site again carefully, and correct your statements in the article. By the way, part of your confusion may be due to the fact that the paper you quote is an older one, written before the proof was complete. When that paper was written, the 10-piece problem was solved, but the full game tree proof was still in progress. Owen× ☎ 15:34, 22 July 2007 (UTC)
  • Then just write to USA Today and tell them that they are incorrect. All they've done is simplify the explanation. I do understand Game Theory and I do understand what a retrograde analysis is. I also can read the UoAlb site, and from what I've read there the full proof tree is still in progress. Are there not around 19 opening moves followed (Most notably, 'White Doctor')? The older paper explains the process leading to the proof quite well, as does the other paper on "Partial Information Endgame Databases." The key words there being partial information. The proof and the second publication explain why all possibilities are not necessary to prove the endgame. In the end the proof will still be the result of a retrograde analysis even if all possibilities are filled in and it becomes a strong proof. That is why the wording "not solved from the beginning" will always be correct. Seeding the proof tree is narrowing the possibilities required by the proof. In time, more explanation could be added to this article regarding proof trees, search trees, retrograde analysis, game theory, and several other topics, but they're not necessary for a simple statement of "solved games." These more technical subjects belong in their own article with "see also" from here. I'll give it more thought as well on how to include some of this information here without confusing the issue and without backing up into more technical information than is required by the article. Surely somebody else is already doing the same. Aspenocean 19:04, 22 July 2007 (UTC)

Independently from this discussion here, I've also noticed the faulty USA Today reference. They've misunderstood the difference between weakly and strongly solving a game and tried to tie it in with the hybrid forward and backward search approach that was taken to weakly solve the game. I'm going to remove the reference. -- Dissident (Talk) 14:53, 28 July 2007 (UTC)

  • How have they misunderstood the difference between weakly and strongly solved? Aspenocean 07:12, 29 July 2007 (UTC)

Reading the article again, one could claim that there's nothing technically incorrect in the article, but it misleads by omission; it exclusively talks about the 10-piece endgame database:

"Schaeffer's proof is what is called a "weakly solved" result. It calculates the result from an initial position — 10 pieces on the board — rather than from the beginning of the game."

But that's not enough to make the game weakly solved; that's where the forward search comes in and that does start from the beginning of the game. The confusion is probably the result from the fact that having a complete database of 24 pieces would indeed automatically make the game strongly solved. -- Dissident (Talk) 18:27, 29 July 2007 (UTC)

  • The confusion more likely is a result of differences in the definition "weakly solved." An algorithm that shows a win or draw from an initial position (in this case 10 or less pieces) is all that is required for a weak solution. I take this to be the author's meaning when he says "It calculates the result from an initial position." Only a few authors define "weak solution" as requiring a strategy from an opening position (i.e. "White Doctor") that reaches a known game-theoretic value. Most authors would describe these strategies as steps towards a strong solution. Shaeffer's team has taken their work past a simple weak solution true enough, but their ongoing work isn't necessary to the proof as a weak solution. I would argue that you mislead by the omission of the USA Today article by leaving the reader to assume that there is a strong solution, that results of all opening moves are known, that the game was solved from the beginning, or that the database is more complete than it is. Aspenocean 00:31, 30 July 2007 (UTC)

From your confused comment I can only conclude that the USA Today article is indeed misleading. Schaeffer et al. are definitely claiming to have solved the game as played from the beginning:[2]

"This paper announces that checkers has been weakly solved. From the starting position (Fig. 1A), we have a computational proof that checkers is a draw. The proof consists of an explicit strategy that never loses ­‒ the program can achieve at least a draw against any opponent, playing either the black or white pieces."

Notice that it says "the starting position", not "a starting position". Otherwise, the concept of weakly solving a game wouldn't make any sense. Nobody (except possibly USA Today) is using a different definition than the one by Victor Allis:[3]

"weakly solved
For the initial position(s), a strategy has been determined to obtain at least the game-theoretic value of the game, for both players, under reasonable resources."

-- Dissident (Talk) 02:23, 30 July 2007 (UTC)

[edit] Re: Checkers proof, maybe I can help

Hi, I am Ed Trice. I was quoted in some of the newspaper articles on checkers being solved. I did assist in some small way by verifying over 132 billion endgame database positions of Schaeffer's were, in fact, correct, back in 2001. He gives my friend Gil Dodgen and I a mention on his "Thank you" page here: http://www.cs.ualberta.ca/~chinook/thankyou/

Ed Gilbert, another programmer, verified portions of his 10-piece database, and maybe the entire thing by now.

Schaeffer's database originally did not agree with ours, and his was found to have some errors (something like only 89,000 out of 132 billion). He recomputed it, matched our results, and, and then he began in earnest to compute the larger databases (we verified his "4 against 4" data sets, which is written as 4x4 in checkers shorthand. So all of our 4x4, 4x3, 4x2, 4x1, 3x4, 3x3, 3x2, 3x1, 2x4, 2x3, 2x2, 2x1, and 1x1 data matched.)

To answer some of the questions here based on my understanding:

"What I don't understand from the articles is that they claim that the computer can always achieve at least a draw if there are at most ten checkers on the board."
The 5x5 subset of the 10-piece database contains 8.5 trillion positions (where 1 trillion = 1,000 x 1,000 x 1,000 x 1,000 which may be different than the British number.) For every one of these positions, the program knows whether the arrangement is a win, loss, or draw. It has no other information, such as how long it takes to win, or how long it could fend off a loss. This data exists in such a way that a RAM buffer can access the information that is most-recently encountered as the program searches. Independent of the number of pieces that are on the board, even 24 checkers at the start, it is possible to search long enough to "hit the databases." The reason is that jumps are compulsory, and when they exist, they must be taken. You can imagine, if you have 6 pieces and the program has 6 pieces, if it can search far enough ahead to any position wherein you cannot avoid a move that it makes to force a jump where there is an immediate recapture, it can "know" the value of the 6x6 position. If it is winning, it will lead play to a forced jump into the 5x5 10-piece database where it will win. If it has no foreseeable win, it can play for the draw. In the unlikely event that it is in trouble, it can seek to play for a draw (or a win if you blunder) should the opportunity present itself.
What is surprising is that even with the 3x3 6-piece database of 2.5 billion endgame positions, a draw can be forseen from many moves away, with 14, 16, or even more pieces on the board. This does not PROVE anything, because there are countless positions outside of the alpha-beta window that are ignored. What Schaeffer had to do was build a "proof tree" consisting of a forward solver that could always back up play from high-frequency hits of many pieces, call it a "middlegame database" if you want, and this middlegame database can contain entries of positions that had known forced play into the endgame databases. Through a widening circle combining retrograde analysis with huge cycles of forward-solving computations, the two worlds met.
That having been said, there is only one program on the planet that you can download today and have strongly solved checkers data. The "World Championship Checkers" program on the PC can announce a win from 167 plies away. You can download that free program here: http://www.WorldChampionshipCheckers.com WCC will announce win distances every move of the game once it has 6 or fewer pieces on the board. This is over 150 MB of data. If you want the 7-piece database, which is about 13 GB of data compressed, you can have them pressed and shipped by Bob Newell at http://www.bobnewell.net/checkers/wccorders/getwcc.html
Gil Dodgen and I produced this software from 1997-2001 before giving it away as freeware. It runs on the PC. I am currently making an OS X version of it at http://www.OnlyPerfectCheckers.com but it is many, many months from completion. For those who might want to see some strong solutions data, I have a text file complete with ASCII diagrams showing the longest wins up to 6-pieces online here:
http://www.onlyperfectcheckers.com/databases.txt
Note - this was solved on a 500 MHz Macintosh G4, a very slow system. It was used as a "double check" of my larger database. The most distant win for 7-pieces requires 253 ply which I wrote about in a paper you can download here: http://www.gothicchess.com/7_piece.pdf

GothicChessInventor 04:32, 2 August 2007 (UTC)

[edit] How long is "a reasonable time" ?

The article states that

a game is not considered to be solved weakly or strongly unless the algorithm can be run by existing hardware in a reasonable time

What does "a reasonable time" concretely mean ? Svasey 18:20, 27 September 2007 (UTC)

[edit] Pentominoes strongly solved ?

A friend and I had to do a sort of end-of-high-school work and we have chosen to work on Pentominoes.

We found out that this game has been weakly solved by H. K. Orman as stated in the article. After implementing our own program, we found out that the game might have been strongly solved by us. Accordingly to the definition, our program is able to play perfectly in any situation.

The thing we want to know is if our solution matches the definition of strongly solved games and if it is, as it seems to be, the first time it has been achieved.

The project is not finished and further details are coming. If our solution does not match the definition of strongly solved game, is it possible to do so by adding features to our program or so ?

(sorry for English mistakes if any, it is not my first language)

YMS 18:24, 27 September 2007 (UTC)