Guide me through building a chess program

[Fguy64]

You know Sapta, this is just an idea. but you may wish to try writing a chess program without making use of any chess programming theory at all. That's what I did the first time around. It would be interesting to compare your results to more accepted practices. Then you will probably want to do a total redesign.

[hgm]

Sorry, couldn't find it on your website given in your profile. Can I get a direct link plz?

It is the first program on my downloads page:

http://home.hccnet.nl/h.g.muller/dwnldpage.html

Ah, also you said 12x16 which seems alright to me, but why does it say 16 x 12 everywhere?

I guess for Chess boards it is usual to mention the numbr of files before the number of ranks. (After all, we sa e2e4, and not 2e4e like Shogi people would.) For 2-dimensional arrays, however, it is usually the last index that varies most rapidly in a linear scan. (Except when you are a FORTRANner...) So I guess the confusion arises because some look at it from the viewpoint of an array, and others from that of a Chess board.

[Sapta]

Ah, also you said 12x16 which seems alright to me, but why does it say 16 x 12 everywhere?

I guess for Chess boards it is usual to mention the numbr of files before the number of ranks. (After all, we sa e2e4, and not 2e4e like Shogi people would.) For 2-dimensional arrays, however, it is usually the last index that varies most rapidly in a linear scan. (Except when you are a FORTRANner...) So I guess the confusion arises because some look at it from the viewpoint of an array, and others from that of a Chess board.

So that's why. Thanks for clearing that up. Never thought it that way

[Sapta]

Hello again everyone, I am back with questions We are currently doing the moves generation part. We are using a Move class with only 3 data.

Code: Select all

class Move
{
     int  to_index, 
          from_index, 
          score;
}

We are scanning a board position, then for a piece we're generating all pseudo moves it can give, storing it in a move object, then adding that object in an arraylist.
Somewhat like this:

Code: Select all

for(i=0;i<120;i++)
{
    if(onboard)
    {
         if(!blank)
         {
             switch(piece)
             {
                case knight:  gen_knight_moves(from);
                                    break;
        ....
              }
          }
    }
}

static int Nmoves[] = { -18, -33, -14, -31, 14, 31, 18, 33};

void gen_knight_moves(int from)
{
        int i, to;
        try
        {
            for(i=0;i<8;i++)
            {
                to = board_index + Nmoves[i];
                if((to & 0x88) == 0)
                {
                    if(board[to] == Blank)
                        make_move(board_index, to);
                    else if(Data.opposite_colors(board_index, to))
                        make_capture_move(board_index, to);
                }
           }
            showlist();        // to show list
        }
catch(Exception ee){System.out.println("\n");ee.printStackTrace();}
 }


    static void make_move(int from, int to)
    {
        Move m = new Move();
        m.from = from;
        m.to = to;
        m.score = 10;

        Data.moveslist.add(m);     //moveslist is the arraylist in a Data class
    }

    static void make_capture_move(int from, int to)
    {
        Move m = new Move();
        m.from = from;
        m.to = to;
        m.score = 100;

        Data.moveslist.add(m);

    }

Is this going alright? Also, what other data should be in the move structure? And what scores for ordinary moves, capture moves and promotion moves?

[Harald]

Hello again everyone, I am back with questions We are currently doing the moves generation part. We are using a Move class with only 3 data.

Code: Select all

class Move
{
     int  to_index, 
          from_index, 
          score;
}

You should include int promotion_piece in the move struct. Together with
from and to the move will be unique and complete. Other infos like
captured_piece or moving_piece or checking may be nice to have but they are optional.

We are scanning a board position, then for a piece we're generating all pseudo moves it can give, storing it in a move object, then adding that object in an arraylist.
Somewhat like this:

Code: Select all

for(i=0;i<120;i++)
{
    if(onboard)
    {
         if(!blank)
         {
             switch(piece)
             {
                case knight:  gen_knight_moves(from);
                                    break;
        ....
              }
          }
    }
}

Perhaps for(i=21;i<99;i++) is enough.
Onboard and blank are typically part of the switch cases when the array
is initialised with the offboard border and blank-pieces. Less if() and more speed.

Code: Select all

static int Nmoves[] = { -18, -33, -14, -31, 14, 31, 18, 33};

void gen_knight_moves(int from)
{
        int i, to;
        try
        {
            for(i=0;i<8;i++)
            {
                to = board_index + Nmoves[i];
                if((to & 0x88) == 0)
                {
                    if(board[to] == Blank)
                        make_move(board_index, to);
                    else if(Data.opposite_colors(board_index, to))
                        make_capture_move(board_index, to);
                }
           }
            showlist();        // to show list
        }
catch(Exception ee){System.out.println("\n");ee.printStackTrace();}
 }


    static void make_move(int from, int to)
    {
        Move m = new Move();
        m.from = from;
        m.to = to;
        m.score = 10;

        Data.moveslist.add(m);     //moveslist is the arraylist in a Data class
    }

In other programs make_move() is the name of the function that actually
changes the board and not a move list. Your function may lead to
confusion when you are discussing your program with others.

Sorry, I did not read or see more now without giving it more time.

Harald

[Fguy64]

Uh Sapta, unless I am missing something it looks like you are going to create a move object for every move in search? Seems to me that might really slow you down. I know that sort of thing really slowed me down. I ended up eliminating object creation in search altogether, with the exception of a game state object that groups stuff like booleans for castling rights and ep target square, and I might get rid of that too.

[Sapta]

...
Perhaps for(i=21;i<99;i++) is enough.
...
Harald

Thanks a lot for the valuable suggestions. That code did have too many unnecessary ifs it seems We'll look into them. Btw, the board is pure 0x88, so can't start from 21. (that's in 10x12 i think)

Uh Sapta, unless I am missing something it looks like you are going to create a move object for every move in search? Seems to me that might really slow you down. I know that sort of thing really slowed me down. I ended up eliminating object creation in search altogether, with the exception of a game state object that groups stuff like booleans for castling rights and ep target square, and I might get rid of that too.

Yes, you got it right. We are thinking of using a move object for each move or maybe each piece(then the to_index will be an arraylist itself). At the moment the space complexity look ominously huge, and we don't have much idea about the time complexity. So, if we remove object creation, should we write the moves in a file? I'm not much familiar with working with files or how much time it takes. I went to your site but the codes are no longer available as the links have expired. How have you implemented this step to make it faster? :/

[Fguy64]

...
Perhaps for(i=21;i<99;i++) is enough.
...
Harald

Thanks a lot for the valuable suggestions. That code did have too many unnecessary ifs it seems We'll look into them. Btw, the board is pure 0x88, so can't start from 21. (that's in 10x12 i think)

Uh Sapta, unless I am missing something it looks like you are going to create a move object for every move in search? Seems to me that might really slow you down. I know that sort of thing really slowed me down. I ended up eliminating object creation in search altogether, with the exception of a game state object that groups stuff like booleans for castling rights and ep target square, and I might get rid of that too.

Yes, you got it right. We are thinking of using a move object for each move or maybe each piece(then the to_index will be an arraylist itself). At the moment the space complexity look ominously huge, and we don't have much idea about the time complexity. So, if we remove object creation, should we write the moves in a file? I'm not much familiar with working with files or how much time it takes. I went to your site but the codes are no longer available as the links have expired. How have you implemented this step to make it faster? :/

Well, in my search, moves are represented by integers, and are stored in static arrays. Essentially it is a 2D array, with one dimension large enough to accomodate the largest # of possible moves at any one node, and the the other dimension representing the maximum search depth. This necessitates the use of counters/pointers.

I am not suggesting my strategy is optimal, but it saved me a lot of time over creating and discarding many millions of move objects.

As for my code, in java, at this time I am having 2nd thoughts about widely publicizing it as available for download. But I'll shoot you a PM with that.

[Sapta]

Our exams are coming up and we have to show how much we have done, which is erm, less than 15% i guess Anyway, we haven't done minmax yet because we kinda stopped doing this. I was wondering if I could use a GUI just to show moves by humans(us) and that only legal moves are allowed. This brings up 2 questions:

1. If I use winboard can i show human vs human game? It will just reflect the moves we give on a GUI board, that's all.

2. We have a pseudo-legal moves generator and we want to make a implement_move() function that will check if it's legal before applying. That's seemed like a standard procedure and is alright if the computer plays a move. But if we(humans) give a move , it doesn't go through pseudo-legal move generator. So, where do the piece move rules apply? Ie, if we ask to give a move e2e5 in the beginning of the game, it shouldn't be possible, but since it doesn't put the king in check, currently the program will just apply the move

[Fguy64]

Our exams are coming up and we have to show how much we have done, which is erm, less than 15% i guess Anyway, we haven't done minmax yet because we kinda stopped doing this. I was wondering if I could use a GUI just to show moves by humans(us) and that only legal moves are allowed. This brings up 2 questions:

1. If I use winboard can i show human vs human game? It will just reflect the moves we give on a GUI board, that's all.

2. We have a pseudo-legal moves generator and we want to make a implement_move() function that will check if it's legal before applying. That's seemed like a standard procedure and is alright if the computer plays a move. But if we(humans) give a move , it doesn't go through pseudo-legal move generator. So, where do the piece move rules apply? Ie, if we ask to give a move e2e5 in the beginning of the game, it shouldn't be possible, but since it doesn't put the king in check, currently the program will just apply the move

There's always more than one way to skin a cat. When I was testing my moveGen code, I just had "human moves" from the GUI use the same code. That is to say, I would generate a list of legal moves using the same code that the engine would use. then I'd validate a human move from the GUI simply by checking that it was on the list. That might not be the way a finished product would work, but it allows you to have a single set of code for legality for both GUI moves and engine moves