Author: Robert Hyatt
Date: 06:41:51 05/15/01
Go up one level in this thread
On May 15, 2001 at 01:00:00, Uri Blass wrote: >On May 15, 2001 at 00:30:39, Robert Hyatt wrote: > >>On May 15, 2001 at 00:13:13, Uri Blass wrote: >> >>> >>>If you have enough memory 2^3000 is not relevant because the relevant number is >>>the number of logical chess positions that is less than 10^50 and in this game >>>even smaller than chess. >> >>First, we argue that everything is O(1) (in theory). Now we are on what are >>logical positions and what are not (again in theory). >> >>But in reality, or in practice, we are not able to discern the difference >>between logical and illogical moves. Which is why we have to do a tree >>search in the first place. We will _never_ be able to exclude illogical >>moves from the tree, any more than we will ever be able to search to the >>end of the game and find out whether it is a forced win or a draw. > >We can use a short search to a small fixed depth at every node in order to >define positions that are a win without doubt. >We can also use evaluation to see that positions are win without doubt(if one >side has only a king and the opponent has two connected passed pawns you can >find by evaluation if the opponent has stalemate chances or if the king is close >enough to capture the pawns. That is what the search does _normally_. I don't see how this is new, since interior nodes are _always_ searched deeper. And as we proceed to the next iteration, they are searched even deeper. If you do a plain search from some position, that is far _worse_ than if you did a normal search to depth N+P, rather than searching to depth N, then doing a shallow search to depth P from that point. That breaks alpha/beta > >If you find by evaluation that the king is not close enough to capture the pawns >and that there are no stalemate chances then it is a win without doubt. Yes... but for every position you categorize as "won without doubt" you are going to find a zillion you can't correctly classify. Otherwise my eval would be perfect in endgames by now with all the cases I handle. > >It is only one example and there are a lot of positions that can be evaluated as >a win without doubt. > >You can define rules that it is illegal to go to these positions so you get less >positions. >> >> >> >>> >>>If you try to construct the 32 piece tablebases in the game when it is illegal >>>to play moves that give the opponent a simple win then it is enough. >> >> >>How would you determine that? IE how can you determine a position is a "simple >>win" without searching to see that result? > >I explained it see above. You "explained" it. But the explanation was "unimplementable". Which leaves us at square zero again. >> >> >> >>> >>>You can also ignore the 50 move rule for the case that you prove that chess is a >>>draw. >>> >>>In this case proving that there is no win in 6500 without the 50 move rule is >>>enough to prove that there is no mate in chess with the 50 move rule because >>>every game of 13000 plies is a draw by the 50 move rule. >>> >>>In this case the number of iterations is not a problem. >>>I believe that chess even without the 50 move rule is a draw. >>> >>>My idea to solve chess in 2050 or 2100 is the following idea: >>> >>>1)Generate all the leagl positions in the game when the sides have no right to >>>let the opponent a win without doubt(you should construct an evaluation to >>>define a win without doubt and it should be something that you can compute in a >>>relatively short time like 0.01 seconds on today's hardware >>> >>>In order to do it you generate all the possible positions in games of x plies >>>when x<13000(the number can be even slightly smaller than 13000 but I am lazy to >>>calculate or to find it) >>> >>>I do not know if the number of these positions is smaller or bigger than 10^25 >>>It may be 10^30 and may be 10^20. >> >>For a full game, W averages 38. Which means your W^13000 is simply beyond >>imagination. Even storing one gigabyte per atom in universe matter. > >I ignore the history in my definition of position so it is not W^13000 and it is >clearly less than 10^50 and it may be 10^30 or even 10^20. Let's ignore enpassant, make captures forced, and we make the game even smaller. YOu can't ignore history unless you use the EGTB construction approach. If you do that, you can't do alpha/beta. So either way, the tree becomes huge. > >> >> >> >>> >>>It means that if you are optimistic you may get 10^20 possible numbers when >>>everyone of them is of 192 bits or even less bits if there is a simple way to >>>represent chess positions by numbers. >> >>I don't see any possible way to get 10^20 that would mean that there is a >>forced win inside 15 plies or so. I don't believe it. > >I am talking about the number of positions when a position only includes the >pieces on the board,right to castle,en passant options,side to move. > >If you search 15 plies you get less positions and you do not need to search the >same position twice(you do not search 1.e4 e5 2.d4, 1.d4 e5 2.e4 and 1.e3 e6 >2.e4 e5 3.d4 but only one of these games). Then you are not doing alpha/beta because all positions are not the same if you have a "depth" requirement for each search. And if you don't do alpha/beta, you once again have a large number of positions to deal with. Assuming there are 2^168 chess positions or so, based on pure combinatorics, I think you will find that number intractable for the next 20 billion years. That is a horrific number. Once again back to a number larger than the atoms in the known universe by a really _huge_ margin. Which means "it will _never_ be searched". > >Uri
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.