Talk:Solved game

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.

Solved puzzles

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

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

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

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

I further removed this bit:

A stealing-argument taught that since the dimensions of a Go board are always odd, consist of an odd number of spaces and have a perfect center in the board, this give an advantage to the black player (the starting player) that it can always win in a perfect play at all board size - by putting the first stone at the only center within the board and closely put the next stones near the enemy while preventing of being encircled or captured. As a result, most competitive Go scoring rules give the second player a certain number of compensatory points, called komi.

The above argument is speculative at best, common myth at worst. See Mirror_go. I replaced it with the well-known ultra-weak argument that gives a win or draw for the first player. 64.30.81.154 (talk) 18:40, 20 January 2010 (UTC)

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

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)

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)

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)

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.

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)

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)

• How the heck can a variation with swapping be solved??? This claim seems preposterous. Citation or it didn't happen.

71.193.11.72 (talk) 19:13, 10 April 2010 (UTC)

• Easy. Swapping is always the second move of the game (in hex). Suppose hex becomes strongly solved in the absense of swapping and is a first-player win with perfect play (this is actually the case on some very small boards). It would be natural for the first player to make the strongest possible opening move (by some criterion such as minimizing the maximum possible length of the game with perfect play). Boring. So we introduce the option of the second player to change places with the first player as his first move. Now the game is won by the second player, and this is proved to exactly the extent that the non-swap version of the game was solved. In practice, this is done to equalize the game somewhat, because now the first player will be motivated to choose a weaker opening move. Perhaps even one that he knows how to defeat. It's up to the second player to decide if that opening move is defeatable or not. If it is, s/he should swap, otherwise not. As a practical matter in hex, the values of all opening moves on boards up to 8x8 (and most of the 9x9) have been determined (claimed in P. Henderson, B. Arneson, and R. Hayward, "Solving 8x8 Hex", Proc. IJCAI-09 505-510 (2009), and in Hayward's paper http://webdocs.cs.ualberta.ca/~hayward/papers/solve8.pdf).

kogorman (talk) 16:14, 29 June 2010 (UTC)

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)

• Sigh. Here's the deal. Go as you please is in fact weakly solved, and determined to be a draw when no mistakes are made by either side. Not all of the 3 move restriction openings are solved. Many of them have been, and are proven draws. All of the openings in three move restriction that are not proven draws can be avoided simply by one player playing perfectly. Therefore the game is weakly solved. Both players have a strategy that cannot lose from the opening position, and that will win if the other player makes a mistake. Chinook now cannot be beaten without a three move restriction random draw forcing a weak opening. A strong solution is not yet computationally feasable. 71.193.11.72 (talk) 21:17, 10 April 2010 (UTC)

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)

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)

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)

Updated International Draughts partially solved

I updated the information on International Draughts partially solved. Mschribr (talk) 10:41, 12 August 2008 (UTC)

Three Musketeers solved

I have strongly solved Three Musketeers. I'm new to Wikipedia and not familiar with the policies. Can I add it to the article myself and cite my own website? Jlaire (talk) 07:22, 10 October 2009 (UTC)

Hello. Cool work! The relevant policies are WP:Verifiability and WP:Reliable sources (and possibly WP:Conflict of interest). The best way to do this would be to get the result "published" in some form, and then it could be added. Cheers, Shreevatsa (talk) 19:50, 10 October 2009 (UTC)

Ok, thanks. WP:Conflict of interest shouldn't be a problem because it's just a mathematical result with nothing to promote. But the other policies definitely are - I have no way to get it published anywhere and the correctness of my program isn't readily verifiable, so just putting it on a personal website isn't good enough. But it's not a big deal - I know only a few people who have even heard of the game. :) Cheers! Jlaire (talk) 01:05, 11 October 2009 (UTC)

I could suggest submitting your game to the ICGA Journal (International Computer Games Association). I do not know for sure that all contents are refereed, as some are just news reports about competitions, but the long articles seem to be of high quality. kogorman (talk) 15:26, 29 June 2010 (UTC)

Thanks for the suggestion, but I don't think Three Musketeers is interesting enough for that. Any programmer could write a strong solution, because there are only a few million positions. The game is also not widely known (except for Vying Games, where you can play it), so I don't think trying to get it in this list is worth the effort of fighting wiki bureaucracy. 80.248.244.32 (talk) 18:17, 11 March 2011 (UTC)

Query about "Perfect Play" versus always improving your situation

In the article's "Perfect Play" subsection, it says "As an example, a perfect player in a drawn position would always get a draw or win, never a loss." This implies that perfect play from that point on in a game would always improve the player's outcome, or at the absolute least would prevent them from getting into more difficulties, right? But isn't it possible that a player who is currently drawn in a game, playing perfectly from that point on, might still be forced into Zugzwang? In which case, that would by definition worsen their position in the game? 79.77.203.214 (talk) 00:42, 5 March 2010 (UTC)

No, it's not possible for a player who is currently in drawn position to be forced into zugzwang. If it was possible, then the initial position would not be called a drawn position, but a lost position (won for another side). 333ES (talk) 01:16, 9 March 2010 (UTC)

Definition and introduction

I suggest the opening section could be improved in the following ways:

• Mention of mathematics is at best tautological, at worst superfluous
• The section is more verbose than required
• The section is incorrect as perfect play can lead to a loss

I propose the following new opening to address these issues:

A solved game is a game whose outcome can be correctly predicted from any position when each side plays optimally. Games which haven't been solved are said to be "unsolved". This article focuses on two-player games that have been solved.

Please let me know what you think. Stephen B Streater (talk) 22:07, 19 March 2010 (UTC)

Agreed. 333ES (talk) 02:45, 24 March 2010 (UTC)

OK - done. Obviously open to further improvements. Stephen B Streater (talk) 10:07, 24 March 2010 (UTC)

Agreed. I suggest the opening sentence should become: A solved game is a game that is solved in any of the three ways mentioned just below. Games which haven't been solved are said to be "unsolved". This article focuses on two-player games that have been solved.

The only other consistent rewording I can think of would refer to games the outcome of whose *initial* positions can be predicted.

This accomodates games like Qubic (weakly solved) which are *not* solved in the manner described in the current opening sentence, but which are nevertheless cataloged here. kogorman (talk) 18:02, 29 June 2010 (UTC)

Dakon moved to Ohvalhu

De Voogt who reported that "Dakon" is solved by human players was mistaken. He was never on Java and never observed the Javanese mancala game of Dakon. Dakon has been described here based on Indonesian sources. They prove that Dakon has its own rules differing from the rules used by de Voogt. De Voogt based his research on observations he had made on the Maldives of a game called Ohvalhu or Naranj, but published them under the name of Dakon, which was nonsense.--93.193.105.40 (talk) 07:31, 4 April 2010 (UTC)

Three men morris and Tic-Tac-toe lacks citations.

These two games are listed as solved games yet there is no citations. Since we are talking about a mathematical concept, full citation is necessary. Tdakpa (talk) 18:58, 7 June 2010 (UTC)

Tic-tac-toe can be solved by school children. I doubt you'll find a refereed article about that. As an alternative, I could post a Java program that does the complete solution (with or without recognizing transpositions and symmetries) that finishes in under a minute on a modern commodity desktop computer. It's just kinda long, and I don't want to publish under your license, but I could post it under another FOSS license if that would help, but you don't seem to like links to personal web pages. Does anyone disagree that it's trivially solvable? Why not just let it be? kogorman (talk) 18:38, 29 June 2010 (UTC)

Forms of Solution

I've been dissatisfied for some time with the three categories of solution, but cannot find any reference to substantiate this: I think there should be a level of solution between Weak and Strong, which provides a theoretically-losing player with the devastating reply to any error by the player who should win. I sometimes think of Weak as a "winner's tree", and the new level as the "competitor's tree". I don't know if it's legitimate to put any comment about that into the page proper until an external reference is available.

Eventually, I may provide the reference myself, but I haven't completed the work. It will most likely appear for the games of Chomp or Qubic, as I'm working on both.

kogorman (talk) 15:00, 29 June 2010 (UTC)