Talk:Solved game

This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Board and table games Low‑importance This article is part of WikiProject Board and table games, an attempt to better organize information in articles related to board games and tabletop games. If you would like to participate, you can edit the article attached to this page, or visit the project page, where you can join the project and/or contribute to the discussion.Board and table gamesWikipedia:WikiProject Board and table gamesTemplate:WikiProject Board and table gamesboard and table game Low This article has been rated as Low-importance on the project's importance scale.

Some time ago, an inconsistent, unreferenced, second definition of weak solution was added - "That is, produce at least one complete ideal game (all moves start to end) with proof that each move is optimal for the player making it." Contrary to this claim, it is in general possible to have an optimally played example of a game, an (indirect, perhaps) proof that the example game is optimal, but no strategy for playing a position that does not occur in the game, so this claimed alternative definition is not appropriate. Elroch (talk) 21:42, 1 March 2022 (UTC)[reply]

@Elroch: I have moved this new section to the bottom of the page, as is traditional here. About the removal, I don't understand your objection (to me, the two phrases appear to say the same thing) but I also don't see the removed text as particularly beneficial so I have no problem with your removal. --JBL (talk) 22:26, 1 March 2022 (UTC)[reply]

My objection to the unsourced claim is stated in the sentence starting "Contrary to this claim" above. The deleted criterion seems obviously much weaker than the exhibition of practical strategies (as achieved for checkers, for example). Note that the difference is a matter of practicality. I can describe an algorithm to play chess optimally as white or black - construct a 32-piece tablebase and play according to it - but this is not practical to execute. If the only information in a solution is the value of the game, there can be no distinction between the definitions. Thus the difference can be practical rather than mathematical. Elroch (talk) 15:04, 2 March 2022 (UTC)[reply]

Changed the word "moves" to "play" in the definition. There is nothing in the prequel to suggest the game is discrete. E.g. many people will have weakly solved the cat and mouse game where the initial position has the mouse in the centre of a circular pool and a cat at the edge who can run four times as fast as the mouse can swim but not as fast as the mouse can run. It has no consecutive positions so no defined moves. Changed "moves" to "details" in the ultra-weak definition correspondingly. Martin Rattigan (talk) 22:16, 25 May 2024 (UTC)[reply]

The paragraph starting with "Despite their name, many game theorists believe that "ultra-weak" proofs are the deepest, most interesting and valuable" contains wrong information. According to their definitions, a "strong" proof will always count as an "ultra-weak" proof, so that sentence as written is trivially false. I believe that paragraph is trying to say that a non-constructive proof is deeper and more insightful than a proof constructed by brute-force search, even if the first is ultra-weak and the second is strong. If that's the case, it should be changed to say that. But since that paragraph is already marked with a "citation needed" tag, I believe it should be simply removed unless a source for that argument is found. RRM (talk) 01:41, 5 November 2023 (UTC)[reply]

Ultra-weak solutions are just following what usually is meant by any other math problem, as almost every proof of modern open problem is non-contructivem, so this added note feels rather out of place, suggesting that this type of solution is in some way not what is usually meant by phrases used in the definition, I would definitely remove that part.

The strong proof on the other hand is not even a problem that can be logically evaluated in any reasonable way, so it is obviously not considered as deep and valuable in theoretical studies, cause to make it distinguishable from weak one it needs some arbitrary constants as thresholds restricting resources used by theoretically most efficient implementation. The allowed implementations also need some restrictions, for example is quantuum computing allowed? If it is, we need next arbitrary constants restricting this special case. Compute shaders again should have separate treatment for algorithms that can be efficiently parallelised, but the parallel processing on CPU cores also should be taken into account. So we on top of that need to agree on formula correcting the number of elementary operations that we apply if the parallel implementation is possible... if we account for all of that, what about memory access? Obviously I took that way too far, but to make it formal we would need this type of absurd, as submitted code of implemented algorithm is a formal proof just as rock falling on the ground is proving that gravity exists - it is empirical, so need empirical science to give it any meaning at all.

In the weak case constructive proofs are part of well defined theory, but what if someone show that constructive proof exist without founding it? From purely logical point of view, this will be a solution of the strong problem, as the hypothesis states that constructive proof exists. The logical evaluated of the sentence cannot refer to the method used to evaluate whether it is true or false. So weak problems in fact must allow non-constructive proofs as solutions, but non-constructive proofs were specifically stated as part of definition for ultra-weak proofs...

I think it becomes quickly clesr that both of these stronger types are interesting problems in context of empirical science, as with empirical scientific methods none of above problems are significant, but from purely formal perspective on which methodology of mathematics is based the ultra-weak solutions are the only candidates for interesting open problems, as additional requirement for existence of constructive proof, apart from having possibly non-constructive solution, exludes almost every tool developed in modern mathematics, as these are very rarely constructive. This is obviously making the problem much harder to solve, but at the same problem much less interesting to work on. From this point of view, the ultra weak solutions are indeed the deepest, interesting and valuable as allow using deep recent results providing new tools that can be used to approach notable unsolved problems and usually making these proofs invalid for weak problems, and using newly developed theory to solve new type of problems that were open problems up to this point actually provides a huge value to the current research in related field, arguably much bigger than finding entremely hard proofs based only on old and well understood theory, even if the proof is 10 times as briliant.

Thats why is see no direct opposition of strong and weak problems being on paper harder to solve but the ultra-weak being considered by as quoted. The only adjective that would make this into contradiction is the claim that these problems are harderst to prove, what was not implied at any point. ~SpectralFlux 04:50, 6 August 2025 (UTC)[reply]

Just wanted to provide some context to my previous edit (first day contributing to a wiki articles).

In alignment with revision 1057486730 of the main Kalah page, I have removed reference to original research and a computer program by Mark Rawlings. These contributions did not comply with Wikipedia's No original research policy. :(

I'd like to encourage Rawlings to publish his research in solving Kalah variations. I believe his work is interesting and could be very valuable. The crate catsby (talk) 04:14, 28 April 2024 (UTC)[reply]

This principle would make almost entire mathematical Wiki unable to find any reference whatsoever so is not respected in pretty much every single article that try to provide sources at all, removing some random papers makes this just as ignored as before, only with sporadic random bursts of applying the rules, with only real effect being maybe looking as preferential treatment ~SpectralFlux 05:06, 6 August 2025 (UTC)[reply]

This directly contradicts the definition of weak solution from above... SpectralFlux (talk) 21:16, 3 March 2025 (UTC)[reply]

You're correct. The definition in the article misstates the the definition in the cited source, which includes "under reasonable resources": "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." http://fragrieu.free.fr/SearchingForSolutions.pdf AndyBloch (talk) 23:26, 6 March 2025 (UTC)[reply]

That definition works clearly for applied CS, but mathematically under reasonable resources is as far as I know undefined so this definition is ususable in any actual theorem ~SpectralFlux 19:48, 18 April 2025 (UTC)[reply]

This classification system can apply to games that have more than 3 values, and the entire article should be rewritten to talk about "game-theoretic value" instead of just win-lose-draw outcomes. I don't have the time to do it at the moment. AndyBloch (talk) 23:40, 6 March 2025 (UTC)[reply]

The article introduction should clarify that this only applies to strictly competitive games. There is some confusion due to people calling certain games "solved" in a more general sense where it doesn't apply in game theory. The Super Mario Bros. entry should be removed as it doesn't fit the proper definition. 2603:6011:5AF0:77F0:60EE:4F62:E8AB:9092 (talk) 20:32, 23 March 2025 (UTC)[reply]

Should MartSnack’s entry for Pokémon Platinum be added to the current list? The video for this implementation was cited in a GameRadar article at the time. I’m not sure about if GameRadar articles are valid citation sources for Wikipedia though. 2600:1009:B00E:EE92:6D13:3DD4:1739:5CEC (talk) 08:48, 26 March 2025 (UTC)[reply]

While I'm not 100% sure on the citation guidelines, that video and process is so unbelievably impressive and represents the sheer scale of solving a game that it deserves to be on the list. Just my opinion, but it should be there. TopoPhill (talk) 06:03, 18 May 2025 (UTC)[reply]

It's a very impressive project, but it doesn't have anything to do with solving a game in a game theory context, so it doesn't belong on this page. 2603:6011:5AF0:8F40:B83B:280B:3F2D:C8C1 (talk) 20:30, 29 May 2025 (UTC)[reply]

I agree. Bubba73 ^{You talkin' to me?} 03:56, 31 May 2025 (UTC)[reply]

Does Super Mario Bros. belong in this article? Bubba73 ^{You talkin' to me?} 06:13, 15 May 2025 (UTC)[reply]

The picture of a completed game of Connect 4 is impossible because both players have won. Thunderhawk256 (talk) 22:03, 26 June 2025 (UTC)[reply]

@Thunderhawk256: I don't see any four consecutive pieces of the light color. Bubba73 ^{You talkin' to me?} 00:05, 27 June 2025 (UTC)[reply]

It's perpendicular to the red winning line. I don't know if that's grounds for removal or anything, but it's not a very meaningful image to the article anyway. Squebbs (talk) 21:26, 27 June 2025 (UTC)[reply]

Right you are - I missed it. Bubba73 ^{You talkin' to me?} 22:32, 27 June 2025 (UTC)[reply]

I got out my Connect 4 game - I'll take a proper photo. Bubba73 ^{You talkin' to me?} 22:44, 27 June 2025 (UTC)[reply]

Should we really remove Othello from the list of unsolved games, given that it's only weak-solved and the paper is contested? Neuhaus (talk) 13:00, 2 July 2025 (UTC)[reply]