TallBill Member Posts: 298 From: St. Louis, MO Registered: 11-22-2002 |
Program "can't" lose at checkers. We all know that every program has flaws because they are written by flawed humans. These flakes claim otherwise, though. ------------------ "...prayer itself is an art which only the Holy Ghost can teach us. He is the giver of all prayer. Pray for prayer---pray till you can pray; pray to be helped to pray, and give not up praying because you cannot pray, for it is when you think you cannot pray that you are most praying. Sometimes when you have no sort of comfort in your supplications, it is then that your heart---all broken and cast down---is really wrestling and truly prevailing with the Most High." |
ArchAngel Member Posts: 3450 From: SV, CA, USA Registered: 01-29-2002 |
I made a TicTacToe game that can't lose. granted it was for a class and so the algorithm was given... the logic is rather simple. Look at all the possibilities and choose only the paths that have a guaranteed win in it for you (or the most favorable position).
------------------ |
jestermax Member Posts: 1064 From: Ontario, Canada Registered: 06-21-2006 |
i think his point that a program written by humans is automatically flawed. I think it's a bit of an overstatement to say that a program "can't lose" at checkers but the Deep Blue family destroyed the world chess champion sooo i think its safe to say that a program can beat a very large majority of humans. Oh yeah, and my tic tac toe game doesn't lose either  but at least mine has techno music (visit www.JestermaxStudios.com)------------------ |
|
Matt Langley Member Posts: 247 From: Eugene, OR, USA Registered: 08-31-2006 |
Just because something can't lose doesn't mean it always wins (as been stated), and though I would agree the narration of this article is a bit annoying I don't think their general claim is Arrogance. In something as structured as checkers you can in fact determine the "best" or a tie for the "best" moves. Checkers is played via fairly structured and simplistic rules. This doesn't translate into many RL applications because just about all of them are amazingly more complex. ------------------ |
samw3 Member Posts: 542 From: Toccoa, GA, USA Registered: 08-15-2006 |
Checkers, like Tic-Tac-Toe and Chess is a deterministic game--meaning the outcome of each full game, is determined solely upon the steps it took to get there and not on any other/external influence. And even though there is randomness introduced into the game, it is controlled by the quantized states defined by the game rules. For instance, you can't put a piece halfway between two squares. All this means that even though there a large number of board states (64*64*5=20,480) and incredibly more endgame positions (39 trillion?), it is simply computable as a lookup tree. The algorithm is simple and thus infallible. The problem is storing the tree and walking the tree fast enough to not make the game boring Sports on the other hand are non-deterministic since they include random time and physical elements, which make predicting them more like predicting the weather. On a more philosophical note, it is possible for a flawed human to conceptualize an infallible system, if the system is simple enough for the human to comprehend all states and paths. And, where infallible means it always operates as designed. Perhaps this is the image of deity imprinted on us by the Creator. "The LORD came down to see the city and the tower which the sons of men had built. The LORD said, "Behold, they are one people, and they all have the same language. And this is what they began to do, and now nothing which they purpose to do will be impossible for them. 'Come, let Us go down and there confuse their language, so that they will not understand one another's speech.'" God Bless! ------------------ |
zookey Member Posts: 1902 From: Great Falls, Montana, USA Registered: 04-28-2002 |
LOL most Team Ninja games (dead or alive, ninja gaiden) have elements that are dang near unbeatable....of course (at least in Ninja Gaiden) it is partially because the player is sometimes expected to battle the enemeies as well as the camera LOL----not anywhere near good enough at checkers to think I could win LOL ------------------ |
steveth45 Member Posts: 536 From: Eugene, OR, USA Registered: 08-10-2005 |
quote: This problem lies outside of the domain of computers. There are more possible chess games than there are particles in the universe. Faster processing speed is no longer a solution. ------------------ |
|
samw3 Member Posts: 542 From: Toccoa, GA, USA Registered: 08-15-2006 |
quote: Don't ya just hate those dependent modules.. I guess its time to finally code that bigger universe. ------------------ |
Cohort X Member Posts: 126 From: The Great Pacific Northwest Registered: 09-16-2006 |
OR instead of trying to brute force a stalemate by memorizing all possible outcomes you could just make the program lock up after the second move. |
HanClinto Administrator Posts: 1828 From: Indiana Registered: 10-11-2004 |
quote: Just to clarify, in order to play a perfect game, one doesn't need to record all possible games (I.E. every permutated sequence of board arrangements -- estimated to be something greater than 10^120), but rather only needs to know every possible board situation and how they link together (more often debated, but estimates seem to range from 10^40 - 10^50). The estimated number of particles in the known universe is around 10^80. So yes, while the number of possible games is greater than the particles in the known universe, the thing that we actually need to keep track of is far less than that. I would apologize for being so pedantic, but talking about completely solving chess/checkers is inherently nerdy and nit-picky to begin with. Cheers! --clint |
Brandon Member Posts: 594 From: Kansas City, Mo, USA Registered: 02-02-2004 |
I've never beaten my computer at chess... I would even cheat, I'd use undo on every turn almost... I stayed up till 3am... and it still won. (Hangs head in shame) ------------------ |
|
steveth45 Member Posts: 536 From: Eugene, OR, USA Registered: 08-10-2005 |
quote: I'm aware of the ins and outs. I thought I'd keep the post short. OK, so you can either store every possible position, or, each turn recurse through all available moves. From the storage perspective, lets say that 10^50 positions is sufficient. Now, the storage option is worse, because you still need to take every single possible position and then recurse through all available moves to find which move (from each side) is the best move. Just storing the moves doesn't do anything for you. The permutations and calculations involved is much larger than just starting from the initial board layout and recursing through all moves once. Now storage is an issue, as well. The earth weighs (very roughly) 10^24 kg. That's (very, very roughly, but in the right order of magnitude) about 10^48 atoms. So, assuming it could be calculated (which can't be done), to store the perfect chess database, assuming that we could store a single chess position and relevant moves by configuring 100 atoms (a very wishful estimate), we would need, roughly 10,000 Earth sized planets mashed together into one large, perfectly arranged holographic storage device. Maybe it could be RAR'ed down to 5000 planets. Assuming Moore's law holds true for the next 100 years (we'll hit hardware limits long before that, but lets assume), it would take a computer similar to Deep Blue how long? Well, DB calculates 10^8 moves per second. 100 years of Moore's law would increase processing power 10^30 times, roughly. So, it would take a Deep Blue style computer from 100 years in the future 10^120/10^38 seconds to recurse all available moves which is about... 10^75 years. Is that detailed enough? Chess will never be solved by computers. ------------------ |
