Author: Vincent Diepeveen
Date: 07:29:48 05/10/01
Go up one level in this thread
On May 10, 2001 at 08:30:19, Andrzej Nagorko wrote: >[snip] > >>In the same sense, even if chess is finite (which it is), it is still not O(1) >>to solve it, because you will have to look at what happens when the dataset >>grows. In this case, what happens when e.g. the chessboard grows? With any known >>algorithm, the complexity grows as O(a^n). If anyone have an algorithm that is >>in a complexity class lower than this, I would really like to know. >> > > This is probably cause of all confusion here. If you look at "solve chess" >problem as a problem from "given any game tree prove who wins/draws" class, then >this problem has exponential complexity (taking average branching factor and >tree depth as data size measure, for example). Which is correct approach IMO. On >the other hand some people try to define it as "trim chess tree to depth n and >prove who wins/draws in this tree" and take n as data size measure. Then, thanks >to 50 moves draw rule, proof tree will stop growing for n big enough and this >class of problems will be solveable in constant time. > >Andrzej EGTB generation involves having an array of size n and then just need 50 passes to generate win/draw/loss scores. In short you don't need to search at all. You juse maximize the chances in the legal move list for 100 times and you have the result. This is only possible if you have *all* positions in RAM. Ram size is not so big when compared to the number of positions which a processor can search. A very simplistic program (only material) can search easily with a few million nodes a second single cpu. In one year you can search: 5 million nodes a second * 3600 seconds/hour * 24 hours * 365 days That's 5MLN * 3600 * 24 * 365 = 10^9 * 5 * 3.6 * 365 = 6.57 * 10^12 Whereas in the average new PC it's very hard to put more as 2 Gigabytes RAM inside. 2 GB RAM = 2 * 10^9 If we look to the number of instructions a second which a cpu can execute on paper 1.33Ghz ==> 1.33 billion clocks Now on average most cpu's do more as 1 instruction a clock. Then it's obvious that the amount of RAM in a PC is behind the speed of the cpu's and it's unlikely that this is going to change soon! In 20 years of computer development the PCs have gotten a lot faster, but even if the doubling rate goes on at the current speed we are far away from solving chess! When i did some calculations some time ago i had the date: 2066 Best regards, Vincent
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.