endgame.cpp

c+++ game uploading now

/**
 @file
 A fast endgame searcher.
*/

#include "Endgame.h"
//no need to compile this if we aren't going to build with it anyway.
#ifdef _ENDGAME_TEST_

#include <cassert>
#include <cstdio>

using namespace Othello;

uchar EndGame::board[91];

EndGame::EmList EndGame::EmHead;
EndGame::EmList EndGame::Ems[64];

uint EndGame::HoleId[91];
uint EndGame::RegionParity;
 
const schar EndGame::dirinc[]={1, -1, 8, -8, 9, -9, 10, -10, 0};
    
const uchar EndGame::dirmask[91] = 
{
    0,0,0,0,0,0,0,0,0,
    0,81,81,87,87,87,87,22,22,
    0,81,81,87,87,87,87,22,22,
    0,121,121,255,255,255,255,182,182,
    0,121,121,255,255,255,255,182,182,
    0,121,121,255,255,255,255,182,182,
    0,121,121,255,255,255,255,182,182,
    0,41,41,171,171,171,171,162,162,
    0,41,41,171,171,171,171,162,162,
    0,0,0,0,0,0,0,0,0,0
};

const int EndGame::worst2best[64] =
{
    20 , 25 , 65 , 70 ,
    11 , 16 , 19 , 26 , 64 , 71 , 74 , 79 ,
    21 , 24 , 29 , 34 , 56 , 61 , 66 , 69 ,
    22 , 23 , 38 , 43 , 47 , 52 , 67 , 68 ,
    31 , 32 , 39 , 42 , 48 , 51 , 58 , 59 ,
    13 , 14 , 37 , 44 , 46 , 53 , 76 , 77 ,
    30 , 33 , 57 , 60 ,
    12 , 15 , 28 , 35 , 55 , 62 , 75 , 78 ,
    10 , 17 , 73 , 80 , 
    40 , 41 , 49 , 50
};

uchar* EndGame::GlobalFlipStack[2048];
uchar **EndGame::FlipStack= &(GlobalFlipStack[0]);

inline void EndGame::DrctnlFlips(uchar *sq, int inc, int color, int oppcol)
{
    uchar *pt = sq + inc;
    if(*pt == oppcol)
    {
        pt += inc;
        if(*pt == oppcol)
        {
            pt += inc;
            if(*pt == oppcol)
            {
                pt += inc;
                if(*pt == oppcol)
                {
                    pt += inc;
                    if(*pt == oppcol)
                    {
                        pt += inc;
                        if(*pt == oppcol)
                            pt += inc;
                    }
                }
            }
        }
        if(*pt == color)
        {
            pt -= inc;
            do
            {
                *pt = color;
                *(FlipStack++) = pt;
                pt -= inc;
            }while( pt != sq);
        }
    }
}


int EndGame::DoFlips( uchar *board, int sqnum, int color, int oppcol )
{
    int j=dirmask[sqnum];
    uchar **OldFlipStack = FlipStack;
    uchar *sq;
    sq = sqnum + board;
    if ( j & 128 )
        DrctnlFlips( sq, dirinc[7], color, oppcol );
    if ( j & 64 )
        DrctnlFlips( sq, dirinc[6], color, oppcol );
    if ( j & 32 )
        DrctnlFlips( sq, dirinc[5], color, oppcol );
    if ( j & 16 )
        DrctnlFlips( sq, dirinc[4], color, oppcol );
    if ( j & 8 )
        DrctnlFlips( sq, dirinc[3], color, oppcol );
    if ( j & 4 )
        DrctnlFlips( sq, dirinc[2], color, oppcol );
    if ( j & 2 )
        DrctnlFlips( sq, dirinc[1], color, oppcol );
    if ( j & 1 )
        DrctnlFlips( sq, dirinc[0], color, oppcol );

    return FlipStack - OldFlipStack;
}

inline 
int EndGame::CtDrctnlFlips( uchar *sq, int inc, int color, int oppcol )
{
    uchar *pt = sq + inc;
    if(*pt == oppcol)
    {
        int count = 1;
        pt += inc;
        if(*pt == oppcol)
        {
            count++;                
            pt += inc;
            if(*pt == oppcol)
            {
                count++;            
                pt += inc;
                if(*pt == oppcol)
                {
                    count++;        
                    pt += inc;
                    if(*pt == oppcol)
                    {
                        count++;    
                        pt += inc;
                        if(*pt == oppcol)
                        {
                            count++;  
                            pt += inc;
                        }
                    }
                }
            }
        }
        if(*pt == color) 
            return count;
    }
   return 0;
}

int EndGame::CountFlips( uchar *board, int sqnum, int color, int oppcol )
{
    int ct=0;
    int j=dirmask[sqnum];
    uchar *sq;
    sq = sqnum + board;
    if ( j & 128 )
        ct += CtDrctnlFlips( sq, dirinc[7], color, oppcol );
    if ( j & 64 )
        ct += CtDrctnlFlips( sq, dirinc[6], color, oppcol );
    if ( j & 32 )
        ct += CtDrctnlFlips( sq, dirinc[5], color, oppcol );
    if ( j & 16 )
        ct += CtDrctnlFlips( sq, dirinc[4], color, oppcol );
    if ( j & 8 )
        ct += CtDrctnlFlips( sq, dirinc[3], color, oppcol );
    if ( j & 4 )
        ct += CtDrctnlFlips( sq, dirinc[2], color, oppcol );
    if ( j & 2 )
        ct += CtDrctnlFlips( sq, dirinc[1], color, oppcol );
    if ( j & 1 )
        ct += CtDrctnlFlips( sq, dirinc[0], color, oppcol );
    return(ct);
}


inline int EndGame::AnyDrctnlFlips( uchar *sq, int inc, int color, int oppcol )
{
    uchar *pt = sq + inc;
    if(*pt == oppcol)
    {
        pt += inc;
        if(*pt == oppcol)
        {
            pt += inc;
            if(*pt == oppcol)
            {
                pt += inc;
                if(*pt == oppcol)
                {
                    pt += inc;
                    if(*pt == oppcol)
                    {
                        pt += inc;
                        if(*pt == oppcol)
                            pt += inc;
                    }
                }
            }
        }
        if(*pt == color) 
            return 1;
    }

   return 0;
}

int EndGame::AnyFlips( uchar *board, int sqnum, int color, int oppcol )
{
    int j=dirmask[sqnum];
    uchar *sq;
    sq = sqnum + board;
    if( (( j & 128 ) && AnyDrctnlFlips( sq, dirinc[7], color, oppcol )) ||
        (( j & 64 )  && AnyDrctnlFlips( sq, dirinc[6], color, oppcol )) ||
        (( j & 32 ) && AnyDrctnlFlips( sq, dirinc[5], color, oppcol )) ||
        (( j & 16 ) && AnyDrctnlFlips( sq, dirinc[4], color, oppcol )) ||
        (( j & 8 ) && AnyDrctnlFlips( sq, dirinc[3], color, oppcol )) ||
        (( j & 4 ) && AnyDrctnlFlips( sq, dirinc[2], color, oppcol )) ||
        (( j & 2 ) && AnyDrctnlFlips( sq, dirinc[1], color, oppcol )) ||
        (( j & 1 ) && AnyDrctnlFlips( sq, dirinc[0], color, oppcol )) )
        return 1;
    return 0;
}



void EndGame::UndoFlips( int FlipCount, int oppcol )
{  
    if(FlipCount%2)
    {
        FlipCount--;
        * (*(--FlipStack)) = oppcol;
    }
    while(FlipCount)
    {
        FlipCount -= 2;
        * (*(--FlipStack)) = oppcol;
        * (*(--FlipStack)) = oppcol;
    }
}

inline uint EndGame::minu(uint a, uint b)
{
    if(a<b) 
        return a;
    return b;
}

void EndGame::PrepareToSolve( uchar *board )
{
    int i,sqnum;
    uint k;
    EmList *pt;
    int z;
    // find hole IDs: 
    k = 1;
    for(i=10; i<=80; i++)
    {
        if(board[i]==EMPTY)
        {
            if( board[i-10]==EMPTY ) HoleId[i] = HoleId[i-10];
            else if( board[i-9]==EMPTY ) HoleId[i] = HoleId[i-9];
            else if( board[i-8]==EMPTY ) HoleId[i] = HoleId[i-8];
            else if( board[i-1]==EMPTY ) HoleId[i] = HoleId[i-1];
            else{ HoleId[i] = k; k<<=1; }
        }
        else HoleId[i] = 0;
    }
    const int MAXITERS=1;
   /* In some sense this is wrong, since you
    * ought to keep doing iters until reach fixed point, but in most
    * othello positions with few empties this ought to work, and besides,
    * this is justifiable since the definition of "hole" in othello
    * is somewhat arbitrary anyway. */
    for(z=MAXITERS; z>0; z--)
    {
        for(i=80; i>=10; i--)
        {
            if(board[i]==EMPTY)
            {
                k = HoleId[i];
                if( board[i+10]==EMPTY ) HoleId[i] = minu(k,HoleId[i+10]);
                if( board[i+9]==EMPTY ) HoleId[i] = minu(k,HoleId[i+9]);
                if( board[i+8]==EMPTY ) HoleId[i] = minu(k,HoleId[i+8]);
                if( board[i+1]==EMPTY ) HoleId[i] = minu(k,HoleId[i+1]);
            }
        }
        for(i=10; i<=80; i++)
        {
            if(board[i]==EMPTY)
            {
                k = HoleId[i];
                if( board[i-10]==EMPTY ) HoleId[i] = minu(k,HoleId[i-10]);
                if( board[i-9]==EMPTY ) HoleId[i] = minu(k,HoleId[i-9]);
                if( board[i-8]==EMPTY ) HoleId[i] = minu(k,HoleId[i-8]);
                if( board[i-1]==EMPTY ) HoleId[i] = minu(k,HoleId[i-1]);
            }
        }
    }
    /* find parity of holes: */
    RegionParity = 0;
    for(i=10; i<=80; i++)
        RegionParity ^= HoleId[i];

    /* create list of empty squares: */
    k = 0;
    pt = &EmHead;
    for(i=60-1; i>=0; i--)
    {
        sqnum = worst2best[i];
        if( board[sqnum]==EMPTY )
        {
            pt->succ = &(Ems[k]);
            Ems[k].pred = pt;