Chess Programming Tutorial

[romichess]

There seems to be a need for a proper chess programming tutorial for QB64. I hope this will be that tutorial. :)

LESSON 1: Basic Data Structures

Code: QB64: [Select]

1. ' ---------------------------------------------------------------------
2. ' The goal is to write a chess program that is simple, fast and strong.
3. ' ---------------------------------------------------------------------
4.  
5. ' -------------------------------------------------------------------------
6. ' The board representation is important for ease of coding and performance.
7. ' A 10x12 board is the easiest to program for and is fast enough.
8. ' The border of -1 values allows for efficient off of board test.
9. ' For example the white knight on b1 (board(22)) can only move to three
10. ' squares on the open board, but we do not want to take the time to
11. ' determine that ahead of time. Instead we just want to add the offsets
12. ' and test on the fly.
13. ' -------------------------------------------------------------------------
14.  
15. DIM SHARED board(120) AS INTEGER
16.  
17. CHESSBOARD:
18. DATA -1,-1,-1,-1,-1,-1,-1,-1,-1,-1
19. DATA -1,-1,-1,-1,-1,-1,-1,-1,-1,-1
20. DATA -1,14,10,12,15,16,11,+9,13,-1
21. DATA -1,+5,+4,+3,+2,+1,+8,+7,+6,-1
22. DATA -1,00,00,00,00,00,00,00,00,-1
23. DATA -1,00,00,00,00,00,00,00,00,-1
24. DATA -1,00,00,00,00,00,00,00,00,-1
25. DATA -1,00,00,00,00,00,00,00,00,-1
26. DATA -1,25,24,23,22,21,28,27,26,-1
27. DATA -1,34,30,32,35,36,31,29,33,-1
28. DATA -1,-1,-1,-1,-1,-1,-1,-1,-1,-1
29. DATA -1,-1,-1,-1,-1,-1,-1,-1,-1,-1
30.  
31. FOR i = 0 TO 119: READ board(i): NEXT
32.  
33. ' ---------------------------------------------------------------------------
34. ' The first thing that one should notice is that the numbers that represent
35. ' the pieces are indexes into a piece list rather than the typical piece type.
36. ' The piece list will be a doubly linked list so that pieces can be deleted
37. ' and later inserted again. The reason for this is so we do not have to scan
38. ' the entire board to find the pieces.
39. ' ---------------------------------------------------------------------------
40.  
41. DIM SHARED next_piece(40) AS INTEGER
42.  
43. NEXT_PIECE:
44. DATA 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20
45. DATA 21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,-1
46.  
47. FOR i = 0 TO 39: READ next_piece(i): NEXT
48.  
49. DIM SHARED previous_piece(40) AS INTEGER
50.  
51. PREVIOUS_PIECE:
52. DATA -1,-1,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19
53. DATA 20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38
54.  
55. FOR i = 0 TO 39: READ previous_piece(i): NEXT
56.  
57. ' ------------------------------------------
58. ' Now we need offsets for moving the pieces
59. ' ------------------------------------------
60. DIM SHARED bishop_offsets(4) AS INTEGER
61.  
62. BISHOP_OFFSETS:
63. DATA 9,11,-9,-11
64.  
65. FOR i = 0 TO 3: READ bishop_offsets(i): NEXT
66.  
67. DIM SHARED rook_offsets(4) AS INTEGER
68.  
69. ROOK_OFFSETS:
70. DATA 1,10,-1,-10
71.  
72. FOR i = 0 TO 3: READ rook_offsets(i): NEXT
73.  
74. DIM SHARED royal_offsets AS INTEGER
75.  
76. ROYAL_OFFSETS:
77. DATA 1,9,10,11,-1,-9,-10,-11
78.  
79. FOR i = 0 TO 7: READ royal_offsets(i): NEXT
80.  
81. DIM SHARED knight_offsets AS INTEGER
82.  
83. KNIGHT_OFFSETS:
84. DATA 8,12,19,21,-8,-12,-19,-21
85.  
86. FOR i = 0 TO 7: READ knight_offsets(i): NEXT
87.  
88. ' ------------------------------------------------------------------------
89. ' Since we are using piece list for efficiency we need an array for every
90. ' trait a piece has. A TYPE structure could be used but the simple fact is
91. ' that arrays are faster.
92. ' ------------------------------------------------------------------------
93. DIM SHARED piece_type(40) AS INTEGER
94.  
95. DATA -1,0,0,0,0,0,0,0,0,1,1,2,2,3,3,4,5,6,7,-1
96. DATA -1,8,8,8,8,8,8,8,8,9,9,10,10,11,11,12,13,14,15,-1
97.  
98. FOR i = 0 TO 39: READ piece_type(i): NEXT
99.  
100. DIM SHARED piece_square(40) AS INTEGER
101.  
102. DATA -1,35,34,33,32,31,38,37,36,27,22,26,23,28,21,24,25,-1,-1,-1
103. DATA -1,85,84,83,82,81,88,87,86,97,92,96,93,98,91,94,95,-1,-1,-1
104.  
105. FOR i = 0 TO 39: READ piece_square(i): NEXT
106.  

More piece trait arrays will be added as needed.

There are a few rough edges in the data because a few things will need to be worked out as we proceed. For example the white king that can castle has the index 16 but a white king that cannot castle has an index of 17 and also there is a pseudo piece that is not on the board. It is a terminator piece that when executed in the SELECT CASE statement cleans up and exits the move generator. These ideas may change as we go.

If there is something that is not understood please let me know! :)

[johnno56]

Um... Line 105 is expecting more "Data"...

J

[romichess]

Sorry, just add another -1 to the end of each data line.

 
DIM SHARED piece_square(40) AS INTEGER
 
DATA -1,35,34,33,32,31,38,37,36,27,22,26,23,28,21,24,25,-1,-1,-1
DATA -1,85,84,83,82,81,88,87,86,97,92,96,93,98,91,94,95,-1,-1,-1
 
FOR i = 0 TO 39: READ piece_square(i): NEXT

[romichess]

Lesson 2: Basic Move Generation

Only the knight and bishop will be covered in this lesson. The king and the other sliding pieces are similar and I'll just flesh them out later. Lesson 3 will be the pawns. They are much more complicated and deserve a lesson of their own. And Lesson 4 will be castling. I'm still a bit new to basic, so if this code can be made faster please let me know. In chess programming one wants to avoid if statements as much as possible because they are poorly predicted due to the changing position on the board. Hopefully the compiler will make jumptables. But, I do not know if it will or not. In C I would not use switch(value) case: because it is possible to create jumptables using function pointers. If jump tables exist in QB64 and I'm just not aware then please let me know and I'll change the code.

Code: QB64: [Select]

1. ' ----------------------------------------------------------------------------------
2. ' The move generator is what we will work on next. The decisions we make in the
3. ' move generator will help us define the data structures we need to conduct the
4. ' search. And will help up clean up the rough edges in the piece arrays. We will
5. ' be doing pseudo legal move generation which means there will be illegal moves
6. ' generated. We will catch those illegal moves when the other side generates moves.
7. ' ----------------------------------------------------------------------------------
8. FUNCTION Move_Generator
9.     ' First we need to initialize the everything went "ok" variable
10.     ok = -1
11.  
12.     ' We have a variable named wtm "white to move". This is standard in chess programming
13.     ' The start index is 0 for white and 20 for black
14.     piece_index = start_index(wtm)
15.  
16.     ' Now we need the first actual piece index
17.     piece_index = next_piece(piece_index)
18.  
19.     ' Now we loop through all the pieces
20.     ' A do loop will do because there will always be at least one piece
21.     DO
22.         ' Since we are using piece type indexes a SELECT CASE statement is perfect but first we need the piece type
23.         typ = piece_type(piece_index)
24.  
25.         ' And we only need to get the from square once
26.         from_square = piece_square(piece_index)
27.  
28.         SELECT CASE typ
29.             CASE 0 ' white pawn
30.             CASE 1 ' white knight
31.                 FOR i = 0 TO 3
32.                     to_square = from_square + knight_offsets(i)
33.                     target = board(to_square)
34.                     ' off board check
35.                     IF NOT target THEN
36.                         action = white_target(target)
37.                         SELECT CASE action
38.                             CASE 0 ' empty square
39.                                 Record_Move from_square, to_square
40.                             CASE 1 ' black piece
41.                                 Record_Capture from_square, to_square, target
42.                             CASE 2 ' illegal move detected
43.                                 Move_Generator = 0
44.                             CASE 3 ' white piece
45.                         END SELECT
46.                     END IF
47.                 NEXT
48.             CASE 2 ' white bishop
49.                 FOR i = 0 TO 3
50.                     to_square = from_square + bishop_offsets(i)
51.                     target = board(to_square)
52.                     WHILE NOT target
53.                         action = white_target(target)
54.                         SELECT CASE action
55.                             CASE 0 ' empty square
56.                                 Record_Move from_square, to_square
57.                             CASE 1 ' black piece
58.                                 Record_Capture from_square, to_square, target
59.                                 EXIT WHILE
60.                             CASE 2 ' illegal move detected
61.                                 Move_Generator = 0
62.                             CASE 3 ' white piece
63.                                 EXIT WHILE
64.                         END SELECT
65.                         to_square = to_square + bishop_offsets(i)
66.                         target = board(to_square)
67.                     WEND
68.                 NEXT
69.             CASE 3 ' white rook
70.             CASE 4 ' white queen
71.             CASE 5 ' white king that can still castle
72.             CASE 6 ' white king that cannot castle
73.             CASE 7 ' black pawn
74.             CASE 8 ' black knight
75.             CASE 9 ' black bishop
76.             CASE 10 ' black rook
77.             CASE 11 ' black queen
78.             CASE 12 ' black king cc
79.             CASE 13 ' black king cnc
80.             CASE 14 ' terminate move generator
81.         END SELECT
82.         piece_index = next_piece(piece_index)
83.     LOOP
84.     Move_Generator = ok
85. END FUNCTION
86.  
87. SUB Record_Move (from_square, to_square)
88.  
89. END SUB
90.  
91. SUB Record_Capture (from_square, to_square, target)
92.  
93. END SUB
94.  

[romichess]

Pawns are a bugger when it comes to efficiency. It is easy to use a plethora of IF statements for pawn move generation. And I'm serious that in chess programming If statements are to be avoided whenever possible. The situation with pawns is that they are really four different pieces depending what rank they are on. Therefore for efficiency they need to be treated as four different piece types. In RomiChess I went so far as to actually have different pawn types and to change the type as it moved up the board. Back then I was called by more than one the maestro of speed. For our tutorial we are not going to that extreme. Instead there are going to be 12 pawn types, LOL. :)

Code: QB64: [Select]

1.             CASE 0 ' white pawn
2.                 typ = white_pawn_board(from_square)
3.                 SELECT CASE typ
4.                     CASE 0 ' F2R, Forward 2 and a right capture possible
5.                         to_square = from_square + 10
6.                         target = board(to_square)
7.                         IF target = 0 THEN
8.                             Record_Move from_square, to_square
9.                             to_square = from_square + 20
10.                             target = board(to_square)
11.                             IF target = 0 THEN
12.                                 Record_Move_mark_ep from_square, to_square
13.                             END IF
14.                         END IF
15.                         to_square = from_square + 11
16.                         target = board(to_square)
17.                         action = white_target(target)
18.                         SELECT CASE action
19.                             CASE 0
20.                             CASE 1
21.                                 Record_Capture from_square, to_square, target
22.                             CASE 2
23.                                 Move_Generator = 0
24.                             CASE 3
25.                         END SELECT
26.                     CASE 1 ' LF2R
27.                     CASE 2 ' LF2
28.                     CASE 3 ' F1R
29.                     CASE 4 ' LF1R
30.                     CASE 5 ' LF1
31.                     CASE 6 ' FER, E is for en-passant
32.                     CASE 7 ' LFER
33.                     CASE 8 ' LFE
34.                     CASE 9 ' FPR, P is for promotion
35.                     CASE 10 ' LFPR
36.                     CASE 11 ' LFP
37.                 END SELECT
38.  

In the past when ram was limited this style of code was unthinkable. Instead shared code that used flags to control a single move generator loop was used so one loop could generate all moves. On today's cpus there is so much on chip instruction cache that we can opt for speed by proliferating piece specific code. Note that for the specific case of a pawn on rank 2 that can move two squares forward that only two IF statements were used. And the second IF statement does not execute if the pawn was blocked from moving. Now if the compiler deems that the SELECT CASE does not have enough cases to avoid using IF then it might substitute IF statements. Not much can be done in that case. The other pawn cases are similar and not hard to write when the idea is known. On the E cases only a check for an en-passant square need be made. On the case for promotion the Record_Promotion SUB is called which records 4 moves instead of one, promotion to Q, N, B and R.

[anttiylikoski]

Someone could try this one for a QB64 chess program

"https://en.wikipedia.org/wiki/B*"

The B Star algorithm.

Dr A. J. Y.
Europe

[romichess]

Someone could try this one for a QB64 chess program

"https://en.wikipedia.org/wiki/B*"

The B Star algorithm.

Dr A. J. Y.
Europe

B* being a best first approach depends on how well the "best" is evaluated ahead of time. If the best move is a queen sacrifice that mates in 16 ply (8 full moves) it may never be found by the B* algorithm. On the other hand if it were the goal to code an engine with human type oversights so as to have more human like frailties then B* is the way to go.

[TempodiBasic]

If there is something that is not understood please let me know! :)

for now and from my knowledge
I'm waiting to see how you embed this kind of chessboard 10x12 with the lists of pieces,  the offset of movements , the generation of moves legal or the selection of legal moves among those generated. And then how you build up the evaluation of the move to find the best move at a set deepness of search.
It is clear that this kind of AI is likely similar to neural perception.  But the puzzle is just at the begin state to get the structure that you are showing.
Thanks for share, I find interesting this approach to chessgame also if it doesn't copy the human behaviour.

[romichess]

Lesson 4 was to be about castling but I'm undecided exactly how I'm going to implement castling. It can be done the simple way which steals hundreds of millions of clock cycles per second even when castling is no longer possible or the complicated way that uses no clock cycles at all once castling is no longer possible.

Okay the move stack. We will start with a stack that is way too much to make sure we do not exceed the bounds. When testing we can keep track of the highest index we reach and adjust the size down later. A type structure is fine because only 4 bytes are needed and the machine instructions with their built in scaling can handle 4 byte types efficiently.

TYPE moves
    from_square as _unsigned _byte
    to_square as _unsigned byte
    target as _unsigned _byte
    special as _unsigned _byte
END TYPE

DIM move_stack(8000) as moves
DIM move_stack_index(80)

The way this works is move_stack_index(ply) points to the last move pushed onto the stack for each ply. The reason we need a move stack index for every ply is because of beta pruning in our alpha/beta search. When a ply is beta pruned the rest of the moves for that ply are discarded. So we just use the previous ply's stored move stack index.

So all the moves for the current ply are pushed onto the move stack. The top move is removed and sent to Make_Move then the search recursively calls itself pushing that ply's moves onto the stack and that is repeated to max depth. That really is all there is to the move stack. :)

Edit: Except there is also a sort to move the best candidate move to the top of the stack. The better the moves are sorted the better the alpha/beta algorithm works. Stockfish and other top engines get the depth they do because their move ordering code is superb.
   

[romichess]

for now and from my knowledge
I'm waiting to see how you embed this kind of chessboard 10x12 with the lists of pieces,  the offset of movements , the generation of moves legal or the selection of legal moves among those generated. And then how you build up the evaluation of the move to find the best move at a set deepness of search.
It is clear that this kind of AI is likely similar to neural perception.  But the puzzle is just at the begin state to get the structure that you are showing.
Thanks for share, I find interesting this approach to chessgame also if it doesn't copy the human behaviour.

I will do my best to show how the puzzle pieces fit together. Before the search code can be written that ties everything together we need to write all the support routines.

Make_Move
Take_Back
Is_Square_Attacked
Is_Side_In_Check
Evaluate_position
etc.

Thanks for your interest! :)

[romichess]

Needs very little comment.

Code: QB64: [Select]

1. ' --------------------------------------------------------------------------------------
2. ' Make_Move is rather simple. We make the move on the board and advance to the next ply.
3. ' --------------------------------------------------------------------------------------
4. SUB Make_Move (move_stack_index AS INTEGER)
5.     DIM move AS moves
6.     move = move_stack(move_stack_index)
7.     SELECT CASE move.special
8.         CASE 0 ' just a simple move
9.             piece_index = chess_board(move.from_square)
10.             chess_board(move.from_square) = 0
11.             chess_board(move.to_square) = piece_index
12.             piece_square(piece_index) = move.to_square
13.         CASE 1 ' just a simple capture
14.             ' delete captured piece
15.             next_piece(previous_piece(move.target)) = next_piece(move.target)
16.             previous_piece(next_piece(move.target)) = previous_piece(move.target)
17.             material_balance = material_balance - piece_value(move.target)
18.             piece_index = chess_board(move.from_square)
19.             chess_board(move.from_square) = 0
20.             chess_board(move.to_square) = piece_index
21.             piece_square(piece_index) = move.to_square
22.         CASE 2
23.  
24.     END SELECT
25.  
26.     move_list(ply) = move
27.     ply = ply + 1
28.     wtm = 1 - wtm
29.  
30. END SUB
31.  
32. ' ----------------------------------------------------------------------------
33. ' Take_Back is rather simple. We drop to the lower ply and take back the move.
34. ' ----------------------------------------------------------------------------
35. SUB Take_Back
36.     DIM move AS moves
37.     ply = ply - 1
38.     move = move_list(ply)
39.     SELECT CASE move.special
40.         CASE 0 ' a simple move
41.             piece_index = chess_board(move.to_square)
42.             chess_board(move.to_square) = 0
43.             chess_board(move.from_square) = piece_index
44.             piece_square(piece_index) = move.from_square
45.         CASE 1 ' a simple capture
46.             ' insert captured piece
47.             next_piece(previous_piece(move.target)) = move.target
48.             previous_piece(next_piece(move.target)) = move.target
49.             piece_index = chess_board(move.to_square)
50.             chess_board(move.from_square) = piece_index
51.             chess_board(move.to_square) = move.target
52.             material_balance = material_balance + piece_value(move.target)
53.         CASE 2
54.  
55.     END SELECT
56.  
57.     wtm = 1 - wtm
58.  
59. END SUB
60.  

[anttiylikoski]

Yes, thanks.

See

https://en.wikipedia.org/wiki/A*_search_algorithm

https://en.wikipedia.org/wiki/SSS*

https://www.chessprogramming.org/SSS*_and_Dual*

The RBFS algorithm

http://mas.cs.umass.edu/classes/cs683/lectures-2010/Lec6_Search5-F2010-4up.pdf

Dr A. J. Y.
Europe

[romichess]

Yes, thanks.

See

https://en.wikipedia.org/wiki/A*_search_algorithm

https://en.wikipedia.org/wiki/SSS*

https://www.chessprogramming.org/SSS*_and_Dual*

The RBFS algorithm

http://mas.cs.umass.edu/classes/cs683/lectures-2010/Lec6_Search5-F2010-4up.pdf

Dr A. J. Y.
Europe

All these algorithms I have read about at some point in the last 40 years. They are definitely interesting. And thanks for the links. But this is just a simple tutorial for a technically correct chess engine that will be able to search 20+ ply deep and yet will be simple enough for people to understand. And the Alpha/Beta negamax algorithm is the simplest and most proven algorithm to use. :)

[DANILIN]

table of index of lectures

http://mas.cs.umass.edu/classes/cs683/lectures-2010/

dont thanks me

[romichess]

table of index of lectures

http://mas.cs.umass.edu/classes/cs683/lectures-2010/

dont thanks me

My chess engine RomiChess was performing reinforcement learning since January of 2006 twelve years before AlphaZero. Up until AlphaZero came out RomiChess was practically the only successful learning chess engine. In a repeating tournament in the Netherlands RomiChess had climbed two whole classes just on the strength of its learning. And was about to climb up another class when the tournament holder had a hard drive crash and lost the learn file. Here is a quote from the Chess Programming Wiki, "RomiChess is famous for its learning approach". So, I might know a little bit about AI. :) But, thanks for the link. All info is useful!