When MF evaluates a position it does local tactical search to see if blocks of stones can be captured. It does this for every block with 3 or fewer liberties, and for points at the diagonals of eyes, and to see if connections are solid by trying to cut and doing a search to see if the cutting stone can be captured. It often does more than one local search for the same block, varying the side to move first and the ko status.
This local search is why the evaluation function is so slow. MF evaluates about 40 to 200 full board positions per second during the global alpha-beta search. The local search examines over 100K positions per second, so a 30 second search examines 3 or 4 million positions in local search. Here is search output for a typical early endgame position (move 175). This is on one processor of a 2.3 GHz Core Duo. First it spends 0.7 seconds in the life/death search, evaluating 101 positions. Then it does 5 iterations of alpha-beta search, on 20 candidate moves, using about 34 seconds. It does a total of 5548 full board evaluations (164 per second). The local tactical search examines 3845717 positions, 24% for eyes, 10% for connections, 19% for blocks. Search 24-48 seconds (10000 max evals), 0.7 secs in life reading level 5, life reading 101 life() New best 1870 (strat 1090)m9 m9 New best 1943 (strat 988)j9 j9 Iteration 1 complete 20 moves in 1.11 secs. Total evals 154, search life() 53, Final value is 1943 for j9 : j9 New best 1818 (strat 988)j9 j9 j8 o11 New best 1885 (strat 1125)m9 m9 l6 Iteration 2 complete 20 moves in 2.57 secs. Total evals 412, search life() 311, Final value is 1885 for m9 : m9 l6 New best 1820 (strat 1125)m9 m9 l6 e13 f13 Iteration 3 complete 20 moves in 5.10 secs. Total evals 879, search life() 778, Final value is 1820 for m9 : m9 l6 e13 f13 New best 1820 (strat 1125)m9 m9 l6 e13 f13 Iteration 4 complete 20 moves in 11.14 secs. Total evals 1932, search life() 1831, Final value is 1820 for m9 : m9 l6 e13 f13 New best 1870 (strat 1125)m9 m9 l6 e13 f13 k6 Iteration 5 complete 20 moves in 33.74 secs. Total evals 5548, search life() 5447, Final value is 1870 for m9 : m9 l6 e13 f13 k6 Pass val -5.6, best val 37.4 33.7 secs. life() 5548 (164/s), searchevals 1613, Nodes 2056 ( 61/s), full gen 319, Q gen 1483, Moves 3246( 96/s), tree nodes 207/207, list 10211/10211, tac nodes 3845717 (113971/s), evalopj 107868 ( 3%), life 3171808 ( 82%) [ fixgralive 3508037 ( 91%) miai 817026 ( 21%) tvpot 603326 ( 16%), group 742975 ( 19%), conn 376456 ( 10%), eye 922580 ( 24%) ] David > -----Original Message----- > From: Peter Christopher [mailto:[EMAIL PROTECTED] > Sent: Saturday, December 15, 2007 3:18 PM > To: [EMAIL PROTECTED] > Subject: several million nodes > > Hi David, > Thanks for you generosity in sharing your experience and perspective > on the computer-go list. I noticed your statement that MFG does > several million nodes of search. I assume this is per move. I see > what you mean that this would be uncachable. It seems really hard for > me to believe, is that really correct? Maybe I don't understand what > is meant by a node - is it the creation of a representation of a > global or local situation with some form of valuation metric applied? > Do several million nodes really get some valuation metric applied to > all of them? > > Sorry to send off-list; my email address almost always gets bounced > from the list for some reason (but I can read the response there). > Peter _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
