Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Bot Development >> help understanding PV line recording
        
(Message started by: IdahoEv on Apr 14^th, 2008, 12:27pm)

Title: help understanding PV line recording
Post by IdahoEv on Apr 14^th, 2008, 12:27pm

So, I'm working on Zombie again, starting with a thorough analysis of Fairy so I can improve my own code. (I've actually rewritten the entirety of Fairy_light in Java.) I've made huge progress, but there is one bit that still escapes me: I cannot understand exactly how it is that unic went about storing the principal variation line for later retrieval. The process involves two arrays, one of which is two-dimensional, and it's just a bit arcane and undocumented.

I remember reading a chess programming page that discussed storing PV in a multidimensional array a week or two ago, but I can't find that link anymore and google isn't helping me. Lots of pages that discuss PV search, but none that discuss actually storing the line for later retrieval. Can anyone point me to a link that will help me understand how this is done, or is anyone willing to help me look at this bit of unic's code to understand what is going on?

Failing that, I'll work by setting up a simple position and stepping through a search with a debugger, looking at the contents of both arrays after every move is searched, to see if i can make sense of it. But that is likely to be an agonizing process, so if anyone can give me a head start...

Title: Re: help understanding PV line recording
Post by IdahoEv on Apr 14^th, 2008, 12:57pm

here's the code in question, if anyone's curious. It's relevant to note that unic's "move" structure allows moves to be any number of steps from 1 to 4. Instead of saving state after the first half of a push or pull move, Fairy simply generates a "move" that includes both steps. Which means the depth increase of a single iteration of the search function is not always 1, but is current_move.steps, which may be 1 or 2. (the capability of 4-step moves is unused as far as I can tell).

// these are the relevant arrays

Code:

#define MAX_PV_LENGTH 100
static move_t pv[MAX_PV_LENGTH][MAX_PV_LENGTH];
static int pv_length[MAX_PV_LENGTH];
static int hash_hit[MAX_PV_LENGTH];

....

Then inside the search function, he runs this bit of code to check
for cutoffs and save the move in the PV array if there was no cutoff.

Code:

if (lower_bound>=upper_bound) // cutoff, so we want to exit right away
{
cutoff=TRUE;
} else
{ // Maintain partial PV
pv_length[depth]=pv_length[depth+current_move->steps]+current_move->steps;

if (hash_hit[depth+current_move->steps]==-1)
{
hash_hit[depth]=-1;
} else
{
hash_hit[depth]=hash_hit[depth+current_move->steps]+current_move->steps;
}
for (j=depth+current_move->steps; j<depth+pv_length[depth]; j+=pv[depth][j].steps)
{
BOARD_Copy_Move(&pv[depth+current_move->steps][j],&pv[depth][j]);
}
BOARD_Copy_Move(current_move,&pv[depth][depth]);
}

The only time he actually accesses the pv array for read purposes (that I can tell) is in the log output function that prints the current PV. When he does, he only looks at one dimension of the array, a single row of the array seems to contain the principal variation:

Code:

for (i=0; i<pv_length[0]; i+=pv[0][i].steps)
{
// some stuff about outputting hash hits cut

BOARD_Print_Move(&pv[0][i]);
pv_steps[i+pv[0][i].steps]=pv[0][i].steps;
}

However, I tried to use this myself once in an improvement to Zombie and it didn't work. I was trying to get rid of the silliness Fairy does in starting a complete new search for each step of the move. (Fairy uses 40% of the time to search and then commits only to the first step of that PV line, then assuming the first step it starts a whole new search for the second step using 20% of the time, etc..) Instead, I wanted to do a single search from the first step using 100% of the time, extract the first 4 steps from the PV best line, and send that as the move.

However, the moves I extracted from pv[0][n], where n was enough entries to add up to 4 steps, were often very stupid moves that did not match the ones being output by that same code. The obvious difference is that the above output code is only being run when Fairy has completed the full width of one step of the iterative deepening process, and I was frequently accessing it in the middle, when the time manager halted the search. It seems the actual best line is only in pv[0][n] when the current depth has been search fully ... otherwise it may be elsewhere. The difference, of course, is that I don't really understand the structure and function of this array; i don't really know why it's 2-dimensional or exactly what's being stored in it.

So, if anyone can help with my understanding of this it would be greatly appreciated. Thanks!

Title: Re: help understanding PV line recording
Post by jdb on Apr 14^th, 2008, 1:50pm

If the program has a transposition table, just create the PV from it. Sometimes the tail end of the PV may get overwritten. This wont happen with the triangular array method.

Title: Re: help understanding PV line recording
Post by IdahoEv on Apr 14^th, 2008, 2:40pm

I do have a transposition table and will likely use that to recreate PV, down the road. However, for my own edumacation I would at least like to understand this array method. It's called the "triangular array" method? Maybe I can find information about that in google...

Title: Re: help understanding PV line recording
Post by Fritzlein on Apr 14^th, 2008, 5:21pm

on 04/14/08 at 14:40:08, IdahoEv wrote:

I do have a transposition table and will likely use that to recreate PV, down the road.

...unless you search deeply enough that your transposition table can't hold all the positions you have examined, and you start recycling entries in the transposition table, and your PV disappears?

Quote:

However, for my own edumacation I would at least like to understand this array method. It's called the "triangular array" method?

OK, I Googled it for my own edumacation. I could only find scraps of description, so I can't link you to a coherent exposition, but here is what I gather:

So you decide to keep your PV separately from the transposition table using the absolute minimal memory possible, because your transposition table keeps filling up. How much special separate space do you need to be certain of reconstructing the PV when you are done searching the whole tree?

Well, if you are searching to depth D, you need D entries to store the best line you have so far. But you don't know yet that that is the best line overall, and you have to keep all of it while searching other lines that might be better. Let's say you finish searching the whole tree beneath one choice for the second move, and now you are looking at an alternative to the second move in your PV. That can play out as a sequence of D-1 moves, and that sequence might turn out to be your PV, but wait, you can't throw away your other PV until you have finished examination of the alternative move to prove it is really better. So you have to keep both of these potential PV's until you look at all possible third moves in reply to the current best first move plus the current alternative second move. You are thus building a potential PV of D-2 moves (plus the two moves already recorded in your table) while being forced to keep potential PV's of length D and D-1. Etc.

So in the process of deciding what your PV is going to be, you need to keep D + (D-1) + (D-2) + ... + 1 entries to sure you can reconstruct it when the search is over. This is the triangular table. You don't actually need the triangular table to complete your search and decide on the best move; you only need to keep the minimax value of the best move while throwing away the search that proved it. Still it's kind of a nice convenience to be able to output a full PV and not just the value of the move you chose.

Perhaps you are getting a garbage variation out of unic's two-dimensional array because you are "reading down the diagonal" instead of "reading along the edge". I mean, given a square table to work with, you can put the triangle into it in various orientations, so that if you read it the wrong way you get "the alternative alternative alternative line I am examining right now" rather than "the best line I have found so far".

Does that make any sense?

Title: Re: help understanding PV line recording
Post by IdahoEv on Apr 14^th, 2008, 6:13pm

on 04/14/08 at 17:21:07, Fritzlein wrote:

...unless you search deeply enough that your transposition table can't hold all the positions you have examined, and you start recycling entries in the transposition table, and your PV disappears?

Depending on how your trans table is implemented, you might start recycling some entries immediately (low probability, but possible), or you might never start recycling entries.

Unic's hashtable in Fairy has no capability to handle collisions. If a new entry hashes to the same index as an old entry, it simply overwrites the old entry. So in principle the very second step could overwrite the first. (Unic's hashtable will be one of the very first things I replace).

If you use a table that writes collided entries into, say, the next empty entry within N slots of the hashkey, you have pretty good robustness against early recycling, and if N>=4 you can guarantee that you can at least get your first move back out. If you use a chaining hashtable (i.e. writes collided entries into a linked list starting from the hash entry) you will never have recycling problems but you may eventually have memory problems.

Quote:

OK, I Googled it for my own edumacation. I could only find scraps of description, so I can't link you to a coherent exposition, but here is what I gather:
...
Does that make any sense?

Moderate amount of sense, and thank you. It will make more sense as I give it more thought, and after the anti-migraine meds I took this morning wear off. They make me woozy. :-)

It's also been a year since my last experiment extracting the PV from unic's array to avoid the multiple-search problem, so it may have been that i did something wrong or that I am misremembering. I'll need to try again.