# Piece of chess engine, which accomplishes move generation

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.
*/
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)) {
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) {
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) {
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) {
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))) {
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) {
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))) {
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) {
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))) {
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) {
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))) {
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) {
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;
}

* 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) {
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) {
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 from_y, MOVE_DATA* move_info, char color, char to_x, char to_y) {
if (copy_board[to_y][to_x] * color <= 0) {
create_move_string(from_x, from_y, to_x, to_y, (char) 0));
return no_error;
}
return 1;
}


#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 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.
• You have a lot of primitive obsession. Make a lot more data types, and replace all these raw types being passed around everywhere. I see a dire need for at least Board, Point, TeamColor (an enum, iffy on the name), and possibly quite a few more. – Alexander - Reinstate Monica Jul 31 '19 at 4:48
• "which accomplishes the generation of all (yet unvalidated) moves" That's a lot of moves. Did you mean all moves possible in one turn instead? – Mast Jul 31 '19 at 7:39
• It's not enough for an answer, but I think you copied and pasted your comment from the rook function on to the knight one and forgot to change 'rook' to 'knight'. – John Gowers Jul 31 '19 at 14:59
• @Mast Yes, I thought this was kinda obvious. I will change it :) – TVSuchty Aug 1 '19 at 12:46
• @JohnGowers Exactly, thanky you! – TVSuchty Aug 1 '19 at 12:47

## 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.

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>

• Hey! Thanks for your answer! I thought a processor will need less time adding chars instead of integers? Is this true? If I typedef it, would not I use char anyway just by an alias? – TVSuchty Jul 30 '19 at 14:00
• @TVSuchty No, it isn't true (unless you have an 8-bit processor ;-) – Cacahuete Frito Jul 30 '19 at 14:04
• @TVSuchty In C the int and unsigned int type will usually be the word size of the processor so all the native operations for the processor will run faster with int. char and short might be used in arrays where memory is tight. – pacmaninbw Jul 30 '19 at 14:08
• @pacmaninbw That's why I put the link. But if the compiler accepts it (most of them, since a decade ago), it's very valid. And when you forget to change the FILE_MACRO_H name after copy&paste (it happened to me more than once), it's a pain in the ass until you find it. #pragma doesn't have that problem. The link provides all this info and discussion, and anyone is of course free to use whatever, and I just pointed to the info just in case he didn't know :) – Cacahuete Frito Jul 30 '19 at 14:37
• This is totally bike shedding, but I disagree on the suggestion to change store_all_moves_of_pawn() to store_moves_pawn(). Perhaps store_pawn_moves() is fine, but my personal fave is store_all_pawn_moves. I would recommend a more expressive approach. Keystrokes are free, and monitors are giant, there's really no need to be pinched on character count. – Alexander - Reinstate Monica Jul 31 '19 at 4:51

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++.

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.

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.
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.
• Just a note that on many 64 bit systems (at least Linux and Mac I think, not sure of Windows), with sane environment settings, any reasonable use of malloc will never return NULL. Program(s) will start being killed if system runs out of memory and swap. A reasonable program will not run out of its own 64 bit virtual address space. It's still good to check it of course, but it's not worth putting much effort into handling it gracefully (just abort() or something). – hyde Jul 30 '19 at 23:10
• @pacmaninbw In that case you should really consider if you want to use a real operating system (such as embedded Linux), and research how you can configure and control malloc behavior (such as make it return NULL reliably, if your application is such that you can actually do something useful about it). – hyde Jul 31 '19 at 6:17