-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathREADME
191 lines (175 loc) · 11.1 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
==============================COMPILATION===================================
(*)steps: 1)make sure that the current directory is the one containing
the Makefile
2)use 'make' or 'make build' to compile the program
============================================================================
===========================PROJECT STRUCTURE================================
-> project has 2 main components: the controller and the internal board
logic.
(*)controller: 1)PRINCIPLES
- mediate the communication between XBoard and the
internal board logic.
- offer modularity.
- hide the I/O processing from the internal board logic
processing.
2)STRUCTURE
- 4 components: I)_in_buffer:
- holds the moves given to the engine
by XBoard that have to be processed
by the internal board logic component.
II)_out_buffer:
- holds the moves given to XBoard by
the engine.
III)_cmd_buffer:
- holds the commands given to the engine
by XBoard that have to be processes by
the controller itself.
IV)_flags:
- holds information about how the engine
should react + misc. information to help
the engine function.
- e.g: if the C_RESIGN flag is set by the
internal board logic component the controller
has to inform XBoard that the engine has resigned
if the C_FORCE flag is set by the
the controller then the internal board logic
component is not allowed to generate any moves
- the structure is made opaque to reduce the number of
mistakes made by the programmer and to offer data
encapsulation.
- found in controller directory.
3)WORKFLOW
- when first started, controller performs a handshake
with XBoard specifying some features if the version allows
it.
- after the handshake, the controller starts taking input
from XBoard and processes it by setting flags accordingly.
- if the controller receives a move from XBoard, it places
it in the input buffer(@_in_buffer) so that the internal
board logic component can process it; it also, toggles
the C_STM flag so that the internal logic component will
know if it can generate moves or not.
- after the internal board logic does its processing, the
controller informs XBoard if needed.
(*)internal board logic: 1)PRINCIPLES
- internal board logic is divided into 3 major
components: move generation, move evaluation,
board update which offers modularity and a clean
representation of how the engine does its internal
logic.
2)STRUCTURE
- 3 components: I)generators:
- folder which contains move
generation modules for each of the
pieces(only pawn move generation
available for now) and the main
move generation module which
combines all move generation modules
for the pieces.
II)evaluator
- module which handles the move selection.
process
III)update
- module which handles board updating
process.
- apart from the 3 main components, the internal board
logic contains 3 secondary components:
I)containers:
- folder which contains the data structures used by the
engine.
II)models:
- folder which contains modules that define how a board
and a move are represented and various functions used to
manipulate them.
III)logic:
- the main module of this component.
- handles the internal board logic processing
using the 3 main components mentioned above
and the controller's current state.
3)WORKFLOW
- in a nutshell, the internal logic processing
component checks the state of the controller
(the flags and the input buffer) and acts
accordingly
- e.g: if C_NEW was set, the board needs to be
cleared
if C_FORCE was set and the input buffer
contains a move, then it needs to update the
board for the side which does the move
============================================================================
==============================ALGORITHMS USED==================================
(*)pawn move generation: - basically all of the functions that start with @add
from the @pawn module do a linear traversal through
all possible pawn moves.
- @add_quiets has a time complexity of O(n), n = number
of pawns because all operations inside the loop are done in
constant time(the push operation from the arraylist has an
amortized cost of O(1)).
- @add_captures has a time complexity of O(n), n = number
of pawns because it does the same operations as @add_quiets +
it computes the piece code for the captured piece which is
done in constant time because the number of types of pieces
never changes.
MOVE GENERATION "ON-SPOT" VS LOOKUP TABLES
- we chose not to use lookup tables for pawn movement generation
because because it would have added an extra loop(iterating through
all possible moves for a pawn position) in the main loop(iterating
through all pawns).
- we actually tried the lookup table version and generating all
possible moves for the initial positions of the pawns was 6 times
slower than our current implementation.
(*)rook move generation: - the functions used find all the paths (going north, south, west and east)
a certain rook can go through; this process is repeated for both rooks
(if they are both alive)
Complexity : O(r + f), where r is the number of ranks (8) and
f is the number of files (8). So, in conclusion, it is
O(16) = O(1)
- unlike the bishops, the rook move finding algorithm was not
done using magic bitboards, due to time constraints. (maybe)
(*)castling: - castling was done by using a series of flags:
2 for each rook (to check if they moved)
1 for if the king is in check
1 for if the king already moved this game
these flags are saved on an 8 bit value
(4 bits for the white player, 4 bits for the black player)
- if all of the flags are in accordance to the rules of castling,
then there are only 2 possible moves: king-side castling and
queen-side castling
- the algorithm also checks if the path the king takes does not go through or
end up in a check position
-these moves are checked by looking up existing internal bitboards,
thus the time complexity is constant (O(1))
(*)move selection: - @select_move does a linear traversal through all available moves
in a given arraylist which has a time complexity of O(n), n = number
of available moves
- we chose a linear traversal because we have to look through all
available moves in order to find the one with the highest score
(*)board update: - the board updating process is done in constant time
(*)move filtering: - @filter_moves does a linear traversal through all available moves
in a given arraylist, makes a move, checks if the king will be in
check after making that move and adds it to a new arraylist if
the answer is no; this has a time complexity of O(n), n = number of
available moves
=================================================================================
================================SOURCES==========================================
1) PAWN MOVE GENERATION + MOVE ENCODING
https://peterellisjones.tumblr.com/post/41238723473/chess-engine-part-ii-move-encoding-and-move
2) INTERNAL BOARD REPRESENTATION + RANDOM EXPLANATIONS
https://www.chessprogramming.org/Main_Page
3) FOR BETTER UNDERSTANDING HOW BITBOARDS AND MOVE GENERATION WORKS
https://www.youtube.com/watch?v=QUNP-UjujBM&list=PLmN0neTso3Jxh8ZIylk74JpwfiWNI76Cs
4) INFO. ABOUT PIECE REPRESENTATION
http://pages.cs.wisc.edu/~psilord/blog/data/chess-pages/physical.html
5) MAGIC BITBOARDS
https://www.chessprogramming.org/Magic_Bitboards
https://rhysre.net/fast-chess-move-generation-with-magic-bitboards.html
https://essays.jwatzman.org/essays/chess-move-generation-with-magic-bitboards.html
=================================================================================
================================RESPONSIBILITIES=================================
COMAN Robert-Alexandru -> all controller-related work, bishop, queen and knight
move generation, move filtering
VRABIE-DINU DARIAN -> board representation, move representation, move evaluation
@logic module, rook, king and queen move generation, move filtering
MIHALCEA Laurentiu-Cristian -> board update, @containers, pawn and king move
generation, move filtering
=================================================================================