Author Topic: Chess Programming Tutorial  (Read 13726 times)

0 Members and 1 Guest are viewing this topic.

This topic contains a post which is marked as Best Answer. Press here if you would like to see it.

Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Chess Programming Tutorial
« on: January 21, 2020, 01:18:41 am »
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! :)
« Last Edit: January 21, 2020, 03:44:29 am by romichess »
My name is Michael, but you can call me Mike :)

Offline johnno56

  • Forum Resident
  • Posts: 1270
  • Live long and prosper.
    • View Profile
Re: Chess Programming Tutorial
« Reply #1 on: January 21, 2020, 01:29:29 am »
Um... Line 105 is expecting more "Data"...

J
Logic is the beginning of wisdom.

Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial
« Reply #2 on: January 21, 2020, 01:54:56 am »
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
My name is Michael, but you can call me Mike :)

Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial
« Reply #3 on: January 21, 2020, 03:21:12 am »
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.  
  86. SUB Record_Move (from_square, to_square)
  87.  
  88.  
  89. SUB Record_Capture (from_square, to_square, target)
  90.  
  91.  
« Last Edit: January 21, 2020, 03:33:20 am by romichess »
My name is Michael, but you can call me Mike :)

Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial: Lesson 3, pawns
« Reply #4 on: January 21, 2020, 11:29:53 am »
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.
My name is Michael, but you can call me Mike :)

Offline anttiylikoski

  • Newbie
  • Posts: 25
    • View Profile
Re: Chess Programming Tutorial
« Reply #5 on: January 22, 2020, 04:30:51 pm »
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


Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial
« Reply #6 on: January 22, 2020, 10:26:13 pm »
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.
My name is Michael, but you can call me Mike :)

Offline TempodiBasic

  • Forum Resident
  • Posts: 1792
    • View Profile
Re: Chess Programming Tutorial
« Reply #7 on: January 23, 2020, 07:59:08 pm »
Quote
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.
Programming isn't difficult, only it's  consuming time and coffee

Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial: Lesson 4, The move Stack
« Reply #8 on: January 24, 2020, 02:54:45 pm »
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.
   
« Last Edit: January 24, 2020, 03:01:35 pm by romichess »
My name is Michael, but you can call me Mike :)

Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial
« Reply #9 on: January 24, 2020, 04:02:08 pm »
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! :)
My name is Michael, but you can call me Mike :)

Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial: Lesson 5, Make_Move and Take_Back
« Reply #10 on: January 24, 2020, 05:16:31 pm »
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.  
  31. ' ----------------------------------------------------------------------------
  32. ' Take_Back is rather simple. We drop to the lower ply and take back the move.
  33. ' ----------------------------------------------------------------------------
  34. SUB Take_Back
  35.     DIM move AS moves
  36.     ply = ply - 1
  37.     move = move_list(ply)
  38.     SELECT CASE move.special
  39.         CASE 0 ' a simple move
  40.             piece_index = chess_board(move.to_square)
  41.             chess_board(move.to_square) = 0
  42.             chess_board(move.from_square) = piece_index
  43.             piece_square(piece_index) = move.from_square
  44.         CASE 1 ' a simple capture
  45.             ' insert captured piece
  46.             next_piece(previous_piece(move.target)) = move.target
  47.             previous_piece(next_piece(move.target)) = move.target
  48.             piece_index = chess_board(move.to_square)
  49.             chess_board(move.from_square) = piece_index
  50.             chess_board(move.to_square) = move.target
  51.             material_balance = material_balance + piece_value(move.target)
  52.         CASE 2
  53.  
  54.     END SELECT
  55.  
  56.     wtm = 1 - wtm
  57.  
  58.  
« Last Edit: January 24, 2020, 05:19:59 pm by romichess »
My name is Michael, but you can call me Mike :)

Offline anttiylikoski

  • Newbie
  • Posts: 25
    • View Profile

Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial
« Reply #12 on: January 25, 2020, 03:33:32 am »
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. :)
My name is Michael, but you can call me Mike :)

Offline DANILIN

  • Forum Regular
  • Posts: 128
    • View Profile
    • Danilin youtube
Re: Chess Programming Tutorial
« Reply #13 on: January 25, 2020, 04:44:16 am »
table of index of lectures

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

dont thanks me
Russia looks world from future. big data is peace data.
https://youtube.com/playlist?list=PLBBTP9oVY7IagpH0g9FNUQ8JqmHwxDDDB
i never recommend anything to anyone and always write only about myself

Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial
« Reply #14 on: January 25, 2020, 05:11:43 am »
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!
My name is Michael, but you can call me Mike :)