Move ordering

Intelligent move ordering is often the keystone to alphabeta/minimax algorithms.

Theoretically if you were to only ever search the two best moves first this would produce a cutoff and limit the search tree to a very small number of nodes.

The mathematical equation for calculating the total nodes searched, is the depth of the search to the power of the average node/branches at each node.

Say you are searching to a depth of 7, and the average move possibilities for each position is 28, this means the full search tree (like a brute force search), is 7^28, which is 4.5998654e+23, that’s 23 decimal places, whereas in alphabeta with perfect move ordering (theoretical – so far), is 7^2, which is 49! 49 positions searched to mathematically and/or logically determine the near exact value of the position being calculated, for the depth anyway, using bruteforce you’d have to wait 9.3874803e+21 as much time used to come to the SAME CONCLUSION!

Of course perfect move ordering is not always possible, but some of the best chess engines out there come fairly close, such as stockfish 5, Houdini and komodo.

For Echo I will keep to the rule of KISS, which means keep it simple, straightforward (or stupid!).

Evaluating capture to a numerical value/guesstimation I will have it count the number of attacks vs defenses, then proceed to test out those captures, possibly catching in between moves when necessary, and always capturing with the least valuable pieces first.

For more on the topic of ‘game complexity’ see this Wikipedia page, http://en.wikipedia.org/wiki/Game_complexity

Note that alphabeta is not our only option there are alternatives like negamax and negascout.

The move ordering will likely be one of the more complicated and intricate parts of Echo. We will be sorting all of the moves not just captures.

todo list

Here is a list of things to be added and/or programmed into Echo before it’s not a beta version anymore.

  • FEN parsing, UCI command “position fen …” FEN parsing will setup the internal board to the position represented by the FEN string.
  • Opening book
  • Alphabeta or Negamax minmax type algorithm
  • Heuristics
  • Evaluation function
  • Intelligent move ordering
  • Absolute pins algorithm
  • Debug (or rewrite) the check algorithms (may be returning double check when position is in fact single check).
  • Be able to parse/read input from interface while calculating bestmove (Alphabeta search).

 

Tidbits

If you are having trouble compiling my source code in code::blocks or gcc, just add ‘#include<cstdlib>’ at the top with the other includes. Sorry!

Going to start work on the minimax algorithm soon.. So far it’s just a random mover.

Source code published

July 27 2014, Today I am publishing the source code of Echo chess program.

On Feb 20th, 2014 I started from scratch to start work on Echo. Then I didn’t do anything for about 4 months, I began work on it again ~June 26th 2014 till about July 7th 2014. I have made it very straightforward so that new programmers can follow the logic and reasoning.

The first step is to make a random mover that chooses a LEGAL chess move out of a list of all possible legal chess moves in the given position, and does so randomly, from there it’s easy to make a thinking program by changing out the random choosing part with a minimax algorithm to search all logical continuations (but I’ve not started that part yet).

Here is the source code so far, keep in mind I have kept the entire program in one file – so far – it makes it easier to take a full snapshot (so to speak) of the program and save it in a passworded rar file named with a date and timestamp so I can see all changes so far and when i worked on it, and what days.

/*Note from the Author and license*/
/*This software is provided as is and is not given under any warranty or guarantee of fitness for any purpose */
/* Echo chess program v 0.7 is open source, personally written by the author and may be reused provided credit is given to the original author (deepglue5 @ lichess and chess.com)*/
 
#include
#include
#include
 
using namespace std;
 
// set each piece and pawn values as constant integers
const int pawn = 100;
const int knight = 300;
const int bishop = 305;
const int rook = 500;
const int queen = 900;
const int king = 20000;
 
// this is the board it will contain the pieces and pawns
// the first array is for files, the second array is ranks
// ie board[file][rank];
int board[8][8];
 
string enpassant;
 
// boolean containers for castling start all with true and become false if castling to their direction becomes broken in the game
// wkside is white kingside castling
// wqside is whites and queenside castling etc....
// If position is loaded from FEN, castling true or false is set according to FEN position
bool wkside;
bool wqside;
bool bkside;
bool bqside;
 
//onmove is a string that contains the character "w" when it is white to move and "b" when it is black to move
string onmove = "w";
void printboard(void);
int file2num(string);
string blackmoves(int, int);
string piece2char(int);
const int setupboard[8][8] = { rook, knight, bishop, queen, king, bishop, knight, rook, pawn, pawn,pawn,pawn,pawn,pawn,pawn, pawn, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -pawn, -pawn, -pawn, -pawn, -pawn, -pawn, -pawn, -pawn, -rook, -knight, -bishop, -queen, -king, -bishop, -knight, -rook};
 
void setupinit (void) {
 
int a;
int b;
 
onmove = "w";
 
wkside = true;
wqside = true;
bkside = true;
bqside = true;
 
enpassant = "";
 
for (a = 0; a < 8; a++){
for (b = 0; b < 8; b++){
board[a][b] = setupboard[a][b];
}
}
}
 
//function prototype
//prototype of function that generates all animal moves regardlessif it leaves or puts friendly king in check
//returns a string containing all moves 4 characters each
string whitemoves(int, int);
int rank2num(string);
int char2promote(char, string);
string checkwhite(int, int, int, int);
string checkblack(int, int, int, int);
 
string chfile(int);
string chrank(int);
 
bool bounds (int a, int b)
{
if ((a >= 0) && (a <= 7) && (b >= 0) && (b <= 7))
{
return true;
}
else
{
return false;
}
}
 
/* ######################## Main ####################################### */
int main (void){
using namespace std;
string passd;
string list;
int x4;
bool usebook = false;
int epsqa, epsqb;
epsqa = 8;
epsqb = 8;
srand ( time(NULL) );
//passd = "a";
//cout << file2num(passd);
//cin.get();
setupinit();
while (1){
getline (cin, passd );
 
if (passd == "uci\x0" )
{
cout << "id name Echo chess program v 0.7" << endl;
cout << "id author avery c. aka deepglue5 aka smackthat9876 @ youtube " << endl;
cout << "option name internal book type check default false" << endl;
//cout << "option name UCI_EngineAbout type string default http://www.website...." << endl; //unremark this to publish your chess engines website inside the executable
cout << "uciok" << endl;
}
if (passd == "ucinewgame\x0")
{
setupinit();
}
if (passd == "isready\x0") {
cout << "readyok" << endl;
}
if (passd == "setoption name internal book value false\x0"){
usebook = false;
cout << "info internal book off" << endl;
}
if (passd == "setoption name internal book value true\x0"){
usebook = true;
cout << "info internal book on" << endl;
}
if (passd == "quit\x0") {
cout << "Goodbye !!" << endl << "Thankyou for Playing Echo chess v 0.7";
goto end1;
}
if (passd.substr(0, 9) == "listmoves"){
if (onmove == "w") {
 
list = whitemoves(epsqa, epsqb);
}
else {
 
list = blackmoves(epsqa, epsqb);
}
cout << list << "\n";
}
if (passd.substr(0, 10) == "printboard"){
printboard();
}
if (passd.substr(0, 2) == "go"){
if (onmove == "w") {
 
list = whitemoves(epsqa, epsqb);
}
else {
 
list = blackmoves(epsqa, epsqb);
}
 
int x, m;
string move1;
x = list.length();
if (x == 0) goto noplay;
x = (x + 1) / 4;
 
m = rand() % x;
m *= 4;
 
move1 = list.substr(m, 4);
 
switch(move1[3]){
case 'q':
if(onmove == "w"){
move1[3] = '8';
}
else{
move1[3] = '1';
}
move1 = move1 + "q";
break;
case 'r':
if(onmove == "w"){
move1[3] = '8';
}
else{
move1[3] = '1';
}
move1 = move1 + "r";
break;
case 'b':
if(onmove == "w"){
move1[3] = '8';
}
else{
move1[3] = '1';
}
move1 = move1 + "b";
break;
case 'n':
if(onmove == "w"){
move1[3] = '8';
}
else{
move1[3] = '1';
}
move1 = move1 + "n"; //NOTE DON'T FORGET EN PASSANT
break;
}
cout << "bestmove " << move1 << '\n';
noplay:;
}
if (passd.substr(0,17) == "position startpos" && passd.length() <= 18) {
setupinit();
}
// -> position startpos moves etc...
if (passd.substr(0, 23) == "position startpos moves") {
int imax, i;
int a, b, c, d;
setupinit();
imax = passd.length();
for (i = 24; i < imax; i +=5 )
{
b = file2num(passd.substr(i, 1));
a = rank2num(passd.substr(i + 1, 1));
d = file2num(passd.substr(i + 2, 1));
c = rank2num(passd.substr(i + 3, 1));
 
if (board[a][b] == king && a == 0 && b == 4 && c == 0 && d == 6){ // castling white kingside
board[0][7] = 0;
board[0][5] = rook;
}
if (board[a][b] == king && b == 4 && d == 2){ //castling white queenside
board[0][0] = 0;
board[0][3] = rook;
}
if (board[a][b] == -king && b == 4 && d == 6){ //castling black kingside
board[7][7] = 0;
board[7][5] = -rook;
}
if (board[a][b] == -king && b == 4 && d == 2){ //castling black queenside
board[7][0] = 0;
board[7][4] = -rook;
}
switch (board[a][b]){ // Rook and King moves break castling
case rook:
if(a == 0 && b == 0){
wqside = false;
}
if(a == 0 && b == 7){
wkside = false;
}
break;
case -rook:
if(a == 7 && b == 0){
bqside = false;
}
if(a == 7 && b == 7){
bkside = false;
}
break;
case king:
wkside = false;
wqside = false;
break;
case -king:
bkside = false;
bqside = false;
break;
}
if(board[a][b] == pawn && a == 1 && c == 3) {
epsqa = 2;
epsqb = b;
}
if(board[a][b] == -pawn && a == 6 && c == 4) {
epsqa = 5;
epsqb = b;
}
if((board[a][b] != pawn && board[a][b] != -pawn) || (abs(a - c) != 2)){ //if the move is not a pawn move en passant is non set, or if it is a pawn move but not 2 ranks up or down
epsqa = 8;
epsqb = 8;
}
 
board[c][d] = board[a][b];
board[a][b] = 0;
 
string str;
x4 = passd.length();
if(passd.length() > unsigned(i + 4)){
 
str = passd[i + 4]; //next character at end of 4 move sequence may be a promotion
if (str != " " && !str.empty()){
board[c][d] = char2promote(passd[i + 4], onmove);
i++; // extra character in sequence of moves.
}
}
 
if (onmove == "w"){ onmove = "b"; }else {onmove = "w";}
}
}
}
end1:
return 0;
}
 
//actual function, generates all possible animal moves for white in string format ie (R@a1) "a1a2" + "a1a3" etc
string whitemoves(int epa, int epb){ //epa is integer for en passant square file, epb is en passant square rank, together they make a coordinate
string allmoves;
int fromSQa[218];
int fromSQb[218];
int toSQa[218];
int toSQb[218];
 
int a = 0;
int b = 0;
int c = 0;
int d = 0;
int e = 0;
int f = 0;
int z = 0;
string promotions;
int i2;
 
promotions = "qrbn";
 
for (a = 0; a < 8; a++){
for (b = 0; b < 8; b++){
switch (board[a][b]) {
 
case queen:
{
for (e = -1; e <= 1; e++) {
for (f = -1; f <= 1; f++) {
c = a + e;
d = b + f;
if (!(f == 0 && e == 0)) {
do {
if (bounds(c, d)) {
 
if (board[c][d] == 0) {
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
z = z + 1;
}
if (board[c][d] < 0) {
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
 
z = z + 1;
break;
}
if (board[c][d] > 0) break;
c = c + e;
d = d + f;
}
}
while (!(bounds(c, d) == false));
 
}
 
}
}
case rook:
for (e = -1; e <= 1; e++) {
for (f = -1; f <= 1; f++) {
c = a + e;
d = b + f;
if (abs(e)+abs(f) == 1) {
do {
if (bounds(c, d)) {
 
if (board[c][d] == 0) {
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
z = z + 1;
}
if (board[c][d] < 0) {
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
 
z = z + 1;
break;
}
if (board[c][d] > 0) break;
c = c + e;
d = d + f;
}
}
while (!(bounds(c, d) == false));
 
}
 
}
}
break;
case bishop:
for (e = -1; e <= 1; e++) {
for (f = -1; f <= 1; f++) {
c = a + e;
d = b + f;
if (abs(e)+abs(f) == 2) {
do {
if (bounds(c, d)) {
 
if (board[c][d] == 0) {
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
z = z + 1;
}
if (board[c][d] < 0) {
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
 
z = z + 1;
break;
}
if (board[c][d] > 0) break;
 
}
c = c + e;
d = d + f;
}
while (!(bounds(c, d) == false));
}
}
}
break;
case knight:
for(e=-2; e<=2; e+=1){
for(f=-2; f<=2; f+=1){
c = a + e;
d = b + f;
if(abs(e) + abs(f) == 3){
if(bounds(c,d)){
if(board[c][d]<=0){
fromSQa[z]=a;
fromSQb[z]=b;
toSQa[z]=c;
toSQb[z]=d;
z+=1;
}
}
}
}
}
break;
case pawn:
//white pawn attack left and forward
c = a + 1;
d = b - 1;
if (bounds(c, d)) { //bounds checks if the square is on the board, if not go to next move direction for pawn.
 
if (board[c][d] < 0 || (epa == c && epb == d)) { //if diagonal square attacked contains a piece valued less than zero then capture is possible, or square is the en passant square from previous move.
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
z = z + 1;
}
}
//white pawn attack right and forward
c = a + 1;
d = b + 1;
if (bounds(c, d)) {
 
if (board[c][d] < 0 || (epa == c && epb == d)) {
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
z = z + 1;
}
}
//check if one square forward is unoccupied and add it to the movelist
if (a == 1) {
c = 2;
d = b;
if (bounds(c, d)) {
 
if (board[c][d] == 0) {
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
z = z + 1;
c = 3;
d = b;
//another square forward if the pawn is on it's starting rank
if (bounds(c, d)) {
 
if (board[c][d] == 0) {
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
z = z + 1;
}
}
}
}
}
else { //pawn is not on starting rank
c = a + 1;
d = b;
if (bounds(c, d)) {
if (board[c][d] == 0) {
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
z = z + 1;
}
}
}
 
break;
case king:
for (e = -1; e <= 1; e++) {
for (f = -1; f <= 1; f++) {
if (!(e == 0 && f == 0)) {
c = a + e;
d = b + f;
 
if (bounds(c, d)) { //checks if coordinates exist on the board
 
if (board[c][d] <= 0 && checkwhite(c, d, a, b).empty()) {
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
z = z + 1;
}
}
}
}
}
//castleKingSide
if (wkside && a == 0 && b == 4 && board[0][7] == rook && board[0][6] == 0 && board[0][5] == 0) {
if (checkwhite(0, 4, 0, 4).empty() && checkwhite(0, 5, 0, 4).empty() && checkwhite(0, 6, 0, 4).empty()) {
fromSQa[z] = 0;
fromSQb[z] = 4;
toSQa[z] = 0;
toSQb[z] = 6;
z = z + 1;
}
}
 
//castleQueenSide
if (wqside == true && a == 0 && b == 4 && board[0][0] == rook && board[0][1] == 0 && board[0][2] == 0 && board[0][3] == 0) {
if (checkwhite(0, 4, 0, 4).empty() && checkwhite(0, 3, 0, 4).empty() && checkwhite(0, 2, 0, 4).empty()) {
fromSQa[z] = 0;
fromSQb[z] = 4;
toSQa[z] = 0;
toSQb[z] = 2;
z = z + 1;
}
}
} // close switch
 
}
}
}
//now all moves are checked to see if they leave the white king in check and if they do they are discarded from the list
int i;
int captured;
int wksqa, wksqb;
string addmove;
 
for(a = 0; a <= 7; a++){
for(b = 0; b <= 7; b++){
if(board[a][b] == king){
wksqa = a;
wksqb = b;
goto kingfound;
}
}
}
kingfound:
bool epcapture;
epcapture = false;
 
i = 0;
for(i = 0; i < z; i++){
a = fromSQa[i];
b = fromSQb[i];
c = toSQa[i];
d = toSQb[i];
 
//perform the move
captured = board[c][d];
board[c][d] = board[a][b];
board[a][b] = 0;
 
if(board[c][d] == pawn && (b != d) && (captured == 0) && bounds((c - 1), d)){
board[c-1][d] = 0;
epcapture = true;
}
 
//if the king is the piece moving wksqa and wksqb won't contain the coordinates of the king! c and d will
if(board[c][d] == king){
if(checkwhite(c, d, 64, 0).empty()){
//add move to list, otherwise discard move (do nothing)
addmove = chfile(b) + chrank(a) + chfile(d) + chrank(c); //convert coordinates to ascii
allmoves = allmoves + addmove; //add to the movelist
}
}
else{ //if the king is not the piece moving then the king is in the coordinates wksqa and wksqb, and we check that square for check, if it is check it is not added to the movelist (allmoves)
if(checkwhite(wksqa, wksqb, 64, 0).empty()){
//add move to list, otherwise discard move (do nothing)
if(!(board[c][d] == pawn && (c == 7))){ // if the move is not a pawn progressed to the 8th rank, then add move to the list, otherwise, pawn promotions and underpromotions must be added to the move list (each)
addmove = chfile(b) + chrank(a) + chfile(d) + chrank(c); //convert coordinates to ascii
allmoves = allmoves + addmove; //add to the movelist
}
else{
for(i2 = 0; i2 < 4; i2++){
addmove = chfile(b) + chrank(a) + chfile(d) + promotions.substr(i2,1); //promotion is 4 characters the file the pawn starts on followed by the rank and file moving to (if capturing will be different) followed by either q for promote to queen, r for rook, n for knight and b for bishop.
allmoves = allmoves + addmove; //add to the movelist
}
}
}
}
//undo the move
board[a][b] = board[c][d];
board[c][d] = captured;
 
if (epcapture == true){
board[c-1][d] = -pawn;
epcapture = false;
 
}
 
}
return allmoves;
}
 
string checkwhite(int ksqa, int ksqb, int remva, int remvb){
int checklista[16];
int checklistb[16];
int a, b, c, d, e, f, g, num, xa, xb;
int repl;
num = 0;
string freturn;
 
if (remva != 64) {
 
repl = board[remva][remvb];
board[remva][remvb] = 0;
 
}
a = ksqa;
b = ksqb;
 
for (e = -2; e < 3; e++){
for (f = -2; f < 3; f++){
 
if ((abs(e) + abs(f)) == 3){ // check for black knight giving check
c = a + e;
d = b + f;
if (bounds(c, d))
{
 
if (board[c][d] == -knight ){
checklista[num] = c;
checklistb[num++] = d;
}
}
} // end check for black knight
if ((abs(e) == 1 || abs(f) == 1) && abs(e) + abs(f) <= 2) //check for black king giving check
{
c = a + e;
d = b + f;
if (bounds(c, d))
{
 
if (board[c][d] == -king )
{
checklista[num] = c;
checklistb[num++] = d;
}
}
} // end check for black king
 
g = abs(e) + abs(f);
if (g == 1) // check for queen and rook
{
c = a + e;
d = b + f;
while (bounds(c, d))
{
//rook or queen (vertical/horizontal)
if (board[c][d] == -queen || board[c][d] == -rook) {
checklista[num] = c;
checklistb[num++] = d;
num++;
}
if (board[c][d] != 0) break;
 
c = c + e;
d = d + f;
}
}
//bishop or queen (diagonally)
if (g == 2 && abs(e) == 1) {
c = a + e;
d = b + f;
while (bounds(c, d)) {
 
if (board[c][d] == -queen || board[c][d] == -bishop) {
checklista[num] = c;
checklistb[num] = d;
num = num + 1;
}
if (board[c][d] != 0) break;
 
c = c + e;
d = d + f;
}
}
}
}
 
//black pawns deliver check
c = a + 1;
d = b + 1;
 
if (bounds(c, d)) {
 
if (board[c][d] == -pawn) {
checklista[num] = c;
checklistb[num] = d;
num++;
}
}
 
c = a + 1;
d = b - 1;
if (bounds(c, d)) {
 
if (board[c][d] == -pawn) {
checklista[num] = c;
checklistb[num] = d;
num++;
}
}
 
string aa, bb, cc, dd;
 
switch (num)
{
case 0:
freturn.clear();
break;
case 1:
 
aa = chfile(ksqb);
bb = chrank(ksqa);
xa = checklista[0];
xb = checklistb[0];
cc = chfile(xb);
dd = chrank(xa);
freturn = aa + bb + cc + dd;
 
break;
default:
aa = chfile(ksqb);
bb = chrank(ksqa);
xa = checklista[0];
xb = checklistb[0];
cc = chfile(xb);
dd = chrank(xa);
freturn = aa + bb + cc + dd;
xa = checklista[1];
xb = checklistb[1];
cc = chfile(xb);
dd = chrank(xa);
freturn = freturn + cc + dd;
break;
 
}
if (remva != 64) {
board[remva][remvb] = repl;
}
return freturn;
}
 
string chfile(int x){ //takes an integer 0-7 and returns ascii character or one character string of file "a" to "h"
static string cho;
switch(x){
case 0:
cho = "a";
break;
case 1:
cho = "b";
break;
case 2:
cho = "c";
break;
case 3:
cho = "d";
break;
case 4:
cho = "e";
break;
case 5:
cho = "f";
break;
case 6:
cho = "g";
break;
case 7:
cho = "h";
break;
 
}
return cho;
}
 
string chrank(int x){ //takes an integer (x) 0-7 and returns ascii "1" to '8" Usually to represent rank on the chessboard
static string cho;
switch(x){
case 0:
cho = "1";
break;
case 1:
cho = "2";
break;
case 2:
cho = "3";
break;
case 3:
cho = "4";
break;
case 4:
cho = "5";
break;
case 5:
cho = "6";
break;
case 6:
cho = "7";
break;
case 7:
cho = "8";
break;
 
}
return cho;
}
 
string checkblack(int ksqa, int ksqb, int remva, int remvb){
int checklista[16];
int checklistb[16];
int a, b, c, d, e, f, g, num, xa, xb;
int repl;
num = 0;
string freturn;
 
if (remva != 64) {
 
repl = board[remva][remvb];
board[remva][remvb] = 0;
 
}
a = ksqa;
b = ksqb;
 
for (e = -2; e < 3; e++){
for (f = -2; f < 3; f++){
 
if ((abs(e) + abs(f)) == 3){ // check for white knight giving check
c = a + e;
d = b + f;
if (bounds(c, d))
{
 
if (board[c][d] == knight ){
checklista[num] = c;
checklistb[num++] = d;
}
}
} // end check for black knight
if ((abs(e) == 1 || abs(f) == 1) && abs(e) + abs(f) <= 2) //check for black king giving check
{
c = a + e;
d = b + f;
if (bounds(c, d))
{
 
if (board[c][d] == king )
{
checklista[num] = c;
checklistb[num++] = d;
}
}
} // end check for black king
 
g = abs(e) + abs(f);
if (g == 1) // check for queen and rook
{
c = a + e;
d = b + f;
while (bounds(c, d))
{
//rook or queen (vertical/horizontal)
if (board[c][d] == queen || board[c][d] == rook) {
checklista[num] = c;
checklistb[num++] = d;
num++;
}
if (board[c][d] != 0) break;
 
c = c + e;
d = d + f;
}
}
//bishop or queen (diagonally)
if (g == 2 && abs(e) == 1) {
c = a + e;
d = b + f;
while (bounds(c, d)) {
 
if (board[c][d] == queen || board[c][d] == bishop) {
checklista[num] = c;
checklistb[num] = d;
num = num + 1;
}
if (board[c][d] != 0) break;
 
c = c + e;
d = d + f;
}
}
}
}
 
//white pawns deliver check
c = a - 1;
d = b + 1;
 
if (bounds(c, d)) {
 
if (board[c][d] == pawn) {
checklista[num] = c;
checklistb[num] = d;
num++;
}
}
 
c = a - 1;
d = b - 1;
if (bounds(c, d)) {
 
if (board[c][d] == pawn) {
checklista[num] = c;
checklistb[num] = d;
num++;
}
}
 
string aa, bb, cc, dd;
 
switch (num)
{
case 0:
freturn.clear();
break;
case 1:
 
aa = chfile(ksqb);
bb = chrank(ksqa);
xa = checklista[0];
xb = checklistb[0];
cc = chfile(xb);
dd = chrank(xa);
freturn = aa + bb + cc + dd;
 
break;
default:
aa = chfile(ksqb);
bb = chrank(ksqa);
xa = checklista[0];
xb = checklistb[0];
cc = chfile(xb);
dd = chrank(xa);
freturn = aa + bb + cc + dd;
xa = checklista[1];
xb = checklistb[1];
cc = chfile(xb);
dd = chrank(xa);
freturn = freturn + cc + dd;
break;
 
}
if (remva != 64) {
board[remva][remvb] = repl;
}
return freturn;
}
 
//actual function, generates all possible animal moves for black in string format ie (R@a1) "a1a2" + "a1a3" etc
string blackmoves(int epa, int epb){ //epa is integer for en passant square file, epb is en passant square rank, together they make a coordinate
string allmoves;
int fromSQa[218];
int fromSQb[218];
int toSQa[218];
int toSQb[218];
 
int a = 0;
int b = 0;
int c = 0;
int d = 0;
int e = 0;
int f = 0;
int z = 0;
string promotions;
int i2;
promotions = "qrbn";
 
for (a = 0; a < 8; ++a){
for (b = 0; b < 8; ++b){
if(a == 7 && b == 0){
//printboard();
}
switch (board[a][b]) {
case -queen: //generate animal moves for black queen (found on square where rank is a, file is b.)
 
{
for (e = -1; e <= 1; e++) {
for (f = -1; f <= 1; f++) {
c = a + e;
d = b + f;
if (!(e == 0 && f == 0)) {
do {
if (bounds(c, d)) {
 
if (board[c][d] == 0) {
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
z = z + 1;
}
if (board[c][d] > 0) {
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
 
z = z + 1;
break;
}
if (board[c][d] < 0) break;
c = c + e;
d = d + f;
}
}
while (!(bounds(c, d) == false));
 
}
 
}
}
 
break;
 
case -rook:
for (e = -1; e <= 1; e++) {
for (f = -1; f <= 1; f++) {
c = a + e;
d = b + f;
if (abs(e)+abs(f) == 1) {
do {
if (bounds(c, d)) {
 
if (board[c][d] == 0) {
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
z = z + 1;
}
if (board[c][d] > 0) {
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
 
z = z + 1;
break;
}
if (board[c][d] < 0) break;
c = c + e;
d = d + f;
}
}
while (!(bounds(c, d) == false));
 
}
 
}
}
break;
case -bishop:
for (e = -1; e <= 1; e++) {
for (f = -1; f <= 1; f++) {
c = a + e;
d = b + f;
if (abs(e)+abs(f) == 2) {
do {
if (bounds(c, d)) {
 
if (board[c][d] == 0) {
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
z = z + 1;
}
if (board[c][d] > 0) {
fromSQa[z] = a; //toSQa[18]
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
 
z = z + 1;
break;
}
if (board[c][d] < 0) break;
 
}
c = c + e;
d = d + f;
}
while (bounds(c, d));
}
}
}
break;
case -knight:
for(e=-2; e<=2; e+=1){
for(f=-2; f<=2; f+=1){
c = a + e;
d = b + f;
if(abs(e) + abs(f) == 3){
if(bounds(c,d)){
if(board[c][d]>=0){
fromSQa[z]=a;
fromSQb[z]=b;
toSQa[z]=c;
toSQb[z]=d;
z+=1;
}
}
}
}
}
break;
case -pawn:
//white pawn attack left and forward (forward from blacks perspective)
c = a - 1;
d = b + 1;
if (bounds(c, d)) {
 
if (board[c][d] > 0 || (epa == c && epb == d)) { //if diagonal square attacked contains a piece valued less than zero then capture is possible, or square is the en passant square from previous move.
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
z = z + 1;
}
}
//white pawn attack right and forward
c = a - 1;
d = b - 1;
if (bounds(c, d)) {
 
if (board[c][d] > 0 || (epa == c && epb == d)) {
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
z = z + 1;
}
}
//check if one square forward is unoccupied and add it to the movelist
if (a == 6) {
c = 5;
d = b;
if (bounds(c, d)) {
 
if (board[c][d] == 0) {
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
z = z + 1;
//decrement the file for c, d (coordinates for move to testing)
c = 4;
d = b;
//another square forward if the pawn is on it's starting rank
if (bounds(c, d)) {
 
if (board[c][d] == 0) {
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
z = z + 1;
}
}
}
}
}
else { //pawn is not on starting rank
c = a - 1;
d = b;
if (bounds(c, d)) {
if (board[c][d] == 0) {
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
z = z + 1;
}
}
}
 
break;
case -king:
for (e = -1; e <= 1; e++) {
for (f = -1; f <= 1; f++) {
if (!(e == 0 && f == 0)) {
c = a + e;
d = b + f;
 
if (bounds(c, d)) { //checks if coordinates exist on the board
 
if (board[c][d] >= 0 && checkblack(c, d, a, b).empty()) {
fromSQa[z] = a;
fromSQb[z] = b;
toSQa[z] = c;
toSQb[z] = d;
z = z + 1;
}
}
}
}
}
//castleKingSide
if (bkside && a == 7 && b == 4 && board[7][7] == -rook && board[7][6] == 0 && board[7][5] == 0) {
if (checkblack(7, 4, 7, 4).empty() && checkblack(7, 5, 7, 4).empty() && checkblack(7, 6, 7, 4).empty()) {
fromSQa[z] = 7;
fromSQb[z] = 4;
toSQa[z] = 7;
toSQb[z] = 6;
z = z + 1;
}
}
 
//castleQueenSide
if (bqside == true && a == 7 && b == 4 && board[7][0] == -rook && board[7][1] == 0 && board[7][2] == 0 && board[7][3] == 0) {
if (checkblack(7, 4, 7, 4).empty() && checkblack(7, 3, 7, 4).empty() && checkblack(7, 2, 7, 4).empty()) {
fromSQa[z] = 7;
fromSQb[z] = 4;
toSQa[z] = 7;
toSQb[z] = 2;
z = z + 1;
}
}
} // close switch
 
}
}
}
//now all moves are checked to see if they leave the white king in check and if they do they are discarded from the list
int i;
int captured;
int bksqa, bksqb;
string addmove;
 
for(a = 0; a <= 7; a++){
for(b = 0; b <= 7; b++){
if(board[a][b] == -king){
bksqa = a;
bksqb = b;
goto kingfound;
}
}
}
kingfound:
 
bool epcapture;
epcapture = false;
 
for(i = 0; i < z; i++){
a = fromSQa[i];
b = fromSQb[i];
c = toSQa[i];
d = toSQb[i];
if(!bounds(a, b) || !bounds(c, d)){
 
}
//perform the move
captured = board[c][d];
board[c][d] = board[a][b];
board[a][b] = 0;
 
if(board[c][d] == -pawn && (b != d) && (captured == 0) && bounds((c + 1), d)){
board[c+1][d] = 0;
epcapture = true;
}
 
//if the king is the piece moving wksqa and wksqb won't contain the coordinates of the king! c and d will
if(board[c][d] == -king){
if(checkblack(c, d, 64, 0).empty()){
//add move to list, otherwise discard move (do nothing)
addmove = chfile(b) + chrank(a) + chfile(d) + chrank(c); //convert coordinates to ascii
allmoves = allmoves + addmove; //add to the movelist
}
}
else{ //if the king is not the piece moving then the king is in the coordinates wksqa and wksqb, and we check that square for check, if it is check it is not added to the movelist (allmoves)
string p2;
p2 = checkblack(bksqa, bksqb, 64, 0);
if(checkblack(bksqa, bksqb, 64, 0).empty()){
//add move to list, otherwise discard move (do nothing)
if(!(board[c][d] == -pawn && (c == 0))){ // if the move is not a pawn progressed to the 8th rank, then add move to the list, otherwise, pawn promotions and underpromotions must be added to the move list (each)
addmove = chfile(b) + chrank(a) + chfile(d) + chrank(c); //convert coordinates to ascii
allmoves = allmoves + addmove; //add to the movelist
}
else{
for(i2 = 0; i2 < 4; i2++){
addmove = chfile(b) + chrank(a) + chfile(d) + promotions.substr(i2,1); //promotion is 4 characters the file the pawn starts on followed by the rank and file moving to (if capturing will be different) followed by either q for promote to queen, r for rook, n for knight and b for bishop.
allmoves = allmoves + addmove; //add to the movelist
}
}
}
}
//undo the move
board[a][b] = board[c][d];
board[c][d] = captured;
 
if (epcapture == true){
board[c+1][d] = -pawn;
epcapture = false;
 
}
 
}
return allmoves;
}
 
int file2num(string f1){
int aa;
switch (f1[0]){
case 'a':
aa = 0;
break;
case 'b':
aa = 1;
break;
case 'c':
aa = 2;
break;
case 'd':
aa = 3;
break;
case 'e':
aa = 4;
break;
case 'f':
aa = 5;
break;
case 'g':
aa = 6;
break;
case 'h':
aa = 7;
break;
}
return aa;
}
 
int rank2num(string f1){
int aa;
switch (f1[0]){
case '1':
aa = 0;
break;
case '2':
aa = 1;
break;
case '3':
aa = 2;
break;
case '4':
aa = 3;
break;
case '5':
aa = 4;
break;
case '6':
aa = 5;
break;
case '7':
aa = 6;
break;
case '8':
aa = 7;
break;
}
return aa;
}
 
int char2promote(char a, string b){
int out1;
char aa;
aa = a;
switch (aa){
case 'q':
out1 = queen;
break;
case 'r':
out1 = rook;
break;
case 'b':
out1 = bishop;
break;
case 'n':
out1 = knight;
break;
}
if (b == "b") out1 *= -1;
return out1;
}
 
void printboard(void){
using namespace std;
int a, b;
cout << "\n";
for(a = 7; a >= 0; a--){
for(b = 0; b <8; b++){
cout << piece2char(board[a][b]);
}
cout << "\n";
}
 
}
 
string piece2char(int piece){
string boardstring;
switch(piece){
case king:
boardstring = boardstring + "K";
break;
case -king:
boardstring = boardstring + "k";
break;
case queen:
boardstring = boardstring + "Q";
break;
case -queen:
boardstring = boardstring + "q";
break;
case rook:
boardstring = boardstring + "R";
break;
case -rook:
boardstring = boardstring + "r";
break;
case 0:
boardstring = boardstring + "-";
break;
case bishop:
boardstring = boardstring + "B";
break;
case -bishop:
boardstring = boardstring + "b";
break;
case knight:
boardstring = boardstring + "N";
break;
case -knight:
boardstring = boardstring + "n";
break;
case pawn:
boardstring = boardstring + "P";
break;
case -pawn:
boardstring = boardstring + "p";
break;
}
return boardstring;
}

So far everything has been debugged and works flawlessly, at least for a random mover anyway. (Except whitecheck and blackcheck may return doublecheck when it is only a normal single check).

The next step from here is to add the alphabeta search algorithm. The most important part of the alphabeta search algorithm is MOVE ORDERING.

What do I have in mind for move ordering?

This!

Priority listed first is highest priority to search.

If any move on the list is a checkmate no other nodes need to be searched from that position, so…

1. Checkmate

2. Doublecheck

3. Check

4. A move that threatens mate, usually a queen threatening a square in front of the king when the king is on the side of the board (or in a corner!). When that square is not protected by the kings color of pieces, but is attacked by more than the queens side of pieces. (This may be harder to program for than the rest).

5. A hanging queen is captured.

6. A hanging rook is captured.

7. A hanging knight or bishop is captured

etc….

For now I don’t plan to make it overcomplicated, an idea I have in mind (that’s probably been done before), is to simply count the number of attacks vs defenses on each piece in a position, but leave out the pieces in an absolute pin (as they usually don’t contribute to a proper defense) and then based on that rank how good or bad it would be to capture on that square, and sort it higher if it’s good and lower if it’s bad.

So far it has a skeleton of the UCI protocol programmed into it, I plan to expand this to include: nodes per second, principle variation, analysis mode and more.

The function whitemoves generates all the animal type moves of the chess pieces as they would naturally move, then the moves are performed one by one and tested to see if they leave their own color king in check, if it doesn’t it is added to a string, when it has tested all the moves the string returned is all of the legal chess moves in the position for the color to play. (Of course en passant and special moves are included). each move is represented by 4 characters ascii, for promotions and underpromotions the rank is left out and replaced by the piece it is promoted to, this enables it all to be formatted as 4 characters each instead of 5 for promotions, as all promotions either happen on the front or back rank according to their color even promotions with capture. (Mind you internally all moves are 4 characters long, externally it follows the UCI protocol).

The function checkwhite searches if whites king is in check, if it isn’t it returns a null string; ie “”, otherwise if it is single check it returns the square the king is on and the piece giving check’s square, ie “e1e8”, if it is double check it returns the square the king is on then the squares of the two pieces giving check. By that logic if we check the length of the string returned by the function we can determine each, no check;  length = 0, single check; length = 4, double check; length = 6. The blackcheck function does the same except for the black king being in check or double check.

All info on the specifications of the UCI protocol can be found here: http://wbec-ridderkerk.nl/html/UCIProtocol.html

-deepglue5

 

Pawns and Pairs

One way to recognize that the back rank pieces have developed are if the back rank squares are empty.

The algorithm I imagine for this could be checking two squares are empty on each place you can measure this, ie: a1, b1, or c1, d1 etc…

Pawns at the 4th rank is often a good predictor of positional control, so giving a positional value to having pawns at e4 and d4 or even c4 and d4 indicates that player must have good control of the center.

Though the positional value generator must take into account weaknesses such as pawn at d4 and e5, where if the opponents Bishop exists that is on the opposite color of those square will have a trump in that position, playwise.

Goals

Debugging is going well.

Future plans for the evaluation and heuristics have been going on in my mind lately. I plan on implementing alot of good positional knowledge into my program.

For example, to help it castle, I will do a kind of Karnaugh mapping like I learned in college, for example, if white king is on square g1, or h1 and pawns sit on f2, g2 and a pawn on h2 or h3 then award white 12 centipawns.

I can do this to award or subtract for good and bad positional instances.

Alphabeta Search

The engine will use Alphabeta prune search algorithm which is standard in all good chess programs today. (Though there are a few that still use minmax and play very well).

In the evaluation it will have to make an ‘educated guess’ at what the immediate tactics in the position resolve to. Without this it would be somewhat tactically blind and would play too much for stupid positional values.

Random numbers

Too spice up the evaluation I will implement random number generator to give slightly different weights for minor pieces on different squares, of course including positional knowledge of the usual ‘a knight on the rim is dim’ and such. This should help for generating Monte Carlos move choices, and giving the opponent a slightly varied play.

 

Good news, bad news

Good news and bad news on the Beta Random Version,

Bad news first, there is a glitch where white puts it’s king in check still, more bad news, the FEN parse function I made doesn’t work as expected.

At first I realised I started parsing the FEN one character late, this was easily fixed.

The FEN string doesn’t work the way I assumed, which I assumed it started at a1 and incremented file wise towards h8. Instead FEN starts at a8 and goes to h8 then decrements the rank and goes a7 to h7 🙁

The good news, I know what I need to do to fix all these bugs.

Once it parses FEN correctly I can debug why it is allowing a piece to break out of a pin allowing the king to become En prise as it’s called.

I have a hunch this is because the function I wrote requires it to know where the king is to work properly, but still doesn’t explain why it is only doing this with the white pieces.

Internet; and other distractions

I try to put so much time in per day or week towards my pet project of writing a decent chess program essentially from scratch.

‘From scratch’ because this program unlike many others isn’t based on the code of any other existing open source chess programs , other than what I have written myself.

Of course, every programmer has distractions. One of the biggest for me is the internet itself.

When I’m on the internet, I check on things like PTC websites where I make a small amount of money for basically alot of time.

My two favorite PTC sites are Neobux, and Clixsense, and a new one i have added to my click list is Nerdbux.

Aside from PTC sites that I spend a few hours a day on, I like to spend a little time on facebook, and other social websites.

Skype is one of the biggest distractions I have, I am in a group that likes to do prank calls, and it’s easy to kill away 4-7 hours at a time on it. Sometimes I help get numbers, or host but rarely actually conduct a call. And it’s not a waste of time because I enjoy it so much.

Youtube isn’t a big deal for me, I’m not always looking out for the next ‘viral’ video, or spend hours listening to music on there, or laughing at joke/prank videos like some people. I would call myself a casual youtuber. Sometimes I’ll watch a video to learn a new guitar riff or song, sometimes people will share videos with me, sometimes I watch tutorials on how to do computer related tasks, even programming and other stuff I am interested in.

I do however spend a ton of my day on the internet, and not even for any kind of adult material.

However, the internet is a powerful and useful tool for communicating and learning.

Yesterday I Googled the guitar tab for The Beatles 8 days a week, and learned the song in a matter of minutes.

Needless to say, I appreciate having that kind of knowledge at my fingertips and wouldn’t give it up easily.

Aside from the internet, I watch TV, though not alot, I did watch the Zimmerman trial on HLN, and enjoy local and world news, I wouldn’t say that’s a waste, because keeping up on current events is important, even if it’s just to give people something to converse about.

I also enjoyed a new episode of the Simpsons and Family Guy tonight. Though I wouldn’t say I’m a hardcore fan of any TV show in particular, though I do follow Breaking Bad.

That sums up a pretty good list of things that distract me from getting ‘work’ and projects done.

Beta random version

Today I did some work on the code, fixed a few bugs, one bug was causing a GPF, which now seems to be cleared up.

The other bug was it was not conveying certain moves properly, causing adjudication of a loss in Arena. This was fixed by changing a ‘>’ to ‘>=’.

In the random version, it simply selects a random legal move from the move list. Which it is now doing perfectly correct.

Except that it is not moving the rook on H8, otherwise it is doing what it is supposed to with no GPF or Arena adjudicated loss for ‘illegal move’ like it was before.

Site installed

Site installed July 29th 2013 9:05 pm Pacific time

Soon you will be able to purchase closed source chess program, i created and named Echo v 0.9.1 and beta versions and future versions, from this site.

Also featured on this site I will cover programming tutorials, that may or may not be mirrored on dream.in.code

Edit: Nov 20 2013, all posts have been moved to a new domain: echochess.pw