Author: Dave Gomboc
Date: 10:35:57 03/07/99
Go up one level in this thread
On March 07, 1999 at 05:39:53, David Blackman wrote: >On March 07, 1999 at 04:57:52, Dave Gomboc wrote: > >>My (not chess) playing software searches fine.. or so it seems, when I have an >>"extend on capture" setting of 0 ply, 1/3 ply, 1/2 ply, etc. But if I set it >> to 1 ply, I occasionally hit a position where boom! there goes the stack. >> >>I am wondering if this is endemic to extending by a full ply or not. >> >>Dave Gomboc > >In chess this shouldn't happen. I have actually tried this. It's not a winner, >but at least it works, and the stack doesn't blow out too badly. > >What game is it for? In chess you have a max of 30 or 31 captures in any given >line, so it's self limiting. I suppose some games might have much more material >to get rid of? > >Actually my chess program tests how deep it is in the tree. If it's more than >about 70 plies it prints a message to the log file, then just does a static eval >and returns. This might be useful for debugging this sort of problem. It's actually a variant of Awari (the variation is that a player is not obligated to provide their opponent with a move). If that means nothing :-), it's one of a class of Mancala games from Africa, where there's two rows of pits, and a bunch of stones in each. As you play, the stones move around, and some are captured... it's like chess in that the game converges from high material count to low/no material count. I figured I'd try to get some numbers, and see if that would shed some light on the issue. (no extension on a capture) Iter Score Internal Leaf Total 6 0 346 371 717 7 0 1061 2033 3094 8 0 15258 37771 53029 9 0 7310 14950 22260 [this search is instant] (extend by 3/12 ply on a capture) 6 0 552 671 1223 7 0 1417 2672 4089 8 0 6425 11070 17495 9 0 26458 51637 78095 [pretty fast] (extend by 6/12 ply on a capture) 6 0 734 1398 2132 7 0 2651 5571 8222 8 0 19567 41195 60762 9 0 192781 432375 625246 (extend by 7/12 ply on a capture) 6 0 1834 2708 4542 7 0 17812 35480 53292 8 0 692247 1548823 2241070 9 0 6416719 9848963 16265682 [this search took maybe 30 seconds] (extend by 8/12 ply on a capture) 6 0 3176 5030 8206 7 0 42431 64892 107323 8 0 13808974 18180405 31989379 [took a long time!] 9 [didn't wait for this one :-] A reminder to us all re: trees grow exponentially? :-) The node count for 8/12, 8 ply is much larger than that of 7/12, 9 ply. Does that seem normal, or buggy, to you? It seems kind of fishy to me... :-| I guess my main concern is I don't know whether to shrug off the deep, deep recursion crashes as a simple consequence of extending too much. If someone told me "yes, the behavior you see is normal, it's expected" that I'd be okay with it. Otherwise I am thinking that I have a bug in my search (perhaps a freaky interaction with TT bounds) and I should go and find it. Dave Gomboc
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.