http://en.wikipedia.org/wiki/Solved_board_games
I was surprised to learn how many board games have been completely solved and how many are close to being solved. I wonder how long until this happens to multiplayer video games. Of course in video games since most don't have turns you have to seperate each move by frames and there are alot of frames to consider espically when you compare them to the number of turns in an average board game. Fortunately though the number of possible moves on each frame is lower than the possible moves for each turn on a board game. If this knowledge was applied to an AI it would be unbeatable and competition between these AI opponents could be more intertaining than watching the best human players. Too bad computers haven't advanced far enough yet.
The problem is as you said that video games typically does not have turns, but are played on reflexes. For example in a fighting game: if it allows both players to perform the same moves, and treat them the same (i.e. no player's moves has predesence + spelling), all matches are a forced draw.
This reminds me of dots and squares.
http://www.apples4theteacher.com/java/dots-and-squares/index.html
I remember I figured out a really good strategy to dominate the crap out of this game back in middle school (usually getting at least 75% of the squares) It was great.
The trick:
After all the free spots are gone, when capturing a group of squares, instead of taking the last two, leave them available to take for the other player, using your turn to create the line at the end of the chain. The other player will take those 2 squares (4 in some cases) and then be forced to give you another long chain!
<Swordless> Go hug a tree, you vegetarian (I bet you really are one)
Joined: 5/1/2004
Posts: 4096
Location: Rio, Brazil
JXQ: that's basic strategy that only works 75% of the time if you're playing someone who doesn't know that strategy. The real thing about the game is to predict the right number of turns you'll need to force control over it by doing that strategy, and drawing the map to force you to have that advantage.
Wouldn't solving the game take all the fun out of it? It might be cool to be like "I can always beat you HA HA!" for a little while, but eventually that would get old. Also, I would have to disagree that watching two perfect AI players in vs would be more entertaining than watching humans. Just go watch someone on cs with aimbot and tell me how long you are entertained. It just doesn't do it for me. Maybe I missed the point, but isn't that how perfect AI would play, except with more precise movement?
That problem is more about choice of game than how boring a perfect player would be.
A shooter of course is boring, perfect knowledge about the position of the enemy (which is nessecary for solving the game) will result in instant double kills every time the players meet.
But what's about Civilization? It's a game that heavily punishes you for not being active, it's turn-based, and as soon both strategies don't think they'd win an invasion both pass and the territory is counted. Draw is not possible on a map with odd number of fields.
(Yes, I play go.)
I wonder what playing a game like mario kart 64 with 2 players perfectly would look like. Since you can manipulate luck both players could get any item they wanted but using items that slow the other player down probably wouldn't work too well since as soon as it was used the other player would probably be able to find a way to block or avoid it somehow. My guess is that every time either player hit an item box they would manipulate luck to get a gold mushroom. Since you can't get these in first place (I think) they would have to slow down and drop just behind the other player when stopping the item roulette. I wonder if it is possible to get ties in mk64. What would happen if both players crossed the finish line on the same frame. I am assuming it would give player 1 the win but I am not sure.
Connect Four is probably another popular game that could be solved completely.
However I'm sure there are some other games that will never be solved completely like Chess for example. It offers so many variations that not even the fastest computer in the world even after 100 years will be able to calculate all possible moves in the game.
640K is enough for anyone. AMIRITE?
Chess *only* has 10^50th or so legal positions. In contrast the world's fastest supercomputer has 32 TB of memory. (10^13)
Fifteen years ago computers had 640K of RAM. Present day, my computer has 2GB RAM. That's an increase of 400,000 fold.
Computers will get there. It'll just take some time.
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
so, even if we keep up with increasing the memory density by 400.000 each 15 years, we'll get from 10^13 to 10^50 in about 120 years. That's definetly not in the timeframe Saturn mentioned.
Also, how are you going to store a whole chess-position as well as one of it's winning moves in just 1 byte? A computer with 10^50 bytes isn't enough, so expect further delay.
oh, and by the way. Even if you somehow managed to store one bit in each hydrogen atom, you'd need 8*10^50 atoms for the storage, which is
485 541 181 493 337 650 646 730 kg, or about 1/12th of Earth's mass.
Good luck.
This is really apropos of nothing, but it is possible to store more than a single bit in but a single particle. I remember some research a few years back where a Japanese (?) scientist showed how it should be possible, in theory, to store an arbitrary amount of information in a single electron. I don't remember the mechanism behind it, but it obviously had something to do with odd quantum mechanical effects and wave functions and other mostly impenetrable concepts. If I recall correctly, the scientist and his team actually successfully stored and retrieved on the order of 8 bits in an electron as a proof of concept. I'm pretty sure I read this in Science News, but it would take me forever to find the article, so sorry about not having any better information.
You only need 32 byte to describe a chess posistion. That's a difference of a single order of magnitude. Thusly,
every half byte is a square.
0000 empty
0001 white pawn
0010 white en passantable pawn (or castlable king as determined by posistion on board)
0011 white bishop
0100 white knight
0101 white rook
0110 white queen
0111 white king
1000 reserved
1001 black pawn
1010 black en passantable pawn (or castlable king as determined by posistion on board)
1011 black bishop
1100 black knight
1101 black rook
1110 black queen
1111 black king
And you still have a bit left over. And you can use a graph with infinite precision integers as memory pointers, requiring 42 bytes max for each pointer. The most contrived example I can think of requires around 160 nodes for both previous and next possiblities. (6720 bytes max)
You can make a calculation vs. memory trade off, you don't need all 10^50 states in memory at once. If you can cut that down to by 10 orders of magnitude you're down to 48 554 118 149 334 kg.
The great pyramid weighs 5 443 108 440 kg. We're four orders of magnitude off.
This is assuming that we don't come up with a way to store memory in something smaller than atoms in the next 100 years. If we were somehow able to store information on the scale of a planck's length (a very long shot, used simply to illustrate, however, it is possible, because the energy of empty space is not zero) you could cram all 6.752 x 10^53 bytes of memory into 2.28055197 × 10^-50 cubic meters of empty space. A proton occupies a space the size of 10^-45 cubic meters.
Do I think this will take place in the next 100 or even 500 years? No.
However, the word I latched onto in Saturn's post was "never." And I don't think that Chess, or even Go will never be solved.
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
Actually, I take back that Go part. Even on a planck length, it's simply not possible to store that much data. O_O; Not until we become a class V civilization at least.
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
You can make a calculation vs. memory trade off, you don't need all 10^50 states in memory at once. If you can cut that down to by 10 orders of magnitude you're down to 48 554 118 149 334 kg.
if you just want to prove that it can be solved, you can discard a lot of game positions along the way. If you want it solved, you'll either need to store every position along with it's winning move(s) and formulate the winning strategy as "just find the current position in the archive and look up the winning move", or find a more generic strategy.
If we were somehow able to store information on the scale of a planck's length (a very long shot, used simply to illustrate, however, it is possible, because the energy of empty space is not zero)
care to tell me how you're going to read that data without destroying it? Or, write that data without destroying the data of nearby bits?
I'm thinking about the transporters on Star Trek. They convert the matter in the away team into energy, then convert energy back into matter. Assuming that you could really do that, and you could materialize only the data you needed (the transporter has been used to filter out viruses, deactivate weapons, or materialize one person and not another), you could store matter used to record the data as energy and simply materialize and de-materialize the data a few trillion positions at a time (depending on how much space you had).
Too far-fetched for this debate?
At any rate, while I agree that it would be a monumental task, I'm skeptical about the word "never". Someone always seems to discover a way to do something in a manner that no one had ever conceived of before.
TASing or playing back a DOS game? Make sure your files match the archive at RGB Classic Games.
You seem to be assuming the only way to solve board games is through a brute force method. Through advances in AI a computer could determine certain sets of moves that don't have a chance of being the best ones. I think in 100 years we will have solutions to every currently invented (as of year 2006) video game and board game.
See also: http://en.wikipedia.org/wiki/Machine_learning
This is probably just the beginning of machine learning and humans and computers will probably be able to come up with better ways they can learn in the future.
Also what do you think is the theoritical max for data storage is. In terms of 10^x GB what do you think the highest number x could be.
