Author: Robert Hyatt
Date: 21:00:38 08/09/04
Go up one level in this thread
On August 09, 2004 at 14:41:57, Stuart Cracraft wrote: >On August 09, 2004 at 10:32:28, Robert Hyatt wrote: > >>On August 09, 2004 at 09:33:07, Stuart Cracraft wrote: >> >>>Here are test results for 2 types of capture-search SEE >>>vs. none. The implementations are: >>> >>>BASICSEE - cut out all capture moves in quiescence search >>>that lose material according to SEE >>> >>>ADVANCEDSEE - search all moves to <2*iteration-depth, >>>search only non-losing captures to <3*iteration-depth >>>aearch only winning captures at 3*iteration-depth and >>>beyond. >>> >>>Unlabeled - do not use see >>> >>>I ran the 300 position test at 1 second per move, >>>5 seconds per move, and 300 seconds per move. >>> >> >>This is the wrong test to run. The point here is are you writing a program to >>solve tactical positions, or to play a complete game? Things that work well in >>one area don't always work well in the other... > >I don't think so -- the test showed a 50% node/time reduction >for deeper plies compared with the non-see. That is a valuable >test result and obviously a superb result for playing games. >My program is just for research though and short searches >are what it has to do well before the next phase can begin. >See within quiescence appears to be for deep searches. And >see for move ordering didn't help improve mvv/lva+historyheuristic+centrality. >It worsened it. Something is wrong. Several years ago Hsu and I had a long discussion about SEE vs MVV/LVA (note that MVV/LVA is something _specifically_ designed for hardware move generators, not software, it was done for the 1980 version of Belle). Several ran tests, including myself. The findings were simple... 1. In normal positions, using SEE rather than MVV/LVA, reduces overall tree size by 10%. Stanback found the same result. Note that this is only SEE vs MVV/LVA, with no "tricks" in the q-search such as avoiding bad captures, etc). 2. When you toss in the "ignore bad captures" which can only be done with SEE, you get _another_ 50% reduction in total tree size. Again verified by a couple of others. MVV/LVA is a lousy way to order captures, because you can't make decisions such as "is this capture bad?" because it is way too simplistic. If you understand the Belle hardware move generator, you'll understand why Ken developed this, but in his words, "I wish I could have done SEE but a finite-state-machine with a fixed clock cycle time can't do SEE, period." If SEE is worsening your move order, you really have something broken, because there is no way possible for SEE to be out-performed by the simplistic MVV/LVA in any but a special-case set of positions. Before pronouncing that SEE doesn't work, you really should try to debug whatever it is that is so broken that it makes SEE look bad. Either your SEE code itself is busted, or your usage of it is busted. This works for _everybody_ that is using it, and most are doing it because it works so well. > >I did check the sorted moves both in quiescence and main search >after see ordered them and saw the bad captures being rightly >put at the end of the move list. There was no speedup. I am >getting cutoffs before either searches through the whole move >list and reaches the bad captures. > >My program doesn't get a lot of full games played with it and I am >far too poor a chess player to evaluate anything but the most >basic of moves. So I don't trust my playing it and use test suites >instead. I should expand to ECM and endgame suites, etc. > >> >>Also there is more left to do in your SEE stuff for q-search. If you reach a >>node where you are a queen down, capturing a free knight (see = +3.0) is >>worthless. > >I think the code understands stand-pat. I don't see why it would do the >above given that it knows and does the basic minimax swapoff already unless >there is something else. Search code might understand it, but your SEE code needs to understand this as well when ordering q-search captures. Again, if you reach node X, generate moves, and find that you can take a free knight which increases the score by +3.0, but you are down a queen already (-9.00 with an alpha value of zero) then there is no reason to search the knight capture. It just wastes time and tree search space. > >What it certainly doesn't know about are hanging pieces and x-ray pieces. >Can't imagine adding those until SEE sinks in. But thanks for the >recommendation. It will come in handy when I upgrade to (much) faster >hardware this or next year. 5x this 1ghz P3 will be easy to achieve and >that would be close to the 5 second test at 1 second and at that level >(5 seconds) see beats non-see. So we shouldn't worry too much about the >total times. See helped and will help further at the 1 second per move >which I use in my research. > >> >> >>>1 second per position - winner is NOSEE >>>// ga -DBASICSEE basicsee.log 1 300 >>>// **** 65% 197/300 265.16 56945056 189817/1/214757 0/0/1682491/0/0/0 >>>// ga -DADVANCEDSEE advsee.log 1 300 >>>// **** 67% 201/300 267.83 62793584 209312/1/234456 0/0/3669891/0/0/0 >>>// ga nosee.log 1 300 >>>// **** 67% 203/300 267.93 63503560 211679/1/237017 0/0/3939450/0/0/0 >>> >>>5 seconds per position - winner is BASIC SEE >>> >>>// ga -DBASICSEE basicsee.log 5 300 >>>// **** 78% 234/300 1247.66 274499200 914997/4/220012 0/0/7530247/0/0/0 >>>// ga -DADVANCEDSEE advsee.log 5 300 >>>// **** 74% 223/300 1254.51 301836992 1006123/4/240602 0/0/17363476/0/0/0 >>>// ga nosee.log 5 300 >>>// **** 75% 226/300 1256.89 301590304 1005301/4/239949 0/0/17803908/0/0/0 >>> >>>30 seconds per move - winner is BASIC SEE >>> >>>// ga -DBASICSEE basicsee.log 30 300 >>>// **** 86% 260/300 7138.30 1588310016 5294367/24/222505 0/0/44017136/0/0/0 >>>// ga -DADVANCEDSEE advsee.log 30 300 >>>// **** 85% 255/300 7204.46 1780278528 5934262/24/247108 0/0/103126448/0/0/0 >>>// ga nosee.log 30 300 >>>// **** 85% 255/300 7205.99 1784190464 5947302/24/247598 0/0/104540648/0/0/0 >>> >>>I plan a run tonight for using SEE to order all captures & as above with >>>BASIC SEE; however preliminary tests at short time controls did more >>>poorly than the current implementation with a simpler move ordering. >>> >>>SEE did not help me as much since my move ordering was already pretty good >>>since I rated all moves in my non-SEE implementation using a score derived >>>from MVV/LVA + History Historic + a Centrality term for captures. >>> >>>Stuart
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.