Author: Uri Blass
Date: 00:45:41 05/12/01
Go up one level in this thread
On May 12, 2001 at 01:39:57, Angrim wrote: >On May 12, 2001 at 00:56:40, Dann Corbit wrote: > >>On May 12, 2001 at 00:48:17, Angrim wrote: >> >>>On May 11, 2001 at 22:24:21, Robert Hyatt wrote: >>> >>>>On May 11, 2001 at 15:49:19, Angrim wrote: >>>> >>>>>On May 11, 2001 at 03:29:43, Dann Corbit wrote: >>>>> >>>>>>On May 11, 2001 at 01:49:03, Angrim wrote: >>>>><snip> >>>>>>>If your goal is to determine how hard it is to solve chess, then yes. >>>>>>>Rather then go into a lengthy rant here, let me give an example. >>>>>>>The following position has pawns advanced a total of 4 squares, so >>>>>>>subtract 4*50 from the max depth, and your math suggests that there are >>>>>>>38^(5900 -200) total games of chess that can result from this position. >>>>>>>However, the position is trivial. No need for sqrt(38^(5900 -200)) >>>>>>>positions to be searched or stored... >>>>>>> >>>>>>>[D]rnbqkbnr/pppp1ppp/4p3/8/6P1/5P2/PPPPP2P/RNBQKBNR b KQkq g3 0 2 >>>>>> >>>>>>Yet there are many quintillions of quintillions of qintillions of games that can >>>>>>sprout from here. >>>>>> >>>>>My point being that if your goal is to solve this position, then all >>>>>but 1 of those games is totally irrelevant.\\\\\ >>>> >>>> >>>> >>>>Unfortunately they are _not_. Because you have to _prove_ that the best >>>>move is best. And to the best of my knowledge, there is no "oracle" that >>>>will give us perfect move ordering so it is not just likely, it is highly >>>>probable that the winning move won't be searched first. Maybe it will be >>>>searched by the 1/2 way mark at this play, maybe it will be last. But >>>>if it isn't first, you have a HUGE tree to search first... >>>> >>>>That's the way alpha/beta works... not best-first but alpha/beta... >>>> >>>> >>> >>>did you happen to look at the position? >>>You need to look at exactly 1 line to prove that it is the best line. >>>If you are unlucky you might need to look at 30 or so other lines first >>>to find this line, >>>but my point was that the "many quintillions of quintillions of >>>qintillions of games" that can result from this position are irrelevant. >>>The fact that with worst play games thousands of moves long could result >>>from this line is also irrelevant. >>>Yet, much of the discussion of this subject to this point has been >>>about how many legal games there are, and the max depth of such games. >> >>Well, the fool's mate is a pretty rare condition. You must remember that it >>won't be a human looking at the line, but a computer. It is possible for the >>computer to get move ordering wrong. Now, in a simple case like this, even if >>you screw it up completely, you will still find the answer after only one ply. >> > >I picked the fools mate because it is easy for a human to understand the >position. > >>So, the real question seems to be: >>What percentage of random board positions are one move away from checkmate? >>We could expand the question to ask: >>What percentage of random board positions are <n> moves away from checkmate? >>for various values of n. > >Well, that wasn't the question that I was discussing, but it could >be an interesting one in its own right. > >> >>Obviously, once you have killed a branch, you don't need to analyze it any more. >> >>Who knows, maybe there's only a few trillion sensible moves in the whole game >>tree. >> >>I still think finding them (even if that's all there were) is out of reach >>forever, but maybe I'm wrong. > >I think that if you only store values for positions that can not be >solved with 1 second of cpu search, and only for positions where white >has not made any mistakes, then there may be less than a trillion >positions whose values need to be stored. This is feasible with current >tech, however(of course) finding which positions those are and what >their values are is difficult. I expect that it will be possible within >my lifetime, but probably not in the next ten years. Trillion is too optimistic if you use the simple definition of winning evaluation for illogical lines and 10^25 or 10^30 is a better estimate. (8*8*14*13/2*12*11/2*10*9)^2>10^15 and I can easily get these number of positions after games that begin with 1.a3 a6 2.b3 b6 3.c3 c6 4.d3 d6 5.e3 e6 6.f3 f6 7.g3 g6 8.h3 h6 when you can use knight moves in the middle If you want to put your knight at a1 you need to start with white Na3 c3 Nc2 a3 Ra2 Na1. All the positions that I talk about are positions when all the pieces of white are in the first 2 ranks and all the pieces of black are in the first 3 ranks. Both sides can put their pieces in every square that they want in the first 2 ranks except bishops. This is the reason that I started with 8*8 that are the number of places to put the white bishops. 14*13/2 is the number of places to put the white rooks,12*11/2 is for the knights and 10 ,9 is for the king and the queen. It is only for white and I need to calculate ^2 in order to count all the possible cases for both sides. I do not believe that there is a forced mate when both sides are so passive so the positions can be logical from computer's point of view. It may be interesting to find the number of logical positions after games of x plies and to compare it with the number of positions after x plies. The question is how to define logical positions and how to define different positions. 1)Logical positions: Positions when one side missed the shortest forced mate or missed a way to force a draw and noe the opponent can force a draw can be described as illogical without doubt but there are more positions that humans can understand that they are illogical. Example: Humans understand that 1.Nf3 d5 2.Ng1 e5 is not a logical line but it is a problem how to explain it to computers without being sure that you do not prune logical lines. It is possible that there are top programs that know to prune this line at any depth and when I say prune I do not mean to null move pruning because in null move you need to search deeper in every iteration before deciding to prune. It is possible that there are practical good rules that are correct and can help to solve chess when we cannot prove that they are correct. I also doubt if using +10 evaluation after 1 second of search is a good rule to decide about illogical lines. There are positions when programs can see +10 after 1 second of search but the side with the +10 evaluation cannot win. I think that the evaluation of chess programs should be improved before using this rule. 2)Different positions You can argue that the positions after 1.d4 d5 2.Nf3 Nf6 may be a draw by the 50 move rule when the position after 1.Nf3 Nf6 2.d4 d5 is not a draw by the 50 move rule. It seem obvious that in this case it is wrong because it is logical for the sides to move more pawns in the next few plies but in another position it can be really different so the word position should include also the number of plies without conversion. A table that tells you for every position with a number of plies if it is a draw or a win should be enough because repetition is not a problem in games because the tables tell you the shortest way to win if there is a way to win and if the shortest way to win include a repetition it means that the computer did a mistake in a previous move so the computer cannot get the position. 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.