Talk:Solved game

From Wikipedia, the free encyclopedia

This is the talk page for discussing improvements to the Solved game article.
Please sign and date your posts using four tildes (~~~~). New discussion topics go at the bottom of the page; click here to start a new topic. New to Wikipedia? Welcome! Frequently asked questions. This is not a forum for general discussion about the article's subject.	Talk page guidelines Be polite Assume good faith No personal attacks Don't bite the newcomers!

Contents 1 Scrabble 2 Solved puzzles 3 Useful article 4 Article name 5 Go solved 6 Games with a finite number of positions 7 The definition of "strong solving" 8 Reversi Nearly Solved 9 Maharajah and the Sepoys 10 Checkers

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

[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