/*                         L A R O L L S . C
 *
 *  Copyright (c) 1998-2000 by David Montgomery.  All rights reserved.
 *
 *
 *  LOOKAHEAD ROLL LIST POLICY
 *  --------------------------
 *  The lookahead roll list policy determines the fraction of the
 *  rolls that are used at each node in the evaluation tree.  The
 *  fraction may vary by depth in a lookahead branch.  For purposes
 *  of the roll list policy, any node that does not back its evaluations
 *  up to its parent node (e.g., candidate pruning steps) is considered
 *  to be at depth 0, the root node of that evaluation.
 *
 *  The roll list policy is stored as an array of MAX_LA_PLY ints.
 *  Each int is a macro from larolls.h indicating what fraction of
 *  the rolls to use as you move deeper into a lookahead evaluation.
 *  The policy always averages over all 21 rolls for depth 0 -- it
 *  only makes sense to use sampling deeper in the search.
 *
 *  Changes in the roll list policy are managed with a stack.  The
 *  depth appropriate to a node is pushed onto the stack by its
 *  parent in laeval.c.  Candidate evaluation steps alway have a 0
 *  pushed, since they are always the root nodes for their lookahead
 *  evaluation.  For the final scoring step of each lookahead evaluation,
 *  the parent's depth + 1 is pushed.
 *
 *  For nodes that only use a portion of the rolls, we have to take
 *  care to properly utilize and distribute the fractional lists.
 *  A counter is maintained for each depth.  These counters are used
 *  to iterate among the different fractional lists, by taking the
 *  counters modulus the number of lists for that particular fractional
 *  policy.  Counters for nodes that might use a fractional list
 *  are incremented by their parents in laeval.c, assuring that each
 *  roll list occurs with approximately the correct frequency.  To
 *  ensure that evaluations are consistent, we initialize these
 *  counters at the overall root node of each lookahead evaluation.
 *  
 */

/*--------------------------------------------------------------
 *
 *                          INTERNAL HEADER
 *
 *--------------------------------------------------------------*/

/* --- conditional compilation --- */
#define DEBUGLEVEL  DEBUGDEFAULT

/* --- headers --- */
#include "debug.h"
#include "bgemover.h"
#include "declare.h"
#include "larolls.h"
#include "laeval.h"
#include "shutdown.h"

/* --- type definitions --- */
typedef struct {
    int numRolls;
    int *d1;
    int *d2;
    int *wt;
} laRollList_t;

typedef struct {
    unsigned        numLists;
    laRollList_t    *list;
} laRollGroup_t;

/* --- prototypes --- */
static laRollList_t *  getRollList( int group, unsigned listIndex );
static boolean         matchedFirsts( eMoveList_t *e1, eMoveList_t *e2 );
static void            getMoveLists( laRollList_t *larl, board_t startBoard,
                            eMoveList_t *eml[], int wt[], int *numLists, int rollIndexer[21] );
    

/*--------------------------------------------------------------
 *
 *                              IMPLEMENTATION
 *
 *--------------------------------------------------------------*/

/* --- globals --- */
static boolean      initialized;

/* --- roll list data --- */
static int all_d1[] = { 6, 5, 4, 3, 2, 1, 6, 6, 6, 6, 6, 5, 5, 5, 5, 4, 4, 4, 3, 3, 2 };
static int all_d2[] = { 6, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 4, 3, 2, 1, 3, 2, 1, 2, 1, 1 };
static int all_wt[] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 };

static int half1_d1[] = { 6, 2, 6, 6, 5, 5, 5, 4, 4, 2 };
static int half1_d2[] = { 6, 2, 4, 3, 3, 2, 1, 3, 1, 1 };
static int half1_wt[] = { 1, 1, 2, 2, 2, 2, 2, 2, 2, 2 };

static int half2_d1[] = { 5, 4, 3, 1, 6, 6, 6, 5, 4, 3, 3 };
static int half2_d2[] = { 5, 4, 3, 1, 5, 2, 1, 4, 2, 2, 1 };
static int half2_wt[] = { 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2 };

static int third1_d1[] = { 2, 1, 6, 6, 5, 4, 4 };
static int third1_d2[] = { 2, 1, 5, 3, 1, 3, 2 };
static int third1_wt[] = { 1, 1, 2, 2, 2, 2, 2 };

static int third2_d1[] = { 6, 3, 6, 5, 5, 4, 2 };
static int third2_d2[] = { 6, 3, 4, 3, 2, 1, 1 };
static int third2_wt[] = { 1, 1, 2, 2, 2, 2, 2 };

static int third3_d1[] = { 5, 4, 6, 6, 5, 3, 3 };
static int third3_d2[] = { 5, 4, 2, 1, 4, 2, 1 };
static int third3_wt[] = { 1, 1, 2, 2, 2, 2, 2 };

static int quarter1_d1[] = { 6, 3, 1, 6, 5, 4 };
static int quarter1_d2[] = { 6, 3, 1, 1, 3, 2 };
static int quarter1_wt[] = { 1, 1, 1, 2, 2, 2 };

static int quarter2_d1[] = { 5, 6, 6, 5, 4 };
static int quarter2_d2[] = { 5, 3, 2, 2, 1 };
static int quarter2_wt[] = { 1, 2, 2, 2, 2 };

static int quarter3_d1[] = { 4, 6, 5, 3, 3 };
static int quarter3_d2[] = { 4, 4, 1, 2, 1 };
static int quarter3_wt[] = { 1, 2, 2, 2, 2 };

static int quarter4_d1[] = { 2, 6, 5, 4, 2 };
static int quarter4_d2[] = { 2, 5, 4, 3, 1 };
static int quarter4_wt[] = { 1, 2, 2, 2, 2 };

/* --- roll lists --- */
static laRollList_t    twentyOneRolls =
                            { 21, all_d1, all_d2, all_wt };
static laRollList_t    halfLists[2] = {
                            { 10, half1_d1, half1_d2, half1_wt },
                            { 11, half2_d1, half2_d2, half2_wt } };
static laRollList_t    thirdLists[3] = {
                            {  7, third1_d1, third1_d2, third1_wt },
                            {  7, third2_d1, third2_d2, third2_wt },
                            {  7, third3_d1, third3_d2, third3_wt } };
static laRollList_t    quarterLists[4] = {
                            {  6, quarter1_d1, quarter1_d2, quarter1_wt },                                      
                            {  5, quarter2_d1, quarter2_d2, quarter2_wt },
                            {  5, quarter3_d1, quarter3_d2, quarter3_wt },
                            {  5, quarter4_d1, quarter4_d2, quarter4_wt } };

/* --- roll groups --- */
static laRollGroup_t   halfRolls    = { 2, halfLists    };
static laRollGroup_t   thirdRolls   = { 3, thirdLists   };
static laRollGroup_t   quarterRolls = { 4, quarterLists };

/* --- roll group policy --- */
static int         policyByDepth[ MAX_LA_PLY ];
static unsigned    counterByDepth[ MAX_LA_PLY ];
static int         depthStack[ MAX_LA_PLY ];
static int         depthStackTop;

/*--------------------------------*/

static laRollList_t *
getRollList( int group, unsigned listIndex ) {

    laRollGroup_t *g;

    if ( group == LARL_HALF_ROLLS )  
        g = &halfRolls;
    else if ( group == LARL_THIRD_ROLLS )  
        g = &thirdRolls;
    else { 
        assume( group == LARL_QUARTER_ROLLS );  
        g = &quarterRolls; 
    }

    listIndex = listIndex % g->numLists;

    return &(g->list[ listIndex ]);
}

/*--------------------------------*/

static boolean
matchedFirsts( eMoveList_t *e1, eMoveList_t *e2 ) {

    eBoard_t *eb1, *eb2;

    eb1 = eml_first( e1 );
    eb2 = eml_first( e2 );

    return boardsAreEqual( eb1->b, eb2->b );
}

/*--------------------------------*/

static void
getMoveLists(
    laRollList_t    *larl,
    board_t         startBoard,
    eMoveList_t     *eml[],
    int             wt[],
    int             *numLists,
    int             rollIndexer[21] ) {
    
    boolean duplicate;
    int     cantMoveIndex;
    int     forcedSingleList[ MAX_LA_ROLL_LISTS ] = {0};
    int     forcedSingles;
    int     forcedBearoffList[ MAX_LA_ROLL_LISTS ] = {0};
    int     forcedBearoffs;
    int     d1, d2, r;
    int     i, j, n;

    #if DEBUG(HIGH)
        for ( i=0; i < 21; i++ ) 
            rollIndexer[i] = -1;
    #endif

    forcedSingles = 0;
    forcedBearoffs = 0;
    cantMoveIndex  = -1;
    
    n = 0;
    for ( i=0; i<larl->numRolls; i++ ) {
        
        duplicate = FALSE;
        
        d1 = larl->d1[i];
        d2 = larl->d2[i];
        r  = twoDicetoOneIndex[ d1 ][ d2 ];
        eml[n] = eml_makeList( startBoard, d1, d2 );

        if ( eml[n]->cantMove ) {
            if ( cantMoveIndex == -1 ) cantMoveIndex = n;
            else {
                duplicate = TRUE;
                wt[ cantMoveIndex ] += larl->wt[i];
                rollIndexer[r] = cantMoveIndex;
            }
        }
        else if ( eml[n]->forcedSingle ) {
            for ( j=0; j < forcedSingles; j++ ) {
                if ( matchedFirsts( eml[n], eml[ forcedSingleList[j] ] ) ) {
                    duplicate = TRUE;
                    wt[ forcedSingleList[j] ] += larl->wt[i];
                    rollIndexer[r] = forcedSingleList[j];
                    break;
                }
            }
            if ( !duplicate )  {
                forcedSingleList[ forcedSingles ] = n;
                ++forcedSingles;
            }
        }
        else if ( eml[n]->forcedBearoff ) {
            for ( j=0; j < forcedBearoffs; j++ ) {
                if ( matchedFirsts( eml[n], eml[ forcedBearoffList[j] ] ) ) {
                    duplicate = TRUE;
                    wt[ forcedBearoffList[j] ] += larl->wt[i];
                    rollIndexer[r] = forcedBearoffList[j];
                    break;
                }
            }
            if ( !duplicate )  {
                forcedBearoffList[ forcedBearoffs ] = n;
                ++forcedBearoffs;
            }
        }

        if ( duplicate ) eml_freeList( eml[n] );
        else {
            wt[n] = larl->wt[i];
            rollIndexer[r] = n;
            ++n;
        }
    }                   

    *numLists = n;
}
    
/*--------------------------------------------------------------
 *
 *                              INTERFACE
 *
 *--------------------------------------------------------------*/

// true globals
const int twoDicetoOneIndex[7][7] =
            { {  -1, -1, -1, -1, -1, -1, -1 },
              {  -1,  5, 20, 19, 17, 14, 10 },
              {  -1, 20,  4, 18, 16, 13,  9 },
              {  -1, 19, 18,  3, 15, 12,  8 },
              {  -1, 17, 16, 15,  2, 11,  7 },
              {  -1, 14, 13, 12, 11,  1,  6 },
              {  -1, 10,  9,  8,  7,  6,  0 } };

void
larl_initializeModule( void ) {
/*
 *  Currently not supporting 2-roll and 1-roll lists. 2-roll
 *  would certainly get set up here.
 */
    int pbd[ MAX_LA_PLY ];
    int i;
    
    assume( initialized == FALSE );

    /* --- initialize depth stack --- */
    depthStackTop = -1;
    larl_pushDepth( 0 );

    /* --- set default roll list policy --- */
    pbd[0] = LARL_ALL_ROLLS;
    pbd[1] = LARL_ALL_ROLLS;
    for ( i=2; i<MAX_LA_PLY; i++ ) 
        pbd[i] = LARL_QUARTER_ROLLS;
    larl_setRollListPolicy( pbd );

    /* --- complete initialization --- */
    sd_registerDecommissioner( larl_decommissionModule );
    initialized = TRUE;
        
}

/*--------------------------------*/

void
larl_decommissionModule( void ) {

    assume( initialized == TRUE );

    larl_popDepth();
    
    sd_removeDecommissioner( larl_decommissionModule );
    initialized = FALSE;
}

/*--------------------------------*/

boolean
larl_isInitialized( void ) {

    assume( initialized == TRUE || initialized == FALSE );
    return initialized;
}

/*--------------------------------*/

void
larl_setRollListPolicy( int pbd[] ) {

    int i;

    for ( i=0; i<MAX_LA_PLY; i++ ) 
        policyByDepth[i] = pbd[i];
}

/*--------------------------------*/

void
larl_restart( void ) {
/*
 *  This is called from the root node of every lookahead evaluation
 *  to ensure that evaluations are constant from one occasion to the
 *  next.  Always starting with counters at zero means we will always
 *  cycle through the lists in the same way.
 */

    int i;

    for ( i=0; i<MAX_LA_PLY; i++ )
        counterByDepth[i] = 0;
}

/*--------------------------------*/

void
larl_getMoveLists(
    board_t     startBoard,
    eMoveList_t *eml[],
    int         wt[],
    int         *numLists,
    int         rollIndexer[21] ) {

    int             group;
    unsigned        list;
    int             depth;
    laRollList_t    *larl;

    depth = larl_depthStackTop();
    group = policyByDepth[ depth ];
    list  = counterByDepth[ depth ];
    
    switch ( group ) {

    case LARL_ALL_ROLLS:
        getMoveLists( &twentyOneRolls, startBoard, eml, wt, numLists, rollIndexer );
        break;

    case LARL_HALF_ROLLS:
    case LARL_THIRD_ROLLS:
    case LARL_QUARTER_ROLLS:
        larl = getRollList( group, list );
        getMoveLists( larl, startBoard, eml, wt, numLists, rollIndexer );
        break;

    default:
        sd_fatalError("Unsupported group type parameter in larl_getMoveLists (%d)\n", group );
        break;

    }
}

/*--------------------------------*/

void
larl_pushDepth( int depth ) {

    ++depthStackTop;
    depthStack[ depthStackTop ] = depth;
}

/*--------------------------------*/

void
larl_popDepth( void ) {

    --depthStackTop;
}

/*--------------------------------*/

int
larl_depthStackTop( void ) {

    return depthStack[ depthStackTop ];
}

/*--------------------------------*/

void
larl_rotateRollList( void ) {

    ++counterByDepth[ larl_depthStackTop() ];
}