Author: David Eppstein
Date: 17:21:31 10/23/97
Go up one level in this thread
On October 23, 1997 at 04:08:09, David Blackman wrote: > The simplest way is to put a "Best known move" at every node in the > transposition table. ... Disadvantage is you often get the > principle variation cut off fairly early by a transposition miss My program doesn't hash all the nodes (think of it as only hashing white moves, its more complicated than that but it would be distracting to explain). So, if I did this I wouldn't even get past one or two moves in the PV. > The triangular array method is to put the current move you are searching > at A[N][N] where N is the number of plies from root. If you decide that > the current position represents the best (or the first, or better than > any others tried so far) move from the previous position, then you copy > A[N][N], A[N][N+1], and so on over to A[N-1][N], A[N-1][N+1] and so on. I do something like this, but with pointers instead of arrays. The trick (if you're using pointers) is to avoid doing lots of memory allocations, they're way too slow. Roughly, each of the nodes I'm searching has two pointers, child and pv. To make a move in the search, I set up the position in the board pointed to by the child pointer, and call alphabeta recursively on that board. Then, if the result is good enough to become the new pv, I just swap the two pointers, and move the pointer from what was child->child to the new child->child position. The result of these manipulations is that my set of nodes can be represented by one linked list (the child pointers) each node of which has another linked list (the pv pointers) hanging off it. The total number of nodes is small (quadratic in the depth) so memory allocation doesn't take much time. I don't think it's faster than the array version, but it's cleaner and I don't think it's slower either. For details, see my source code at http://www.ics.uci.edu/~eppstein/180a/projects/fanorona/source/Board.java -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/
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.