Piece of chess engine, which accomplishes move generation

Question

This is a piece of a chess - engine which accomplishes the generation of all (yet unvalidated) moves given a legal board. However, I have the strong doubt this is well written. The following action are not yet included:

1. Promoting
2. Castling
3. En passant.

This code:

#include "chess.h"
#include "odinutilities.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

/*
 * Stores all moves given a pawns position,the pawns color, and a valid board position in move_info
 * Returns 0 if failed, otherwise 1. If a error occured, some valid moves might still be stored.
 * e.p not added yet.  
 */
char store_all_moves_of_pawn(char copy_board[8][8], char from_x, char from_y,
        MOVE_DATA* move_info, char color) {
    const char dy = (color + 1) ? 1 : -1;
    const char to_y = from_y + dy;
    for (char m = -1; m < 2; m++) {
        const char to_x = from_x + m;
        if ((to_x < 0) | (to_x > 7)) {
            continue;
        }
        if (m != 0) {
            //check if pawn can take left and right
            if (((to_y >= 0) & (to_y <= 7)) & (to_x >= 0) & (to_x <= 7)
                    & ((copy_board[(int) to_y][(int) to_x] * color) < 0)) {
                add_move_to_data(move_info,
                        create_move_string(from_x, from_y, to_x, to_y,
                                (char) 0));
            }

        } else {
            //can pawn move forward
            if (copy_board[(int) to_y][(int) to_x] == 0) {
                add_move_to_data(move_info,
                        create_move_string(from_x, from_y, to_x, to_y,
                                (char) 0));
            }
        }
    }
    return 1;
}

/*
 * Stores all moves given a rocks position, the rocks color, and a valid board position in move_info
 * Returns 0 if failed, otherwise 1. If a error occured, some valid moves might still be stored.
 */
char store_all_moves_of_knight(char copy_board[8][8], char from_x, char from_y,
        MOVE_DATA* move_info, char color) {
    char no_error = 1;
    char dx;
    char dy;
    char* p1 = &dx;
    char* p2 = &dy;

    //Compressed code using pointer arithmetic:
    for (char i = 0; i < 2; i++) {
        for (*p1 = -2; *p1 < 3; *p1 = *p1 + 4) {
            for (*p2 = -1; *p2 < 2; *p2 = *p2 + 2) {
                char to_x = from_x + dx;
                char to_y = from_y + dy;
                if (0 <= to_x & to_x < 8 & 0 <= to_y & to_y < 8) {
                    no_error = add_move_if_unused_by_equal_color(copy_board,
                            from_x, from_y, move_info, color, to_x, to_y);
                    if (!no_error)
                        return no_error;
                }
            }
        }
        p1 = &dy;
        p2 = &dx;
    }
    return no_error;
}

/*
 * Stores all moves given a rocks position, the rocks color, and a valid board position in move_info
 * Returns 0 if failed, otherwise 1. If a error occured, some valid moves might still be stored.
 */
char store_all_moves_of_rock(char copy_board[8][8], char from_x, char from_y,
        MOVE_DATA* move_info, char color) {
    //Vertikal
    //Up
    char no_error = 1;
    for (char dy = 1; from_y + dy < 8; dy++) {
        char temp_field = copy_board[(int) from_y + dy][(int) from_x];
        if (temp_field == 0) {
            no_error = add_move_to_data(move_info,
                    create_move_string(from_x, from_y, from_x, from_y + dy,
                            (char) 0));
            if (!no_error) {
                return 0;
            }
        } else {
            if ((!color & (temp_field > 0)) || (color & !(temp_field > 0))) {
                no_error = add_move_to_data(move_info,
                        create_move_string(from_x, from_y, from_x, from_y + dy,
                                (char) 0));
            }
            if (!no_error) {
                return 0;
            }
            break;
        }
    }
    //Down
    for (char dy = -1; from_y + dy >= 0; dy--) {
        char temp_field = copy_board[(int) from_y + dy][(int) from_x];
        if (temp_field == 0) {
            no_error = add_move_to_data(move_info,
                    create_move_string(from_x, from_y, from_x, from_y + dy,
                            (char) 0));
            if (!no_error) {
                return 0;
            }
        } else {
            if ((!color & (temp_field > 0)) || (color & !(temp_field > 0))) {
                no_error = add_move_to_data(move_info,
                        create_move_string(from_x, from_y, from_x, from_y + dy,
                                (char) 0));
            }
            if (!no_error) {
                return 0;
            }
            break;
        }
    }
    //Horizontal
    //Right
    for (char dx = 1; from_x + dx < 8; dx++) {
        char temp_field = copy_board[(int) from_y][(int) from_x + dx];
        if (temp_field == 0) {
            no_error = add_move_to_data(move_info,
                    create_move_string(from_x, from_y, from_x + dx, from_y,
                            (char) 0));
            if (!no_error) {
                return 0;
            }
        } else {
            if ((!color & (temp_field > 0)) || (color & !(temp_field > 0))) {
                add_move_to_data(move_info,
                        create_move_string(from_x, from_y, from_x + dx, from_y,
                                (char) 0));
            }
            if (!no_error) {
                return 0;
            }
            break;
        }
    }
    //Left
    for (char dx = -1; from_x + dx >= 0; dx--) {
        char temp_field = copy_board[(int) from_y][(int) from_x + dx];
        if (temp_field == 0) {
            no_error = add_move_to_data(move_info,
                    create_move_string(from_x, from_y, from_x + dx, from_y,
                            (char) 0));
            if (!no_error) {
                return 0;
            }
        } else {
            if ((!color & (temp_field > 0)) || (color & !(temp_field > 0))) {
                no_error = add_move_to_data(move_info,
                        create_move_string(from_x, from_y, from_x + dx, from_y,
                                (char) 0));

            }
            if (!no_error) {
                return 0;
            }
            break;
        }
    }
    return 1;
}

/*
 * Stores all moves given a bishops position, the bishops color, and a valid board position in move_info
 * Returns 0 if failed, otherwise 1. If a error occured, some valid moves might still be stored.
 */
char store_all_moves_of_bishop(char copy_board[8][8], char from_x, char from_y,
        MOVE_DATA* move_info, char color) {
    char no_error = generate_all_moves_of_bishops_direction(copy_board, from_x,
            from_y, move_info, color, -1, -1);
    if (!no_error)
        return no_error;
    no_error = generate_all_moves_of_bishops_direction(copy_board, from_x,
            from_y, move_info, color, -1, 1);
    if (!no_error)
        return no_error;
    no_error = generate_all_moves_of_bishops_direction(copy_board, from_x,
            from_y, move_info, color, 1, -1);
    if (!no_error)
        return no_error;
    no_error = generate_all_moves_of_bishops_direction(copy_board, from_x,
            from_y, move_info, color, 1, 1);
    return no_error;
}

/*
 * Stores all moves given a queens position, the queens color, and a valid board position in move_info
 * Returns 0 if failed, otherwise 1. If a error occured, some valid moves might still be stored.
 */
char store_all_moves_of_queen(char copy_board[8][8], char from_x, char from_y,
        MOVE_DATA* move_info, char color) {
    char no_error = store_all_moves_of_rock(copy_board, from_x, from_y,
            move_info, color);
    if (!no_error)
        return no_error;
    no_error = store_all_moves_of_bishop(copy_board, from_x, from_y, move_info,
            color);
    return no_error;
}

/*
 * Stores all moves given a queens position, the queens color, and a valid board position in move_info
 * Returns 0 if failed, otherwise 1. If a error occured, some valid moves might still be stored.
 */
char store_all_moves_of_king(char copy_board[8][8], char from_x, char from_y,
        MOVE_DATA* move_info, char color) {
    char no_error;
    for (int i = -1; i < 2; i++) {
        for (int k = -1; k < 2; k++) {
            char to_x = from_x + k;
            char to_y = from_y + i;
            if (0 <= to_x & to_x < 8 & 0 <= to_y & to_y < 8) {
                no_error = add_move_if_unused_by_equal_color(copy_board, from_x,
                        from_y, move_info, color, to_x, to_y);
                if (!no_error)
                    return no_error;
            }
        }
    }
    return 1;
}

/*
 * Returns all moves given a Board-State, including a legal board position. For illegal positions the
 * behaviour is undefined. However, it is allowed to pass a position, where the color to move is checked.
 */
MOVE_DATA return_all_moves(BOARD_STATE* plegal_board_state,
        char ignore_check) {
    MOVE_DATA move_data;
    move_data.array_size = MOVE_ARRAY_SIZE_BY_INIT;
    move_data.used_array_size = 0;
    move_data.moves = (char**) malloc(move_data.array_size * sizeof(char*));
    char copy_board[8][8];
    memcpy(copy_board, (plegal_board_state->board), sizeof(copy_board));
    for (int i = 0; i < BOARD_LEN; i++) {
        for (int k = 0; k < BOARD_LEN; k++) {
            char piece = copy_board[i][k];
            char color = piece > 0 ? 1 : -1;
            if (color != plegal_board_state->to_move) {
                continue;
            }
            switch (piece * color) {
            char c;
        case free_piece:
            continue;
        case pawn:
            c = store_all_moves_of_pawn(copy_board, k, i, &move_data, color);
            if (!c) {
                perror("OutOfMemoryException.");
                exit(EXIT_FAILURE);
            }
            continue;
        case knight:
            c = store_all_moves_of_knight(copy_board, k, i, &move_data, color);
            if (!c) {
                perror("OutOfMemoryException.");
                exit(EXIT_FAILURE);
            }
            continue;
        case bishop:
            c = store_all_moves_of_bishop(copy_board, k, i, &move_data, color);
            if (!c) {
                perror("OutOfMemoryException.");
                exit(EXIT_FAILURE);
            }
            continue;
        case rock:
            ; //this is an empty statement since a label is not allowed before a declaration
            c = store_all_moves_of_rock(copy_board, k, i, &move_data, color);
            if (!c) {
                perror("OutOfMemoryException.");
                exit(EXIT_FAILURE);
            }
            continue;
        case queen:
            c = store_all_moves_of_queen(copy_board, k, i, &move_data, color);
            if (!c) {
                perror("OutOfMemoryException.");
                exit(EXIT_FAILURE);
            }
            continue;
        case king:
            c = store_all_moves_of_king(copy_board, k, i, &move_data, color);
            if (!c) {
                perror("OutOfMemoryException.");
                exit(EXIT_FAILURE);
            }
            continue;
        default:
            fprintf(stderr, "Unknown piece: %c on the board\nError.", piece);
            exit(EXIT_FAILURE);

            }
        }
    }
    return move_data;
}

/*Merges to_be_added into to dest.
 * If successful, to_be_added moves will be freed.
 * Returns 1, if successful
 * Returns 0, OutOfMemoryException
 */
char merge(MOVE_DATA* dest, MOVE_DATA* to_be_merged) {
    void* c;
    if (dest->array_size
            < dest->used_array_size + to_be_merged->used_array_size) {
        c = realloc(dest->moves,
                (dest->used_array_size + to_be_merged->used_array_size)
                        * sizeof(char*));
        if (!c) {
            return 0;
        } else {
            dest->moves = (char**) c;
        }
        dest->array_size = dest->used_array_size
                + to_be_merged->used_array_size;
    }
    c = memcpy((dest->moves) + dest->used_array_size, to_be_merged->moves,
            to_be_merged->used_array_size);
    if (!c) {
        return 0;
    }
    return 1;
}

/* Adds a move string to a MOVE_DATA
 * If there is no more space left, space of the MOVE_DATA will be doubled.
 * Returns 1, if successful
 * Returns 0, OutOfMemoryException
 */
char add_move_to_data(MOVE_DATA* move_info, char* move) {
    if (move_info->array_size == move_info->used_array_size) {
        char** p = realloc(move_info->moves,
                2 * (move_info->array_size) * sizeof(char*));
        move_info->array_size = 2 * (move_info->array_size);
        if (!p) {
            return 0;
        } else {
            move_info->moves = (char**) p;
        }
    }
    move_info->moves[move_info->used_array_size++] = move;
    return 1;
}

char generate_all_moves_of_bishops_direction(char copy_board[8][8], char from_x,
        char from_y, MOVE_DATA* move_info, char color, char dhorizontal,
        char dvertical) {
    char n = 1;
    char to_x;
    char to_y;
    char no_error = 1;
    while (((to_x = dhorizontal * n + from_x) < 8 & (to_x >= 0))
            & (((to_y = dvertical * n + from_y) < 8) & (to_y >= 0))) {
        if (copy_board[(int) to_y][(int) to_x] == 0) {
            no_error = add_move_to_data(move_info,
                    create_move_string(from_x, from_y, to_x, to_y, (char) 0));
        } else {
            if (color * copy_board[(int) to_y][(int) to_x] < 0) {
                no_error = add_move_to_data(move_info,
                        create_move_string(from_x, from_y, to_x, to_y,
                                (char) 0));
            }
            break;
        }
        n++;
    }
    return no_error;
}

//Returns 1 if successful, else 0
/*
 * NOTE THIS FUNCTION IS NOT CHECKING IF THE MOVE IS LEGAL. IT IS ONLY LOOKING IF THE FIELD IS USED BY ANOTHER
 * PIECE OF EQUAL COLOR AND THEN ADDS THE MOVE OR NOT. IN BOTH CASES 1 WILL BE RETURNED.
 */
char add_move_if_unused_by_equal_color(char copy_board[8][8], char from_x,
        char from_y, MOVE_DATA* move_info, char color, char to_x, char to_y) {
    if (copy_board[to_y][to_x] * color <= 0) {
        char no_error = add_move_to_data(move_info,
                create_move_string(from_x, from_y, to_x, to_y, (char) 0));
        return no_error;
    }
    return 1;
}

This is the header-file:

#ifndef BOARD_H
#define BOARD_H

#define BOARD_LEN 8
#define MOVE_ARRAY_SIZE_BY_INIT 20

#include <stdlib.h>

typedef struct  {
    char board[8][8];
    char to_move;
    char pieces_moved[6];
} BOARD_STATE;

typedef struct {
    char** moves;
    size_t array_size;
    size_t used_array_size;
} MOVE_DATA;

char** return_all_moves(BOARD_STATE* pstate);
MOVE_DATA return_all_legal_moves(BOARD_STATE* pstate, char ignore_check);
char board_is_legal(BOARD_STATE* pstate);

char store_all_moves_of_pawn(char copy_board[8][8], char from_x, char from_y, MOVE_DATA* move_info, char color);
char store_all_moves_of_bishop(char copy_board[8][8], char from_x, char from_y, MOVE_DATA* move_info, char color);
char store_all_moves_of_rock(char copy_board[8][8], char from_x, char from_y, MOVE_DATA* move_info, char color);
char store_all_moves_of_queen(char copy_board[8][8], char from_x, char from_y, MOVE_DATA* move_info, char color);
char store_all_moves_of_king(char copy_board[8][8], char from_x, char from_y, MOVE_DATA* move_info, char color);

char add_move_to_data(MOVE_DATA* move_info, char* move);
char merge(MOVE_DATA* dest, MOVE_DATA* to_be_merged);
char generate_all_moves_of_bishops_direction(char copy_board[8][8], char from_x, char from_y,
        MOVE_DATA* move_info, char color, char dhorizontal, char dvertical);
char add_move_if_unused_by_equal_color(char copy_board[8][8], char from_x, char from_y, MOVE_DATA* move_info, char color,
        char to_x, char to_y);

#endif

1. I am searching for a general advice for a better desgin of the engine.
2. I am not looking for any optimizations yet.
3. I would also love your comments about readability.

Answer 1

return type

char should only be user for characters, as it's name says. unsigned char for characters or for aliasing other types. For everything else, use anything else.

If you want (u)int8_t, use <stdint.h>, and if you don't have that header, feel free to write your own typedef (enclosed in an #if).

But for error codes, the best is to use good old int. Everybody uses int for error codes, so you won't mess with their brains when they wonder why you did use char :)

---

Function return values and names (source: Linux Kernel Coding Style)

Functions can return values of many different kinds, and one of the most common is a value indicating whether the function succeeded or failed. Such a value can be represented as an error-code integer (-Exxx = failure, 0 = success) or a succeeded boolean (0 = failure, non-zero = success).

Mixing up these two sorts of representations is a fertile source of difficult-to-find bugs. If the C language included a strong distinction between integers and booleans then the compiler would find these mistakes for us... but it doesn’t. To help prevent such bugs, always follow this convention:

If the name of a function is an action or an
 imperative command, the function should
 return an error-code integer. If the name is a
 predicate, the function should return a
 "succeeded" boolean. 

For example, add work is a command, and the add_work() function returns 0 for success or -EBUSY for failure. In the same way, PCI device present is a predicate, and the pci_dev_present() function returns true if it succeeds in finding a matching device or false if it doesn’t.

---

no_error

The variable no_error is misleading: it can hold an error code. Probably the origin of the name was the inverted error return codes. With non-zero error codes better names are: error or status.

---

copy_board

The name of the parameter copy_board is misleading, given that it's not a copy, but a pointer to the original board.

---

function names short

For making function names shorter, you can omit prepositions in them (when they are obvious). For example, store_all_moves_of_pawn() -> store_moves_pawn()

---

#pragma once

Although it has its own problems (only if your build configuration is completely broken, actually), it is less error-prone than typical #ifndef&#define include guards.

It's not standard, but most compilers accept it.

Just write this line at the beginning of the header:

#pragma once

#pragma once vs include guards

---

Names and Order of Includes (source: Google C++ Style Guide)

Use standard order for readability and to avoid hidden dependencies: Related header, C library, C++ library, other libraries' .h, your project's .h.

All of a project's header files should be listed as descendants of the project's source directory without use of UNIX directory shortcuts . (the current directory) or .. (the parent directory). For example, google-awesome-project/src/base/logging.h should be included as:

#include "base/logging.h" 

In dir/foo.cc or dir/foo_test.cc, whose main purpose is to implement or test the stuff in dir2/foo2.h, order your includes as follows:

dir2/foo2.h.

A blank line

C system files.

C++ system files.

A blank line

Other libraries' .h files.

Your project's .h files.

Note that any adjacent blank lines should be collapsed.

With the preferred ordering, if dir2/foo2.h omits any necessary includes, the build of dir/foo.cc or dir/foo_test.cc will break. Thus, this rule ensures that build breaks show up first for the people working on these files, not for innocent people in other packages.

dir/foo.cc and dir2/foo2.h are usually in the same directory (e.g. base/basictypes_test.cc and base/basictypes.h), but may sometimes be in different directories too.

Within each section the includes should be ordered alphabetically.

• In your case this would mean this order of includes:

#include "chess.h"

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

#include "odinutilities.h"

---

unnecessary casts

Most (if not all) the casts you use are unnecessary. Casts usually lead to bugs, remove them all if there's not a good reason for them to be.

---

ptrdiff_t

The proper type for pointer arithmetics is ptrdiff_t, not char nor int.

Variables such as to_y should be declared of this type.

You will need #include <stddef.h>

Answer 2

First, interesting code!

I agree with most of what @CacahueteFrito wrote in his review except for the #pragma once item. The method you are using is more portable. I sometimes use #pragma once when the editor defaults to it on windows (Visual Studio), but not for C++.

I will primarily address style.

Code Consistency
The code is consistently indented, which is great, but the use of braces ({ and }) in if statements is inconsistent. There are many places where braces are used around a single statement, but there are many places where braces aren't used around a single statement. It is more readable and maintainable when the code is consistent. Braces around a single statement are a good practice because quite often a new line of code needs to be inserted during maintenance.

Always Test the Return Value of Memory Allocation Functions
In most of the cases where memory is allocated the code is testing the return value, however, in the function MOVE_DATA return_all_moves(BOARD_STATE* plegal_board_state, char ignore_check) there is a call to malloc(size_t size) that is not tested. The function malloc() may also return NULL if there is not enough memory.

It might be better if the code was

char **tmp = malloc(move_data.array_size * sizeof(*p));
if (tmp) {
    move_data.moves = tmp;
}
else {
    // needs to be defined
}

because only the type of tmp needs to change if the type of move_data.moves is changed. This would be true for all the memory allocation performed in the program.

Casting Malloc
In modern C the functions malloc(), calloc() and realloc() return void *. It is not necessary to cast the memory returned by these statement to the proper type.

Readability
The code would be easier to read if there were some blank lines between blocks of code, such as after variable declarations at the top of the function, after a if then else block, after each of the cases in the switch statement.

Function Complexity
The function char store_all_moves_of_rock(char copy_board[8][8], char from_x, char from_y, MOVE_DATA* move_info, char color) is very complex and could be broken up into at least 4 sub functions, up, down, left and right. This function is probably misnamed, I believe is should be all_moves_of_rook rather than rock.