Artificial Intelligence Algorithm
I am Making a Checkers Game....I have made a bit of it...Here is my Coding....
// Project By Shujahat Ali :: Hamza Khan :: Nabeel Ahmed :: //
// //
// Checkers //
// //
//////////////////////////////////////////////////////////////
#include<iostream>
#include<conio.h>
#include<stdio.h>
using namespace std;
enum state{state_black,state_white,state_board_m,state_board_im,state_black_k,state_white_k}; // shows states of pieces on board ( white, white_king, black, black_king and the board surface )
char fun_piece_wk() // function to return white piece .
{
return 'W';
}
char fun_piece_bk() // function to return black_king piece .
{
return 'M';
}
char fun_piece_w() // function to return white piece .
{
return 'X';
}
char fun_piece_b() // function to return black piece .
{
return '@';
}
char fun_board_m() // function to return checker movable board places .
{
return '_';
}
char fun_board_im() // function to show checker immovable board places .
{
return ' ';
}
int main () // main function
{
// User Variables
int mf_row,mf_column; // Move from co-ordinates
int mt_row,mt_column; // Move to co-ordinates
// Computer Variables
int com_mf_row,com_mf_column;
int com_mt_row,com_mt_column;
int n=0; // while loop holder
state arr[8][8]; // 8 x 8 state type array it takes values : (black,white,board)
cout<<"********************************************************************************"<<endl;
cout<<"************ Checkers Game By Shujahat Ali, Hamza Khan, Nabeel Ahmed **********"<<endl;
cout<<"********************************************************************************"<<endl<<endl<<endl;
cout<<" The Game Rules : \n\n 1. You Can Only Move Diagonally Forward.\n";
cout<<" 2. When You Reach the Opposite Side You Become King.\n";
cout<<" 3. Only King Can Move Backward and Forward Diagonally.\n";
cout<<" 4. When You have Opponent Checker adjacent to You, You will Have to JUMP it.\n";
cout<<" 5. You Are the White Checker (X).\n";
cout<<" 6. Move Piece By Their Co-ordinates (0-7) in terms of rows and column.\n";
cout<<" 7. You Loose When You Have No Checker Left or You Get Out of Turns.\n\n\n";
for(int i=0;i<8;i++) // loop to declare the states in the array (black,white,board)
{
for(int j=0;j<8;j++)
{
if( // conditions to declare black piece
(i==0 && (j==1 || j==3 || j==5 || j==7)) ||
(i==1 && (j==0 || j==2 || j==4 || j==6)) ||
(i==2 && (j==1 || j==3 || j==5 || j==7))
)
{
arr[i][j]=state_black;
}
else if ( // conditions to declare white pieces
(i==5 && (j==0 || j==2 || j==4 || j==6)) ||
(i==6 && (j==1 || j==3 || j==5 || j==7)) ||
(i==7 && (j==0 || j==2 || j==4 || j==6))
)
{
arr[i][j]=state_white;
}
else if (
(i==0 && (j==0 || j==2 || j==4 || j==6)) ||
(i==1 && (j==1 || j==3 || j==5 || j==7)) ||
(i==2 && (j==0 || j==2 || j==4 || j==6)) ||
(i==3 && (j==1 || j==3 || j==5 || j==7)) ||
(i==4 && (j==0 || j==2 || j==4 || j==6)) ||
(i==5 && (j==1 || j==3 || j==5 || j==7)) ||
(i==6 && (j==0 || j==2 || j==4 || j==6)) ||
(i==7 && (j==1 || j==3 || j==5 || j==7))
)
{
arr[i][j]=state_board_im;
}
else // declaring board pieces
arr[i][j]=state_board_m;
}
}
try_again: // goto position if user makes a wrong move
for(int m=0;m<8;m++) // loop to call functions to print pieces
{
for(int n=0;n<8;n++)
{
if(arr[m][n]== state_white)
{
cout<<fun_piece_w()<<" "; // calling function to print white piece == X
}
else if (arr[m][n]== state_black)
{
cout<<fun_piece_b()<<" "; // calling function to print black piece == @
}
else if (arr[m][n]==state_board_m)
{
cout<<fun_board_m()<<" ";
}
else
cout<<fun_board_im()<<" "; // calling function to print board == _ to show board places where checkers can move
}
cout<<endl<<endl;
}
do
{
cout<<" Which White Piece (X) Do You Want to Move ? \n\n Enter the Row No (0-7) : "; // Which Piece to Move
cin>>mf_row;
cout<<"\n Enter the Column No (0-7) : ";
cin>>mf_column;
if( arr[mf_row][mf_column] != state_white) // Condition to select white checker only
{
cout<<"\n\n !!! Error !!!...Try Your Move Again \n\n\n\n"; // If User to Tries to Move other than Diagonal Show Error and Ask him to Retry
goto try_again;
}
cout<<"\n\n Where Do You Want To Move It ? \n\n Enter the Row No (0-7): "; // Co-ordinates Where the Checker is Moved to
cin>>mt_row;
cout<<"\n Enter the Column No (0-7) : ";
cin>>mt_column;
cout<<"\n\n\n";
if( (arr[mt_row][mt_column] != state_board_m) || // If Immovable Board Places are Selected Give Error " " Or If Another Checker is Selected Give Error
(mt_row > mf_row) || // Restricts Backward Movement
(mf_row - mt_row != 1 ) || // Restricts ...
(mf_column - mt_column < -1) || // ... the Checker to Move only to...
(mf_column - mt_column > 1) // ...Adjacent forward Diagonal Spaces...
)
{
cout<<"\n\n !!! Error !!!...Try Your Move Again \n\n\n\n";
goto try_again;
}
arr[mf_row][mf_column] = state_board_m; // Changing the State of place from White Checker to Board Movable
arr[mt_row][mt_column] = state_white; // Turning the State of Board Movable to White Checker
for(int m=0;m<8;m++ ) // loop to call functions to print pieces
{
for(int n=0;n<8;n++)
{
if(arr[m][n]==state_white)
{
cout<<fun_piece_w()<<" "; // calling function to print white piece == X
}
else if (arr[m][n]==state_black)
{
cout<<fun_piece_b()<<" "; // calling function to print black piece == @
}
else if (arr[m][n]==state_board_m)
{
cout<<fun_board_m()<<" "; // calling function to print board movable places "_"
}
else
cout<<fun_board_im()<<" "; // calling function to print board immovable places " "
}
cout<<endl<<endl;
}
if(mt_row==4)
{
com_mf_row=2;
com_mf_column=1;
com_mt_row=3;
com_mt_column=2;
arr[com_mf_row][com_mf_row]=state_board_m;
arr[com_mt_row][com_mt_row]=state_black;
cout<<"\n\n\n\n\n";
for(int m=0;m<8;m++ ) // loop to call functions to print pieces
{
for(int n=0;n<8;n++)
{
if(arr[m][n]==state_white)
{
cout<<fun_piece_w()<<" "; // calling function to print white piece == X
}
else if (arr[m][n]==state_black)
{
cout<<fun_piece_b()<<" "; // calling function to print black piece == @
}
else if (arr[m][n]==state_board_m)
{
cout<<fun_board_m()<<" "; // calling function to print board movable places "_"
}
else
cout<<fun_board_im()<<" "; // calling function to print board immovable places " "
}
cout<<endl<<endl;
}
}
n++;
} while(n=1);
getch();
return 0;
}.
.
.
.
.
.
.
.
i have not yet designed the algorithms.... i want to put it such that the computer itself calculates the move.....i have the following code ((which i don't understand )) which is using artificial intelligence i presume because i don't see many if-else statements or switch statements....
// Project By Shujahat Ali :: Hamza Khan :: Nabeel Ahmed :: //
// //
// Checkers //
// //
//////////////////////////////////////////////////////////////
#include<iostream>
#include<conio.h>
#include<stdio.h>
using namespace std;
enum state{state_black,state_white,state_board_m,state_board_im,state_black_k,state_white_k}; // shows states of pieces on board ( white, white_king, black, black_king and the board surface )
char fun_piece_wk() // function to return white piece .
{
return 'W';
}
char fun_piece_bk() // function to return black_king piece .
{
return 'M';
}
char fun_piece_w() // function to return white piece .
{
return 'X';
}
char fun_piece_b() // function to return black piece .
{
return '@';
}
char fun_board_m() // function to return checker movable board places .
{
return '_';
}
char fun_board_im() // function to show checker immovable board places .
{
return ' ';
}
int main () // main function
{
// User Variables
int mf_row,mf_column; // Move from co-ordinates
int mt_row,mt_column; // Move to co-ordinates
// Computer Variables
int com_mf_row,com_mf_column;
int com_mt_row,com_mt_column;
int n=0; // while loop holder
state arr[8][8]; // 8 x 8 state type array it takes values : (black,white,board)
cout<<"********************************************************************************"<<endl;
cout<<"************ Checkers Game By Shujahat Ali, Hamza Khan, Nabeel Ahmed **********"<<endl;
cout<<"********************************************************************************"<<endl<<endl<<endl;
cout<<" The Game Rules : \n\n 1. You Can Only Move Diagonally Forward.\n";
cout<<" 2. When You Reach the Opposite Side You Become King.\n";
cout<<" 3. Only King Can Move Backward and Forward Diagonally.\n";
cout<<" 4. When You have Opponent Checker adjacent to You, You will Have to JUMP it.\n";
cout<<" 5. You Are the White Checker (X).\n";
cout<<" 6. Move Piece By Their Co-ordinates (0-7) in terms of rows and column.\n";
cout<<" 7. You Loose When You Have No Checker Left or You Get Out of Turns.\n\n\n";
for(int i=0;i<8;i++) // loop to declare the states in the array (black,white,board)
{
for(int j=0;j<8;j++)
{
if( // conditions to declare black piece
(i==0 && (j==1 || j==3 || j==5 || j==7)) ||
(i==1 && (j==0 || j==2 || j==4 || j==6)) ||
(i==2 && (j==1 || j==3 || j==5 || j==7))
)
{
arr[i][j]=state_black;
}
else if ( // conditions to declare white pieces
(i==5 && (j==0 || j==2 || j==4 || j==6)) ||
(i==6 && (j==1 || j==3 || j==5 || j==7)) ||
(i==7 && (j==0 || j==2 || j==4 || j==6))
)
{
arr[i][j]=state_white;
}
else if (
(i==0 && (j==0 || j==2 || j==4 || j==6)) ||
(i==1 && (j==1 || j==3 || j==5 || j==7)) ||
(i==2 && (j==0 || j==2 || j==4 || j==6)) ||
(i==3 && (j==1 || j==3 || j==5 || j==7)) ||
(i==4 && (j==0 || j==2 || j==4 || j==6)) ||
(i==5 && (j==1 || j==3 || j==5 || j==7)) ||
(i==6 && (j==0 || j==2 || j==4 || j==6)) ||
(i==7 && (j==1 || j==3 || j==5 || j==7))
)
{
arr[i][j]=state_board_im;
}
else // declaring board pieces
arr[i][j]=state_board_m;
}
}
try_again: // goto position if user makes a wrong move
for(int m=0;m<8;m++) // loop to call functions to print pieces
{
for(int n=0;n<8;n++)
{
if(arr[m][n]== state_white)
{
cout<<fun_piece_w()<<" "; // calling function to print white piece == X
}
else if (arr[m][n]== state_black)
{
cout<<fun_piece_b()<<" "; // calling function to print black piece == @
}
else if (arr[m][n]==state_board_m)
{
cout<<fun_board_m()<<" ";
}
else
cout<<fun_board_im()<<" "; // calling function to print board == _ to show board places where checkers can move
}
cout<<endl<<endl;
}
do
{
cout<<" Which White Piece (X) Do You Want to Move ? \n\n Enter the Row No (0-7) : "; // Which Piece to Move
cin>>mf_row;
cout<<"\n Enter the Column No (0-7) : ";
cin>>mf_column;
if( arr[mf_row][mf_column] != state_white) // Condition to select white checker only
{
cout<<"\n\n !!! Error !!!...Try Your Move Again \n\n\n\n"; // If User to Tries to Move other than Diagonal Show Error and Ask him to Retry
goto try_again;
}
cout<<"\n\n Where Do You Want To Move It ? \n\n Enter the Row No (0-7): "; // Co-ordinates Where the Checker is Moved to
cin>>mt_row;
cout<<"\n Enter the Column No (0-7) : ";
cin>>mt_column;
cout<<"\n\n\n";
if( (arr[mt_row][mt_column] != state_board_m) || // If Immovable Board Places are Selected Give Error " " Or If Another Checker is Selected Give Error
(mt_row > mf_row) || // Restricts Backward Movement
(mf_row - mt_row != 1 ) || // Restricts ...
(mf_column - mt_column < -1) || // ... the Checker to Move only to...
(mf_column - mt_column > 1) // ...Adjacent forward Diagonal Spaces...
)
{
cout<<"\n\n !!! Error !!!...Try Your Move Again \n\n\n\n";
goto try_again;
}
arr[mf_row][mf_column] = state_board_m; // Changing the State of place from White Checker to Board Movable
arr[mt_row][mt_column] = state_white; // Turning the State of Board Movable to White Checker
for(int m=0;m<8;m++ ) // loop to call functions to print pieces
{
for(int n=0;n<8;n++)
{
if(arr[m][n]==state_white)
{
cout<<fun_piece_w()<<" "; // calling function to print white piece == X
}
else if (arr[m][n]==state_black)
{
cout<<fun_piece_b()<<" "; // calling function to print black piece == @
}
else if (arr[m][n]==state_board_m)
{
cout<<fun_board_m()<<" "; // calling function to print board movable places "_"
}
else
cout<<fun_board_im()<<" "; // calling function to print board immovable places " "
}
cout<<endl<<endl;
}
if(mt_row==4)
{
com_mf_row=2;
com_mf_column=1;
com_mt_row=3;
com_mt_column=2;
arr[com_mf_row][com_mf_row]=state_board_m;
arr[com_mt_row][com_mt_row]=state_black;
cout<<"\n\n\n\n\n";
for(int m=0;m<8;m++ ) // loop to call functions to print pieces
{
for(int n=0;n<8;n++)
{
if(arr[m][n]==state_white)
{
cout<<fun_piece_w()<<" "; // calling function to print white piece == X
}
else if (arr[m][n]==state_black)
{
cout<<fun_piece_b()<<" "; // calling function to print black piece == @
}
else if (arr[m][n]==state_board_m)
{
cout<<fun_board_m()<<" "; // calling function to print board movable places "_"
}
else
cout<<fun_board_im()<<" "; // calling function to print board immovable places " "
}
cout<<endl<<endl;
}
}
n++;
} while(n=1);
getch();
return 0;
}.
.
.
.
.
.
.
.
i have not yet designed the algorithms.... i want to put it such that the computer itself calculates the move.....i have the following code ((which i don't understand )) which is using artificial intelligence i presume because i don't see many if-else statements or switch statements....
// A Simple Checkers Program.
// by Jonathan Kreuzer
// jkreuzer@3dkingdoms.com
// I compiled it with MSVC++ 6.0, haven't tested it with other compilers
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <iostream>
#include <conio.h>
#include <memory.h>
#include <windows.h>
#include "resource.h"
using namespace std;
#define WHITE 2
#define BLACK 1 // Black == Red
#define EMPTY 0
#define BPIECE 1
#define WPIECE 2
#define BKING 5
#define WKING 6
#define INVALID 8
#define NONE 255
#define KINGEVAL 32
#define TIMEOUT 31000
#define HASHTABLESIZE 400000 // 4 megabytes, 400,000 entries
#define DOUBLEJUMP 2000
#define HUMAN 128
#define MAKEMOVE 129
#define SEARCHED 127
#define MAX_SEARCHDEPTH 54
#define MAX_GAMEMOVES 1024
const int LAZY_EVAL_MARGIN = 40;
const int BEGINNER_DEPTH = 2, NORMAL_DEPTH = 40; // Max depth for each level
// GLOBAL VARIABLES... ugg, too many?
char *g_sNameVer = "Gui Checkers 0.80";
float fMaxSeconds = 2.0f; // The number of seconds the computer is allowed to search
const int g_bEndHard = FALSE; // Set to true to stop search after MaxSeconds no matter what.
int g_MaxDepth = NORMAL_DEPTH;
char cCompColor = WHITE;
clock_t starttime, endtime;
int hashing = 1, BoardFlip = 0;
int nodes, nodes2, SearchDepth;
int g_xAdd = 44, g_yAdd = 20, g_nSqSize = 64;
HBITMAP PieceBitmaps[32];
HWND MainWnd= NULL, BottomWnd = NULL;
int g_nSelSquare = NONE;
int g_SearchingMove = 0, g_SearchEval = 0;
int g_nDouble = 0, g_nMoves = 0; // Number of moves played so far in the current game
struct CBoard;
struct SMove;
struct CMoveList;
// GUI function definitions
long CALLBACK WindowProc( HWND hwnd, unsigned msg, UINT wparam, LONG lparam );
long CALLBACK InfoProc( HWND hwnd, unsigned msg, UINT wparam, LONG lparam );
void DrawBitmap( HDC hdc, HBITMAP bitmap, int x, int y, int nSize );
void HighlightSquare ( HDC hdc, int Square, int sqSize, int bRedraw, unsigned long color, int border);
void DisplayText (char *sText);
void DrawBoard (const CBoard &board);
void DisplaySearchInfo ( CBoard &InBoard, int SearchDepth, int Eval, int nodes);
void RunningDisplay ();
void ReplayGame ( int nMove, CBoard &Board );
// =================================================
// BOARD Representation. I changed to this representation after seeing code by Martin Fierz
// everything else in this file I believe was made without looking at other checkers source of any kind.
/* 37 38 39 40
32 33 34 35
28 29 30 31
23 24 25 26
19 20 21 22
14 15 16 17
10 11 12 13
5 6 7 8 */
// =================================================
struct CBoard
{
void StartPosition ();
int EvaluateBoard (int ahead, int extra, int alpha, int beta);
// Data
unsigned __int64 HashKey;
short nEval, nWhite, nBlack;
char SideToMove, Start;
char Sqs[48];
};
CBoard g_Boardlist[MAX_SEARCHDEPTH];
CBoard g_CBoard;
unsigned char KBoard[68];
int BoardLoc[66] =
{ 0, 37, 0, 38, 0, 39, 0, 40, 32, 0, 33, 0, 34, 0, 35, 0, 0, 28, 0, 29, 0 ,30, 0, 31, 23, 0, 24, 0, 25, 0, 26, 0,
0, 19, 0, 20, 0, 21, 0, 22, 14, 0, 15, 0, 16, 0, 17, 0, 0, 10, 0, 11, 0, 12, 0, 13, 5, 0, 6, 0, 7, 0, 8, 0};
// =================================================
//
// TRANSPOSITION TABLE
//
// =================================================
struct TEntry
{
// FUNCTIONS
public:
void inline Read ( unsigned long CheckSum, short alpha, short beta, int &bestmove, int &value, int depth, int ahead)
{
if (m_checksum == CheckSum ) //To be almost totally sure these are really the same position.
{
int tempVal;
// Get the Value if the search was deep enough, and bounds usable
if (m_depth >= depth)
{
if (abs (m_eval) > 1800) // This is a game ending value, must adjust it since it depends on the variable ahead
{
if (m_eval > 0) tempVal = m_eval - ahead + (m_failtypeXahead>>2);
if (m_eval < 0) tempVal = m_eval + ahead - (m_failtypeXahead>>2);
}
else tempVal = m_eval;
switch ( (m_failtypeXahead&3) )
{
case 0: value = tempVal; // Exact value
break;
case 1: if (tempVal <= alpha) value = tempVal; // Alpha Bound (check to make sure it's usuable)
break;
case 2: if (tempVal >= beta) value = tempVal; // Beta Bound (check to make sure it's usuable)
break;
}
}
// Otherwise take the best move from Transposition Table
bestmove = m_bestmove;
}
}
void inline Write ( unsigned long CheckSum, short alpha, short beta, int &bestmove, int &value, int depth, int ahead)
{
m_checksum = CheckSum;
m_eval = value;
m_failtypeXahead = (ahead<<2);
if (value <= alpha) m_failtypeXahead |= 1;
if (value >= beta) m_failtypeXahead |= 2;
m_depth = depth;
m_bestmove = bestmove;
}
static void Create_HashFunction ();
static unsigned __int64 HashBoard (const CBoard &Board);
// DATA
private:
unsigned long m_checksum;
char m_depth;
char m_failtypeXahead; // 2 separate values are packed in to this char
short m_eval;
short m_bestmove;
};
// Declare and allocate the transposition table
TEntry *TTable = (TEntry *) malloc( sizeof (TEntry) * HASHTABLESIZE + 2);
// ------------------
// Hash Board
//
// HashBoard is called to get the hash value of the start board.
// ------------------
unsigned __int64 HashFunction [48][12];
void TEntry::Create_HashFunction ( )
{
for (int i = 0; i <48; i++)
for (int x = 0; x < 9; x++)
{HashFunction [i][x] = rand() + (rand()*256) + (rand()*65536);
HashFunction [i][x] <<= 32;
HashFunction [i][x] += rand() + (rand()*256) + (rand()*65536);
}
}
unsigned __int64 TEntry::HashBoard (const CBoard &Board)
{
unsigned __int64 CheckSum = 0;
for (int index = 5; index <= 40; index++)
{
int nPiece = Board.Sqs [ index ];
if (nPiece != EMPTY) CheckSum ^= HashFunction [ index ][ nPiece ];
}
if (Board.SideToMove == BLACK)
{
CheckSum = ~CheckSum ;
}
return CheckSum;
}
// Check for a repeated board
// (only checks every other move, because side to move must be the same)
__int64 RepNum[ MAX_GAMEMOVES ];
// with Hashvalue passed
int inline Repetition ( const __int64 HashKey, int ahead)
{
int i = 0;
if ((i&1) != (ahead&1)) i++;
ahead-=2;
for ( ; i < ahead; i+=2)
if (RepNum[i] == HashKey) return TRUE;
return FALSE;
}
void inline AddRepBoard ( const __int64 HashKey, int ahead )
{
RepNum[ ahead ] = HashKey;
}
// by Jonathan Kreuzer
// jkreuzer@3dkingdoms.com
// I compiled it with MSVC++ 6.0, haven't tested it with other compilers
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <iostream>
#include <conio.h>
#include <memory.h>
#include <windows.h>
#include "resource.h"
using namespace std;
#define WHITE 2
#define BLACK 1 // Black == Red
#define EMPTY 0
#define BPIECE 1
#define WPIECE 2
#define BKING 5
#define WKING 6
#define INVALID 8
#define NONE 255
#define KINGEVAL 32
#define TIMEOUT 31000
#define HASHTABLESIZE 400000 // 4 megabytes, 400,000 entries
#define DOUBLEJUMP 2000
#define HUMAN 128
#define MAKEMOVE 129
#define SEARCHED 127
#define MAX_SEARCHDEPTH 54
#define MAX_GAMEMOVES 1024
const int LAZY_EVAL_MARGIN = 40;
const int BEGINNER_DEPTH = 2, NORMAL_DEPTH = 40; // Max depth for each level
// GLOBAL VARIABLES... ugg, too many?
char *g_sNameVer = "Gui Checkers 0.80";
float fMaxSeconds = 2.0f; // The number of seconds the computer is allowed to search
const int g_bEndHard = FALSE; // Set to true to stop search after MaxSeconds no matter what.
int g_MaxDepth = NORMAL_DEPTH;
char cCompColor = WHITE;
clock_t starttime, endtime;
int hashing = 1, BoardFlip = 0;
int nodes, nodes2, SearchDepth;
int g_xAdd = 44, g_yAdd = 20, g_nSqSize = 64;
HBITMAP PieceBitmaps[32];
HWND MainWnd= NULL, BottomWnd = NULL;
int g_nSelSquare = NONE;
int g_SearchingMove = 0, g_SearchEval = 0;
int g_nDouble = 0, g_nMoves = 0; // Number of moves played so far in the current game
struct CBoard;
struct SMove;
struct CMoveList;
// GUI function definitions
long CALLBACK WindowProc( HWND hwnd, unsigned msg, UINT wparam, LONG lparam );
long CALLBACK InfoProc( HWND hwnd, unsigned msg, UINT wparam, LONG lparam );
void DrawBitmap( HDC hdc, HBITMAP bitmap, int x, int y, int nSize );
void HighlightSquare ( HDC hdc, int Square, int sqSize, int bRedraw, unsigned long color, int border);
void DisplayText (char *sText);
void DrawBoard (const CBoard &board);
void DisplaySearchInfo ( CBoard &InBoard, int SearchDepth, int Eval, int nodes);
void RunningDisplay ();
void ReplayGame ( int nMove, CBoard &Board );
// =================================================
// BOARD Representation. I changed to this representation after seeing code by Martin Fierz
// everything else in this file I believe was made without looking at other checkers source of any kind.
/* 37 38 39 40
32 33 34 35
28 29 30 31
23 24 25 26
19 20 21 22
14 15 16 17
10 11 12 13
5 6 7 8 */
// =================================================
struct CBoard
{
void StartPosition ();
int EvaluateBoard (int ahead, int extra, int alpha, int beta);
// Data
unsigned __int64 HashKey;
short nEval, nWhite, nBlack;
char SideToMove, Start;
char Sqs[48];
};
CBoard g_Boardlist[MAX_SEARCHDEPTH];
CBoard g_CBoard;
unsigned char KBoard[68];
int BoardLoc[66] =
{ 0, 37, 0, 38, 0, 39, 0, 40, 32, 0, 33, 0, 34, 0, 35, 0, 0, 28, 0, 29, 0 ,30, 0, 31, 23, 0, 24, 0, 25, 0, 26, 0,
0, 19, 0, 20, 0, 21, 0, 22, 14, 0, 15, 0, 16, 0, 17, 0, 0, 10, 0, 11, 0, 12, 0, 13, 5, 0, 6, 0, 7, 0, 8, 0};
// =================================================
//
// TRANSPOSITION TABLE
//
// =================================================
struct TEntry
{
// FUNCTIONS
public:
void inline Read ( unsigned long CheckSum, short alpha, short beta, int &bestmove, int &value, int depth, int ahead)
{
if (m_checksum == CheckSum ) //To be almost totally sure these are really the same position.
{
int tempVal;
// Get the Value if the search was deep enough, and bounds usable
if (m_depth >= depth)
{
if (abs (m_eval) > 1800) // This is a game ending value, must adjust it since it depends on the variable ahead
{
if (m_eval > 0) tempVal = m_eval - ahead + (m_failtypeXahead>>2);
if (m_eval < 0) tempVal = m_eval + ahead - (m_failtypeXahead>>2);
}
else tempVal = m_eval;
switch ( (m_failtypeXahead&3) )
{
case 0: value = tempVal; // Exact value
break;
case 1: if (tempVal <= alpha) value = tempVal; // Alpha Bound (check to make sure it's usuable)
break;
case 2: if (tempVal >= beta) value = tempVal; // Beta Bound (check to make sure it's usuable)
break;
}
}
// Otherwise take the best move from Transposition Table
bestmove = m_bestmove;
}
}
void inline Write ( unsigned long CheckSum, short alpha, short beta, int &bestmove, int &value, int depth, int ahead)
{
m_checksum = CheckSum;
m_eval = value;
m_failtypeXahead = (ahead<<2);
if (value <= alpha) m_failtypeXahead |= 1;
if (value >= beta) m_failtypeXahead |= 2;
m_depth = depth;
m_bestmove = bestmove;
}
static void Create_HashFunction ();
static unsigned __int64 HashBoard (const CBoard &Board);
// DATA
private:
unsigned long m_checksum;
char m_depth;
char m_failtypeXahead; // 2 separate values are packed in to this char
short m_eval;
short m_bestmove;
};
// Declare and allocate the transposition table
TEntry *TTable = (TEntry *) malloc( sizeof (TEntry) * HASHTABLESIZE + 2);
// ------------------
// Hash Board
//
// HashBoard is called to get the hash value of the start board.
// ------------------
unsigned __int64 HashFunction [48][12];
void TEntry::Create_HashFunction ( )
{
for (int i = 0; i <48; i++)
for (int x = 0; x < 9; x++)
{HashFunction [i][x] = rand() + (rand()*256) + (rand()*65536);
HashFunction [i][x] <<= 32;
HashFunction [i][x] += rand() + (rand()*256) + (rand()*65536);
}
}
unsigned __int64 TEntry::HashBoard (const CBoard &Board)
{
unsigned __int64 CheckSum = 0;
for (int index = 5; index <= 40; index++)
{
int nPiece = Board.Sqs [ index ];
if (nPiece != EMPTY) CheckSum ^= HashFunction [ index ][ nPiece ];
}
if (Board.SideToMove == BLACK)
{
CheckSum = ~CheckSum ;
}
return CheckSum;
}
// Check for a repeated board
// (only checks every other move, because side to move must be the same)
__int64 RepNum[ MAX_GAMEMOVES ];
// with Hashvalue passed
int inline Repetition ( const __int64 HashKey, int ahead)
{
int i = 0;
if ((i&1) != (ahead&1)) i++;
ahead-=2;
for ( ; i < ahead; i+=2)
if (RepNum[i] == HashKey) return TRUE;
return FALSE;
}
void inline AddRepBoard ( const __int64 HashKey, int ahead )
{
RepNum[ ahead ] = HashKey;
}
// =================================================
//
// BOARD FUNCTIONS
//
// =================================================
// ------------------------------------------------
// Setup the Board in the starting position
// ------------------------------------------------
void CBoard::StartPosition ()
{int i;
for (i = 0; i< 48; i++) Sqs [i] = EMPTY;
for (i = 0; i < 5; i++) Sqs [i] = INVALID;
for (i = 5; i<= 8; i++) Sqs [i] = BPIECE;
for (i = 10; i <= 17; i++) Sqs [i] = BPIECE;
for (i = 28; i <= 35; i++) Sqs [i] = WPIECE;
for (i = 37; i <= 40; i++) Sqs [i] = WPIECE;
for (i = 41; i < 48; i++) Sqs [i] = INVALID;
Sqs[9] = INVALID; Sqs[18] = INVALID; Sqs[27] = INVALID; Sqs[36] = INVALID;
nBlack = 12;
nWhite = 12;
nEval = 0;
SideToMove = BLACK;
g_nMoves = 0;
// King Centralization evaluation of the board
for (i = 0; i< 48; i++) KBoard[i] = 0;
KBoard [20] = 7; KBoard [25] = 7;
KBoard [15] = 5; KBoard [24] = 5; KBoard [29] = 5; KBoard [30] = 5; KBoard[21] = 5;
KBoard [11] = 3; KBoard [12] = 3; KBoard [17] = 3; KBoard [26] = 3; KBoard[19] = 3; KBoard[28] = 3; KBoard [33] = 3; KBoard[34] =3; KBoard[35] = 3; KBoard[10] = 3;
// Calculate Hash values
HashKey = TEntry::HashBoard ( *this );
}
// ------------------
// Evaluate Board
//
// I don't know much about checkers, this is the best I could do for an evaluation function
// ------------------
int CBoard::EvaluateBoard (int ahead, int extra, int alpha, int beta)
{
register int eval = 0;
// Game is over?
if (nWhite == 0) return -2001 + ahead;
if (nBlack == 0) return 2001 - ahead;
// Number of pieces present. A ratio is used to encourage trading for the side that is up.
eval = (nWhite-nBlack) * (95 + ( 20 - nWhite - nBlack ) );
eval += nEval; // add in incremendtally updated King/location evaluation
eval +=extra;
// Too far from the alpha beta window? Forget about the rest of the eval, it probably won't get value back within the window
if (eval+LAZY_EVAL_MARGIN < alpha) return eval;
if (eval-LAZY_EVAL_MARGIN > beta) return eval;
// For near the end of the game, There are two corners where the losing side
// can make it tough to for the computer to win the game by moving a King back and forth on the 2 corner squares.
if (eval > 20)
{if (Sqs[8] == BKING || Sqs[13] == BKING) eval-=13;
if (Sqs[32] == BKING || Sqs[37] == BKING) eval-=13;
}
if (eval < -20)
{if (Sqs[8] == WKING || Sqs[13] == WKING) eval+=13;
if (Sqs[32] == WKING || Sqs[37] == WKING) eval+=13;
}
// Bonus for leaving pieces guarding the back row.
if (Sqs[5] == BPIECE) eval-=3;
if (Sqs[6] == BPIECE) eval-=8;
if (Sqs[7] == BPIECE) eval-=8;
if (Sqs[8] == BPIECE) eval-=8;
if (Sqs[37] == WPIECE) eval+=8;
if (Sqs[38] == WPIECE) eval+=8;
if (Sqs[39] == WPIECE) eval+=8;
if (Sqs[40] == WPIECE) eval+=3;
// Reward checkers that will king on the next move
int square;
for (square = 32; square <= 35; square++)
{
if (Sqs [ square ] == BPIECE)
{
if (Sqs [ square + 4] == EMPTY || Sqs [ square + 5] == EMPTY ) {eval-=(KINGEVAL-2); break;}
}
}
for (square = 10; square <= 13; square++)
{
if (Sqs [ square ] == WPIECE)
{if (Sqs [ square - 4] == EMPTY || Sqs [ square - 5] == EMPTY ) {eval+=(KINGEVAL-2); break;}
}
}
return eval;
}
// =================================================
//
// MOVE GENERATION
//
// =================================================
//
// MoveList Structures
//
struct SMove
{
unsigned long SrcDst;
char cPath[8];
};
struct CMoveList
{
// FUNCTIONS
void inline SetMove (SMove &Move, int src, int dst)
{
Move.SrcDst = (src)+(dst<<6) + (1<<12);
}
void inline AddJump (SMove &Move, int pathNum)
{
Move.cPath[pathNum] = 0;
Moves [ ++nJumps ] = Move;
nMoves = nJumps;
}
void inline AddMove (int src, int dst)
{
if (nJumps != 0) return; // Ignore non-jumps if a jump move is present
Moves [ ++nMoves ].SrcDst = (src)+(dst<<6);
return;
}
void FindMovesBlack ( char board[]);
void FindMovesWhite ( char board[]);
void FindJumpsBlack ( char board[]);
void FindJumpsWhite ( char board[]);
void inline FindSqJumpsBlack ( char board[], int square, int nPiece, int pathNum, int nJumpSq);
void inline FindSqJumpsWhite ( char board[], int square, int nPiece, int pathNum, int nJumpSq);
// DATA
int nMoves, nJumps;
SMove Moves[32];
SMove m_JumpMove;
};
CMoveList g_Movelist[MAX_SEARCHDEPTH];
SMove g_GameMoves [ MAX_GAMEMOVES ];
//
// Now the Movelist functions, which come in pairs for each color
//
// -------------------------------------------------
// Find the Moves available on board, and store them in Movelist
// -------------------------------------------------
void CMoveList::FindMovesBlack ( char board[])
{
// Clear the Move list
nJumps = 0;
nMoves = 0;
// Now loop through the legals squares on the board looking for black pieces
for (register int square = 40; square >= 5; square--)
{
if ( (board[ square ]&BPIECE) ) // found a black piece
{
// Check for normal move
if ( board[square + 4 ] == EMPTY ) AddMove (square , square +4);
// If normal move not possible, check for a jump
else if ( (board[square + 4 ]&WPIECE) && board[square + 8 ] == EMPTY)
{// A jump is possible, call FindSqJumpsBlack to detect double/triple/etc. jumps
SetMove (m_JumpMove, square, square+8);
FindSqJumpsBlack ( board, square + 8, board[ square ], 0, square+4);}
// Again for the other forwards direction
if (board[square + 5 ] == EMPTY ) AddMove (square , square + 5);
else if ( (board[square + 5 ]&WPIECE) && board[square + 10] == EMPTY)
{SetMove (m_JumpMove, square, square+10);
FindSqJumpsBlack ( board, square + 10, board[ square ], 0, square+5);}
// Check to see if this is a king, if so check for backwards moves and jumps
if (board[ square ] == BKING )
{
if (board[square - 5 ] == EMPTY ) AddMove ( square , square - 5);
else if ( (board[square - 5 ]&WPIECE) && board[square - 10 ] == EMPTY )
{SetMove (m_JumpMove, square, square-10);
FindSqJumpsBlack ( board, square - 10, board[ square ], 0, square-5);}
if (board[square - 4 ] == EMPTY ) AddMove (square , square - 4);
else if ( (board[square - 4 ]&WPIECE) && board[square - 8 ] == EMPTY )
{SetMove (m_JumpMove, square, square- 8);
FindSqJumpsBlack ( board, square - 8, board[ square ], 0, square-4);}
}
}
}
}
//
// BOARD FUNCTIONS
//
// =================================================
// ------------------------------------------------
// Setup the Board in the starting position
// ------------------------------------------------
void CBoard::StartPosition ()
{int i;
for (i = 0; i< 48; i++) Sqs [i] = EMPTY;
for (i = 0; i < 5; i++) Sqs [i] = INVALID;
for (i = 5; i<= 8; i++) Sqs [i] = BPIECE;
for (i = 10; i <= 17; i++) Sqs [i] = BPIECE;
for (i = 28; i <= 35; i++) Sqs [i] = WPIECE;
for (i = 37; i <= 40; i++) Sqs [i] = WPIECE;
for (i = 41; i < 48; i++) Sqs [i] = INVALID;
Sqs[9] = INVALID; Sqs[18] = INVALID; Sqs[27] = INVALID; Sqs[36] = INVALID;
nBlack = 12;
nWhite = 12;
nEval = 0;
SideToMove = BLACK;
g_nMoves = 0;
// King Centralization evaluation of the board
for (i = 0; i< 48; i++) KBoard[i] = 0;
KBoard [20] = 7; KBoard [25] = 7;
KBoard [15] = 5; KBoard [24] = 5; KBoard [29] = 5; KBoard [30] = 5; KBoard[21] = 5;
KBoard [11] = 3; KBoard [12] = 3; KBoard [17] = 3; KBoard [26] = 3; KBoard[19] = 3; KBoard[28] = 3; KBoard [33] = 3; KBoard[34] =3; KBoard[35] = 3; KBoard[10] = 3;
// Calculate Hash values
HashKey = TEntry::HashBoard ( *this );
}
// ------------------
// Evaluate Board
//
// I don't know much about checkers, this is the best I could do for an evaluation function
// ------------------
int CBoard::EvaluateBoard (int ahead, int extra, int alpha, int beta)
{
register int eval = 0;
// Game is over?
if (nWhite == 0) return -2001 + ahead;
if (nBlack == 0) return 2001 - ahead;
// Number of pieces present. A ratio is used to encourage trading for the side that is up.
eval = (nWhite-nBlack) * (95 + ( 20 - nWhite - nBlack ) );
eval += nEval; // add in incremendtally updated King/location evaluation
eval +=extra;
// Too far from the alpha beta window? Forget about the rest of the eval, it probably won't get value back within the window
if (eval+LAZY_EVAL_MARGIN < alpha) return eval;
if (eval-LAZY_EVAL_MARGIN > beta) return eval;
// For near the end of the game, There are two corners where the losing side
// can make it tough to for the computer to win the game by moving a King back and forth on the 2 corner squares.
if (eval > 20)
{if (Sqs[8] == BKING || Sqs[13] == BKING) eval-=13;
if (Sqs[32] == BKING || Sqs[37] == BKING) eval-=13;
}
if (eval < -20)
{if (Sqs[8] == WKING || Sqs[13] == WKING) eval+=13;
if (Sqs[32] == WKING || Sqs[37] == WKING) eval+=13;
}
// Bonus for leaving pieces guarding the back row.
if (Sqs[5] == BPIECE) eval-=3;
if (Sqs[6] == BPIECE) eval-=8;
if (Sqs[7] == BPIECE) eval-=8;
if (Sqs[8] == BPIECE) eval-=8;
if (Sqs[37] == WPIECE) eval+=8;
if (Sqs[38] == WPIECE) eval+=8;
if (Sqs[39] == WPIECE) eval+=8;
if (Sqs[40] == WPIECE) eval+=3;
// Reward checkers that will king on the next move
int square;
for (square = 32; square <= 35; square++)
{
if (Sqs [ square ] == BPIECE)
{
if (Sqs [ square + 4] == EMPTY || Sqs [ square + 5] == EMPTY ) {eval-=(KINGEVAL-2); break;}
}
}
for (square = 10; square <= 13; square++)
{
if (Sqs [ square ] == WPIECE)
{if (Sqs [ square - 4] == EMPTY || Sqs [ square - 5] == EMPTY ) {eval+=(KINGEVAL-2); break;}
}
}
return eval;
}
// =================================================
//
// MOVE GENERATION
//
// =================================================
//
// MoveList Structures
//
struct SMove
{
unsigned long SrcDst;
char cPath[8];
};
struct CMoveList
{
// FUNCTIONS
void inline SetMove (SMove &Move, int src, int dst)
{
Move.SrcDst = (src)+(dst<<6) + (1<<12);
}
void inline AddJump (SMove &Move, int pathNum)
{
Move.cPath[pathNum] = 0;
Moves [ ++nJumps ] = Move;
nMoves = nJumps;
}
void inline AddMove (int src, int dst)
{
if (nJumps != 0) return; // Ignore non-jumps if a jump move is present
Moves [ ++nMoves ].SrcDst = (src)+(dst<<6);
return;
}
void FindMovesBlack ( char board[]);
void FindMovesWhite ( char board[]);
void FindJumpsBlack ( char board[]);
void FindJumpsWhite ( char board[]);
void inline FindSqJumpsBlack ( char board[], int square, int nPiece, int pathNum, int nJumpSq);
void inline FindSqJumpsWhite ( char board[], int square, int nPiece, int pathNum, int nJumpSq);
// DATA
int nMoves, nJumps;
SMove Moves[32];
SMove m_JumpMove;
};
CMoveList g_Movelist[MAX_SEARCHDEPTH];
SMove g_GameMoves [ MAX_GAMEMOVES ];
//
// Now the Movelist functions, which come in pairs for each color
//
// -------------------------------------------------
// Find the Moves available on board, and store them in Movelist
// -------------------------------------------------
void CMoveList::FindMovesBlack ( char board[])
{
// Clear the Move list
nJumps = 0;
nMoves = 0;
// Now loop through the legals squares on the board looking for black pieces
for (register int square = 40; square >= 5; square--)
{
if ( (board[ square ]&BPIECE) ) // found a black piece
{
// Check for normal move
if ( board[square + 4 ] == EMPTY ) AddMove (square , square +4);
// If normal move not possible, check for a jump
else if ( (board[square + 4 ]&WPIECE) && board[square + 8 ] == EMPTY)
{// A jump is possible, call FindSqJumpsBlack to detect double/triple/etc. jumps
SetMove (m_JumpMove, square, square+8);
FindSqJumpsBlack ( board, square + 8, board[ square ], 0, square+4);}
// Again for the other forwards direction
if (board[square + 5 ] == EMPTY ) AddMove (square , square + 5);
else if ( (board[square + 5 ]&WPIECE) && board[square + 10] == EMPTY)
{SetMove (m_JumpMove, square, square+10);
FindSqJumpsBlack ( board, square + 10, board[ square ], 0, square+5);}
// Check to see if this is a king, if so check for backwards moves and jumps
if (board[ square ] == BKING )
{
if (board[square - 5 ] == EMPTY ) AddMove ( square , square - 5);
else if ( (board[square - 5 ]&WPIECE) && board[square - 10 ] == EMPTY )
{SetMove (m_JumpMove, square, square-10);
FindSqJumpsBlack ( board, square - 10, board[ square ], 0, square-5);}
if (board[square - 4 ] == EMPTY ) AddMove (square , square - 4);
else if ( (board[square - 4 ]&WPIECE) && board[square - 8 ] == EMPTY )
{SetMove (m_JumpMove, square, square- 8);
FindSqJumpsBlack ( board, square - 8, board[ square ], 0, square-4);}
}
}
}
}
// -------------------------------------------------
// These two functions only add jumps or moves that king a checker to the movelist
// they are used in the quiescence search
// -------------------------------------------------
void CMoveList::FindJumpsBlack ( char board[])
{
nJumps = 0; // Clear the Move list
nMoves = 0;
// Now look for moves
for (register int square = 5; square <= 40; square++)
{
if ( (board[ square ]&BPIECE) )
{
if ( (board[square + 4 ]&WPIECE) && board[square + 8 ] == EMPTY)
{SetMove (m_JumpMove, square, square+8); FindSqJumpsBlack ( board, square + 8, board[ square ], 0, square+4);}
if ( (board[square + 5 ]&WPIECE) && board[square + 10] == EMPTY)
{SetMove (m_JumpMove, square, square+10); FindSqJumpsBlack ( board, square + 10, board[ square ], 0, square+5);}
if (board[ square ] == BKING )
{
if ( (board[square - 5 ]&WPIECE) && board[square - 10 ] == EMPTY )
{SetMove (m_JumpMove, square, square-10); FindSqJumpsBlack ( board, square - 10, board[ square ], 0, square-5);}
if ( (board[square - 4 ]&WPIECE) && board[square - 8 ] == EMPTY )
{SetMove (m_JumpMove, square, square- 8); FindSqJumpsBlack ( board, square - 8, board[ square ], 0, square-4);}
}
}
}
}
// for WHITE
void CMoveList::FindJumpsWhite ( char board[])
{
nJumps = 0;
nMoves = 0;
for (register int square = 5; square <= 40; square++)
{
if ( (board[ square ]&WPIECE) )
{
if ((board[square - 4 ]&BPIECE) && board[square - 8 ] == 0 )
{SetMove (m_JumpMove, square, square-8); FindSqJumpsWhite ( board, square - 8, board[ square ], 0, square-4);}
if ((board[square - 5 ]&BPIECE) && board[square - 10] == 0)
{SetMove (m_JumpMove, square, square-10); FindSqJumpsWhite ( board, square - 10, board[ square ], 0, square-5);}
if (board[ square ] == WKING)
{
if ( (board[square + 4 ]&BPIECE) && board[square + 8 ] == 0)
{SetMove (m_JumpMove, square, square+8); FindSqJumpsWhite ( board, square + 8, board[ square ], 0, square+4);}
if ( (board[square + 5 ]&BPIECE) && board[square + 10 ] == 0)
{SetMove (m_JumpMove, square, square+10); FindSqJumpsWhite ( board, square + 10, board[ square ], 0, square+5);}
}
}
}
}
// -------------
// If a jump move was possible, we must make the jump then check
// to see if the same piece can jump again.
// There might be multiple paths a piece can take on a double jump, these functions
// store each possible path as a move.
// -------------
void CMoveList::FindSqJumpsBlack ( char board[], int square, int nPiece, int pathNum, int nJumpSq)
{
int nSqMoves = 0;
// Remove the jumped piece (until the end of this function), so we can't jump it again
int nJumpPiece = board [ nJumpSq ];
board [ nJumpSq ] = EMPTY;
// Now see if a piece on this square has more jumps
if ( (board[square + 4 ]&WPIECE) && board[square + 8 ] == EMPTY )
{m_JumpMove.cPath[ pathNum ] = 8; nSqMoves++; FindSqJumpsBlack ( board, square+8, nPiece, pathNum+1, square+4); }
if ( (board[square + 5 ]&WPIECE) && board[square + 10] == EMPTY )
{m_JumpMove.cPath[ pathNum ] = 10; nSqMoves++; FindSqJumpsBlack ( board, square+10, nPiece, pathNum+1, square+5); }
if ( nPiece == BKING)
{// If this pieces is a king, it can also jump backwards
if ( (board[square - 5 ]&WPIECE) && board[square - 10] == EMPTY )
{m_JumpMove.cPath[ pathNum ] = -10; nSqMoves++; FindSqJumpsBlack ( board, square-10, nPiece, pathNum+1, square-5); }
if ( (board[square - 4 ]&WPIECE) && board[square - 8 ] == EMPTY )
{m_JumpMove.cPath[ pathNum ] = -8; nSqMoves++; FindSqJumpsBlack ( board, square-8, nPiece, pathNum+1, square-4); }
}
if (nSqMoves == 0) AddJump (m_JumpMove, pathNum); // this is a leaf, so store the move
// Put back the jumped piece
board [ nJumpSq ] = nJumpPiece;
}
void CMoveList::FindSqJumpsWhite ( char board[], int square, int nPiece, int pathNum, int nJumpSq)
{
int nSqMoves = 0;
int nJumpPiece = board [ nJumpSq ];
board [ nJumpSq ] = EMPTY;
if ( (board[square - 4 ]&BPIECE) && board[square - 8 ] == EMPTY )
{m_JumpMove.cPath[ pathNum ] = -8; nSqMoves++; FindSqJumpsWhite ( board, square-8, nPiece, pathNum+1, square-4); }
if ( (board[square - 5 ]&BPIECE) && board[square - 10] == EMPTY )
{m_JumpMove.cPath[ pathNum ] = -10; nSqMoves++; FindSqJumpsWhite ( board, square-10, nPiece, pathNum+1, square-5); }
if ( nPiece == WKING)
{
if ( (board[square + 5 ]&BPIECE) && board[square + 10] == EMPTY )
{m_JumpMove.cPath[ pathNum ] = 10; nSqMoves++; FindSqJumpsWhite ( board, square+10, nPiece, pathNum+1, square+5); }
if ( (board[square + 4 ]&BPIECE) && board[square + 8 ] == EMPTY )
{m_JumpMove.cPath[ pathNum ] = +8; nSqMoves++; FindSqJumpsWhite ( board, square+8, nPiece, pathNum+1, square+4); }
}
if (nSqMoves == 0) AddJump (m_JumpMove, pathNum);
board [ nJumpSq ] = nJumpPiece;
}
// =================================================
//
// MOVE EXECUTION
//
// =================================================
// ---------------------
// Helper Functions for DoMove
// ---------------------
void inline DoSingleJump (CBoard &board, int src, int dst, int nPiece)
{
int jumpedSq = (dst + src) >> 1;
if (board.Sqs [ jumpedSq ] == WPIECE ) {board.nWhite--;}
else if (board.Sqs [jumpedSq ] == BPIECE) {board.nBlack--;}
else if (board.Sqs [jumpedSq ] == BKING) {board.nBlack--; board.nEval+=KINGEVAL;}
else if (board.Sqs [jumpedSq ] == WKING) {board.nWhite--; board.nEval-=KINGEVAL;}
board.HashKey ^= HashFunction [ src ][ nPiece ] ^ HashFunction [ dst ][ nPiece ] ^ HashFunction [ jumpedSq ][ board.Sqs [ jumpedSq ] ];
// Update the board array
board.Sqs [ dst ] = nPiece;
board.Sqs [ jumpedSq ] = EMPTY;
board.Sqs [ src ] = EMPTY;
}
// This function will test if a checker needs to be upgraded to a king, and upgrade if necessary
void inline CheckKing (CBoard &board, int dst, int nPiece)
{
if (dst <= 8 && nPiece == WPIECE)
{board.Sqs [ dst ] = WKING;
board.nEval+=KINGEVAL;
board.HashKey ^= HashFunction [ dst ][ nPiece ] ^ HashFunction [ dst ][ WKING ];
}
if (dst >= 37 && nPiece == BPIECE)
{board.Sqs [ dst ] = BKING;
board.nEval-=KINGEVAL;
board.HashKey ^= HashFunction [ dst ][ nPiece ] ^ HashFunction [ dst ][ BKING ];
}
}
// ---------------------
// Execute a Move
// ---------------------
int DoMove (SMove &Move, CBoard &board, int nType)
{
// Get Info From Move
unsigned int ulMove = Move.SrcDst;
unsigned int src = (ulMove&63);
unsigned int dst = (ulMove>>6)&63;
unsigned int bJump = (ulMove>>12);
unsigned int nPiece = board.Sqs [src];
board.SideToMove ^=3;
board.HashKey = ~board.HashKey; // Flip hash stm
if (bJump == 0)
{
// Update hash values
board.HashKey ^= HashFunction [ src ][ nPiece ] ^ HashFunction [ dst ][ nPiece ];
// Update the board array
board.Sqs [ dst ] = board.Sqs [ src ];
board.Sqs [ src ] = EMPTY;
// Update King Evaluation incrementally
if (nPiece == BKING) board.nEval -= KBoard[ dst ] - KBoard [ src ];
else if (nPiece == WKING) board.nEval += KBoard[ dst ] - KBoard [ src ];
else
{CheckKing ( board, dst, nPiece );
return 1;}
return 0;
}
DoSingleJump (board, src, dst, nPiece);
CheckKing ( board, dst, nPiece );
// Double Jump?
if (Move.cPath [0] == 0) return 1;
if (nType == HUMAN) return DOUBLEJUMP;
for (int i = 0; i < 8; i++)
{
int nDir = Move.cPath [i];
if (nDir == 0) break;
if (nType == MAKEMOVE)
{DrawBoard ( board );
Sleep (300);// pause a bit on displaying double jumps
}
DoSingleJump (board, dst, dst+nDir, nPiece);
dst+=nDir;
}
CheckKing ( board, dst, nPiece );
return 1;
}
// ---------------------------------------------
// Check Possiblity/Execute Move from one selected square to another
// returns 0 if the move is not possible, otherwise 1, or a double jump value the move is an uncompleted jump
// ---------------------------------------------
int SquareMove( CBoard &Board, int x , int y, int xloc, int yloc, char cColor)
{
int i, src, dst, nMSrc, nMDst;
CMoveList MoveList;
if (cColor == BLACK)
MoveList.FindMovesBlack (Board.Sqs);
else MoveList.FindMovesWhite (Board.Sqs);
for (i = 1; i <= MoveList.nMoves; i++)
{
dst = BoardLoc[xloc + yloc*8];
src = BoardLoc[x + y*8];
nMSrc = MoveList.Moves[i].SrcDst&63;
nMDst = (MoveList.Moves[i].SrcDst>>6)&63;
if ( nMSrc == src && nMDst == dst ) // Check if the src & dst match a move from the generated movelist
{
if (g_nDouble > 0) {g_GameMoves[g_nMoves-1].cPath[g_nDouble-1] = nMDst - nMSrc;
g_GameMoves[g_nMoves-1].cPath[ g_nDouble ] = 0;}
else
{
g_GameMoves [ g_nMoves ].SrcDst = MoveList.Moves[i].SrcDst;
g_GameMoves [ g_nMoves++ ].cPath[0] = 0;
g_GameMoves [ g_nMoves ].SrcDst = 0;
}
if (DoMove ( MoveList.Moves[i], Board, HUMAN) == DOUBLEJUMP)
{
g_nDouble++;
Board.SideToMove ^=3;
return DOUBLEJUMP;
}
g_nDouble = 0;
return 1;
}
}
return 0;
}
// ===============================================
//
// SEARCH
//
// ===============================================
// -------------------------------------------------
// Quiescence Search... Search all jumps, if there are no jumps, stop the search
// -------------------------------------------------
int QuiesceBoard ( int color, int ahead, int alpha, int beta )
{
int value;
// Find Jump Moves
if (color == WHITE)
{g_Movelist[ahead].FindJumpsWhite( g_Boardlist[ahead-1].Sqs );}
else
{g_Movelist[ahead].FindJumpsBlack( g_Boardlist[ahead-1].Sqs );}
// No more jump moves, return evaluation
if (g_Movelist[ahead].nJumps == 0 || (ahead+1) >= MAX_SEARCHDEPTH)
{
nodes++;
return g_Boardlist[ahead-1].EvaluateBoard ( ahead-1, 0, alpha, beta);
}
// There were jump moves, so we keep searching.
for (int i = 1; i <= g_Movelist[ahead].nJumps; i++)
{
g_Boardlist[ahead] = g_Boardlist[ahead-1];
DoMove(g_Movelist[ahead].Moves[i] , g_Boardlist[ahead], SEARCHED);
nodes++;
// Recursive Call
value = QuiesceBoard( (color^3) , ahead+1 , alpha, beta);
// Keep Track of Best Move and Alpha-Beta Prune
if (color == WHITE && value > alpha )
{
alpha = value;
if (alpha >= beta ) return beta;
}
if (color == BLACK && value < beta )
{
beta = value;
if (alpha >= beta ) return alpha;
}
}
if (color == WHITE) return alpha; else return beta;
}
// -------------------------------------------------
// Alpha Beta Search with Transposition(Hash) Table
// -------------------------------------------------
short ABSearch(int color, int ahead, short alpha, short beta, int &bestmove)
{
short Max, i, temp;
int value, nextbest, nM;
unsigned long indexTT, checksumTT;
// Check to see if move time has run out every 100,000 nodes
if (nodes > nodes2 + 100000 )
{
endtime = clock ();
nodes2 = nodes;
// If time has run out, we allow running up to 2*Time if g_bEndHard == FALSE and we are still searching a depth
if ( (endtime - starttime) > (CLOCKS_PER_SEC * fMaxSeconds) )
if ((endtime - starttime) > (2* CLOCKS_PER_SEC * fMaxSeconds) || g_bEndHard == TRUE || g_SearchingMove == 0 || abs(g_SearchEval) > 1500 )
return TIMEOUT;
}
// Use Internal Iterative Deepening to set bestmove if there's no best move
if (bestmove == NONE && (SearchDepth-ahead) > 3 )
{
SearchDepth-=4; // Reduce searchdepth by 4
ABSearch (color, ahead, alpha, beta, bestmove);
SearchDepth+=4;
}
// Find possible moves (and set a couple variables)
if (color == WHITE)
{
Max = -9999;
g_Movelist[ahead].FindMovesWhite(g_Boardlist[ahead-1].Sqs );
}
else
{
Max = 9999;
g_Movelist[ahead].FindMovesBlack(g_Boardlist[ahead-1].Sqs );
}
// If you can't move, you lose the game
if (g_Movelist[ahead].nMoves == 0)
{if (color == WHITE) return -2001+ahead;
else return 2001 - ahead;
}
// Run through the g_Movelist, doing each move
for (i = 0; i <= g_Movelist[ahead].nMoves; i++)
{
// if bestmove is set, try Best Move at i=0, and skip it later
if (i == bestmove) continue;
if (i == 0)
{if (bestmove == NONE) continue;
nM = bestmove;
}
else nM = i;
if (ahead == 1)
{
g_SearchingMove = i;
if (i > bestmove) g_SearchingMove--;
g_SearchEval = Max;
if (SearchDepth > 12) RunningDisplay ();
}
// Reset the move board to the one it was called with, then do the move # nM in the Movelist
g_Boardlist[ahead] = g_Boardlist[ahead-1];
temp = DoMove(g_Movelist[ahead].Moves[nM] , g_Boardlist[ahead], SEARCHED);
nodes++;
// If the game is over, return a gameover value now
if (g_Boardlist[ahead].nWhite == 0 || g_Boardlist[ahead].nBlack == 0)
{
bestmove = nM;
return g_Boardlist[ahead].EvaluateBoard ( ahead, 0, -100000, 100000);
}
// If this is the max depth, quiesce then evaluate the board position
if (ahead >= SearchDepth)
{
value = QuiesceBoard ( (color^3) , ahead+1, alpha, beta );
}
//If this isn't the max depth, or a repetition, continue to look ahead
else {value = -9999; nextbest = NONE;
// Look up the this Position in the Transposition Table
if (ahead < (SearchDepth - 3) && hashing == 1 )
{
indexTT = ((unsigned long)g_Boardlist[ahead].HashKey) % HASHTABLESIZE;
checksumTT = (unsigned long)(g_Boardlist[ahead].HashKey>>32);
TTable [ indexTT ].Read ( checksumTT, alpha, beta, nextbest, value, SearchDepth - ahead, ahead);
}
// If value wasn't set from the Transposition Table look ahead further with a recursive call
if (value == -9999)
{
// call ABSearch with opposite color & ahead incremented
value = ABSearch( (color^3) , ahead+1 , alpha, beta, nextbest);
if (value == TIMEOUT) return value;
// Store for the search info for this position in the Transposition Table
if (ahead < (SearchDepth - 3) && hashing == 1)
{
TTable [ indexTT ].Write ( checksumTT, alpha, beta, nextbest, value, SearchDepth - ahead, ahead);
}
}
}
// Penalize moves at root that repeat positions, so hopefully the computer will always make progress if possible
if (ahead == 1 && abs(value)<1000)
{
if ( Repetition ( g_Boardlist[ahead].HashKey, g_nMoves+1) ) value = (value>>1) + (value>>2);
else if (temp == 0) {if (color == WHITE) value-=1; else value+=1;} // if moves are the same, prefer the non-repeatable move
}
// Keep Track of Best Move and Alpha-Beta Prune
if (color==WHITE && value > Max )
{
Max = value;
bestmove = nM;
if (Max > alpha) alpha = Max;
if (alpha >= beta ) return beta;
}
if (color==BLACK && value < Max )
{
Max = value;
bestmove = nM;
if (Max < beta) beta = Max;
if (alpha >= beta ) return alpha;
}
} // end for
return Max;
}
// -------------------------------------------------
// The computer calculates a move then updates g_CBoard.
// -------------------------------------------------
void ComputerMove ( char cColor, CBoard &InBoard)
{
int LastEval = 0, Eval, nps = 0, nDoMove = NONE;
int bestmove = NONE;
CBoard TempBoard;
CMoveList Movelist;
// return if game is over
if (InBoard.nBlack == 0 || InBoard.nWhite == 0) return;
SetCursor ( LoadCursor ( NULL, IDC_WAIT ) );
if (cColor == BLACK) Movelist.FindMovesBlack(InBoard.Sqs );
if (cColor == WHITE) Movelist.FindMovesWhite(InBoard.Sqs );
// Do the first move randomly to add some variation.
if (g_nMoves == 0)
{
nDoMove = rand() % 7 + 1;
SearchDepth = 0;
}
else// Otherwise minimax search
{
ReplayGame ( g_nMoves, InBoard); // Make sure the repetition checker has all the values needed.
// Initialize variables (node count, start time, search depth)
nodes = 0;
nodes2 = 0;
starttime = clock ();
endtime = starttime;
if (g_MaxDepth < 4) SearchDepth = g_MaxDepth-2;
else if (g_MaxDepth < 8 ) SearchDepth = 2;
else SearchDepth = 6;
Eval = 0;
// Iteratively deepen until until the computer runs out of time, or reaches 22 ply
while ( SearchDepth < g_MaxDepth && Eval!=TIMEOUT)
{
SearchDepth +=2;
g_Boardlist[0] = InBoard;
g_Boardlist[0].HashKey = TEntry::HashBoard ( g_Boardlist[0] );
Eval = ABSearch (cColor, 1, -4000, 4000, bestmove);
if (bestmove!=NONE) nDoMove = bestmove;
if (Eval!=TIMEOUT)
{
g_SearchingMove = 0;
LastEval = Eval;
TempBoard = g_Boardlist[0];
// Check if there is only one legal move, if so don't keep searching
if (Movelist.nMoves == 1 && g_MaxDepth > 6) Eval = TIMEOUT;
}
else
{
if (abs(g_SearchEval) < 3000) LastEval = g_SearchEval;
if (g_SearchingMove == 0) SearchDepth-=2;
}
if (abs (Eval) > 2001-SearchDepth ) Eval = TIMEOUT; // found a win, can stop searching now
}
}
if ( (clock ()-starttime) < (CLOCKS_PER_SEC/4) ) Sleep (500); // pause a bit if move is really quick
if (nDoMove != NONE)
{
DoMove(Movelist.Moves[nDoMove], InBoard , MAKEMOVE );
g_GameMoves [ g_nMoves++ ] = Movelist.Moves[nDoMove];
g_GameMoves [ g_nMoves ].SrcDst = 0;
}
DrawBoard ( InBoard );
DisplaySearchInfo ( InBoard, SearchDepth, LastEval, nodes);
SetCursor ( LoadCursor ( NULL, IDC_ARROW ) );
}
// -----------------------
// Move Being Searched
// -----------------------
void inline RunningDisplay ()
{
static char sTemp[96];
static int LastEval = 0;
if (abs (g_SearchEval) < 3000) LastEval = g_SearchEval;
sprintf(sTemp,"Depth: %d (%d/%d) \nEval: %d\n", SearchDepth, g_SearchingMove, g_Movelist[1].nMoves, LastEval);
DisplayText (sTemp);
}
// -------------------------------------------------
// Print some info on the search just completed for the user
// -------------------------------------------------
void DisplaySearchInfo ( CBoard &InBoard, int SearchDepth, int Eval, int nodes )
{
char sTemp[5000];
int nps = 0, j = 0;
j+=sprintf(sTemp+j,"Red: %d White: %d ", InBoard.nBlack, InBoard.nWhite);
if (g_MaxDepth < 8) j+=sprintf(sTemp+j, "Level: Beginner\n");
else j+=sprintf(sTemp+j, "Level: Normal\n");
j+=sprintf(sTemp+j,"Eval: %d KNodes: %d \n",(Eval ), (nodes/1000) );
float fDiv = float (endtime - starttime) * CLOCKS_PER_SEC / 1000;
if ( fDiv <= 0.0f) nps = 0;
else nps = int (float(nodes) / fDiv);
if (endtime == starttime) nps = 0;
if (g_SearchingMove == 0) j+=sprintf(sTemp+j,"Depth: %d KN/Sec: %d \n", SearchDepth, nps );
else j+=sprintf(sTemp+j,"Depth: %d(%d/%d) KN/Sec: %d \n", SearchDepth, g_SearchingMove, g_Movelist[1].nMoves, nps );
DisplayText (sTemp);
}
// ===============================================
//
// G U I S T U F F
//
// ===============================================
void DisplayText ( char *sText)
{
if (BottomWnd == NULL) return;
SetDlgItemText (BottomWnd, 150, sText);
}
// INITILIZATION FUNCTION
static int AnyInstance (HINSTANCE this_inst)
{
// create main window
MainWnd = CreateWindow( "CheckClass", g_sNameVer,
WS_OVERLAPPEDWINDOW | WS_CLIPCHILDREN,
CW_USEDEFAULT, CW_USEDEFAULT, 620, 650, // x,y Position x,y Size
NULL, NULL, this_inst, NULL);
if (MainWnd == NULL) return (FALSE);
BottomWnd = CreateDialog( this_inst, "BotWnd", MainWnd, (DLGPROC)InfoProc);
// Load Piece Bitmaps
char* psBitmapNames[10] = {NULL, "Rcheck", "Wcheck", NULL, NULL, "RKing", "Wking", "Wsquare", "Bsquare", NULL};
for (int i = 0; i < 9; i++)
{
if (psBitmapNames[i] != NULL)
PieceBitmaps [ i ] = (HBITMAP)LoadImage ( this_inst, psBitmapNames[i], IMAGE_BITMAP, 0, 0, 0 );
}
MoveWindow (BottomWnd, 0, 550, 680, 150, TRUE);
ShowWindow (MainWnd, SW_SHOW);
TEntry::Create_HashFunction ( );
g_CBoard.StartPosition();
DrawBoard ( g_CBoard );
return (TRUE);
}
// ------------------------------------
// FirstInstance - register window class for the application,
// ------------------------------------
static void RegisterClass( HINSTANCE this_inst )
{
WNDCLASS wc;
wc.style = CS_HREDRAW | CS_VREDRAW;
wc.lpfnWndProc = WindowProc;
wc.cbClsExtra = 0;
wc.cbWndExtra = sizeof( DWORD );
wc.hInstance = this_inst;
wc.hIcon = LoadIcon( this_inst, "chIcon" );
wc.hCursor = NULL;
wc.hbrBackground = (HBRUSH)GetStockObject( DKGRAY_BRUSH );
wc.lpszMenuName = "CheckMenu";
wc.lpszClassName = "CheckClass";
BOOL rc = RegisterClass( &wc );
}
// ------------------------------------
// WinMain - initialization, message loop
// ------------------------------------
int PASCAL WinMain( HINSTANCE this_inst, HINSTANCE prev_inst, LPSTR cmdline,
int cmdshow )
{
MSG msg;
if( !prev_inst ) RegisterClass( this_inst );
if (AnyInstance( this_inst ) == FALSE) return (FALSE);
while( GetMessage( &msg, NULL, NULL, NULL ) ) {
TranslateMessage( &msg );
DispatchMessage( &msg );
}
return( msg.wParam );
}
//---------------------------------------------------------
//Draw a frame around a square clicked on by user
//----------------------------------------------------------
void HighlightSquare ( HDC hdc, int Square, int sqSize, int bRedraw, unsigned long color, int border)
{
HBRUSH brush;
RECT rect;
brush = CreateSolidBrush ( color );
if (Square >= 0 && Square <=63)
{
int x=Square%8, y=Square/8;
if (BoardFlip == 1) {x = 7-x; y = 7-y;}
rect.left = x*sqSize + g_xAdd;
rect.right = (x+1)*sqSize + g_xAdd;
rect.top = y * sqSize + g_yAdd;
rect.bottom = (y+1)*sqSize + g_yAdd;
FrameRect(hdc, &rect, brush);
if (border == 2)
{
rect.left+=1; rect.right -=1; rect.top+=1; rect.bottom-=1;
FrameRect(hdc, &rect, brush);
}
}
DeleteObject( brush );
}
//---------------------------------------------------------------
// Function to Draw a single Bitmap
// --------------------------------------------------------------
void DrawBitmap( HDC hdc, HBITMAP bitmap, int x, int y, int nSize )
{
BITMAP bitmapbuff;
HDC memorydc;
POINT origin, size;
memorydc = CreateCompatibleDC( hdc );
SelectObject( memorydc, bitmap );
SetMapMode( memorydc, GetMapMode( hdc ) );
GetObject( bitmap, sizeof( BITMAP ), (LPSTR) &bitmapbuff );
origin.x = x;
origin.y = y;
if (nSize ==0)
{size.x = bitmapbuff.bmWidth;
size.y = bitmapbuff.bmHeight;
}
else
{size.x = nSize;
size.y = nSize;
}
DPtoLP( hdc, &origin, 1 );
DPtoLP( memorydc, &size, 1 );
if (nSize == bitmapbuff.bmWidth)
{
BitBlt( hdc, origin.x, origin.y, size.x, size.y, memorydc, 0, 0, SRCCOPY);
}
else {
SetStretchBltMode( hdc, COLORONCOLOR/*STRETCH_HALFTONE*/ );
SetBrushOrgEx( hdc, 0, 0, NULL);
StretchBlt( hdc, origin.x, origin.y, size.x, size.y, memorydc, 0, 0, bitmapbuff.bmWidth, bitmapbuff.bmHeight, SRCCOPY);
}
DeleteDC( memorydc );
}
// ------------------
// Draw Board
// ------------------
void DrawBoard (const CBoard &board)
{
HDC hdc = GetDC (MainWnd);
int i, start = 0, add = 1, add2 = 1, x = 0, y = 0, mul = 1;
int nSize = 64;
if (BoardFlip == 1) {start = 63;
add = -1;
add2 = 0;}
for (i = start; i>=0 && i<=63; i+=add)
{
// piece
if (board.Sqs [ BoardLoc[i] ] != EMPTY && board.Sqs [ BoardLoc[i] ] != INVALID) DrawBitmap (hdc, PieceBitmaps [ board.Sqs[ BoardLoc[i] ] ] , x*nSize*mul +g_xAdd , y*nSize*mul +g_yAdd, nSize );
// empty square
else if ( ((i%2 == 1) && (i/8)%2 == 1 ) || ((i%2 == 0) && (i/8)%2 == 0) )
DrawBitmap (hdc, PieceBitmaps [ 7 ] , x*nSize*mul +g_xAdd , y*nSize*mul +g_yAdd, nSize );
else DrawBitmap (hdc, PieceBitmaps [ 8 ] , x*nSize*mul +g_xAdd , y*nSize*mul +g_yAdd, nSize );
x++;
if (x == 8){x = 0; y++;}
}
if (g_nSelSquare != NONE) HighlightSquare ( hdc, g_nSelSquare, g_nSqSize, TRUE, 0xFFFFFF, 1);
ReleaseDC(MainWnd, hdc );
}
// ------------------
// Replay Game from Game Move History up to nMove
// ------------------
void ReplayGame ( int nMove, CBoard &Board )
{
int i = 0;
Board.StartPosition ();
while (g_GameMoves[i].SrcDst != 0 && i < nMove)
{
AddRepBoard ( Board.HashKey, i);
DoMove ( g_GameMoves[i], Board, SEARCHED);
i++;
}
g_nMoves = i;
}
// ------------------
// File I/O
// ------------------
void SaveGame ( char *sFilename)
{
FILE* pFile = fopen (sFilename, "wb");
if (pFile == NULL) return;
int i = 0;
while (g_GameMoves[i].SrcDst !=0)
{
fwrite (&g_GameMoves[i], sizeof (SMove), 1, pFile );
i++;
}
fwrite (&g_GameMoves[i], sizeof (SMove), 1, pFile );
fclose (pFile);
}
void LoadGame ( char *sFilename )
{
FILE* pFile = fopen (sFilename, "rb");
if (pFile == NULL) return;
int i = 0;
while (!feof (pFile))
{
fread (&g_GameMoves[i], sizeof (SMove), 1, pFile );
i++;
}
fclose (pFile);
ReplayGame ( 1000, g_CBoard);
DrawBoard (g_CBoard);
}
// ===============================================
// Process messages to the Bottom Window
// ===============================================
long CALLBACK InfoProc ( HWND hwnd, unsigned msg, UINT wparam, LONG lparam )
{
switch (msg)
{
case WM_COMMAND:
switch (LOWORD(wparam))
{
case IDC_PREV:
if (g_nMoves > 0)
{
g_nMoves--;
ReplayGame (g_nMoves, g_CBoard);
DrawBoard (g_CBoard);
}
break;
case IDC_NEXT:
g_nMoves++;
ReplayGame (g_nMoves, g_CBoard );
DrawBoard (g_CBoard);
break;
case IDC_START:
g_nMoves = 0;
ReplayGame (g_nMoves, g_CBoard );
DrawBoard (g_CBoard);
break;
case IDC_END:
g_nMoves = 1000;
ReplayGame (g_nMoves, g_CBoard );
DrawBoard (g_CBoard);
break;
case IDC_GO:
cCompColor = (char)g_CBoard.SideToMove;
ComputerMove ( cCompColor, g_CBoard );
break;
}
default:
return( DefWindowProc( hwnd, msg, wparam, lparam ) );
}
return (0);
}
// ===============================================
// Process messages to the MAIN Window
// ===============================================
long CALLBACK WindowProc( HWND hwnd, unsigned msg, UINT wparam, LONG lparam )
{
PAINTSTRUCT ps;
HDC hdc;
int nSquare;
int x, y;
switch (msg)
{
// Process Menu Commands
case WM_COMMAND:
switch (LOWORD(wparam))
{
case ID_GAME_FLIPBOARD:
BoardFlip^=1;
DrawBoard (g_CBoard);
break;
case ID_GAME_NEW:
g_nSelSquare = NONE;
g_nMoves = 0;
g_GameMoves [ g_nMoves ].SrcDst = 0;
g_CBoard.StartPosition();
DrawBoard ( g_CBoard );
if (cCompColor == BLACK) ComputerMove ( cCompColor, g_CBoard );
break;
case ID_GAME_COMPUTERMOVE:
cCompColor = (char)g_CBoard.SideToMove;
ComputerMove ( cCompColor, g_CBoard );
break;
case ID_GAME_COMPUTEROFF:
cCompColor = 0;
break;
case ID_GAME_HASHING:
hashing ^=1;
break;
case ID_GAME_CLEAR_HASH:
ZeroMemory (TTable, sizeof (TEntry) * HASHTABLESIZE );
break;
case ID_OPTIONS_BEGINNER:
g_MaxDepth = BEGINNER_DEPTH;
break;
case ID_OPTIONS_NORMAL:
g_MaxDepth = NORMAL_DEPTH;
break;
case ID_FILE_SAVEGAME:
SaveGame ("save.chk");
break;
case ID_FILE_LOADGAME:
LoadGame ("save.chk");
break;
case ID_FILE_EXIT:
PostMessage (hwnd, WM_DESTROY, 0, 0);
break;
}
break;
// Process Mouse Clicks on the board
case WM_LBUTTONDOWN:
SetFocus (hwnd);
x = (int)(short)LOWORD(lparam );
y = (int)(short)HIWORD(lparam );
// Calculate the square the user clicked on (0-63)
x = (x-g_xAdd) / g_nSqSize;
y = (y-g_yAdd) / g_nSqSize;
if (BoardFlip == 1) {x=7-x; y = 7-y;}
nSquare = x + y*8;
// Did the user click on his/her own piece?
if (nSquare >=0 && nSquare <=63 && g_CBoard.Sqs [ BoardLoc[nSquare] ] != EMPTY)
{
if (( (g_CBoard.Sqs [ BoardLoc[nSquare] ]&BPIECE) && g_CBoard.SideToMove == BLACK) ||
( (g_CBoard.Sqs [ BoardLoc[nSquare] ]&WPIECE) && g_CBoard.SideToMove == WHITE ))
{
g_nSelSquare = nSquare;
if (g_nSelSquare != NONE)
{
DrawBoard (g_CBoard);
}
hdc = GetDC (MainWnd);
HighlightSquare ( hdc, g_nSelSquare, g_nSqSize, TRUE, 0xFFFFFF, 1);
ReleaseDC(MainWnd, hdc );
}
}
else // Did the user click on a valid destination square?
{
int MoveResult = SquareMove( g_CBoard, g_nSelSquare %8 , g_nSelSquare/8 , x, y, g_CBoard.SideToMove);
if (MoveResult == 1)
{
g_nSelSquare = NONE;
DrawBoard (g_CBoard);
if (cCompColor == g_CBoard.SideToMove) ComputerMove ( cCompColor, g_CBoard );
}
else if (MoveResult == DOUBLEJUMP)
{
g_nSelSquare = nSquare;
DrawBoard (g_CBoard);
}
}
return (TRUE);
case WM_SETCURSOR:
SetCursor ( LoadCursor ( NULL, IDC_ARROW ) );
return (TRUE);
case WM_PAINT:
hdc = BeginPaint (hwnd, &ps);
DrawBoard ( g_CBoard );
EndPaint(hwnd, &ps);
break;
case WM_DESTROY:
PostQuitMessage( 0 );
break;
default:
return( DefWindowProc( hwnd, msg, wparam, lparam ) );
}
return (0);
}
Sorry For the Length of the code...:(
I wanted to know how can i use the algorithm he has used to calculate the computer's move in my code.....??
I wanted to know how can i use the algorithm he has used to calculate the computer's move in my code.....??
There isn't really a general "Artificial Intelligence Algorithm," though there are path-finding algorithms and such. What exactly is your question here?
And for the record 8 posts of code that doesn't even use tags will just discourage people from helping you. Give us the exact part of your code you have a question about.
And for the record 8 posts of code that doesn't even use tags will just discourage people from helping you. Give us the exact part of your code you have a question about.
i think this part has the algorithms...
// =================================================
//
// MOVE GENERATION
//
// =================================================
//
// MoveList Structures
//
struct SMove
{
unsigned long SrcDst;
char cPath[8];
};
struct CMoveList
{
// FUNCTIONS
void inline SetMove (SMove &Move, int src, int dst)
{
Move.SrcDst = (src)+(dst<<6) + (1<<12);
}
void inline AddJump (SMove &Move, int pathNum)
{
Move.cPath[pathNum] = 0;
Moves [ ++nJumps ] = Move;
nMoves = nJumps;
}
void inline AddMove (int src, int dst)
{
if (nJumps != 0) return; // Ignore non-jumps if a jump move is present
Moves [ ++nMoves ].SrcDst = (src)+(dst<<6);
return;
}
void FindMovesBlack ( char board[]);
void FindMovesWhite ( char board[]);
void FindJumpsBlack ( char board[]);
void FindJumpsWhite ( char board[]);
void inline FindSqJumpsBlack ( char board[], int square, int nPiece, int pathNum, int nJumpSq);
void inline FindSqJumpsWhite ( char board[], int square, int nPiece, int pathNum, int nJumpSq);
// DATA
int nMoves, nJumps;
SMove Moves[32];
SMove m_JumpMove;
};
CMoveList g_Movelist[MAX_SEARCHDEPTH];
SMove g_GameMoves [ MAX_GAMEMOVES ];
//
// Now the Movelist functions, which come in pairs for each color
//
// -------------------------------------------------
// Find the Moves available on board, and store them in Movelist
// -------------------------------------------------
void CMoveList::FindMovesBlack ( char board[])
{
// Clear the Move list
nJumps = 0;
nMoves = 0;
// Now loop through the legals squares on the board looking for black pieces
for (register int square = 40; square >= 5; square--)
{
if ( (board[ square ]&BPIECE) ) // found a black piece
{
// Check for normal move
if ( board[square + 4 ] == EMPTY ) AddMove (square , square +4);
// If normal move not possible, check for a jump
else if ( (board[square + 4 ]&WPIECE) && board[square + 8 ] == EMPTY)
{// A jump is possible, call FindSqJumpsBlack to detect double/triple/etc. jumps
SetMove (m_JumpMove, square, square+8);
FindSqJumpsBlack ( board, square + 8, board[ square ], 0, square+4);}
// Again for the other forwards direction
if (board[square + 5 ] == EMPTY ) AddMove (square , square + 5);
else if ( (board[square + 5 ]&WPIECE) && board[square + 10] == EMPTY)
{SetMove (m_JumpMove, square, square+10);
FindSqJumpsBlack ( board, square + 10, board[ square ], 0, square+5);}
// Check to see if this is a king, if so check for backwards moves and jumps
if (board[ square ] == BKING )
{
if (board[square - 5 ] == EMPTY ) AddMove ( square , square - 5);
else if ( (board[square - 5 ]&WPIECE) && board[square - 10 ] == EMPTY )
{SetMove (m_JumpMove, square, square-10);
FindSqJumpsBlack ( board, square - 10, board[ square ], 0, square-5);}
if (board[square - 4 ] == EMPTY ) AddMove (square , square - 4);
else if ( (board[square - 4 ]&WPIECE) && board[square - 8 ] == EMPTY )
{SetMove (m_JumpMove, square, square- 8);
FindSqJumpsBlack ( board, square - 8, board[ square ], 0, square-4);}
}
}
}
}
// for WHITE
// This goes through the same process as the above does for black
void CMoveList::FindMovesWhite ( char board[])
{
nJumps = 0;
nMoves = 0;
for (register int square = 5; square <= 40; square++)
{
if ( (board[ square ]&WPIECE) )
{
if ( board[square - 4 ] == EMPTY ) AddMove ( square , square - 4); // Move
else if ((board[square - 4 ]&BPIECE) && board[square - 8 ] == 0 )
{SetMove (m_JumpMove, square, square-8);
FindSqJumpsWhite ( board, square - 8, board[ square ], 0, square-4);}
if ( board[square - 5 ] == EMPTY ) AddMove (square , square - 5);
else if ((board[square - 5 ]&BPIECE) && board[square - 10] == 0)
{SetMove (m_JumpMove, square, square-10);
FindSqJumpsWhite ( board, square - 10, board[ square ], 0, square-5);}
if (board[ square ] == WKING)
{
if ( board[square + 4 ] == EMPTY ) AddMove (square , square+4);
else if ( (board[square + 4 ]&BPIECE) && board[square + 8 ] == 0)
{SetMove (m_JumpMove, square, square+8);
FindSqJumpsWhite ( board, square + 8, board[ square ], 0, square+4);}
if ( board[square + 5 ] == EMPTY ) AddMove (square , square + 5);
else if ( (board[square + 5 ]&BPIECE) && board[square + 10 ] == 0)
{SetMove (m_JumpMove, square, square+10);
FindSqJumpsWhite ( board, square + 10, board[ square ], 0, square+5);}
}
}
}
}
// -------------------------------------------------
// These two functions only add jumps or moves that king a checker to the movelist
// they are used in the quiescence search
// -------------------------------------------------
void CMoveList::FindJumpsBlack ( char board[])
{
nJumps = 0; // Clear the Move list
nMoves = 0;
// Now look for moves
for (register int square = 5; square <= 40; square++)
{
if ( (board[ square ]&BPIECE) )
{
if ( (board[square + 4 ]&WPIECE) && board[square + 8 ] == EMPTY)
{SetMove (m_JumpMove, square, square+8); FindSqJumpsBlack ( board, square + 8, board[ square ], 0, square+4);}
if ( (board[square + 5 ]&WPIECE) && board[square + 10] == EMPTY)
{SetMove (m_JumpMove, square, square+10); FindSqJumpsBlack ( board, square + 10, board[ square ], 0, square+5);}
if (board[ square ] == BKING )
{
if ( (board[square - 5 ]&WPIECE) && board[square - 10 ] == EMPTY )
{SetMove (m_JumpMove, square, square-10); FindSqJumpsBlack ( board, square - 10, board[ square ], 0, square-5);}
if ( (board[square - 4 ]&WPIECE) && board[square - 8 ] == EMPTY )
{SetMove (m_JumpMove, square, square- 8); FindSqJumpsBlack ( board, square - 8, board[ square ], 0, square-4);}
}
}
}
}
// for WHITE
void CMoveList::FindJumpsWhite ( char board[])
{
nJumps = 0;
nMoves = 0;
for (register int square = 5; square <= 40; square++)
{
if ( (board[ square ]&WPIECE) )
{
if ((board[square - 4 ]&BPIECE) && board[square - 8 ] == 0 )
{SetMove (m_JumpMove, square, square-8); FindSqJumpsWhite ( board, square - 8, board[ square ], 0, square-4);}
if ((board[square - 5 ]&BPIECE) && board[square - 10] == 0)
{SetMove (m_JumpMove, square, square-10); FindSqJumpsWhite ( board, square - 10, board[ square ], 0, square-5);}
if (board[ square ] == WKING)
{
if ( (board[square + 4 ]&BPIECE) && board[square + 8 ] == 0)
{SetMove (m_JumpMove, square, square+8); FindSqJumpsWhite ( board, square + 8, board[ square ], 0, square+4);}
if ( (board[square + 5 ]&BPIECE) && board[square + 10 ] == 0)
{SetMove (m_JumpMove, square, square+10); FindSqJumpsWhite ( board, square + 10, board[ square ], 0, square+5);}
}
}
}
}
// =================================================
//
// MOVE GENERATION
//
// =================================================
//
// MoveList Structures
//
struct SMove
{
unsigned long SrcDst;
char cPath[8];
};
struct CMoveList
{
// FUNCTIONS
void inline SetMove (SMove &Move, int src, int dst)
{
Move.SrcDst = (src)+(dst<<6) + (1<<12);
}
void inline AddJump (SMove &Move, int pathNum)
{
Move.cPath[pathNum] = 0;
Moves [ ++nJumps ] = Move;
nMoves = nJumps;
}
void inline AddMove (int src, int dst)
{
if (nJumps != 0) return; // Ignore non-jumps if a jump move is present
Moves [ ++nMoves ].SrcDst = (src)+(dst<<6);
return;
}
void FindMovesBlack ( char board[]);
void FindMovesWhite ( char board[]);
void FindJumpsBlack ( char board[]);
void FindJumpsWhite ( char board[]);
void inline FindSqJumpsBlack ( char board[], int square, int nPiece, int pathNum, int nJumpSq);
void inline FindSqJumpsWhite ( char board[], int square, int nPiece, int pathNum, int nJumpSq);
// DATA
int nMoves, nJumps;
SMove Moves[32];
SMove m_JumpMove;
};
CMoveList g_Movelist[MAX_SEARCHDEPTH];
SMove g_GameMoves [ MAX_GAMEMOVES ];
//
// Now the Movelist functions, which come in pairs for each color
//
// -------------------------------------------------
// Find the Moves available on board, and store them in Movelist
// -------------------------------------------------
void CMoveList::FindMovesBlack ( char board[])
{
// Clear the Move list
nJumps = 0;
nMoves = 0;
// Now loop through the legals squares on the board looking for black pieces
for (register int square = 40; square >= 5; square--)
{
if ( (board[ square ]&BPIECE) ) // found a black piece
{
// Check for normal move
if ( board[square + 4 ] == EMPTY ) AddMove (square , square +4);
// If normal move not possible, check for a jump
else if ( (board[square + 4 ]&WPIECE) && board[square + 8 ] == EMPTY)
{// A jump is possible, call FindSqJumpsBlack to detect double/triple/etc. jumps
SetMove (m_JumpMove, square, square+8);
FindSqJumpsBlack ( board, square + 8, board[ square ], 0, square+4);}
// Again for the other forwards direction
if (board[square + 5 ] == EMPTY ) AddMove (square , square + 5);
else if ( (board[square + 5 ]&WPIECE) && board[square + 10] == EMPTY)
{SetMove (m_JumpMove, square, square+10);
FindSqJumpsBlack ( board, square + 10, board[ square ], 0, square+5);}
// Check to see if this is a king, if so check for backwards moves and jumps
if (board[ square ] == BKING )
{
if (board[square - 5 ] == EMPTY ) AddMove ( square , square - 5);
else if ( (board[square - 5 ]&WPIECE) && board[square - 10 ] == EMPTY )
{SetMove (m_JumpMove, square, square-10);
FindSqJumpsBlack ( board, square - 10, board[ square ], 0, square-5);}
if (board[square - 4 ] == EMPTY ) AddMove (square , square - 4);
else if ( (board[square - 4 ]&WPIECE) && board[square - 8 ] == EMPTY )
{SetMove (m_JumpMove, square, square- 8);
FindSqJumpsBlack ( board, square - 8, board[ square ], 0, square-4);}
}
}
}
}
// for WHITE
// This goes through the same process as the above does for black
void CMoveList::FindMovesWhite ( char board[])
{
nJumps = 0;
nMoves = 0;
for (register int square = 5; square <= 40; square++)
{
if ( (board[ square ]&WPIECE) )
{
if ( board[square - 4 ] == EMPTY ) AddMove ( square , square - 4); // Move
else if ((board[square - 4 ]&BPIECE) && board[square - 8 ] == 0 )
{SetMove (m_JumpMove, square, square-8);
FindSqJumpsWhite ( board, square - 8, board[ square ], 0, square-4);}
if ( board[square - 5 ] == EMPTY ) AddMove (square , square - 5);
else if ((board[square - 5 ]&BPIECE) && board[square - 10] == 0)
{SetMove (m_JumpMove, square, square-10);
FindSqJumpsWhite ( board, square - 10, board[ square ], 0, square-5);}
if (board[ square ] == WKING)
{
if ( board[square + 4 ] == EMPTY ) AddMove (square , square+4);
else if ( (board[square + 4 ]&BPIECE) && board[square + 8 ] == 0)
{SetMove (m_JumpMove, square, square+8);
FindSqJumpsWhite ( board, square + 8, board[ square ], 0, square+4);}
if ( board[square + 5 ] == EMPTY ) AddMove (square , square + 5);
else if ( (board[square + 5 ]&BPIECE) && board[square + 10 ] == 0)
{SetMove (m_JumpMove, square, square+10);
FindSqJumpsWhite ( board, square + 10, board[ square ], 0, square+5);}
}
}
}
}
// -------------------------------------------------
// These two functions only add jumps or moves that king a checker to the movelist
// they are used in the quiescence search
// -------------------------------------------------
void CMoveList::FindJumpsBlack ( char board[])
{
nJumps = 0; // Clear the Move list
nMoves = 0;
// Now look for moves
for (register int square = 5; square <= 40; square++)
{
if ( (board[ square ]&BPIECE) )
{
if ( (board[square + 4 ]&WPIECE) && board[square + 8 ] == EMPTY)
{SetMove (m_JumpMove, square, square+8); FindSqJumpsBlack ( board, square + 8, board[ square ], 0, square+4);}
if ( (board[square + 5 ]&WPIECE) && board[square + 10] == EMPTY)
{SetMove (m_JumpMove, square, square+10); FindSqJumpsBlack ( board, square + 10, board[ square ], 0, square+5);}
if (board[ square ] == BKING )
{
if ( (board[square - 5 ]&WPIECE) && board[square - 10 ] == EMPTY )
{SetMove (m_JumpMove, square, square-10); FindSqJumpsBlack ( board, square - 10, board[ square ], 0, square-5);}
if ( (board[square - 4 ]&WPIECE) && board[square - 8 ] == EMPTY )
{SetMove (m_JumpMove, square, square- 8); FindSqJumpsBlack ( board, square - 8, board[ square ], 0, square-4);}
}
}
}
}
// for WHITE
void CMoveList::FindJumpsWhite ( char board[])
{
nJumps = 0;
nMoves = 0;
for (register int square = 5; square <= 40; square++)
{
if ( (board[ square ]&WPIECE) )
{
if ((board[square - 4 ]&BPIECE) && board[square - 8 ] == 0 )
{SetMove (m_JumpMove, square, square-8); FindSqJumpsWhite ( board, square - 8, board[ square ], 0, square-4);}
if ((board[square - 5 ]&BPIECE) && board[square - 10] == 0)
{SetMove (m_JumpMove, square, square-10); FindSqJumpsWhite ( board, square - 10, board[ square ], 0, square-5);}
if (board[ square ] == WKING)
{
if ( (board[square + 4 ]&BPIECE) && board[square + 8 ] == 0)
{SetMove (m_JumpMove, square, square+8); FindSqJumpsWhite ( board, square + 8, board[ square ], 0, square+4);}
if ( (board[square + 5 ]&BPIECE) && board[square + 10 ] == 0)
{SetMove (m_JumpMove, square, square+10); FindSqJumpsWhite ( board, square + 10, board[ square ], 0, square+5);}
}
}
}
}
// -------------
// If a jump move was possible, we must make the jump then check
// to see if the same piece can jump again.
// There might be multiple paths a piece can take on a double jump, these functions
// store each possible path as a move.
// -------------
void CMoveList::FindSqJumpsBlack ( char board[], int square, int nPiece, int pathNum, int nJumpSq)
{
int nSqMoves = 0;
// Remove the jumped piece (until the end of this function), so we can't jump it again
int nJumpPiece = board [ nJumpSq ];
board [ nJumpSq ] = EMPTY;
// Now see if a piece on this square has more jumps
if ( (board[square + 4 ]&WPIECE) && board[square + 8 ] == EMPTY )
{m_JumpMove.cPath[ pathNum ] = 8; nSqMoves++; FindSqJumpsBlack ( board, square+8, nPiece, pathNum+1, square+4); }
if ( (board[square + 5 ]&WPIECE) && board[square + 10] == EMPTY )
{m_JumpMove.cPath[ pathNum ] = 10; nSqMoves++; FindSqJumpsBlack ( board, square+10, nPiece, pathNum+1, square+5); }
if ( nPiece == BKING)
{// If this pieces is a king, it can also jump backwards
if ( (board[square - 5 ]&WPIECE) && board[square - 10] == EMPTY )
{m_JumpMove.cPath[ pathNum ] = -10; nSqMoves++; FindSqJumpsBlack ( board, square-10, nPiece, pathNum+1, square-5); }
if ( (board[square - 4 ]&WPIECE) && board[square - 8 ] == EMPTY )
{m_JumpMove.cPath[ pathNum ] = -8; nSqMoves++; FindSqJumpsBlack ( board, square-8, nPiece, pathNum+1, square-4); }
}
if (nSqMoves == 0) AddJump (m_JumpMove, pathNum); // this is a leaf, so store the move
// Put back the jumped piece
board [ nJumpSq ] = nJumpPiece;
}
void CMoveList::FindSqJumpsWhite ( char board[], int square, int nPiece, int pathNum, int nJumpSq)
{
int nSqMoves = 0;
int nJumpPiece = board [ nJumpSq ];
board [ nJumpSq ] = EMPTY;
if ( (board[square - 4 ]&BPIECE) && board[square - 8 ] == EMPTY )
{m_JumpMove.cPath[ pathNum ] = -8; nSqMoves++; FindSqJumpsWhite ( board, square-8, nPiece, pathNum+1, square-4); }
if ( (board[square - 5 ]&BPIECE) && board[square - 10] == EMPTY )
{m_JumpMove.cPath[ pathNum ] = -10; nSqMoves++; FindSqJumpsWhite ( board, square-10, nPiece, pathNum+1, square-5); }
if ( nPiece == WKING)
{
if ( (board[square + 5 ]&BPIECE) && board[square + 10] == EMPTY )
{m_JumpMove.cPath[ pathNum ] = 10; nSqMoves++; FindSqJumpsWhite ( board, square+10, nPiece, pathNum+1, square+5); }
if ( (board[square + 4 ]&BPIECE) && board[square + 8 ] == EMPTY )
{m_JumpMove.cPath[ pathNum ] = +8; nSqMoves++; FindSqJumpsWhite ( board, square+8, nPiece, pathNum+1, square+4); }
}
if (nSqMoves == 0) AddJump (m_JumpMove, pathNum);
board [ nJumpSq ] = nJumpPiece;
}
// =================================================
//
// MOVE EXECUTION
//
// =================================================
// ---------------------
// Helper Functions for DoMove
// ---------------------
void inline DoSingleJump (CBoard &board, int src, int dst, int nPiece)
{
int jumpedSq = (dst + src) >> 1;
if (board.Sqs [ jumpedSq ] == WPIECE ) {board.nWhite--;}
else if (board.Sqs [jumpedSq ] == BPIECE) {board.nBlack--;}
else if (board.Sqs [jumpedSq ] == BKING) {board.nBlack--; board.nEval+=KINGEVAL;}
else if (board.Sqs [jumpedSq ] == WKING) {board.nWhite--; board.nEval-=KINGEVAL;}
board.HashKey ^= HashFunction [ src ][ nPiece ] ^ HashFunction [ dst ][ nPiece ] ^ HashFunction [ jumpedSq ][ board.Sqs [ jumpedSq ] ];
// Update the board array
board.Sqs [ dst ] = nPiece;
board.Sqs [ jumpedSq ] = EMPTY;
board.Sqs [ src ] = EMPTY;
}
// This function will test if a checker needs to be upgraded to a king, and upgrade if necessary
void inline CheckKing (CBoard &board, int dst, int nPiece)
{
if (dst <= 8 && nPiece == WPIECE)
{board.Sqs [ dst ] = WKING;
board.nEval+=KINGEVAL;
board.HashKey ^= HashFunction [ dst ][ nPiece ] ^ HashFunction [ dst ][ WKING ];
}
if (dst >= 37 && nPiece == BPIECE)
{board.Sqs [ dst ] = BKING;
board.nEval-=KINGEVAL;
board.HashKey ^= HashFunction [ dst ][ nPiece ] ^ HashFunction [ dst ][ BKING ];
}
}
// ---------------------
// Execute a Move
// ---------------------
int DoMove (SMove &Move, CBoard &board, int nType)
{
// Get Info From Move
unsigned int ulMove = Move.SrcDst;
unsigned int src = (ulMove&63);
unsigned int dst = (ulMove>>6)&63;
unsigned int bJump = (ulMove>>12);
unsigned int nPiece = board.Sqs [src];
board.SideToMove ^=3;
board.HashKey = ~board.HashKey; // Flip hash stm
if (bJump == 0)
{
// Update hash values
board.HashKey ^= HashFunction [ src ][ nPiece ] ^ HashFunction [ dst ][ nPiece ];
// Update the board array
board.Sqs [ dst ] = board.Sqs [ src ];
board.Sqs [ src ] = EMPTY;
// Update King Evaluation incrementally
if (nPiece == BKING) board.nEval -= KBoard[ dst ] - KBoard [ src ];
else if (nPiece == WKING) board.nEval += KBoard[ dst ] - KBoard [ src ];
else
{CheckKing ( board, dst, nPiece );
return 1;}
return 0;
}
DoSingleJump (board, src, dst, nPiece);
CheckKing ( board, dst, nPiece );
// Double Jump?
if (Move.cPath [0] == 0) return 1;
if (nType == HUMAN) return DOUBLEJUMP;
for (int i = 0; i < 8; i++)
{
int nDir = Move.cPath [i];
if (nDir == 0) break;
if (nType == MAKEMOVE)
{DrawBoard ( board );
Sleep (300);// pause a bit on displaying double jumps
}
DoSingleJump (board, dst, dst+nDir, nPiece);
dst+=nDir;
}
CheckKing ( board, dst, nPiece );
return 1;
}
// ---------------------------------------------
// Check Possiblity/Execute Move from one selected square to another
// returns 0 if the move is not possible, otherwise 1, or a double jump value the move is an uncompleted jump
// ---------------------------------------------
int SquareMove( CBoard &Board, int x , int y, int xloc, int yloc, char cColor)
{
int i, src, dst, nMSrc, nMDst;
CMoveList MoveList;
if (cColor == BLACK)
MoveList.FindMovesBlack (Board.Sqs);
else MoveList.FindMovesWhite (Board.Sqs);
for (i = 1; i <= MoveList.nMoves; i++)
{
dst = BoardLoc[xloc + yloc*8];
src = BoardLoc[x + y*8];
nMSrc = MoveList.Moves[i].SrcDst&63;
nMDst = (MoveList.Moves[i].SrcDst>>6)&63;
if ( nMSrc == src && nMDst == dst ) // Check if the src & dst match a move from the generated movelist
{
if (g_nDouble > 0) {g_GameMoves[g_nMoves-1].cPath[g_nDouble-1] = nMDst - nMSrc;
g_GameMoves[g_nMoves-1].cPath[ g_nDouble ] = 0;}
else
{
g_GameMoves [ g_nMoves ].SrcDst = MoveList.Moves[i].SrcDst;
g_GameMoves [ g_nMoves++ ].cPath[0] = 0;
g_GameMoves [ g_nMoves ].SrcDst = 0;
}
if (DoMove ( MoveList.Moves[i], Board, HUMAN) == DOUBLEJUMP)
{
g_nDouble++;
Board.SideToMove ^=3;
return DOUBLEJUMP;
}
g_nDouble = 0;
return 1;
}
}
return 0;
}
// ===============================================
//
// SEARCH
//
// ===============================================
// -------------------------------------------------
// Quiescence Search... Search all jumps, if there are no jumps, stop the search
// -------------------------------------------------
int QuiesceBoard ( int color, int ahead, int alpha, int beta )
{
int value;
// Find Jump Moves
if (color == WHITE)
{g_Movelist[ahead].FindJumpsWhite( g_Boardlist[ahead-1].Sqs );}
else
{g_Movelist[ahead].FindJumpsBlack( g_Boardlist[ahead-1].Sqs );}
// No more jump moves, return evaluation
if (g_Movelist[ahead].nJumps == 0 || (ahead+1) >= MAX_SEARCHDEPTH)
{
nodes++;
return g_Boardlist[ahead-1].EvaluateBoard ( ahead-1, 0, alpha, beta);
}
// There were jump moves, so we keep searching.
for (int i = 1; i <= g_Movelist[ahead].nJumps; i++)
{
g_Boardlist[ahead] = g_Boardlist[ahead-1];
DoMove(g_Movelist[ahead].Moves[i] , g_Boardlist[ahead], SEARCHED);
nodes++;
// Recursive Call
value = QuiesceBoard( (color^3) , ahead+1 , alpha, beta);
// Keep Track of Best Move and Alpha-Beta Prune
if (color == WHITE && value > alpha )
{
alpha = value;
if (alpha >= beta ) return beta;
}
if (color == BLACK && value < beta )
{
beta = value;
if (alpha >= beta ) return alpha;
}
}
if (color == WHITE) return alpha; else return beta;
}
// -------------------------------------------------
// Alpha Beta Search with Transposition(Hash) Table
// -------------------------------------------------
short ABSearch(int color, int ahead, short alpha, short beta, int &bestmove)
{
short Max, i, temp;
int value, nextbest, nM;
unsigned long indexTT, checksumTT;
// Check to see if move time has run out every 100,000 nodes
if (nodes > nodes2 + 100000 )
{
endtime = clock ();
nodes2 = nodes;
// If time has run out, we allow running up to 2*Time if g_bEndHard == FALSE and we are still searching a depth
if ( (endtime - starttime) > (CLOCKS_PER_SEC * fMaxSeconds) )
if ((endtime - starttime) > (2* CLOCKS_PER_SEC * fMaxSeconds) || g_bEndHard == TRUE || g_SearchingMove == 0 || abs(g_SearchEval) > 1500 )
return TIMEOUT;
}
// Use Internal Iterative Deepening to set bestmove if there's no best move
if (bestmove == NONE && (SearchDepth-ahead) > 3 )
{
SearchDepth-=4; // Reduce searchdepth by 4
ABSearch (color, ahead, alpha, beta, bestmove);
SearchDepth+=4;
}
// Find possible moves (and set a couple variables)
if (color == WHITE)
{
Max = -9999;
g_Movelist[ahead].FindMovesWhite(g_Boardlist[ahead-1].Sqs );
}
else
{
Max = 9999;
g_Movelist[ahead].FindMovesBlack(g_Boardlist[ahead-1].Sqs );
}
// If you can't move, you lose the game
if (g_Movelist[ahead].nMoves == 0)
{if (color == WHITE) return -2001+ahead;
else return 2001 - ahead;
}
// Run through the g_Movelist, doing each move
for (i = 0; i <= g_Movelist[ahead].nMoves; i++)
{
// if bestmove is set, try Best Move at i=0, and skip it later
if (i == bestmove) continue;
if (i == 0)
{if (bestmove == NONE) continue;
nM = bestmove;
}
else nM = i;
if (ahead == 1)
{
g_SearchingMove = i;
if (i > bestmove) g_SearchingMove--;
g_SearchEval = Max;
if (SearchDepth > 12) RunningDisplay ();
}
// Reset the move board to the one it was called with, then do the move # nM in the Movelist
g_Boardlist[ahead] = g_Boardlist[ahead-1];
temp = DoMove(g_Movelist[ahead].Moves[nM] , g_Boardlist[ahead], SEARCHED);
nodes++;
// If the game is over, return a gameover value now
if (g_Boardlist[ahead].nWhite == 0 || g_Boardlist[ahead].nBlack == 0)
{
bestmove = nM;
return g_Boardlist[ahead].EvaluateBoard ( ahead, 0, -100000, 100000);
}
// If this is the max depth, quiesce then evaluate the board position
if (ahead >= SearchDepth)
{
value = QuiesceBoard ( (color^3) , ahead+1, alpha, beta );
}
//If this isn't the max depth, or a repetition, continue to look ahead
else {value = -9999; nextbest = NONE;
// Look up the this Position in the Transposition Table
if (ahead < (SearchDepth - 3) && hashing == 1 )
{
indexTT = ((unsigned long)g_Boardlist[ahead].HashKey) % HASHTABLESIZE;
checksumTT = (unsigned long)(g_Boardlist[ahead].HashKey>>32);
TTable [ indexTT ].Read ( checksumTT, alpha, beta, nextbest, value, SearchDepth - ahead, ahead);
}
// If value wasn't set from the Transposition Table look ahead further with a recursive call
if (value == -9999)
{
// call ABSearch with opposite color & ahead incremented
value = ABSearch( (color^3) , ahead+1 , alpha, beta, nextbest);
if (value == TIMEOUT) return value;
// Store for the search info for this position in the Transposition Table
if (ahead < (SearchDepth - 3) && hashing == 1)
{
TTable [ indexTT ].Write ( checksumTT, alpha, beta, nextbest, value, SearchDepth - ahead, ahead);
}
}
}
// Penalize moves at root that repeat positions, so hopefully the computer will always make progress if possible
if (ahead == 1 && abs(value)<1000)
{
if ( Repetition ( g_Boardlist[ahead].HashKey, g_nMoves+1) ) value = (value>>1) + (value>>2);
else if (temp == 0) {if (color == WHITE) value-=1; else value+=1;} // if moves are the same, prefer the non-repeatable move
}
// Keep Track of Best Move and Alpha-Beta Prune
if (color==WHITE && value > Max )
{
Max = value;
bestmove = nM;
if (Max > alpha) alpha = Max;
if (alpha >= beta ) return beta;
}
if (color==BLACK && value < Max )
{
Max = value;
bestmove = nM;
if (Max < beta) beta = Max;
if (alpha >= beta ) return alpha;
}
} // end for
return Max;
}
Did you listen to anything anyone just said? Please don't just dump 15 posts worth of code. No one is going to read through it all, and you still haven't used code tags or asked a question!
Last edited on
Topic archived. No new replies allowed.