-
Notifications
You must be signed in to change notification settings - Fork 17
/
Copy pathDOC.html
413 lines (384 loc) · 11.7 KB
/
DOC.html
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
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
<!DOCTYPE html>
<html>
<head>
<title>mchess design documentation</title>
<style>
table, th, td {
border: 1px solid black;
border-collapse: collapse;
}
th, td {
padding: 5px;
text-align: right;
}
</style>
</head>
<body>
This document is a description of the design of <em>mchess</em> and
<em>mchess2</em>
<h1>Piece representation</h1>
The chess board consists of 64 squares. Each square may be empty or contain a
white or black piece. Each piece is given an integer value (this is not
related to the <em>worth</em> of the piece in number of pawns).
<p/>
This enumeration is called <em>e_piece</em> and is defined in the file
<em>CMove.h</em>:
<pre>
typedef enum {
EM = 0, // Empty
WP = 1, // White Pawn
WN = 2, // White Knight
WB = 3, // White Bishop
WR = 4, // White Rook
WQ = 5, // White Queen
WK = 6, // White King
BP = -1, // Black Pawn
BN = -2, // Black Knight
BB = -3, // Black Bishop
BR = -4, // Black Rook
BQ = -5, // Black Queen
BK = -6, // Black King
IV = 99 // INVALID
} e_piece;
</pre>
The above is merely an enumeration, and the actual numerical values are
arbitrary. However, I do in the following rely on the fact that:
<ul>
<li>The empty space has value zero</li>
<li>All white pieces have positive values</li>
<li>All black pieces have negative values</li>
</ul>
<p/>
Additionally, I have a special value for an <em>invalid</em> piece. This has
several uses, the foremost will be explained in the following.
<h1>Square representation</h1>
An important function in a chess engine is to be able to generate a list of all
legal moves in a given position. This function is used all the time, and
therefore must be as fast as possible.
<p/>
When writing such a function, one must first consider how to represent the
board configuration, i.e. where each piece is placed, or equivalently, which
piece is on a given square.
<p/>
I've chosen to represent the board as a simple
one-dimensional array of integers. Each index in the array corresponds to a
particular square, and each value in the array is the corresponding piece,
according to the enumeration above.
<p/>
When generating a list of legal moves, it is necessary to check if a piece is
about to move outside the edge of the board. For instance, a rook on H1 can not
move to the right.
<p/>
This is dealt with in a very smart way: The board is <em>enlarged</em>, so that
it is surrounded by two layers of invalid squares. This gives a total of 12
rows of ten squares each, i.e. 120 elements in the array.
<table>
<tr>
<td>110</td>
<td>111</td>
<td>112</td>
<td>113</td>
<td>114</td>
<td>115</td>
<td>116</td>
<td>117</td>
<td>118</td>
<td>119</td>
</tr>
<tr>
<td>100</td>
<td>101</td>
<td>102</td>
<td>103</td>
<td>104</td>
<td>105</td>
<td>106</td>
<td>107</td>
<td>108</td>
<td>109</td>
</tr>
<tr>
<td>90</td>
<td><b>A8</b></td>
<td><b>B8</b></td>
<td><b>C8</b></td>
<td><b>D8</b></td>
<td><b>E8</b></td>
<td><b>F8</b></td>
<td><b>G8</b></td>
<td><b>H8</b></td>
<td>99</td>
</tr>
<tr>
<td>80</td>
<td><b>A7</b></td>
<td><b>B7</b></td>
<td><b>C7</b></td>
<td><b>D7</b></td>
<td><b>E7</b></td>
<td><b>F7</b></td>
<td><b>G7</b></td>
<td><b>H7</b></td>
<td>89</td>
</tr>
<tr>
<td>70</td>
<td><b>A6</b></td>
<td><b>B6</b></td>
<td><b>C6</b></td>
<td><b>D6</b></td>
<td><b>E6</b></td>
<td><b>F6</b></td>
<td><b>G6</b></td>
<td><b>H6</b></td>
<td>79</td>
</tr>
<tr>
<td>60</td>
<td><b>A5</b></td>
<td><b>B5</b></td>
<td><b>C5</b></td>
<td><b>D5</b></td>
<td><b>E5</b></td>
<td><b>F5</b></td>
<td><b>G5</b></td>
<td><b>H5</b></td>
<td>69</td>
</tr>
<tr>
<td>50</td>
<td><b>A4</b></td>
<td><b>B4</b></td>
<td><b>C4</b></td>
<td><b>D4</b></td>
<td><b>E4</b></td>
<td><b>F4</b></td>
<td><b>G4</b></td>
<td><b>H4</b></td>
<td>59</td>
</tr>
<tr>
<td>40</td>
<td><b>A3</b></td>
<td><b>B3</b></td>
<td><b>C3</b></td>
<td><b>D3</b></td>
<td><b>E3</b></td>
<td><b>F3</b></td>
<td><b>G3</b></td>
<td><b>H3</b></td>
<td>49</td>
</tr>
<tr>
<td>30</td>
<td><b>A2</b></td>
<td><b>B2</b></td>
<td><b>C2</b></td>
<td><b>D2</b></td>
<td><b>E2</b></td>
<td><b>F2</b></td>
<td><b>G2</b></td>
<td><b>H2</b></td>
<td>39</td>
</tr>
<tr>
<td>20</td>
<td><b>A1</b></td>
<td><b>B1</b></td>
<td><b>C1</b></td>
<td><b>D1</b></td>
<td><b>E1</b></td>
<td><b>F1</b></td>
<td><b>G1</b></td>
<td><b>H1</b></td>
<td>29</td>
</tr>
<tr>
<td>10</td>
<td>11</td>
<td>12</td>
<td>13</td>
<td>14</td>
<td>15</td>
<td>16</td>
<td>17</td>
<td>18</td>
<td>19</td>
</tr>
<tr>
<td>0</td>
<td>1</td>
<td>2</td>
<td>3</td>
<td>4</td>
<td>5</td>
<td>6</td>
<td>7</td>
<td>8</td>
<td>9</td>
</tr>
</table>
<p/>
When testing whether a move is legal, it is enough to test if the target square
is empty or contains an enemy piece. It is not even necessary to exlicitly test
for invalid squares.
<p/>
An enumeration is used to define the index of each square. This enumeration is
defined in the file <em>CSquare.h</em>. This is purely for code readability,
i.e. if I refer to a square as E2 it is more readable, than using the integer
35.
<pre>
enum // Squares
{
A8 = 91, B8, C8, D8, E8, F8, G8, H8,
A7 = 81, B7, C7, D7, E7, F7, G7, H7,
A6 = 71, B6, C6, D6, E6, F6, G6, H6,
A5 = 61, B5, C5, D5, E5, F5, G5, H5,
A4 = 51, B4, C4, D4, E4, F4, G4, H4,
A3 = 41, B3, C3, D3, E3, F3, G3, H3,
A2 = 31, B2, C2, D2, E2, F2, G2, H2,
A1 = 21, B1, C1, D1, E1, F1, G1, H1,
};
</pre>
<h2>The CSquare class</h2>
It does become necessary to determine the row and/or column number of a given
square, for instance when checking for pawn promotion. Therefore I've chosen
to write a class <em>CSquare</em> to handle this. The following is the
essential ingredients:
<pre>
class CSquare
{
public:
int row() const {return (m_sq/10) - 1;} // returns 1 - 8
int col() const {return (m_sq%10);} // returns 1 - 8
operator int() const { return m_sq; } // Implicit conversion to integer
private:
uint8_t m_sq; // Internal representation, 0 - 119.
}; // end of class CSquare
</pre>
The conversion operator <em>int()</em> allows the CSquare class to be used
directly as an array index.
<h1>Move representation</h1>
The next to consider is how to represent a move. Obviously, we need an
originating square, and a target square. However, this is not quite enough.
When a pawn reaches the back rank, it may promote to any other piece, and this
must be given as well.
<h2>The CMove class</h2>
The class CMove is used to represent a single chess move. The essential
ingredients in this class are:
<pre>
class CMove
{
public:
CSquare From(void) const {return m_from;}
CSquare To(void) const {return m_to;}
private:
CSquare m_from;
CSquare m_to;
int8_t m_promoted; // This handles pawn promotion.
}; // end of CMove
</pre>
<p/>
Note the member variable <em>m_promoted</em>. This is only used during pawn
promotion, where it contains the piece that the pawn promotes to. In case of an
ordinary move, the variable is not used, and should be set to zero (empty).
<h2>Enhancements</h2>
This class contains two additional private member variables:
<pre>
int8_t m_piece;
int8_t m_captured;
</pre>
The first, <em>m_piece</em>, contains the current piece being moved, the second
variable, <em>m_captured</em>, contains the piece being captured, if any. They
are both used only for printing the current move to the user.
<h2>The CMoveList class</h2>
When generating a list of all the legal moves in a chess position, it becomes necessary to
manipulate lists of moves. I've found it convenient to write a separate class just for this:
<pre>
class CMoveList
{
public:
void clear()
{
m_moveList.clear();
}
void push_back(const CMove& move)
{
m_moveList.push_back(move);
}
unsigned int size() const
{
return m_moveList.size();
}
const CMove & operator [] (unsigned int ix) const { return m_moveList[ix]; }
private:
std::vector<CMove> m_moveList;
}; // end of CMoveList
</pre>
<p/>
The purpose of this class is just to encapsulate the semantics of an ordinary
array. Here I've chosen to implement the array using the <em>std::vector</em>
container class.
<p/>
When populating the list, the functions <em>clear()</em> and <em>push_back(move)</em> are used.
When examining the list, the functions <em>size()</em> and <em>operator []</em> are used.
<h1>Board representation</h1>
<h2>The CBoard class</h2>
This class is defined in the file <em>CBoard.h</em> and contains all the
information defining the current position on the board. Of course, this
includes the above mentioned array. Additionally, it includes an integer value
that specifies whether it is the white or the black pieces to move.
<pre>
class CBoard
{
public:
void newGame();
void find_legal_moves(CMoveList &moves) const;
void make_move(const CMove &move);
int get_value();
private:
std::vector<int8_t> m_board;
int m_side_to_move;
}; // end of class CBoard
</pre>
<p/>
The function <em>newGame()</em> resets the board to the starting position, the
function <em>make_move()</em> updates the board position with the supplied
move, and finally <em>find_legal_moves()</em> generates a list of all legal moves
in the current board position.
<h2>Enhancements</h2>
To improve performance, I've added another member variable that keeps track of
the current material balance.
<pre>
int m_material;
</pre>
This is kind of like a cache. Instead of
calculating the material balance after each move, it is much faster to check
for captures and promotion, and adjust the current cache incrementally.
<h1>Searching for the best move</h1>
<h2>The AI class</h2>
This class contains an implementation of the alpha-beta pruning algorithm.
This is a complicated function, and is best described in <a
href="http://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning">wikipedia</a>
and the <a href="http://chessprogramming.wikispaces.com/Alpha-Beta">chess
programming</a> site.
The class interface is very simple, however:
<pre>
class AI
{
public:
AI(CBoard& board) : m_board(board) { }
CMove find_best_move();
private:
int search(int alpha, int beta, int level);
CBoard& m_board;
}; // end of class AI
</pre>
Note that the <em>m_board</em> variable is a reference. This is to avoid making copies of the entire <em>CBoard</em> class.
<h1>Final remarks</h1>
These are the basic ingredients necessary to make a working chess engine.
There only remains to write a <em>main()</em> function that instantiates a
<em>CBoard</em> and a <em>AI</em> object. The you must read the user input and
call <em>ai.find_best_move()</em>.
</body>
</html>