Author: blass uri
Date: 13:16:54 05/31/00
Go up one level in this thread
On May 31, 2000 at 16:05:55, Ricardo Gibert wrote: >On May 31, 2000 at 15:46:15, blass uri wrote: > >>On May 31, 2000 at 15:23:28, Robert Hyatt 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: >>> >>>That particular idea isn't open to debate. Alpha/beta is all about minimizing >>>the number of nodes searched. It is easy to prove mathematically that if I >>>get the best move first every time, and you don't, I am going to search fewer >>>total nodes than you are to get the exact same score. >>> >>> >>> >>> >>> >>>> >>>>[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 >>> >>> >>>No... that is the wrong way to think about alpha/beta. In any given position, >>>the 'best' move is the one which produces the best score _in that position_. It >>>doesn't matter a dime what has happened in similar positions, or at shallower >>>search depths. Ie it doesn't matter if a move looks "best" to a human, in the >>>context of alpha/beta, or anything else. >> >> >>If a program rejects Nxb6 or Nc5 because of Ra1+ Re1 Rxe1# it is using less time >>about Nxb6 and Nc5. >> >>If a program is using less time to get to the same depth the order of moves is >>better. >> >>The point is not to search first the best move but to search first the move that >>you need the minimal number of nodes to create a cutoff. >> >> >> >> It is all about the move that produces >>>a move that causes a cutoff. It is _not_ necessary that alpha search the "best" >>>move first, ever. It is only necessary that alpha/beta searches a move good >>>enough to cause a cutoff... >> >>If you search first the move that you need less time to get the cutoff then the >>order of moves is better. >> >> >>> >>>My original statement is still on target: If, at every move where you get a >>>cutoff, you get it on the _first_ move, you are searching the "minimal tree" >>>which is the goal of alpha/beta. >> >>No >>You are not searching the minimal tree because after Nxb6 because you search >>more nodes in the line Rxb6 then in the line Ra1+ with the only exception of a >>very shallow search. >> >>Uri > >Line A Line B >1 Nxb6 1 Nxb6 >2 Rxb6 2 Ra1+ >3 No captures for white 3 Re1 > 4 Rxe1 > 5 No captures for white > >Which is shorter Line A or Line B? You posted the only exception of a very shallow search that I explained. When you search for 1 or 2 plies you can see only Nxb6 Rxb6 in line A but when you search for more plies you will see that line B is shorter. If the depth you need to search is only 1 or 2 plies I can agree that Rxb6 first is a better order of moves. If the depth is bigger than 2 plies than Ra1+ first is better. 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.