lundi 30 mai 2016

My c/c++ implementation with adversarial search on artificial intellgence game playing program

Recently I'm embarking on my self-studying program(using c/c++) implementation of an artificial intelligence Japanese chess(i.e. Shogi) playing program. In order to speed up the efficiency of optimal alpha-beta search expansion,I use the "bitboard" data structure as unsigned 32-bit integer to represent each position on the 5x5 board.While getting an optimal alpha score from the function ABmove(),it simply tell which piece to move to get the maximum game score.

There were six basic pieces on each sides,they are: Pawn x 1 Rook x 1 Bishop x 1 Silver general x 1 Gold general x 1 King x 1 Unlike chess,some of the specific pieces(Pawn,Rook,Bishop and Silver general) can be promoted to another pieces as them move to the end of the opposite side of opponent,and their moves will be different,too.
I'm curious about what function I should call at the begin of main(),and whether should I determine who's turn(there should be a flag,1=my turn and 0=opp's turn,right?).Any response will be welcomed and appreciated:)!

My C/C++ code are as follows:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

enum pieces{    
PAWN_BLACK = 0,
ROOK_BLACK = 1,
BISHOP_BLACK = 2,
SILVER_GERERAL_BLACK = 3,
GOLD_GENERAL_BLACK = 4,
KING_BLACK = 5,

PAWN_WHITE = 6,
ROOK_WHITE = 7,
BISHOP_WHITE = 8,
SILVER_GERERAL_WHITE  = 9,
GOLD_GENERAL_WHITE = 10,
KING_WHITE =11,

Promoted_Rook_White=12,
Promoted_Bishop_White=13,
Promoted_Silver_General_White=14,
Promoted_Pawn_White=15,

Promoted_Rook_Black=16,
Promoted_Bishop_Black=17,
Promoted_Silver_General_Black=18,
Promoted_Pawn_Black=19,};


struct Bitboard{
int32_t p[20]={
    0x0000020,
    0x0000010,
    0x0000008,
    0x0000004,
    0x0000002,
    0x0000001,

    0x0080000,
    0x0100000,
    0x0200000,
    0x0400000,
    0x0800000,
    0x1000000,

    0x0000000,
    0x0000000,
    0x0000000,
    0x0000000,

    0x0000000,
    0x0000000,
    0x0000000,
    0x0000000,
};
bool isTerminal;};



static const uint32_t mask[20][25] ={   /*PAWN_BLACK_move_mask*/
0x0000020, 0x0000040, 0x0000080, 0x0000100, 0x0000200,
0x0000400, 0x0000800, 0x0001000, 0x0002000, 0x0004000,
0x0008000, 0x0010000, 0x0020000, 0x0040000, 0x0080000,
0x0100000, 0x0200000, 0x0400000, 0x0800000, 0x1000000,
0x0000000, 0x0000000, 0x0000000, 0x0000000, 0x0000000,
/*ROOK_BLACK_move_mask*/
0x010843E, 0x021085D, 0x042109B, 0x0842117, 0x108420F,
0x01087C1, 0x0210BA2, 0x0421364, 0x08822E8, 0x10841F0,
0x010F821, 0x0217442, 0x0426C84, 0x0845D08, 0x1083E10,
0x01F0421, 0x02E8842, 0x04D9084, 0x08BA108, 0x107C210,
0x1E08421, 0x1D10842, 0x1B21084, 0x1742108, 0x0F84210,
/*BISHOP_BLACK_move_mask*/
0x1041040, 0x0082080, 0x0004540, 0x0008A80, 0x0111100,
0x0820802, 0x1041405, 0x008A80A, 0x0115014, 0x0222008,
0x0410044, 0x08280A8, 0x1150151, 0x02A0282, 0x0440104,
0x0200888, 0x0501510, 0x0A02A20, 0x1405041, 0x0802082,
0x0011110, 0x002A200, 0x0054400, 0x00A0820, 0x0041041,
/*SILVER_GERERAL_BLACK_move_mask*/
0x0000060, 0x00000E0, 0x00001C0, 0x0000380, 0x0000300,
0x0000C02, 0x0001C05, 0x000380A, 0x0007014, 0x0006008,
0x0018040, 0x003804A, 0x0070140, 0x00E0280, 0x00C0100,
0x0300800, 0x0701400, 0x0E02800, 0x1C05000, 0x1802000,
0x0010000, 0x0028000, 0x0050000, 0x00A0000, 0x0040000,
/*GOLD_GERERAL_BLACK_move_mask*/
0x0000062, 0x00000E5, 0x00001CA, 0x0000394, 0x0000308,
0x0000C41, 0x0001CA2, 0x0003944, 0x0007288, 0x0006110,
0x0018820, 0x0039440, 0x0072880, 0x00E5100, 0x00C2200,
0x0310400, 0x0728800, 0x0E51000, 0x1CA2000, 0x1844000,
0x0208000, 0x0510000, 0x0A20000, 0x1440000, 0x0880000,
/*KING_BLACK_move_mask*/
0x0000062, 0x00000E5, 0x00001CA, 0x0000394, 0x0000308,
0x0000C43, 0x0001CA7, 0x000394E, 0x000729C, 0x0006118,
0x0018860, 0x00394E0, 0x00729C0, 0x00E5380, 0x00C2200,
0x0310400, 0x0728800, 0x0E51000, 0x1CA2000, 0x1846000,
0x0218000, 0x0538000, 0x0A70000, 0x14E0000, 0x08C0000,
/*PAWN_WHITE_move_mask*/
0x0000000, 0x0000000, 0x0000000, 0x0000000, 0x0000000,
0x0000001, 0x0000002, 0x0000004, 0x0000008, 0x0000010,
0x0000020, 0x0000040, 0x0000080, 0x0000100, 0x0000200,
0x0000400, 0x0000800, 0x0001000, 0x0002000, 0x0004000,
0x0008000, 0x0010000, 0x0020000, 0x0040000, 0x0100000,
/*ROOK_WHITE_move_mask*/
0x010843E, 0x021085D, 0x042109B, 0x0842117, 0x108420F,
0x01087C1, 0x0210BA2, 0x0421364, 0x08822E8, 0x10841F0,
0x010F821, 0x0217442, 0x0426C84, 0x0845D08, 0x1083E10,
0x01F0421, 0x02E8842, 0x04D9084, 0x08BA108, 0x107C210,
0x1E08421, 0x1D10842, 0x1B21084, 0x1742108, 0x0F84210,
/*BISHOP_WHITE_move_mask*/
0x1041040, 0x0082080, 0x0004540, 0x0008A80, 0x0111100,
0x0820802, 0x1041405, 0x008A80A, 0x0115014, 0x0222008,
0x0410044, 0x08280A8, 0x1150151, 0x02A0282, 0x0440104,
0x0200888, 0x0501510, 0x0A02A20, 0x1405041, 0x0802082,
0x0011110, 0x002A200, 0x0054400, 0x00A0820, 0x0041041,
/*SILVER_GERERAL_WHITE_move_mask*/
0x0000040, 0x00000A0, 0x0000140, 0x0000280, 0x0000200,
0x0000803, 0x0001407, 0x000280E, 0x000501C, 0x0002018,
0x0010060, 0x00280E0, 0x00501C0, 0x00A0380, 0x0040300,
0x0200C00, 0x0501C00, 0x0A03800, 0x1407000, 0x0806000,
0x0018000, 0x0038000, 0x0070000, 0x00E0000, 0x00C0000,
/*GOLD_GENERAL_WHITE_move_mask*/
0x0000022, 0x0000045, 0x000008A, 0x0000114, 0x0000208,
0x0000443, 0x00008A7, 0x000114E, 0x000229C, 0x0004118,
0x0008860, 0x00114E0, 0x00229C0, 0x0045380, 0x0082300,
0x0110C00, 0x0229C00, 0x0453800, 0x08A7000, 0x1046000,
0x0218000, 0x0538000, 0x0A70000, 0x14E0000, 0x08C0000,
/*KING_WHITE_move_mask*/
0x0000062, 0x00000E5, 0x00001CA, 0x0000394, 0x0000308,
0x0000C43, 0x0001CA7, 0x000394E, 0x000729C, 0x0006118,
0x0018860, 0x00394E0, 0x00729C0, 0x00E5380, 0x00C2200,
0x0310400, 0x0728800, 0x0E51000, 0x1CA2000, 0x1846000,
0x0218000, 0x0538000, 0x0A70000, 0x14E0000, 0x08C0000,

/*Promoted_Rook_White_move_mask*//*龍王*/
0x010847F, 0x02108FF, 0x04211DF, 0x084239F, 0x108431C,
0x0108FE3, 0x0211FE7, 0x0423BEE, 0x08473FC, 0x10863F8,
0x011FC61, 0x023FCE2, 0x0477DC4, 0x08E7F88, 0x10C7F10,
0x03F8C21, 0x07F9C42, 0x0EFB884, 0x1CFF108, 0x18FE210,
0x1F18421, 0x1F38842, 0x1F71084, 0x1FE2108, 0x1FC4210,
/*Promoted_Bishop_White_move_mask*//*龍馬*/
0x1041062, 0x00820E5, 0x00045CA, 0x0008B94, 0x0111308,
0X0820C43, 0X1041CA7, 0X008B94E, 0X011729C, 0x0226118,
0x0418864, 0x08394E8, 0x11729D1, 0x02E5382, 0x04C2304,
0x0310C88, 0x0729D10, 0x0E52A20, 0x1CA7041, 0x1846082,
0x0219110, 0x053A200, 0x0A74400, 0x14E0820, 0x08C1041,
/*Promoted_Silver_General_White_move_mask*//*成金*/
0x0000022, 0x0000045, 0x000008A, 0x0000114, 0x0000208,
0x0000443, 0x00008A7, 0x000114E, 0x000229C, 0x0226118,
0x0008860, 0x00114E0, 0x00229C0, 0x0045380, 0x0082300,
0x0110C00, 0x0229C00, 0x0453800, 0x08A7000, 0x1046000,
0x0218000, 0x0538000, 0x0A70000, 0x14E0000, 0x08C0000,
/*Promoted_Pawn_White_move_mask*//*金*/
0x0000022, 0x0000045, 0x000008A, 0x0000114, 0x0000208,
0x0000443, 0x00008A7, 0x000114E, 0x000229C, 0x0004118,
0x0008860, 0x00114E0, 0x00229C0, 0x0045380, 0x0082300,
0x0110C00, 0x0229C00, 0x0453800, 0x08A7000, 0x1046000,
0x0218000, 0x0538000, 0x0A70000, 0x14E0000, 0x08C0000,
/*Promoted_Rook_Black_move_mask*//*龍王*/
0x010847F, 0x02108FF, 0x04211DF, 0x084239F, 0x108431C,
0x0108FE3, 0x0211FE7, 0x0423BEE, 0x08473FC, 0x10863F8,
0x011FC61, 0x023FCE2, 0x0477DC4, 0x08E7F88, 0x10C7F10,
0x03F8C21, 0x07F9C42, 0x0EFB884, 0x1CFF108, 0x18FE210,
0x1F18421, 0x1F38842, 0x1F71084, 0x1FE2108, 0x1FC4210,
/*Promoted_Bishop_Black_move_mask*//*龍馬*/
0x1041062, 0x00820E5, 0x00045CA, 0x0008B94, 0x0111308,
0X0820C43, 0X1041CA7, 0X008B94E, 0X011729C, 0x0226118,
0x0418864, 0x08394E8, 0x11729D1, 0x02E5382, 0x04C2304,
0x0310C88, 0x0729D10, 0x0E52A20, 0x1CA7041, 0x1846082,
0x0219110, 0x053A200, 0x0A74400, 0x14E0820, 0x08C1041,
/*Promoted_Silver_General_Black_move_mask*//*成金*/
0x0000062, 0x00000E5, 0x00001CA, 0x0000394, 0x0000308,
0x0000C41, 0x0001CA2, 0x0003944, 0x0007288, 0x0006110,
0x0018820, 0x0039440, 0x0072880, 0x00E5100, 0x00C2200,
0x0310400, 0x0728800, 0x0E51000, 0x1CA2000, 0x1844000,
0x0208000, 0x0510000, 0x0A20000, 0x1440000, 0x0880000,
/*Promoted_Pawn_Black_move_mask*//*金*/
0x0000062, 0x00000E5, 0x00001CA, 0x0000394, 0x0000308,
0x0000C41, 0x0001CA2, 0x0003944, 0x0007288, 0x0006110,
0x0018820, 0x0039440, 0x0072880, 0x00E5100, 0x00C2200,
0x0310400, 0x0728800, 0x0E51000, 0x1CA2000, 0x1844000,
0x0208000, 0x0510000, 0x0A20000, 0x1440000, 0x0880000,};

int position(uint32_t piece)

if(piece == 0x0000001)return 0;
else if(piece == 0x0000002)return 1;
else if(piece == 0x0000004)return 2;
else if(piece == 0x0000008)return 3;
else if(piece == 0x0000010)return 4;
else if(piece == 0x0000020)return 5;
else if(piece == 0x0000040)return 6;
else if(piece == 0x0000080)return 7;
else if(piece == 0x0000100)return 8;
else if(piece == 0x0000200)return 9;
else if(piece == 0x0000400)return 10;
else if(piece == 0x0000800)return 11;
else if(piece == 0x0001000)return 12;
else if(piece == 0x0002000)return 13;
else if(piece == 0x0004000)return 14;
else if(piece == 0x0008000)return 15;
else if(piece == 0x0010000)return 16;
else if(piece == 0x0020000)return 17;
else if(piece == 0x0040000)return 18;
else if(piece == 0x0080000)return 19;
else if(piece == 0x0100000)return 20;
else if(piece == 0x0200000)return 21;
else if(piece == 0x0400000)return 22;
else if(piece == 0x0800000)return 23;
else if(piece == 0x1000000)return 24;}
struct move{
int piece;
uint32_t pos;};

move bestmove;

class Board{
Board *playMove;
move nextMoves;};

struct Effects{
int King=30000;
int Promoted_bishop=84;
int Promoted_rook=80;
int rook=60;
int bishop=54;
int Gold_gereral=74;
int Sliver_general=64;
int pawn=50;};

int AB(Bitboard board, int alpha, int beta, int depth){
if(board.isTerminal)return 0; // Win (super big) or Loser(super small)
if(depth <= 0)return 0;// using board to compute the score
int value;
for(int i = 0; i < 12; i++)
{
    uint32_t mov = mask[i][position(board.p[i])];
    while(mov)
    {
        uint32_t pos = mov & -mov;
        mov &= (mov-1);
        Bitboard child = board;
        //one move
        //black <--> white
        value = -AB(child, -beta, -alpha, depth-1);
        if(value >= beta) return value;
        if(value > alpha) alpha = value;
    }
}
return alpha;}

int ABmove(Bitboard board, int alpha, int beta, int depth){

if(board.isTerminal)return 0; // Win (super big) or Loser(super small)
if(depth <= 0)return 0;// using board to compute the score
int value;
for(int i = 0; i < 12; i++)
{
    uint32_t mov = mask[i][position(board.p[i])];
    while(mov)
    {
        uint32_t pos = mov & -mov;
        mov &= (mov-1);
        Bitboard child = board;
        //one move
        //black <--> white
        value = -AB(child, -beta, -alpha, depth-1);
        if(value >= beta) return value;
        if(value > alpha)
        {
            alpha = value;
            bestmove.piece = i;
            bestmove.pos = pos;
        }
    }
}
return alpha;}

int main(){
Bitboard b[5][5];

/**what should I call?*/

return 0;}

Aucun commentaire:

Enregistrer un commentaire