- Joined
- 29 Dec 08
- Moves
- 6788
03 Jul 10
Originally posted by savage4731If up against a higher ranked human or machine, it would make sense to draw if a loss or draw by best play is foreseeable, but against an opponent of lower or unknown ranking, it might not. I have had opponents fail to see my blunders and missteps. Generally speaking though, I think you are right. Take the draw if you see that there is a reasonable chance that your opponent will find a best-play win.
By "unwinnable" I meant that the player whose turn it is to move has a position that cannot be won with correct play by the opponent. It could potentially be lost but the best he could hope for is a draw.
The payoff for a draw on each successive move would be lower. If we assume the payoff for a draw is .5 and the probability of the draw occuring if c ...[text shortened]... If a computer has a choice between a mate in 1 or a mate in 10 it will choose the mate in 1.
As to the rule "of two ways to mate, use the shortest route", I agree, we don't program sadism into the machine. 🙂
03 Jul 10
I didn't read all of the messeges but I can say this..
The game-ology claims that every game has a strategy to win, or at the very least. not to lose.
Also, something is called a game if:
a. there is no random factor involved ( random as in.. dices, cards etc )
b. the final value of the game is 1 ( as in score of 1-0 0-1 0.5-0.5 )
c. All of the information is revealed. ( for exsemple, in "battleship", one side doesn't know where the other's ships are placed, therefore it's not a game)
d. there are 2 players, and they are playing by turns.
e. both players start with a similar situation.
I think I forgot something but these are the main things.
Now since chess includes all of the rules, it's a game, therefore, there's a winning strategy.
But I think I've seen a comment or two saying it doesn't metter anyways, since unlike 4 in a row or checkers, even if there will be a computer strong enough to colculate the winning strategy, you'll have to memorize numerous moves, which is impossible really.
Hope that answers your question, and that no one said that before, lol.
03 Jul 10
Originally posted by Svin1"No, the truth is that raw computational power is useless if you want to brute force solve chess,"
No, the truth is that raw computational power is useless if you want to brute force solve chess, you would have to break several fundamental laws of physics to even contain the analysis. The reason engines are getting stronger is due to refinements of the heuristics used to search for moves rather than the hardware.
For the past 50 years computational powe ...[text shortened]... law--at the current rate the universe will die of old age before computers catch up with chess.
I've done the math. If IBM wanted to let me have anything I wanted I could do it in about 5 years. There are ways to significantly cut the amount of information that would need to be processed. For some reason, most of the people that talk about this subject dont seem to figure those in.
"you would have to break several fundamental laws of physics to even contain the analysis."
Funny, I was just watching the Science Channel last night and based on what he said, I think Michio Kaku would disagree. I'll take his word over yours. Bottom line is there is no limit to storage capacity. If one drive isnt enough then get 20 (one for each opening move). If thats not enough then get 400 (one for each black response) and so on...The only limit is financial.
"The reason engines are getting stronger is due to refinements of the heuristics used to search for moves rather than the hardware. "
I know how computers analyze and I also know thats completely the wrong way to do it if you want to solve chess as opposed to just playing chess.
"For the past 50 years computational power has doubled every two years as predicted by Moore's law--at the current rate the universe will die of old age before computers catch up with chess."
I think you're forgetting Moore's law is talking about exponential increases. It wouldnt take anywhere near that long with current technology. Exponential increases are only going to dramatically shorten the amount of time.
I started playing chess pretty late and havent been playing much the last few years so I dont have much of my life invested in the game. I think a lot of people who have devoted significant parts of their life to chess are terrified at the prospect of it being solved and dont want to believe what I'm saying. But, the truth is, I'm right.
03 Jul 10
Originally posted by savage4731My point is, that if you want to solve chess a brute force approach is not feasible because all the computational power imaginable would be insufficient due to the nature of chess. All the computers on Earth working in tandem would be no match at all for a problem like chess because of its exponential nature.
I've done the math. If IBM wanted to let me have anything I wanted I could do it in about 5 years. There are ways to significantly cut the amount of information that would need to be processed. For some reason, most of the people that talk about this subject dont seem to figure those in.
Funny, I was just watching the Science Channel last night and ba ...[text shortened]... of it being solved and dont want to believe what I'm saying. But, the truth is, I'm right.
I did figure in ways to cut down the amount of needed calculations--in fact I claim that the only real improvements to computer chess are due to refinements of the search-heuristics. It is trivial to make a program that can check every line in a game of chess so all research is directed towards ways of limiting the search-tree. However, no matter how many tricks you employ to weed out the irrelevant lines, the function remains exponential.
In 1978 the first computer won against an IM and 30 years later computers have only climbed to GM level even though they are now about 100.000 times as fast as back then. Playing chess and solving chess may not be the same thing but the problems are certainly related.
I'm not saying that there is no way to solve chess, just that a naive brute force assault on chess won't yield results no matter how much computer power you pour into the mix. There are several problems in computer science that can't be solved by adding more processor cycles, chess is only one of them.
I hope that chess will be solved eventually but I'm confident that if it happens it won't be because some super computer looked through all possible games. You say you have a better way to solve chess than the ideas currently employed, maybe you could elaborate?
03 Jul 10
Originally posted by savage4731I’m certainly not an expert on this matter, so there were bound to be flaws in my (wishful, I guess) “logic”, and I’m not going to argue with this. But I think you are really too optimistic (pessimistic?!) about when chess can be solved, as others already noted.
First of all, in a game theory sense, the act of claiming a draw IS a move. You cant arbitrarily exclude it anymore than you could exclude a move by a piece. Therefore your two examples are meaningless because they dont include all of the options available to the players.
Second, when you reach a position of 3 fold repitition the player has three choi ...[text shortened]... about 50 years most people will have computers powerful enough to solve chess on their phone.
Anyway, suppose there is a device assigned a mission to solve chess. At the start the processor of this device can perform U operations per year. Let R be the ratio at which the speed of this processor increases every year, and let S denote the number of operations required to perform in order to solve chess. Suppose it will take k years for this device to solve chess; what is the value of k?
The simple formula for the sum of the first k terms of a geometric series (with R not equal to 1) is
S = [U(R^k – 1)] / [R – 1] <=> k = [log (S(R-1)/U) +1] / log R.
If you have S and U in the form S = 10^a, U = 10^b, a good approximation (given that numbers are so obscure) for k is
(a - b)/logR (with log base 10).
I realize this may be very simplistic model, but that’s a view of someone who knows nothing about computers. So here’s my try.
If the processing power doubles every 2 years, and we make an assumption it will keep doing so for another few centuries, then we can take R = sqrt(2) < 1.42.
The most powerful computer on Earth, called Jaguar, or whatever (that’s from a quick Internet search) can perform 1759 teraflops (?), so this gives 1.8x10^15 operations per second. Let’s say we use 2 of them, giving 3.6x10^15 power. A year (365 days) has 31536000 seconds, so the 2Jags can perform 1.1x10^23 operations per year; let’s just take 10^23 for convenience.
As for S – I have no clue. Suppose we take S = 10^123, which is the estimated game tree complexity with game length 80 moves and on average 35 options at every node.
Putting R = 1.42, U = 10^23 and S = 10^123 in the above formula gives k = 654 years, the 2Jags able to perform 1.4x10^115 operations per second in the last year.
Even if you start with quantum computers and U = 10^63, k = 392.
If you are fine with the above, what values of U, R and S would you take to make k = 5; if not, why? (Just asking, I realize this may be a load of garbage).
03 Jul 10
1 edit
YES there is. It hasn't been discovered yet.
In time, chess will be SOLVED as checkers has been. Think of it. FINITE number of squares. Finite number of pieces. Finite number of possible MOVES per piece. FINITE solution.
They thought checkers was too complex to SOLVE. The problem was that they never told CHINOOK that. See, it is one of my GOALS in life to at least start the ball rolling in solving chess.
The computational power is not YET invented, but there will come a day, and I HOPE that I get some credit, when chess will be reduced to the popularity of tic tac toe.
See, even though there are 10 to the power of 20 moves or some NONSENSE like that, all the extraneous moves will get weeded out. The PERFECT game will have a SET opening, played no matter what your opponet plays. A set line of middle game play, no matter what your opponent plays, and a set end game that will deliver a win 100% (or a draw 100% time when played against another perfect player ala tic tac toe). Don't believe me, play CHINOOK and analyze how it plays.
04 Jul 10
Originally posted by kes29I dont really consider myself an expert either. I've just spent some time thinking about it.
I’m certainly not an expert on this matter, so there were bound to be flaws in my (wishful, I guess) “logic”, and I’m not going to argue with this. But I think you are really too optimistic (pessimistic?!) about when chess can be solved, as others already noted.
Anyway, suppose there is a device assigned a mission to solve chess. At the start the processor ...[text shortened]... uld you take to make k = 5; if not, why? (Just asking, I realize this may be a load of garbage).
What would I change?
I wouldnt even worry about R. I said with current Technology.
For U I think we we could increase that two different ways. First, and simplest, is just to use more computers. You only used 2 but why not 10 or 100 or 1000? We're assuming unlimited resources right? I think I used 25 when I was first determining this. The second way is to improve it is to shorten the computer's evaluation process.
S is where we could really have the most impact. I've come up with probably about 10 ways to decrease it and we could really make that number a lot smaller. I'll give some examples but I'm not going to give everything away just in case I actually do decide to try and do this someday.
First, is transpositions. The way you've got it set up you've got the computer analyzing both 1.e4,c5 2. c4, e5 and 1.c4, e5 2. e4, c5 at the same time even though they're the exact same position. All we do is tell the computer that when it reaches a position its seen before to stop analyzing one of them. That one little transpsition makes up .00000625% of all the available lines. That may not sound like much but consider thats only one tranposition at one move and only one idea out of about ten. If you look at the position 1.e4,e5, 2.Nf3 black has 22 legal moves. Every one of them can be reached by a different move order. For example 2...Nf6 could also be reached by 1.Nf3,Nf6 2.e4,e5 or 1.e4, Nf6 2.Nf3, e5 or 1.Nf3, e5 2. e4, Nf6. I understand that some lines cant transpose but a rough guess on my part would say maybe the total number could be cut in half just based on 2nd move transpositions alone. Then you have 3rd move, 4th, 5th etc.
Forced mates and draws- If you give the computer the position 1.f4, e5 2.g4 it will analyze 2...a6 and then 2...a5 and then 2...b6 and so on. What you do is tell the computer once it has a forced mate or a forced draw not to analyze any further. There's no reason for it to. Its not like white is going to find some great response after 2...Qh4#.
Endgames- The computer should be able to recognize certain endgames and know whether or not they are won or drawn in much the same way Fine does in BCE. Without that there would be a lot of wasted moves. Imagine a wrong color bishop ending with the computer endlessly moving his bishop from g6 to f5 to e4 and so on. Then imagine that same ending going on in 100,000 games simultaneously. Instead the analysis stops immediately when reaching that position saving a lot of wasted analysis. I would imagine the vast majority of games would be decided by move 40 so nearly all analysis past that point would be unnecessary.
I could go on but I think you get the point.
05 Jul 10
Originally posted by teacher1I agree it must be there and hasn't been discovered yet, at least no one has published anything. I do not agree that the powers in the calculations are nonsense.
YES there is. It hasn't been discovered yet.
In time, chess will be SOLVED as checkers has been.
Don't believe me, play CHINOOK and analyze how it plays.
With chess it is possible, in principle, to play a perfect game or construct a machine to do so as follows: One considers in a given position all possible moves, then all moves for the opponent, etc., to the end of the game (in each variation). The end must occur, by the rules of the games after a finite number of moves (remembering the 50 move drawing rule). Each of these variations ends in win, loss or draw. By working backward from the end one can determine whether there is a forced win, the position is a draw or is lost. It is easy to show, however, even with the high computing speed available in electronic calculators this computation is impractical. --Claude E. Shannon, XXII. Programming a Computer for Playing Chess
Chinook play checkers in the same way a typical chess engine play chess: it use a database for the opening, calculate the middle-game and look up the ending in a database. In the end, Chinook managed to connect its opening book with its endgame table using a 20+ ply search function and thus solved checkers.
As for the question of solving a game like chess, which people suspect will also result in a draw, the amount of data is even more monstrous. The number of positions in checkers is thought to be roughly the square root of the number of positions in chess. That’s somewhere in the order of 1040 to 1050 positions. [Prof. Jonathan] Schaeffer says that even with the two-pronged technique he used in solving checkers, a breakthrough such as quantum computing would be needed to even attempt to solve chess. But he isn’t quick to rule out the possibility. "The one thing I’ve learned in all of this is to never underestimate the advances in technology," he says. --http://spectrum.ieee.org/computing/software/checkers-solved
It was bright ideas rather than technology that solved checkers, the faster computers were just tools. Schaeffer was a computer-chess pioneer before he started work on Chinook and probably turned to checkers because he realised it could be solved in his lifetime given the state of technology.
Moore's Law doesn't dictate exponential growth in all the foreseeable future. The term was coined after an article by Moore in which he describes a trend in transistor-engineering: the number of components on a computer-chip doubles every two years. While the trend has proven very resilient, it will end when atoms need to be split to cram more components onto an integrated circuit, which is soon. "It can't continue forever. The nature of exponentials is that you push them out and eventually disaster happens." --Gordon Moore, father of law.
I'm sure mankind will find new ways to speed up computers after Moore's Law collapse but it would be naive to believe that technology alone will bring us a solution to chess in the near future, some ground-breaking ideas are needed.
- Joined
- 29 Dec 08
- Moves
- 6788
08 Jul 10
Originally posted by Svin1Forget all the stuff about computational power in our lifetimes. Ground breaking ideas are only required if there are unresolved complexities. There being no element of chance other than whether you are white or black, chess is solvable, it is always with best play a draw or win for white,or it is aways a draw or win for black. To think otherwise is to make chess a game of chance, which it is not. It is either solvable, or it is a coin flip. I would prefer that it be solvable, and hope that we who engage it, move together toward its solution.
I agree it must be there and hasn't been discovered yet, at least no one has published anything. I do not agree that the powers in the calculations are nonsense.
[i]With chess it is possible, in principle, to play a perfect game or construct a machine to do so as follows: One considers in a given position all possible moves, then all moves for the opponent, ...[text shortened]... ring us a solution to chess in the near future, some ground-breaking ideas are needed.