Author: blass uri
Date: 14:21:05 05/31/00
Go up one level in this thread
On May 31, 2000 at 17:10:41, blass uri wrote: >On May 31, 2000 at 17:04:34, blass uri wrote: > >>On May 31, 2000 at 16:24:36, Ricardo Gibert wrote: >> >>>On May 31, 2000 at 16:12:23, blass uri wrote: >>> >>>>On May 31, 2000 at 15:25:12, Ricardo Gibert wrote: >>>> >>>>>On May 31, 2000 at 13:22:34, blass uri wrote: >>>>> >>>>>>On May 30, 2000 at 18:11:51, Robert Hyatt wrote: >>>>>> >>>>>>>On May 30, 2000 at 15:24:36, Ed Schröder wrote: >>>>>>> >>>>>>>>On May 30, 2000 at 00:28:47, Robert Hyatt wrote: >>>>>>>> >>>>>>>>>On May 28, 2000 at 16:37:32, Gian-Carlo Pascutto wrote: >>>>>>>>> >>>>>>>>>>On May 28, 2000 at 10:02:05, Georg v. Zimmermann wrote: >>>>>>>>>> >>>>>>>>>>>From my tests it shows that it sticks with the hash-move about 50% of the time. >>>>>>>>>>>Should this number be higher ? >>>>>>>>>> >>>>>>>>>>Hmm...if this number is also effectively your 'move ordering percentage', >>>>>>>>>>which I assume it is, it is quite low. I'd expect it to be at least about 75%. >>>>>>>>>> >>>>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>>The classic definition of a "strongly-ordered tree" is this: If, for every >>>>>>>>>node where you fail high, you fail high on the first move at least 90% of the >>>>>>>>>time, then your move ordering is good." If you are much below 90% and already >>>>>>>>>have a serious problem that is not hard to fix. The traditional ordering ideas >>>>>>>>>holds Crafty at 92% and better for most of the game. >>>>>>>> >>>>>>>>I can't understand the 92%. A perfect mini-max search requires many many >>>>>>>>nodes an alpha-beta cutoff will not work and you are forced to search all >>>>>>>>the nodes of the ply in question. And this number is certainly much higher >>>>>>>>than 8%. >>>>>>> >>>>>>>You have to re-read the definition again, _very carefully_ to avoid the semantic >>>>>>>trap you just fell into. >>>>>>> >>>>>>>For every position where you fail high, if you fail high on the first move you >>>>>>>try, you increment a counter "right++". You always increment a counter "fh++". >>>>>>>When you finish the search, you compute percent=right/fh. That number needs to >>>>>>>be over 90% to consider your tree strongly ordered. Notice that this 92% number >>>>>>>(in crafty) simply says this: >>>>>>> >>>>>>> "if we look at _all_ the positions in the tree where the search fails high, >>>>>>> then 92% of those fail highs happen on the first move searched in that >>>>>>> position, which is known as 'optimal move ordering'. >>>>>> >>>>>> >>>>>>I do not agree that failing high on the first move is optimal move ordering. >>>>>> >>>>>>Here is an example: >>>>>> >>>>>>[D]8/6k1/rp3ppp/8/N7/8/4RPPP/6K1 w - - 0 1 >>>>>> >>>>>>My understanding of optimal move ordering is that after the moves Nxb6 or Nc5 >>>>>>the first move to search will be Ra1+(at least in cases that you are going to >>>>>>search more than few plies after these moves because Ra1+ Re1 Rxe1# is the >>>>>>faster way to prove that Nxb6 or Nc5 is wrong) >>>>>> >>>>>>If you start with taking the knight than your first move may fail high but you >>>>>>waste more time to prove that Nxb6 or Nc5 are wrong. >>>>>> >>>>>>Uri >>>>> >>>>>I don't understand. It makes no difference in your example whether the program >>>>>rejects Nxb6 due to Rxb6 or Ra1. In fact, since Ra1 is not mate, the program >>>>>must still look an additional 2 ply to determine that Ra1+ is really better. >>>> >>>>If the program searches 10 plies after Rxb6 it needs more time than in the case >>>>that it search 10 plies after Ra1. >>>> >>>>The only case when searching Ra1 first is not better is when the program >>>>does a very shallow search and it is logical to have a different order of moves >>>>in the cases that the program needs to do a very shallow search. >>>> >>>>>Whether it is better is irrelevant. The issue is "optimal move ordering" and not >>>>>what the optimal move is. That's something different. It is possible that a >>>>>program could search a larger tree by always examining the best move first, >>>>>since it is possible for "good enough" moves to get a quicker cut-off. >>>> >>>>I agree and I do not say that the best order of moves is to have the best move >>>>first but to have the move that generates a cut off in the smallest number of >>>>nodes. >>>> >>>> >>>> Here >>>>>black is led into finding the best move Ra2 for white as quickly by Rxb6 in >>>>>reply to Nxb6 as anything else. Your example is a good example of why it is good >>>>>idea to examine captures first. They are the most succinct way of generating a >>>>>fail high. Yes? >>>> >>>>In the example that I posted it is a better idea to search Ra1+ first. >>>> >>>>It may be a good idea to search for short mates not in every node but only in >>>>some nodes close to the root in order to have a better order of moves. >>> >>>You seem to place too much "weight" on finding mates outside of the PV when it >>>is actually irrelevant. >> >>It is relevant to waste less time. >>I can see that if I give programs some minutes to calculate the initial position >>they may waste some seconds about moves like Nxb6 because they calculate Nxb6 >>Rxb6 and not Nxb6 Ra1+. >> >>If they had better move ordering they would not do it. >> >>Maybe it is a be better idea to search for mate in at most 2 only in the first x >>plies when you search to depth 10+x. >> >> >>The best move order is not about searching the best move first. >>Here is another example: >> >>[D]1k6/2q5/4p1p1/5pPp/5P1P/8/6Q1/K7 b - - 0 1 >> >>1...Qc2 2.Qxc2 is not the best move order if you search more than 2 plies. >>The best move order here is 1...Qc2 2.Qb7+ with the forced Kxb7 with stalemate. >> >>It is practically impossible to have a perfect move ordering but my idea about >>the best move ordering is that you cannot change the order of move and be faster >>in getting the same depth. > >I mean that a better move ordering is if you need less nodes to get the same >depth. > >It is possible to get a better move ordering without being faster if you waste >more time about calculating the order of moves so you waste more time about >getting the same depth inspite of the fact that you search less nodes. > >In this case better move ordering is not a good idea. > >Uri If people want to get an estimate how much better they can improve the move ordering then I suggest to develop 2 programs. 1)Program A searches with the same extensions of the original program when only the order of moves may be different because it gets it from program B 2)program B searches for the best move ordering and gives program A only the knowledge about the order of moves to search. When you count nodes count only nodes of program A to get a fixed depth and compare it with the number of nodes of the original program to get the same depth. Uri
This page took 0.01 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.