Text Only | Text with Attachments

QB64.org Forum

Active Forums => Programs => Topic started by: romichess on January 21, 2020, 01:18:41 am

Title: Chess Programming Tutorial
Post by: romichess 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! :)
Title: Re: Chess Programming Tutorial
Post by: johnno56 on January 21, 2020, 01:29:29 am
Um... Line 105 is expecting more "Data"...

J
Title: Re: Chess Programming Tutorial
Post by: romichess 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
Title: Re: Chess Programming Tutorial
Post by: romichess 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
  86.  
  87. SUB Record_Move (from_square, to_square)
  88.  
  90.  
  91. SUB Record_Capture (from_square, to_square, target)
  92.  
  94.  
Title: Re: Chess Programming Tutorial: Lesson 3, pawns
Post by: romichess 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.
Title: Re: Chess Programming Tutorial
Post by: anttiylikoski 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

Title: Re: Chess Programming Tutorial
Post by: romichess on January 22, 2020, 10:26:13 pm
Quote from: anttiylikoski 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

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.
Title: Re: Chess Programming Tutorial
Post by: TempodiBasic 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.
Title: Re: Chess Programming Tutorial: Lesson 4, The move Stack
Post by: romichess 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.
   
Title: Re: Chess Programming Tutorial
Post by: romichess on January 24, 2020, 04:02:08 pm
Quote from: TempodiBasic on January 23, 2020, 07:59: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! :)
Title: Re: Chess Programming Tutorial: Lesson 5, Make_Move and Take_Back
Post by: romichess 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.  
  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.  
  60.  
Title: Re: Chess Programming Tutorial
Post by: anttiylikoski on January 24, 2020, 08:55:59 pm
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

Title: Re: Chess Programming Tutorial
Post by: romichess on January 25, 2020, 03:33:32 am
Quote from: anttiylikoski on January 24, 2020, 08:55:59 pm
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. :)
Title: Re: Chess Programming Tutorial
Post by: DANILIN 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
Title: Re: Chess Programming Tutorial
Post by: romichess on January 25, 2020, 05:11:43 am
Quote from: DANILIN 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

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!
Title: Re: Chess Programming Tutorial: Lesson 5, Search
Post by: romichess on January 25, 2020, 05:44:46 am
The search routine is recursive. Some people understand recursion without much trouble. Others find it a difficult idea to master. As this is a chess programming tutorial and not a programming tutorial it would be best for the confused reader to research recursion on their own. The search routine in this example is the nega_max variant. It is really difficult to wrap one's brain around. And yet it is quite simple. We are recursively calling Search in a way that we change sides and look at the situation from the other sides point of view. Alpha is the lower bound and beta is the higher bound. So if we are currently with white to move then as we find better moves alpha increases because alpha is the best we have found so far. However, beta represents the best that the other side has found so far. So when we call Search -beta becomes the other sides alpha and our -alpha becomes the other sides beta. And since alpha and beta are negated so is the score returned negated to flip it back to our point of view.

The search control function searches the root moves and in a more developed state does time management and plays book moves, etc. It starts out with alpha and beta set to -INFINITY and INFINITY which is -/+ 10000 in this case. Even though we might set the search depth to say 8 ply we search using iterative deepening. That is to develop a principle variation so as to order the moves better that then will greatly speed up the nega_max algorithm. This is the most basic search code possible. It is good enough to get a working engine.  And it is all I can do right now because it is way past my bedtime, again. gn

NOTE: I have modified the move stack definition to include a score and a stats integer. It is a little wasteful to include a score and a stats with every single move in the move stack but it makes the coding more simple.

Code: QB64: [Select]
  1. FUNCTION Search (alpha AS INTEGER, beta AS INTEGER, depth AS INTEGER)
  2.     ' IF depth < 1 then Search = Qsearch(alpha, beta)
  3.     IF NOT Move_Generator THEN Search = 10000
  4.     FOR i = move_stack_index(ply) TO move_stack_index(ply - 1) + 1 STEP -1
  5.         Make_Move (i)
  6.         move_stack(i).score = -Search(-beta, -alpha, depth - 1)
  7.         Take_Back
  8.         IF move_stack(i).score > alpha THEN
  9.             IF move_stack(i).score >= beta THEN Search = beta
  10.             alpha = move_stack(i).score
  11.         END IF
  12.     NEXT
  13.     Search = alpha
  15.  
  16. SUB Search_control
  17.     legal = Move_Generator
  18.     FOR depth = 1 TO max_depth
  19.         FOR i = move_stack_index(ply) TO move_stack_index(ply - 1) + 1 STEP -1
  20.             Make_Move (i)
  21.             move_stack(i).score = Search(-10000, 10000, depth - 1)
  22.             Take_Back
  23.             IF move_stack(i).score > best THEN
  24.                 best = score
  25.                 move = move_stack(i)
  26.             END IF
  27.         NEXT
  28.         ' Sort_Root_Moves
  29.     NEXT
Title: Re: Chess Programming Tutorial
Post by: anttiylikoski on January 25, 2020, 09:58:25 am
Ref: the signature---

You say

"Russia looks world from future. big data is peace data i never
recommend anything to anyone and always write only about myself"

Russia -- First







adversary



The Satan-2 has some ~5 MIRV warheads, about 500kt thermonuclear.

And:



Dr A. J. Y.
Finland

Title: Re: Chess Programming Tutorial: Lesson 6, castling
Post by: romichess on January 29, 2020, 07:40:22 pm
I have opted for a simple way. This way is new and even simpler than the traditional simple way. The traditional way uses bit flags and logical operator test called castling rights. This new way uses more memory but is really much more simple. Since the simple ways always take clock cycles even if castling is no longer possible this new way will not be any slower and might be faster as the mechanism is more simple.

We keep a count array the size of the board.

DIM count(120) AS INTEGER 'initialized to -1

In Make_Move and Takeback we increment and decrement respectively the from square and to square count of all moves. That way the test for the king's right to castle is as simple as, IF count(E1). That is more simple than IF (castle AND 1) and what is needed to maintain the flag bits in the first place. :) Here is the king move code with castling.
Code: QB64: [Select]
  1.             CASE 5 ' white king that can still castle
  2.                 FOR i = 0 TO 7
  3.                     to_square = from_square + royal_offsets(i)
  4.                     target = board(to_square)
  5.                     ' off board check
  6.                     IF NOT target THEN
  7.                         action = white_target(target)
  8.                         SELECT CASE action
  9.                             CASE 0 ' empty square
  10.                                 Record_Move from_square, to_square
  11.                             CASE 1 ' black piece
  12.                                 Record_Capture from_square, to_square, target
  13.                             CASE 2 ' illegal move detected
  14.                                 Move_Generator = 0
  15.                             CASE 3 ' white piece
  16.                         END SELECT
  17.                     END IF
  18.                 NEXT
  19.                 IF count(E1) THEN
  20.                     IF count(H1) THEN
  21.                         IF chess_board(F1) = 0 AND chess_board(G1) = 0 THEN
  22.                             IF Not_Attacked_By(BLACK, E1) AND Not_Attacked_By(BLACK, F1) AND Not_Attacked_By(BLACK, G1) THEN
  23.                                 Record_Castle(E1, G1)
  24.                             END IF
  25.                         END IF
  26.                     END IF
  27.                     IF count(A1) THEN
  28.  
  29.                     END IF
  30.                 END IF
  31.  
Title: Re: Chess Programming Tutorial: Lesson 7, Going forward
Post by: romichess on January 29, 2020, 08:16:50 pm
The above 6 lessons form the basis for our chess engine. Going forward I'm going to finish each routine and post the code. The very next goal is also something new, AFAIK. Instead of the traditional search we are going to write a very useful new search function called something like Gen_One_Move_Then_Q. Q stands for quiescent which means a quiet space. At the leaf node of every search a qsearch is done to resolve capture sequences that remain on the board. It is impossible to have a strong chess engine without resolving captures. We could get away with a static exchange analysing function for a simple chess engine but I much prefer a full capture search.

This new function will have several benefits. First of all, all the moves generated will be legal as the illegal moves from the pseudo legal move generator will be caught by the qsearch. The second advantage will be that the moves will be evaluated and have a score. That will mean a good move ordering which is so important for how fast the alpha/beta algorithm will run. Yes, I have already mentioned the importance of move ordering. I'm repeating it because it is one of the most important things in achieving a deep searching chess engine. It is magnitudes better to have slow code and excellent move ordering than to have fast code and poor move ordering!
Title: Re: Chess Programming Tutorial
Post by: SMcNeill on January 29, 2020, 09:18:46 pm
Do you guys know what I’d love to see, and what I thought about working on sometime?

A custom chess engine!!

Everyone always tries to build a chess game that follows all the rules of chess, and that’s fine an all — but it’s so LIMITING!!

Pass a chess set to a group of four year olds, spend a few hours teaching them the rules, and then leave them alone.  When you go back into the room and check on them three hours later, you’ll find they have the car from Monopoly, Mr Potato Head’s ear, two marbles, and a Barbie inserted into the game!!  And they’re having a blast!!

I’d love to see this flexibility inserted into a computerized chess game sometime!  My concept would be:

1) Load icons to form the pieces on each side — name them and number them as you do.
2) Create the game board, of X by Y size, in whatever shades/colors are desired, with any agreed upon obstacles.  Add a black hole, a swamp, a tower — whatever!  It’s basically just a set of choosing icons, setting them on the board, and naming them.
3) Each player places their pieces on the board.
4) You then choose the rules for your pieces and how they interact with the board.

“Pawns” move “1 step forward.”
“Pawns” attack “1 step diagional.”
“Cars” move “6 steps forward” and “run over everything.”

5) You then save the game and ruleset for quick loading and replayability.

Then you play against your opponent(s)!
Title: Re: Chess Programming Tutorial: Lesson 8, First Official Code
Post by: romichess on January 29, 2020, 09:25:35 pm
Now it is time to start writing the official code starting with the heart of the chess engine which is the one move generator plus quiescent search.


Code: QB64: [Select]
  1. TYPE moves
  2.     from_square AS _UNSIGNED _BYTE
  3.     to_square AS _UNSIGNED _BYTE
  4.     target AS _UNSIGNED _BYTE
  5.     special AS _UNSIGNED _BYTE
  6.     score AS INTEGER
  8.  
  9. CONST TERMINATE = 0
  10.  
  12. DIM SHARED move_stack(8000) AS moves
  13.  
  14. SUB Search_One_Q (alpha AS INTEGER, beta AS INTEGER)
  15.     Generate_Moves
  16.     i = move_stack_index(ply)
  17.     while move_stack(i).special <> TERMINATE
  18.         Make_Move i
  19.         move_stack(i).score = Qsearch(alpha, beta)
  20.         Take_Back
  21.         i = i - 1
  22.     WEND
  24.  
Title: Re: Chess Programming Tutorial
Post by: romichess on January 29, 2020, 09:31:41 pm
Quote from: SMcNeill on January 29, 2020, 09:18:46 pm
Do you guys know what I’d love to see, and what I thought about working on sometime?

A custom chess engine!!

Everyone always tries to build a chess game that follows all the rules of chess, and that’s fine an all — but it’s so LIMITING!!

Pass a chess set to a group of four year olds, spend a few hours teaching them the rules, and then leave them alone.  When you go back into the room and check on them three hours later, you’ll find they have the car from Monopoly, Mr Potato Head’s ear, two marbles, and a Barbie inserted into the game!!  And they’re having a blast!!

I’d love to see this flexibility inserted into a computerized chess game sometime!  My concept would be:

1) Load icons to form the pieces on each side — name them and number them as you do.
2) Create the game board, of X by Y size, in whatever shades/colors are desired, with any agreed upon obstacles.  Add a black hole, a swamp, a tower — whatever!  It’s basically just a set of choosing icons, setting them on the board, and naming them.
3) Each player places their pieces on the board.
4) You then choose the rules for your pieces and how they interact with the board.

“Pawns” move “1 step forward.”
“Pawns” attack “1 step diagional.”
“Cars” move “6 steps forward” and “run over everything.”

5) You then save the game and ruleset for quick loading and replayability.

Then you play against your opponent(s)!

There is something like that that already exist. It was from a couple decades ago. It is called something like the "Incredible Game Machine". The user defined the board type, squares or hexes, size and the pieces with their rules. Also what the board looked like and the pieces looked like. More than that I do not remember. 
Title: Re: Chess Programming Tutorial
Post by: STxAxTIC on January 29, 2020, 09:48:17 pm
I love the question of an abstracted game engine. Not for games, you all know me - but for the sake of creating a Turing complete world within a world. Indeed the chess engine can be, ahem, in the right language - very easily generalized for any kind of topology (a Cartesian board is very last millennium), abstract "pieces", which in this sense don't even need to be discrete - entities are more generally fields, waves, blobs of density - stuff along those lines. Turn-based moves become asynchronous events, etc. etc.

And if you've done it right, all you have to do is set some initial parameters to have chess, checkers, Chinese checkers, stratego, backgammon, whatever. Poker. It's endless.

Hell of a big job. You may as well design an OOP sublanguage for QB64 first, it'll make things way easier.

I like the mission though.
Title: Re: Chess Programming Tutorial
Post by: romichess on January 30, 2020, 02:03:30 am
At the end of any day in which I have written a substantial amount of code I will post the code. Please do not try to compile the code, yet. The code that is posted is for tutorial purposes so one can follow the thought process. As stated earlier my first goal is to complete the Search_One_Q subroutine and all of its subroutines. That in itself will make for a nice one move search engine!

Code: QB64: [Select]
  1. TYPE PIECES
  2.     typ AS _BYTE
  3.     squ AS _BYTE
  4.     nxt AS _BYTE
  5.     prv AS _BYTE
  7.  
  8. TYPE MOVES
  9.     from_square AS _UNSIGNED _BYTE
  10.     to_square AS _UNSIGNED _BYTE
  11.     target AS _UNSIGNED _BYTE
  12.     special AS _UNSIGNED _BYTE
  13.     score AS INTEGER
  15.  
  16. CONST FALSE = 0
  17. CONST TRUE = 1
  18.  
  19. CONST ILLEGAL = -1
  20.  
  21. CONST BLACK = 0
  22. CONST WHITE = 1
  23.  
  24. CONST EMPTY = 0
  25. CONST FP = 1
  26. CONST EP = 2
  27. CONST EK = 3
  28.  
  29. CONST NA = -1
  30. CONST NON = -1
  31. CONST TERMINATE = 0
  32. CONST WP = 1
  33. CONST WN = 2
  34. CONST WB = 3
  35. CONST WR = 4
  36. CONST WQ = 5
  37. CONST WC = 6
  38. CONST WK = 7
  39. CONST BP = 8
  40. CONST BN = 9
  41. CONST BB = 10
  42. CONST BR = 11
  43. CONST BQ = 12
  44. CONST BK = 13
  45.  
  46. CONST A1 = 21
  47. CONST B1 = 22
  48. CONST C1 = 23
  49. CONST D1 = 24
  50. CONST E1 = 25
  51. CONST F1 = 26
  52. CONST G1 = 27
  53. CONST H1 = 28
  54. CONST A2 = 31
  55. CONST B2 = 32
  56. CONST C2 = 33
  57. CONST D2 = 34
  58. CONST E2 = 35
  59. CONST F2 = 36
  60. CONST G2 = 37
  61. CONST H2 = 38
  62. CONST A7 = 81
  63. CONST B7 = 82
  64. CONST C7 = 83
  65. CONST D7 = 84
  66. CONST E7 = 85
  67. CONST F7 = 86
  68. CONST G7 = 87
  69. CONST H7 = 88
  70. CONST A8 = 91
  71. CONST B8 = 92
  72. CONST C8 = 93
  73. CONST D8 = 94
  74. CONST E8 = 95
  75. CONST f8 = 96
  76. CONST G8 = 97
  77. CONST H8 = 98
  78.  
  79. CONST X2R = 0
  80. CONST L2R = 1
  81. CONST L2X = 2
  82. CONST X1R = 3
  83. CONST L1R = 4
  84. CONST L1X = 5
  85. CONST XER = 6
  86. CONST LER = 7
  87. CONST LEX = 8
  88. CONST XPR = 9
  89. CONST LPR = 10
  90. CONST LPX = 11
  91.  
  94. DIM SHARED move_stack(8000) AS MOVES
  95. DIM SHARED start_index(2) AS _BYTE
  96.  
  97. DIM SHARED chess_board(120) AS _BYTE
  98.  
  99. DATA -1,-1,-1,-1,-1,-1,-1,-1,-1,-1
  100. DATA -1,-1,-1,-1,-1,-1,-1,-1,-1,-1
  101. DATA -1,14,10,12,15,16,11,+9,13,-1
  102. DATA -1,+5,+4,+3,+2,+1,+8,+7,+6,-1
  103. DATA -1,00,00,00,00,00,00,00,00,-1
  104. DATA -1,00,00,00,00,00,00,00,00,-1
  105. DATA -1,00,00,00,00,00,00,00,00,-1
  106. DATA -1,00,00,00,00,00,00,00,00,-1
  107. DATA -1,25,24,23,22,21,28,27,26,-1
  108. DATA -1,34,30,32,35,36,31,29,33,-1
  109. DATA -1,-1,-1,-1,-1,-1,-1,-1,-1,-1
  110. DATA -1,-1,-1,-1,-1,-1,-1,-1,-1,-1
  111.  
  112. FOR i = 0 TO 119: READ chess_board(i): NEXT
  113.  
  114.  
  115. DIM SHARED white_pawns(120) AS _BYTE
  116.  
  117. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  118. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  119. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  120. DATA NON,X2R,L2R,L2R,L2R,L2R,L2R,L2R,R2X,NON
  121. DATA NON,X1R,L1R,L1R,L1R,L1R,L1R,L1R,L1X,NON
  122. DATA NON,X1R,L1R,L1R,L1R,L1R,L1R,L1R,L1X,NON
  123. DATA NON,XER,LER,LER,LER,LER,LER,LER,LEX,NON
  124. DATA NON,X1R,L1R,L1R,L1R,L1R,L1R,L1R,L1X,NON
  125. DATA NON,XPR,LPR,LPR,LPR,LPR,LPR,LPR,LPX,NON
  126. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  127. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  128. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  129.  
  130. FOR i = 0 TO 119: READ white_pawns(i): NEXT
  131.  
  132.  
  133. DIM SHARED black_pawns(120) AS _BYTE
  134.  
  135. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  136. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  137. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  138. DATA NON,XPR,LPR,LPR,LPR,LPR,LPR,LPR,LPX,NON
  139. DATA NON,X1R,L1R,L1R,L1R,L1R,L1R,L1R,L1X,NON
  140. DATA NON,XER,LER,LER,LER,LER,LER,LER,LEX,NON
  141. DATA NON,X1R,L1R,L1R,L1R,L1R,L1R,L1R,L1X,NON
  142. DATA NON,X1R,L1R,L1R,L1R,L1R,L1R,L1R,L1X,NON
  143. DATA NON,X2R,L2R,L2R,L2R,L2R,L2R,L2R,R2X,NON
  144. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  145. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  146. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  147.  
  148. FOR i = 0 TO 119: READ black_pawns(i): NEXT
  149.  
  150.  
  151. DIM SHARED piece(40) AS PIECES
  152.  
  153. DATA NA,NA,+1,NA
  154. DATA WP,E2,+2,NA
  155. DATA WP,D2,+3,+1
  156. DATA WP,C2,+4,+2
  157. DATA WP,B2,+5,+3
  158. DATA WP,A2,+6,+4
  159. DATA WP,H2,+7,+5
  160. DATA WP,G2,+8,+6
  161. DATA WP,F2,+9,+7
  162. DATA WN,G1,10,+8
  163. DATA WN,B1,11,+9
  164. DATA WB,F1,12,10
  165. DATA WB,C1,13,11
  166. DATA WR,H1,14,12
  167. DATA WR,A1,15,13
  168. DATA WQ,D1,16,14
  169. DATA WK,NA,NA,NA
  170. DATA WC,E1,39,16
  171. DATA NA,NA,NA,NA
  172. DATA NA,NA,NA,NA
  173. DATA NA,NA,21,NA
  174. DATA BP,E7,22,NA
  175. DATA BP,D7,23,21
  176. DATA BP,C7,24,22
  177. DATA BP,B7,25,23
  178. DATA BP,A7,26,24
  179. DATA BP,H7,27,25
  180. DATA BP,G7,28,26
  181. DATA BP,F7,29,27
  182. DATA BN,G8,30,28
  183. DATA BN,B8,31,29
  184. DATA BB,F8,32,30
  185. DATA BB,C8,33,31
  186. DATA BR,H8,34,32
  187. DATA BR,A8,35,33
  188. DATA BQ,D8,36,34
  189. DATA BK,NA,NA,NA
  190. DATA BC,E8,39,36
  191. DATA NA,NA,NA,NA
  192. DATA NA,NA,NA,NA
  193. DATA TERMINATE,NA,NA,NA
  194.  
  195. FOR i = 0 TO 39: READ piece(i).typ: READ piece(i).squ: READ piece(i).nxt: READ piece(i).prv: NEXT
  196.  
  197. DIM SHARED white_target(40) AS _BYTE
  198.  
  199. DATA EMPTY,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,0,0
  200. DATA EMPTY,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EK,EK,0,0
  201.  
  202. FOR i = 0 TO 99: READ white_target(i): NEXT
  203.  
  204.  
  205. DIM SHARED black_target(40) AS _BYTE
  206.  
  207. DATA EMPTY,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EK,EK,0,0
  208. DATA EMPTY,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,0,0
  209.  
  210. FOR i = 0 TO 99: READ black_target(i): NEXT
  211.  
  212.  
  213. DIM SHARED bishop_offsets(4) AS _BYTE
  214.  
  215. DATA 9,11,-9,-11
  216.  
  217. FOR i = 0 TO 3: READ bishop_offsets(i): NEXT
  218.  
  219.  
  220. DIM SHARED rook_offsets(4) AS _BYTE
  221.  
  222. DATA 1,10,-1,-10
  223.  
  224. FOR i = 0 TO 3: READ rook_offsets(i): NEXT
  225.  
  226.  
  227. DIM SHARED royal_offsets AS _BYTE
  228.  
  229. DATA 1,9,10,11,-1,-9,-10,-11
  230.  
  231. FOR i = 0 TO 7: READ royal_offsets(i): NEXT
  232.  
  233.  
  234. DIM SHARED knight_offsets AS _BYTE
  235.  
  236. DATA 8,12,19,21,-8,-12,-19,-21
  237.  
  238. FOR i = 0 TO 7: READ knight_offsets(i): NEXT
  239.  
  240. SUB Record_Move (from_square AS _BYTE, to_square AS _BYTE)
  241.  
  243.  
  244. SUB Record_Capture (from_square AS _BYTE, to_square AS _BYTE, target AS _BYTE)
  245.  
  247.  
  248. SUB Record_Move_Mark_ep (from_square AS _BYTE, to_square AS _BYTE)
  249.  
  251.  
  252. SUB Record_ep (from_square AS _BYTE, to_square AS _BYTE)
  253.  
  255.  
  256. SUB Record_Move_Promotion (from_square AS _BYTE, to_square AS _BYTE)
  257.  
  259.  
  260. SUB Record_capture_Promotion (from_square AS _BYTE, to_square AS _BYTE, target AS _BYTE)
  261.  
  263.  
  264. SUB Generate_Moves
  265.     piece_index = next_piece(start_index(wtm))
  266.     DO
  267.         from_square = piece(piece_index).squ
  268.         SELECT CASE piece(piece_index).typ
  269.             CASE TERMINATE
  270.                 EXIT SUB
  271.             CASE WP
  272.                 SELECT CASE white_pawns(from_square)
  273.                     CASE X2R
  274.                         to_square = from_square + 10
  275.                         target = chess_board(to_square)
  276.                         IF target = EMPTY THEN
  277.                             Record_Move from_square, to_square
  278.                             to_square = from_square + 20
  279.                             target = chess_board(to_square)
  280.                             IF target = EMPTY THEN
  281.                                 Record_Move_Mark_ep from_square, to_square
  282.                             END IF
  283.                         END IF
  284.                         to_square = from_square + 11
  285.                         target = chess_board(to_square)
  286.                         action = white_target(target)
  287.                         SELECT CASE action
  288.                             CASE 0
  289.                             CASE 1
  290.                             CASE 2
  291.                                 Record_Capture from_square, to_square, target
  292.                         END SELECT
  293.  
  294.                     CASE L2R
  295.                         to_square = from_square + 9
  296.                         target = chess_board(to_square)
  297.                         action = white_target(target)
  298.                         SELECT CASE action
  299.                             CASE 0
  300.                             CASE 1
  301.                             CASE 2
  302.                                 Record_Capture from_square, to_square, target
  303.                         END SELECT
  304.                         to_square = from_square + 10
  305.                         target = chess_board(to_square)
  306.                         IF target = EMPTY THEN
  307.                             Record_Move from_square, to_square
  308.                             to_square = from_square + 20
  309.                             target = chess_board(to_square)
  310.                             IF target = EMPTY THEN
  311.                                 Record_Move_Mark_ep from_square, to_square
  312.                             END IF
  313.                         END IF
  314.                         to_square = from_square + 11
  315.                         target = chess_board(to_square)
  316.                         action = white_target(target)
  317.                         SELECT CASE action
  318.                             CASE 0
  319.                             CASE 1
  320.                             CASE 2
  321.                                 Record_Capture from_square, to_square, target
  322.                         END SELECT
  323.  
  324.                     CASE L2X
  325.                         to_square = from_square + 9
  326.                         target = chess_board(to_square)
  327.                         action = white_target(target)
  328.                         SELECT CASE action
  329.                             CASE 0
  330.                             CASE 1
  331.                             CASE 2
  332.                                 Record_Capture from_square, to_square, target
  333.                         END SELECT
  334.                         to_square = from_square + 10
  335.                         target = chess_board(to_square)
  336.                         IF target = EMPTY THEN
  337.                             Record_Move from_square, to_square
  338.                             to_square = from_square + 20
  339.                             target = chess_board(to_square)
  340.                             IF target = EMPTY THEN
  341.                                 Record_Move_Mark_ep from_square, to_square
  342.                             END IF
  343.                         END IF
  344.  
  345.                     CASE X1R
  346.                         to_square = from_square + 10
  347.                         target = chess_board(to_square)
  348.                         IF target = EMPTY THEN
  349.                             Record_Move from_square, to_square
  350.                         END IF
  351.                         to_square = from_square + 11
  352.                         target = chess_board(to_square)
  353.                         action = white_target(target)
  354.                         SELECT CASE action
  355.                             CASE 0
  356.                             CASE 1
  357.                             CASE 2
  358.                                 Record_Capture from_square, to_square, target
  359.                         END SELECT
  360.  
  361.                     CASE L1R
  362.                         to_square = from_square + 9
  363.                         target = chess_board(to_square)
  364.                         action = white_target(target)
  365.                         SELECT CASE action
  366.                             CASE 0
  367.                             CASE 1
  368.                             CASE 2
  369.                                 Record_Capture from_square, to_square, target
  370.                         END SELECT
  371.                         to_square = from_square + 10
  372.                         target = chess_board(to_square)
  373.                         IF target = EMPTY THEN
  374.                             Record_Move from_square, to_square
  375.                         END IF
  376.                         to_square = from_square + 11
  377.                         target = chess_board(to_square)
  378.                         action = white_target(target)
  379.                         SELECT CASE action
  380.                             CASE 0
  381.                             CASE 1
  382.                             CASE 2
  383.                                 Record_Capture from_square, to_square, target
  384.                         END SELECT
  385.  
  386.                     CASE L1X
  387.                         to_square = from_square + 9
  388.                         target = chess_board(to_square)
  389.                         action = white_target(target)
  390.                         SELECT CASE action
  391.                             CASE 0
  392.                             CASE 1
  393.                             CASE 2
  394.                                 Record_Capture from_square, to_square, target
  395.                         END SELECT
  396.                         to_square = from_square + 10
  397.                         target = chess_board(to_square)
  398.                         IF target = EMPTY THEN
  399.                             Record_Move from_square, to_square
  400.                         END IF
  401.  
  402.                     CASE XER
  403.                         to_square = from_square + 10
  404.                         target = chess_board(to_square)
  405.                         IF target = EMPTY THEN
  406.                             Record_Move from_square, to_square
  407.                         END IF
  408.                         to_square = from_square + 11
  409.                         target = chess_board(to_square)
  410.                         action = white_target(target)
  411.                         SELECT CASE action
  412.                             CASE 0
  413.                                 IF to_square = ep_square(ply) THEN Record_ep from_square, to_square
  414.                             CASE 1
  415.                             CASE 2
  416.                                 Record_Capture from_square, to_square, target
  417.                         END SELECT
  418.  
  419.                     CASE LER
  420.                         to_square = from_square + 9
  421.                         target = chess_board(to_square)
  422.                         action = white_target(target)
  423.                         SELECT CASE action
  424.                             CASE 0
  425.                                 IF to_square = ep_square(ply) THEN Record_ep from_square, to_square
  426.                             CASE 1
  427.                             CASE 2
  428.                                 Record_Capture from_square, to_square, target
  429.                         END SELECT
  430.                         to_square = from_square + 10
  431.                         target = chess_board(to_square)
  432.                         IF target = EMPTY THEN
  433.                             Record_Move from_square, to_square
  434.                         END IF
  435.                         to_square = from_square + 11
  436.                         target = chess_board(to_square)
  437.                         action = white_target(target)
  438.                         SELECT CASE action
  439.                             CASE 0
  440.                                 IF to_square = ep_square(ply) THEN Record_ep from_square, to_square
  441.                             CASE 1
  442.                             CASE 2
  443.                                 Record_Capture from_square, to_square, target
  444.                         END SELECT
  445.  
  446.                     CASE LEX
  447.                         to_square = from_square + 9
  448.                         target = chess_board(to_square)
  449.                         action = white_target(target)
  450.                         SELECT CASE action
  451.                             CASE 0
  452.                                 IF to_square = ep_square(ply) THEN Record_ep from_square, to_square
  453.                             CASE 1
  454.                             CASE 2
  455.                                 Record_Capture from_square, to_square, target
  456.                         END SELECT
  457.                         to_square = from_square + 10
  458.                         target = chess_board(to_square)
  459.                         IF target = EMPTY THEN
  460.                             Record_Move from_square, to_square
  461.                         END IF
  462.  
  463.                     CASE XPR
  464.                         to_square = from_square + 10
  465.                         target = chess_board(to_square)
  466.                         IF target = EMPTY THEN
  467.                             Record_Move_Promotion from_square, to_square
  468.                         END IF
  469.                         to_square = from_square + 11
  470.                         target = chess_board(to_square)
  471.                         action = white_target(target)
  472.                         SELECT CASE action
  473.                             CASE 0
  474.                             CASE 1
  475.                             CASE 2
  476.                                 Record_capture_Promotion from_square, to_square, target
  477.                         END SELECT
  478.  
  479.                     CASE LPR
  480.                         to_square = from_square + 9
  481.                         target = chess_board(to_square)
  482.                         action = white_target(target)
  483.                         SELECT CASE action
  484.                             CASE 0
  485.                             CASE 1
  486.                             CASE 2
  487.                                 Record_capture_Promotion from_square, to_square, target
  488.                         END SELECT
  489.                         to_square = from_square + 10
  490.                         target = chess_board(to_square)
  491.                         IF target = EMPTY THEN
  492.                             Record_Move_Promotion from_square, to_square
  493.                         END IF
  494.                         to_square = from_square + 11
  495.                         target = chess_board(to_square)
  496.                         action = white_target(target)
  497.                         SELECT CASE action
  498.                             CASE 0
  499.                             CASE 1
  500.                             CASE 2
  501.                                 Record_capture_Promotion from_square, to_square, target
  502.                         END SELECT
  503.  
  504.                     CASE LPX
  505.                         to_square = from_square + 9
  506.                         target = chess_board(to_square)
  507.                         action = white_target(target)
  508.                         SELECT CASE action
  509.                             CASE 0
  510.                             CASE 1
  511.                             CASE 2
  512.                                 Record_capture_Promotion from_square, to_square, target
  513.                         END SELECT
  514.                         to_square = from_square + 10
  515.                         target = chess_board(to_square)
  516.                         IF target = EMPTY THEN
  517.                             Record_Move_Promotion from_square, to_square
  518.                         END IF
  519.  
  520.                 END SELECT
  521.             CASE WN
  522.  
  523.             CASE WB
  524.  
  525.             CASE WR
  526.  
  527.             CASE WQ
  528.  
  529.             CASE WK
  530.  
  531.             CASE WC
  532.  
  533.             CASE BP
  534.  
  535.             CASE BN
  536.  
  537.             CASE BB
  538.  
  539.             CASE BR
  540.  
  541.             CASE BQ
  542.  
  543.             CASE BK
  544.  
  545.             CASE BC
  546.  
  547.         END SELECT
  548.     LOOP
  550.  
  551. SUB Make_Move (i AS INTEGER)
  552.  
  554.  
  555. SUB Take_Back
  556.  
  558.  
  559. SUB Search_One_Q (alpha AS INTEGER, beta AS INTEGER)
  560.     Generate_Moves
  561.     i = move_stack_index(ply)
  562.     WHILE move_stack(i).special <> TERMINATE
  563.         Make_Move i
  564.         move_stack(i).score = Qsearch(alpha, beta)
  565.         Take_Back
  566.         i = i - 1
  567.     WEND
  569.  
Title: Re: Chess Programming Tutorial
Post by: TempodiBasic on March 17, 2020, 08:23:04 pm
Bump
:-)
Title: Re: Chess Programming Tutorial
Post by: romichess on March 25, 2020, 02:05:43 pm
Quote from: TempodiBasic on March 17, 2020, 08:23:04 pm
Bump
:-)
I thought it would go quietly into the night. My apologies! I'll start devoting some time to the project.
Title: Re: Chess Programming Tutorial
Post by: romichess on March 25, 2020, 04:13:19 pm
The move generator is almost done. There have been minor changes to the data to allow the code to be more efficient. Edge squares now have a value of 39. So target = white_target(chess_board(to_square)) yields 4 which is the case  4 EXIT DO. Therefore no separate test needed for an off board test. In the old eight bit days move generation was done in one looping structure with lots of if statements. On today's cpus with megabytes of instruction cache code proliferation like loop unrolling is desirable for speed of execution.

If anyone sees any errors please let me know. Or if anyone has any suggestions for faster code. Or any questions. To be honest I quit posting because I was feeling rather lonely. And I can do that all by myself very well by not posting, LOL!

EDIT: I flubbed up. In the slider code I forgot why there needs to be a target and an action. I'm just going to edit the first bishop direction. It will be fully corrected in my next post.

Code: QB64: [Select]
  1. TYPE PIECES
  2.     typ AS _BYTE
  3.     squ AS _BYTE
  4.     nxt AS _BYTE
  5.     prv AS _BYTE
  7.  
  8. TYPE MOVES
  9.     from_square AS _UNSIGNED _BYTE
  10.     to_square AS _UNSIGNED _BYTE
  11.     target AS _UNSIGNED _BYTE
  12.     special AS _UNSIGNED _BYTE
  13.     score AS INTEGER
  15.  
  16. CONST FALSE = 0
  17. CONST TRUE = 1
  18.  
  19. CONST ILLEGAL = -1
  20.  
  21. CONST BLACK = 0
  22. CONST WHITE = 1
  23.  
  24. CONST EMPTY_SQUARE = 0
  25. CONST FRIENDLY_PIECE = 1
  26. CONST ENEMY_PIECE = 2
  27. CONST OFF_BOARD = 3
  28. CONST ENEMY_KING = 4
  29.  
  30. CONST ES = 0
  31. CONST FP = 1
  32. CONST EP = 2
  33. CONST OB = 3
  34. CONST EK = 4
  35.  
  36. CONST NA = -1
  37. CONST NON = -1
  38. CONST TERMINATE = 0
  39. CONST WP = 1
  40. CONST WN = 2
  41. CONST WB = 3
  42. CONST WR = 4
  43. CONST WQ = 5
  44. CONST WC = 6
  45. CONST WK = 7
  46. CONST BP = 8
  47. CONST BN = 9
  48. CONST BB = 10
  49. CONST BR = 11
  50. CONST BQ = 12
  51. CONST BK = 13
  52.  
  53. CONST A1 = 21
  54. CONST B1 = 22
  55. CONST C1 = 23
  56. CONST D1 = 24
  57. CONST E1 = 25
  58. CONST F1 = 26
  59. CONST G1 = 27
  60. CONST H1 = 28
  61. CONST A2 = 31
  62. CONST B2 = 32
  63. CONST C2 = 33
  64. CONST D2 = 34
  65. CONST E2 = 35
  66. CONST F2 = 36
  67. CONST G2 = 37
  68. CONST H2 = 38
  69. CONST A7 = 81
  70. CONST B7 = 82
  71. CONST C7 = 83
  72. CONST D7 = 84
  73. CONST E7 = 85
  74. CONST F7 = 86
  75. CONST G7 = 87
  76. CONST H7 = 88
  77. CONST A8 = 91
  78. CONST B8 = 92
  79. CONST C8 = 93
  80. CONST D8 = 94
  81. CONST E8 = 95
  82. CONST f8 = 96
  83. CONST G8 = 97
  84. CONST H8 = 98
  85.  
  86. CONST X2R = 0
  87. CONST L2R = 1
  88. CONST L2X = 2
  89. CONST X1R = 3
  90. CONST L1R = 4
  91. CONST L1X = 5
  92. CONST XER = 6
  93. CONST LER = 7
  94. CONST LEX = 8
  95. CONST XPR = 9
  96. CONST LPR = 10
  97. CONST LPX = 11
  98.  
  101. DIM SHARED move_stack(8000) AS MOVES
  102. DIM SHARED start_index(2) AS _BYTE
  103.  
  104. DIM SHARED chess_board(120) AS _BYTE
  105.  
  106. DATA 39,39,39,39,39,39,39,39,39,39
  107. DATA 39,39,39,39,39,39,39,39,39,39
  108. DATA 39,14,10,12,15,16,11,09,13,39
  109. DATA 39,05,04,03,02,01,08,07,06,39
  110. DATA 39,00,00,00,00,00,00,00,00,39
  111. DATA 39,00,00,00,00,00,00,00,00,39
  112. DATA 39,00,00,00,00,00,00,00,00,39
  113. DATA 39,00,00,00,00,00,00,00,00,39
  114. DATA 39,25,24,23,22,21,28,27,26,39
  115. DATA 39,34,30,32,35,36,31,29,33,39
  116. DATA 39,39,39,39,39,39,39,39,39,39
  117. DATA 39,39,39,39,39,39,39,39,39,39
  118.  
  119. FOR i = 0 TO 119: READ chess_board(i): NEXT
  120.  
  121.  
  122. DIM SHARED white_pawns(120) AS _BYTE
  123.  
  124. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  125. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  126. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  127. DATA NON,X2R,L2R,L2R,L2R,L2R,L2R,L2R,R2X,NON
  128. DATA NON,X1R,L1R,L1R,L1R,L1R,L1R,L1R,L1X,NON
  129. DATA NON,X1R,L1R,L1R,L1R,L1R,L1R,L1R,L1X,NON
  130. DATA NON,XER,LER,LER,LER,LER,LER,LER,LEX,NON
  131. DATA NON,X1R,L1R,L1R,L1R,L1R,L1R,L1R,L1X,NON
  132. DATA NON,XPR,LPR,LPR,LPR,LPR,LPR,LPR,LPX,NON
  133. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  134. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  135. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  136.  
  137. FOR i = 0 TO 119: READ white_pawns(i): NEXT
  138.  
  139.  
  140. DIM SHARED black_pawns(120) AS _BYTE
  141.  
  142. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  143. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  144. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  145. DATA NON,XPR,LPR,LPR,LPR,LPR,LPR,LPR,LPX,NON
  146. DATA NON,X1R,L1R,L1R,L1R,L1R,L1R,L1R,L1X,NON
  147. DATA NON,XER,LER,LER,LER,LER,LER,LER,LEX,NON
  148. DATA NON,X1R,L1R,L1R,L1R,L1R,L1R,L1R,L1X,NON
  149. DATA NON,X1R,L1R,L1R,L1R,L1R,L1R,L1R,L1X,NON
  150. DATA NON,X2R,L2R,L2R,L2R,L2R,L2R,L2R,R2X,NON
  151. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  152. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  153. DATA NON,NON,NON,NON,NON,NON,NON,NON,NON,NON
  154.  
  155. FOR i = 0 TO 119: READ black_pawns(i): NEXT
  156.  
  157.  
  158. DIM SHARED piece(40) AS PIECES
  159.  
  160. DATA NA,NA,+1,NA
  161. DATA WP,E2,+2,NA
  162. DATA WP,D2,+3,+1
  163. DATA WP,C2,+4,+2
  164. DATA WP,B2,+5,+3
  165. DATA WP,A2,+6,+4
  166. DATA WP,H2,+7,+5
  167. DATA WP,G2,+8,+6
  168. DATA WP,F2,+9,+7
  169. DATA WN,G1,10,+8
  170. DATA WN,B1,11,+9
  171. DATA WB,F1,12,10
  172. DATA WB,C1,13,11
  173. DATA WR,H1,14,12
  174. DATA WR,A1,15,13
  175. DATA WQ,D1,16,14
  176. DATA WK,NA,NA,NA
  177. DATA WC,E1,39,16
  178. DATA NA,NA,NA,NA
  179. DATA NA,NA,NA,NA
  180. DATA NA,NA,21,NA
  181. DATA BP,E7,22,NA
  182. DATA BP,D7,23,21
  183. DATA BP,C7,24,22
  184. DATA BP,B7,25,23
  185. DATA BP,A7,26,24
  186. DATA BP,H7,27,25
  187. DATA BP,G7,28,26
  188. DATA BP,F7,29,27
  189. DATA BN,G8,30,28
  190. DATA BN,B8,31,29
  191. DATA BB,F8,32,30
  192. DATA BB,C8,33,31
  193. DATA BR,H8,34,32
  194. DATA BR,A8,35,33
  195. DATA BQ,D8,36,34
  196. DATA BK,NA,NA,NA
  197. DATA BC,E8,39,36
  198. DATA NA,NA,NA,NA
  199. DATA NA,NA,NA,NA
  200. DATA TERMINATE,NA,NA,NA
  201.  
  202. FOR i = 0 TO 39: READ piece(i).typ: READ piece(i).squ: READ piece(i).nxt: READ piece(i).prv: NEXT
  203.  
  204. DIM SHARED white_target(40) AS _BYTE
  205.  
  206. DATA EMPTY,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,0,0
  207. DATA EMPTY,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EK,EK,0,OB
  208.  
  209. FOR i = 0 TO 99: READ white_target(i): NEXT
  210.  
  211.  
  212. DIM SHARED black_target(40) AS _BYTE
  213.  
  214. DATA EMPTY,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EK,EK,0,0
  215. DATA EMPTY,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,0,OB
  216.  
  217. FOR i = 0 TO 99: READ black_target(i): NEXT
  218.  
  219.  
  220. DIM SHARED bishop_offsets(4) AS _BYTE
  221.  
  222. DATA 9,11,-9,-11
  223.  
  224. FOR i = 0 TO 3: READ bishop_offsets(i): NEXT
  225.  
  226.  
  227. DIM SHARED rook_offsets(4) AS _BYTE
  228.  
  229. DATA 1,10,-1,-10
  230.  
  231. FOR i = 0 TO 3: READ rook_offsets(i): NEXT
  232.  
  233.  
  234. DIM SHARED royal_offsets AS _BYTE
  235.  
  236. DATA 1,9,10,11,-1,-9,-10,-11
  237.  
  238. FOR i = 0 TO 7: READ royal_offsets(i): NEXT
  239.  
  240.  
  241. DIM SHARED knight_offsets AS _BYTE
  242.  
  243. DATA 8,12,19,21,-8,-12,-19,-21
  244.  
  245. FOR i = 0 TO 7: READ knight_offsets(i): NEXT
  246.  
  247. SUB Record_Move (from_square AS _BYTE, to_square AS _BYTE)
  248.  
  250.  
  251. SUB Record_Capture (from_square AS _BYTE, to_square AS _BYTE, target AS _BYTE)
  252.  
  254.  
  255. SUB Record_Move_Mark_ep (from_square AS _BYTE, to_square AS _BYTE)
  256.  
  258.  
  259. SUB Record_ep (from_square AS _BYTE, to_square AS _BYTE)
  260.  
  262.  
  263. SUB Record_Move_Promotion (from_square AS _BYTE, to_square AS _BYTE)
  264.  
  266.  
  267. SUB Record_capture_Promotion (from_square AS _BYTE, to_square AS _BYTE, target AS _BYTE)
  268.  
  270.  
  271. SUB Generate_Moves
  272.     piece_index = next_piece(start_index(wtm))
  273.     DO
  274.         from_square = piece(piece_index).squ
  275.         SELECT CASE piece(piece_index).typ
  276.             CASE TERMINATE
  277.                 EXIT SUB
  278.             CASE WP
  279.                 SELECT CASE white_pawns(from_square)
  280.                     CASE X2R
  281.                         to_square = from_square + 10
  282.                         target = chess_board(to_square)
  283.                         IF target = EMPTY THEN
  284.                             Record_Move from_square, to_square
  285.                             to_square = from_square + 20
  286.                             target = chess_board(to_square)
  287.                             IF target = EMPTY THEN
  288.                                 Record_Move_Mark_ep from_square, to_square
  289.                             END IF
  290.                         END IF
  291.                         to_square = from_square + 11
  292.                         target = chess_board(to_square)
  293.                         action = white_target(target)
  294.                         SELECT CASE action
  295.                             CASE EMPTY_SQUARE
  296.                             CASE FRIENDLY_PIECE
  297.                             CASE ENEMY_PIECE
  298.                                 Record_Capture from_square, to_square, target
  299.                         END SELECT
  300.  
  301.                     CASE L2R
  302.                         to_square = from_square + 9
  303.                         target = chess_board(to_square)
  304.                         action = white_target(target)
  305.                         SELECT CASE action
  306.                             CASE EMPTY_SQUARE
  307.                             CASE FRIENDLY_PIECE
  308.                             CASE ENEMY_PIECE
  309.                                 Record_Capture from_square, to_square, target
  310.                         END SELECT
  311.                         to_square = from_square + 10
  312.                         target = chess_board(to_square)
  313.                         IF target = EMPTY THEN
  314.                             Record_Move from_square, to_square
  315.                             to_square = from_square + 20
  316.                             target = chess_board(to_square)
  317.                             IF target = EMPTY THEN
  318.                                 Record_Move_Mark_ep from_square, to_square
  319.                             END IF
  320.                         END IF
  321.                         to_square = from_square + 11
  322.                         target = chess_board(to_square)
  323.                         action = white_target(target)
  324.                         SELECT CASE action
  325.                             CASE EMPTY_SQUARE
  326.                             CASE FRIENDLY_PIECE
  327.                             CASE ENEMY_PIECE
  328.                                 Record_Capture from_square, to_square, target
  329.                         END SELECT
  330.  
  331.                     CASE L2X
  332.                         to_square = from_square + 9
  333.                         target = chess_board(to_square)
  334.                         action = white_target(target)
  335.                         SELECT CASE action
  336.                             CASE EMPTY_SQUARE
  337.                             CASE FRIENDLY_PIECE
  338.                             CASE ENEMY_PIECE
  339.                                 Record_Capture from_square, to_square, target
  340.                         END SELECT
  341.                         to_square = from_square + 10
  342.                         target = chess_board(to_square)
  343.                         IF target = EMPTY THEN
  344.                             Record_Move from_square, to_square
  345.                             to_square = from_square + 20
  346.                             target = chess_board(to_square)
  347.                             IF target = EMPTY THEN
  348.                                 Record_Move_Mark_ep from_square, to_square
  349.                             END IF
  350.                         END IF
  351.  
  352.                     CASE X1R
  353.                         to_square = from_square + 10
  354.                         target = chess_board(to_square)
  355.                         IF target = EMPTY THEN
  356.                             Record_Move from_square, to_square
  357.                         END IF
  358.                         to_square = from_square + 11
  359.                         target = chess_board(to_square)
  360.                         action = white_target(target)
  361.                         SELECT CASE action
  362.                             CASE EMPTY_SQUARE
  363.                             CASE FRIENDLY_PIECE
  364.                             CASE ENEMY_PIECE
  365.                                 Record_Capture from_square, to_square, target
  366.                         END SELECT
  367.  
  368.                     CASE L1R
  369.                         to_square = from_square + 9
  370.                         target = chess_board(to_square)
  371.                         action = white_target(target)
  372.                         SELECT CASE action
  373.                             CASE EMPTY_SQUARE
  374.                             CASE FRIENDLY_PIECE
  375.                             CASE ENEMY_PIECE
  376.                                 Record_Capture from_square, to_square, target
  377.                         END SELECT
  378.                         to_square = from_square + 10
  379.                         target = chess_board(to_square)
  380.                         IF target = EMPTY THEN
  381.                             Record_Move from_square, to_square
  382.                         END IF
  383.                         to_square = from_square + 11
  384.                         target = chess_board(to_square)
  385.                         action = white_target(target)
  386.                         SELECT CASE action
  387.                             CASE EMPTY_SQUARE
  388.                             CASE FRIENDLY_PIECE
  389.                             CASE ENEMY_PIECE
  390.                                 Record_Capture from_square, to_square, target
  391.                         END SELECT
  392.  
  393.                     CASE L1X
  394.                         to_square = from_square + 9
  395.                         target = chess_board(to_square)
  396.                         action = white_target(target)
  397.                         SELECT CASE action
  398.                             CASE EMPTY_SQUARE
  399.                             CASE FRIENDLY_PIECE
  400.                             CASE ENEMY_PIECE
  401.                                 Record_Capture from_square, to_square, target
  402.                         END SELECT
  403.                         to_square = from_square + 10
  404.                         target = chess_board(to_square)
  405.                         IF target = EMPTY THEN
  406.                             Record_Move from_square, to_square
  407.                         END IF
  408.  
  409.                     CASE XER
  410.                         to_square = from_square + 10
  411.                         target = chess_board(to_square)
  412.                         IF target = EMPTY THEN
  413.                             Record_Move from_square, to_square
  414.                         END IF
  415.                         to_square = from_square + 11
  416.                         target = chess_board(to_square)
  417.                         action = white_target(target)
  418.                         SELECT CASE action
  419.                             CASE EMPTY_SQUARE
  420.                                 IF to_square = ep_square(ply) THEN Record_ep from_square, to_square
  421.                             CASE FRIENDLY_PIECE1
  422.                             CASE ENEMY_PIECE
  423.                                 Record_Capture from_square, to_square, target
  424.                         END SELECT
  425.  
  426.                     CASE LER
  427.                         to_square = from_square + 9
  428.                         target = chess_board(to_square)
  429.                         action = white_target(target)
  430.                         SELECT CASE action
  431.                             CASE EMPTY_SQUARE
  432.                                 IF to_square = ep_square(ply) THEN Record_ep from_square, to_square
  433.                             CASE FRIENDLY_PIECE
  434.                             CASE ENEMY_PIECE
  435.                                 Record_Capture from_square, to_square, target
  436.                         END SELECT
  437.                         to_square = from_square + 10
  438.                         target = chess_board(to_square)
  439.                         IF target = EMPTY THEN
  440.                             Record_Move from_square, to_square
  441.                         END IF
  442.                         to_square = from_square + 11
  443.                         target = chess_board(to_square)
  444.                         action = white_target(target)
  445.                         SELECT CASE action
  446.                             CASE EMPTY_SQUARE
  447.                                 IF to_square = ep_square(ply) THEN Record_ep from_square, to_square
  448.                             CASE FRIENDLY_PIECE
  449.                             CASE ENEMY_PIECE
  450.                                 Record_Capture from_square, to_square, target
  451.                         END SELECT
  452.  
  453.                     CASE LEX
  454.                         to_square = from_square + 9
  455.                         target = chess_board(to_square)
  456.                         action = white_target(target)
  457.                         SELECT CASE action
  458.                             CASE EMPTY_SQUARE
  459.                                 IF to_square = ep_square(ply) THEN Record_ep from_square, to_square
  460.                             CASE FRIENDLY_PIECE
  461.                             CASE ENEMY_PIECE
  462.                                 Record_Capture from_square, to_square, target
  463.                         END SELECT
  464.                         to_square = from_square + 10
  465.                         target = chess_board(to_square)
  466.                         IF target = EMPTY THEN
  467.                             Record_Move from_square, to_square
  468.                         END IF
  469.  
  470.                     CASE XPR
  471.                         to_square = from_square + 10
  472.                         target = chess_board(to_square)
  473.                         IF target = EMPTY THEN
  474.                             Record_Move_Promotion from_square, to_square
  475.                         END IF
  476.                         to_square = from_square + 11
  477.                         target = chess_board(to_square)
  478.                         action = white_target(target)
  479.                         SELECT CASE action
  480.                             CASE EMPTY_SQUARE
  481.                             CASE FRIENDLY_PIECE
  482.                             CASE ENEMY_PIECE
  483.                                 Record_capture_Promotion from_square, to_square, target
  484.                         END SELECT
  485.  
  486.                     CASE LPR
  487.                         to_square = from_square + 9
  488.                         target = chess_board(to_square)
  489.                         action = white_target(target)
  490.                         SELECT CASE action
  491.                             CASE EMPTY_SQUARE
  492.                             CASE FRIENDLY_PIECE
  493.                             CASE ENEMY_PIECE
  494.                                 Record_capture_Promotion from_square, to_square, target
  495.                         END SELECT
  496.                         to_square = from_square + 10
  497.                         target = chess_board(to_square)
  498.                         IF target = EMPTY THEN
  499.                             Record_Move_Promotion from_square, to_square
  500.                         END IF
  501.                         to_square = from_square + 11
  502.                         target = chess_board(to_square)
  503.                         action = white_target(target)
  504.                         SELECT CASE action
  505.                             CASE EMPTY_SQUARE
  506.                             CASE FRIENDLY_PIECE
  507.                             CASE ENEMY_PIECE
  508.                                 Record_capture_Promotion from_square, to_square, target
  509.                         END SELECT
  510.  
  511.                     CASE LPX
  512.                         to_square = from_square + 9
  513.                         target = chess_board(to_square)
  514.                         action = white_target(target)
  515.                         SELECT CASE action
  516.                             CASE EMPTY_SQUARE
  517.                             CASE FRIENDLY_PIECE
  518.                             CASE ENEMY_PIECE
  519.                                 Record_capture_Promotion from_square, to_square, target
  520.                         END SELECT
  521.                         to_square = from_square + 10
  522.                         target = chess_board(to_square)
  523.                         IF target = EMPTY THEN
  524.                             Record_Move_Promotion from_square, to_square
  525.                         END IF
  526.  
  527.                 END SELECT
  528.             CASE WN
  529.                 to_square = from_square + 8
  530.                 target = chess_board(to_square)
  531.                 action = white_target(target)
  532.                 SELECT CASE action
  533.                     CASE EMPTY_SQUARE
  534.                         Record_Move from_square, to_square
  535.                     CASE FRIENDLY_PIECE
  536.                     CASE ENEMY_PIECE
  537.                         Record_Capture from_square, to_square, target
  538.                     CASE OFF_BOARD
  539.                 END SELECT
  540.                 to_square = from_square + 19
  541.                 target = chess_board(to_square)
  542.                 action = white_target(target)
  543.                 SELECT CASE action
  544.                     CASE EMPTY_SQUARE
  545.                         Record_Move from_square, to_square
  546.                     CASE FRIENDLY_PIECE
  547.                     CASE ENEMY_PIECE
  548.                         Record_Capture from_square, to_square, target
  549.                     CASE OFF_BOARD
  550.                 END SELECT
  551.                 to_square = from_square + 21
  552.                 target = chess_board(to_square)
  553.                 action = white_target(target)
  554.                 SELECT CASE action
  555.                     CASE EMPTY_SQUARE
  556.                         Record_Move from_square, to_square
  557.                     CASE FRIENDLY_PIECE
  558.                     CASE ENEMY_PIECE
  559.                         Record_Capture from_square, to_square, target
  560.                     CASE OFF_BOARD
  561.                 END SELECT
  562.                 to_square = from_square + 12
  563.                 target = chess_board(to_square)
  564.                 action = white_target(target)
  565.                 SELECT CASE action
  566.                     CASE EMPTY_SQUARE
  567.                         Record_Move from_square, to_square
  568.                     CASE FRIENDLY_PIECE
  569.                     CASE ENEMY_PIECE
  570.                         Record_Capture from_square, to_square, target
  571.                     CASE OFF_BOARD
  572.                 END SELECT
  573.                 to_square = from_square - 8
  574.                 target = chess_board(to_square)
  575.                 action = white_target(target)
  576.                 SELECT CASE action
  577.                     CASE EMPTY_SQUARE
  578.                         Record_Move from_square, to_square
  579.                     CASE FRIENDLY_PIECE
  580.                     CASE ENEMY_PIECE
  581.                         Record_Capture from_square, to_square, target
  582.                     CASE OFF_BOARD
  583.                 END SELECT
  584.                 to_square = from_square - 19
  585.                 target = chess_board(to_square)
  586.                 action = white_target(target)
  587.                 SELECT CASE action
  588.                     CASE EMPTY_SQUARE
  589.                         Record_Move from_square, to_square
  590.                     CASE FRIENDLY_PIECE
  591.                     CASE ENEMY_PIECE
  592.                         Record_Capture from_square, to_square, target
  593.                     CASE OFF_BOARD
  594.                 END SELECT
  595.                 to_square = from_square - 21
  596.                 target = chess_board(to_square)
  597.                 action = white_target(target)
  598.                 SELECT CASE action
  599.                     CASE EMPTY_SQUARE
  600.                         Record_Move from_square, to_square
  601.                     CASE FRIENDLY_PIECE
  602.                     CASE ENEMY_PIECE
  603.                         Record_Capture from_square, to_square, target
  604.                     CASE OFF_BOARD
  605.                 END SELECT
  606.                 to_square = from_square - 12
  607.                 target = chess_board(to_square)
  608.                 action = white_target(target)
  609.                 SELECT CASE action
  610.                     CASE EMPTY_SQUARE
  611.                         Record_Move from_square, to_square
  612.                     CASE FRIENDLY_PIECE
  613.                     CASE ENEMY_PIECE
  614.                         Record_Capture from_square, to_square, target
  615.                     CASE OFF_BOARD
  616.                 END SELECT
  617.             CASE WB
  618.                 to_square = from_square + 9
  619.                 DO
  620.                     target = chess_board(to_square)
  621.                     action = white_targets(target)
  622.                     SELECT CASE action
  623.                         CASE EMPTY_SQUARE
  624.                             Record_Move from_square, to_square
  625.                             to_square = to_square + 9
  626.                         CASE FRIENDLY_PIECE
  627.                             EXIT DO
  628.                         CASE ENEMY_PIECE
  629.                             Record_Capture from_square, to_square, target
  630.                             EXIT DO
  631.                         CASE OFF_BOARD
  632.                             EXIT DO
  633.                     END SELECT
  634.                 LOOP
  635.                 to_square = from_square + 11
  636.                 DO
  637.                     target = white_targets(chess_board(to_square))
  638.                     SELECT CASE target
  639.                         CASE EMPTY_SQUARE
  640.                             Record_Move from_square, to_square
  641.                             to_square = to_square + 11
  642.                         CASE FRIENDLY_PIECE
  643.                             EXIT DO
  644.                         CASE ENEMY_PIECE
  645.                             Record_Capture from_square, to_square, target
  646.                             EXIT DO
  647.                         CASE OFF_BOARD
  648.                             EXIT DO
  649.                     END SELECT
  650.                 LOOP
  651.                 to_square = from_square - 9
  652.                 DO
  653.                     target = white_targets(chess_board(to_square))
  654.                     SELECT CASE target
  655.                         CASE EMPTY_SQUARE
  656.                             Record_Move from_square, to_square
  657.                             to_square = to_square - 9
  658.                         CASE FRIENDLY_PIECE
  659.                             EXIT DO
  660.                         CASE ENEMY_PIECE
  661.                             Record_Capture from_square, to_square, target
  662.                             EXIT DO
  663.                         CASE OFF_BOARD
  664.                             EXIT DO
  665.                     END SELECT
  666.                 LOOP
  667.                 to_square = from_square - 11
  668.                 DO
  669.                     target = white_targets(chess_board(to_square))
  670.                     SELECT CASE target
  671.                         CASE EMPTY_SQUARE
  672.                             Record_Move from_square, to_square
  673.                             to_square = to_square - 11
  674.                         CASE FRIENDLY_PIECE
  675.                             EXIT DO
  676.                         CASE ENEMY_PIECE
  677.                             Record_Capture from_square, to_square, target
  678.                             EXIT DO
  679.                         CASE OFF_BOARD
  680.                             EXIT DO
  681.                     END SELECT
  682.                 LOOP
  683.             CASE WR
  684.                 to_square = from_square + 1
  685.                 DO
  686.                     target = white_targets(chess_board(to_square))
  687.                     SELECT CASE target
  688.                         CASE EMPTY_SQUARE
  689.                             Record_Move from_square, to_square
  690.                             to_square = to_square + 1
  691.                         CASE FRIENDLY_PIECE
  692.                             EXIT DO
  693.                         CASE ENEMY_PIECE
  694.                             Record_Capture from_square, to_square, target
  695.                             EXIT DO
  696.                         CASE OFF_BOARD
  697.                             EXIT DO
  698.                     END SELECT
  699.                 LOOP
  700.                 to_square = from_square + 10
  701.                 DO
  702.                     target = white_targets(chess_board(to_square))
  703.                     SELECT CASE target
  704.                         CASE EMPTY_SQUARE
  705.                             Record_Move from_square, to_square
  706.                             to_square = to_square + 10
  707.                         CASE FRIENDLY_PIECE
  708.                             EXIT DO
  709.                         CASE ENEMY_PIECE
  710.                             Record_Capture from_square, to_square, target
  711.                             EXIT DO
  712.                         CASE OFF_BOARD
  713.                             EXIT DO
  714.                     END SELECT
  715.                 LOOP
  716.                 to_square = from_square - 1
  717.                 DO
  718.                     target = white_targets(chess_board(to_square))
  719.                     SELECT CASE target
  720.                         CASE EMPTY_SQUARE
  721.                             Record_Move from_square, to_square
  722.                             to_square = to_square - 1
  723.                         CASE FRIENDLY_PIECE
  724.                             EXIT DO
  725.                         CASE ENEMY_PIECE
  726.                             Record_Capture from_square, to_square, target
  727.                             EXIT DO
  728.                         CASE OFF_BOARD
  729.                             EXIT DO
  730.                     END SELECT
  731.                 LOOP
  732.                 to_square = from_square - 10
  733.                 DO
  734.                     target = white_targets(chess_board(to_square))
  735.                     SELECT CASE target
  736.                         CASE EMPTY_SQUARE
  737.                             Record_Move from_square, to_square
  738.                             to_square = to_square - 10
  739.                         CASE FRIENDLY_PIECE
  740.                             EXIT DO
  741.                         CASE ENEMY_PIECE
  742.                             Record_Capture from_square, to_square, target
  743.                             EXIT DO
  744.                         CASE OFF_BOARD
  745.                             EXIT DO
  746.                     END SELECT
  747.                 LOOP
  748.             CASE WQ
  749.                 to_square = from_square + 9
  750.                 DO
  751.                     target = white_targets(chess_board(to_square))
  752.                     SELECT CASE target
  753.                         CASE EMPTY_SQUARE
  754.                             Record_Move from_square, to_square
  755.                             to_square = to_square + 9
  756.                         CASE FRIENDLY_PIECE
  757.                             EXIT DO
  758.                         CASE ENEMY_PIECE
  759.                             Record_Capture from_square, to_square, target
  760.                             EXIT DO
  761.                         CASE OFF_BOARD
  762.                             EXIT DO
  763.                     END SELECT
  764.                 LOOP
  765.                 to_square = from_square + 11
  766.                 DO
  767.                     target = white_targets(chess_board(to_square))
  768.                     SELECT CASE target
  769.                         CASE EMPTY_SQUARE
  770.                             Record_Move from_square, to_square
  771.                             to_square = to_square + 11
  772.                         CASE FRIENDLY_PIECE
  773.                             EXIT DO
  774.                         CASE ENEMY_PIECE
  775.                             Record_Capture from_square, to_square, target
  776.                             EXIT DO
  777.                         CASE OFF_BOARD
  778.                             EXIT DO
  779.                     END SELECT
  780.                 LOOP
  781.                 to_square = from_square - 9
  782.                 DO
  783.                     target = white_targets(chess_board(to_square))
  784.                     SELECT CASE target
  785.                         CASE EMPTY_SQUARE
  786.                             Record_Move from_square, to_square
  787.                             to_square = to_square - 9
  788.                         CASE FRIENDLY_PIECE
  789.                             EXIT DO
  790.                         CASE ENEMY_PIECE
  791.                             Record_Capture from_square, to_square, target
  792.                             EXIT DO
  793.                         CASE OFF_BOARD
  794.                             EXIT DO
  795.                     END SELECT
  796.                 LOOP
  797.                 to_square = from_square - 11
  798.                 DO
  799.                     target = white_targets(chess_board(to_square))
  800.                     SELECT CASE target
  801.                         CASE EMPTY_SQUARE
  802.                             Record_Move from_square, to_square
  803.                             to_square = to_square - 11
  804.                         CASE FRIENDLY_PIECE
  805.                             EXIT DO
  806.                         CASE ENEMY_PIECE
  807.                             Record_Capture from_square, to_square, target
  808.                             EXIT DO
  809.                         CASE OFF_BOARD
  810.                             EXIT DO
  811.                     END SELECT
  812.                 LOOP
  813.                 to_square = from_square + 1
  814.                 DO
  815.                     target = white_targets(chess_board(to_square))
  816.                     SELECT CASE target
  817.                         CASE EMPTY_SQUARE
  818.                             Record_Move from_square, to_square
  819.                             to_square = to_square + 1
  820.                         CASE FRIENDLY_PIECE
  821.                             EXIT DO
  822.                         CASE ENEMY_PIECE
  823.                             Record_Capture from_square, to_square, target
  824.                             EXIT DO
  825.                         CASE OFF_BOARD
  826.                             EXIT DO
  827.                     END SELECT
  828.                 LOOP
  829.                 to_square = from_square + 10
  830.                 DO
  831.                     target = white_targets(chess_board(to_square))
  832.                     SELECT CASE target
  833.                         CASE EMPTY_SQUARE
  834.                             Record_Move from_square, to_square
  835.                             to_square = to_square + 10
  836.                         CASE FRIENDLY_PIECE
  837.                             EXIT DO
  838.                         CASE ENEMY_PIECE
  839.                             Record_Capture from_square, to_square, target
  840.                             EXIT DO
  841.                         CASE OFF_BOARD
  842.                             EXIT DO
  843.                     END SELECT
  844.                 LOOP
  845.                 to_square = from_square - 1
  846.                 DO
  847.                     target = white_targets(chess_board(to_square))
  848.                     SELECT CASE target
  849.                         CASE EMPTY_SQUARE
  850.                             Record_Move from_square, to_square
  851.                             to_square = to_square - 1
  852.                         CASE FRIENDLY_PIECE
  853.                             EXIT DO
  854.                         CASE ENEMY_PIECE
  855.                             Record_Capture from_square, to_square, target
  856.                             EXIT DO
  857.                         CASE OFF_BOARD
  858.                             EXIT DO
  859.                     END SELECT
  860.                 LOOP
  861.                 to_square = from_square - 10
  862.                 DO
  863.                     target = white_targets(chess_board(to_square))
  864.                     SELECT CASE target
  865.                         CASE EMPTY_SQUARE
  866.                             Record_Move from_square, to_square
  867.                             to_square = to_square - 10
  868.                         CASE FRIENDLY_PIECE
  869.                             EXIT DO
  870.                         CASE ENEMY_PIECE
  871.                             Record_Capture from_square, to_square, target
  872.                             EXIT DO
  873.                         CASE OFF_BOARD
  874.                             EXIT DO
  875.                     END SELECT
  876.                 LOOP
  877.             CASE WK
  878.                 to_square = from_square + 9
  879.                 target = chess_board(to_square)
  880.                 action = white_target(target)
  881.                 SELECT CASE action
  882.                     CASE EMPTY_SQUARE
  883.                         Record_Move from_square, to_square
  884.                     CASE FRIENDLY_PIECE
  885.                     CASE ENEMY_PIECE
  886.                         Record_Capture from_square, to_square, target
  887.                     CASE OFF_BOARD
  888.                 END SELECT
  889.                 to_square = from_square + 10
  890.                 target = chess_board(to_square)
  891.                 action = white_target(target)
  892.                 SELECT CASE action
  893.                     CASE EMPTY_SQUARE
  894.                         Record_Move from_square, to_square
  895.                     CASE FRIENDLY_PIECE
  896.                     CASE ENEMY_PIECE
  897.                         Record_Capture from_square, to_square, target
  898.                     CASE OFF_BOARD
  899.                 END SELECT
  900.                 to_square = from_square + 11
  901.                 target = chess_board(to_square)
  902.                 action = white_target(target)
  903.                 SELECT CASE action
  904.                     CASE EMPTY_SQUARE
  905.                         Record_Move from_square, to_square
  906.                     CASE FRIENDLY_PIECE
  907.                     CASE ENEMY_PIECE
  908.                         Record_Capture from_square, to_square, target
  909.                     CASE OFF_BOARD
  910.                 END SELECT
  911.                 to_square = from_square + 1
  912.                 target = chess_board(to_square)
  913.                 action = white_target(target)
  914.                 SELECT CASE action
  915.                     CASE EMPTY_SQUARE
  916.                         Record_Move from_square, to_square
  917.                     CASE FRIENDLY_PIECE
  918.                     CASE ENEMY_PIECE
  919.                         Record_Capture from_square, to_square, target
  920.                     CASE OFF_BOARD
  921.                 END SELECT
  922.                 to_square = from_square - 9
  923.                 target = chess_board(to_square)
  924.                 action = white_target(target)
  925.                 SELECT CASE action
  926.                     CASE EMPTY_SQUARE
  927.                         Record_Move from_square, to_square
  928.                     CASE FRIENDLY_PIECE
  929.                     CASE ENEMY_PIECE
  930.                         Record_Capture from_square, to_square, target
  931.                     CASE OFF_BOARD
  932.                 END SELECT
  933.                 to_square = from_square - 10
  934.                 target = chess_board(to_square)
  935.                 action = white_target(target)
  936.                 SELECT CASE action
  937.                     CASE EMPTY_SQUARE
  938.                         Record_Move from_square, to_square
  939.                     CASE FRIENDLY_PIECE
  940.                     CASE ENEMY_PIECE
  941.                         Record_Capture from_square, to_square, target
  942.                     CASE OFF_BOARD
  943.                 END SELECT
  944.                 to_square = from_square - 11
  945.                 target = chess_board(to_square)
  946.                 action = white_target(target)
  947.                 SELECT CASE action
  948.                     CASE EMPTY_SQUARE
  949.                         Record_Move from_square, to_square
  950.                     CASE FRIENDLY_PIECE
  951.                     CASE ENEMY_PIECE
  952.                         Record_Capture from_square, to_square, target
  953.                     CASE OFF_BOARD
  954.                 END SELECT
  955.                 to_square = from_square - 1
  956.                 target = chess_board(to_square)
  957.                 action = white_target(target)
  958.                 SELECT CASE action
  959.                     CASE EMPTY_SQUARE
  960.                         Record_Move from_square, to_square
  961.                     CASE FRIENDLY_PIECE
  962.                     CASE ENEMY_PIECE
  963.                         Record_Capture from_square, to_square, target
  964.                     CASE OFF_BOARD
  965.                 END SELECT
  966.             CASE WC
  967.                 to_square = from_square + 9
  968.                 target = chess_board(to_square)
  969.                 action = white_target(target)
  970.                 SELECT CASE action
  971.                     CASE EMPTY_SQUARE
  972.                         Record_Move from_square, to_square
  973.                     CASE FRIENDLY_PIECE
  974.                     CASE ENEMY_PIECE
  975.                         Record_Capture from_square, to_square, target
  976.                     CASE OFF_BOARD
  977.                 END SELECT
  978.                 to_square = from_square + 10
  979.                 target = chess_board(to_square)
  980.                 action = white_target(target)
  981.                 SELECT CASE action
  982.                     CASE EMPTY_SQUARE
  983.                         Record_Move from_square, to_square
  984.                     CASE FRIENDLY_PIECE
  985.                     CASE ENEMY_PIECE
  986.                         Record_Capture from_square, to_square, target
  987.                     CASE OFF_BOARD
  988.                 END SELECT
  989.                 to_square = from_square + 11
  990.                 target = chess_board(to_square)
  991.                 action = white_target(target)
  992.                 SELECT CASE action
  993.                     CASE EMPTY_SQUARE
  994.                         Record_Move from_square, to_square
  995.                     CASE FRIENDLY_PIECE
  996.                     CASE ENEMY_PIECE
  997.                         Record_Capture from_square, to_square, target
  998.                     CASE OFF_BOARD
  999.                 END SELECT
  1000.                 to_square = from_square + 1
  1001.                 target = chess_board(to_square)
  1002.                 action = white_target(target)
  1003.                 SELECT CASE action
  1004.                     CASE EMPTY_SQUARE
  1005.                         Record_Move from_square, to_square
  1006.                     CASE FRIENDLY_PIECE
  1007.                     CASE ENEMY_PIECE
  1008.                         Record_Capture from_square, to_square, target
  1009.                     CASE OFF_BOARD
  1010.                 END SELECT
  1011.                 to_square = from_square - 9
  1012.                 target = chess_board(to_square)
  1013.                 action = white_target(target)
  1014.                 SELECT CASE action
  1015.                     CASE EMPTY_SQUARE
  1016.                         Record_Move from_square, to_square
  1017.                     CASE FRIENDLY_PIECE
  1018.                     CASE ENEMY_PIECE
  1019.                         Record_Capture from_square, to_square, target
  1020.                     CASE OFF_BOARD
  1021.                 END SELECT
  1022.                 to_square = from_square - 10
  1023.                 target = chess_board(to_square)
  1024.                 action = white_target(target)
  1025.                 SELECT CASE action
  1026.                     CASE EMPTY_SQUARE
  1027.                         Record_Move from_square, to_square
  1028.                     CASE FRIENDLY_PIECE
  1029.                     CASE ENEMY_PIECE
  1030.                         Record_Capture from_square, to_square, target
  1031.                     CASE OFF_BOARD
  1032.                 END SELECT
  1033.                 to_square = from_square - 11
  1034.                 target = chess_board(to_square)
  1035.                 action = white_target(target)
  1036.                 SELECT CASE action
  1037.                     CASE EMPTY_SQUARE
  1038.                         Record_Move from_square, to_square
  1039.                     CASE FRIENDLY_PIECE
  1040.                     CASE ENEMY_PIECE
  1041.                         Record_Capture from_square, to_square, target
  1042.                     CASE OFF_BOARD
  1043.                 END SELECT
  1044.                 to_square = from_square - 1
  1045.                 target = chess_board(to_square)
  1046.                 action = white_target(target)
  1047.                 SELECT CASE action
  1048.                     CASE EMPTY_SQUARE
  1049.                         Record_Move from_square, to_square
  1050.                     CASE FRIENDLY_PIECE
  1051.                     CASE ENEMY_PIECE
  1052.                         Record_Capture from_square, to_square, target
  1053.                     CASE OFF_BOARD
  1054.                 END SELECT
  1055.             CASE BP
  1056.  
  1057.             CASE BN
  1058.  
  1059.             CASE BB
  1060.  
  1061.             CASE BR
  1062.  
  1063.             CASE BQ
  1064.  
  1065.             CASE BK
  1066.  
  1067.             CASE BC
  1068.  
  1069.         END SELECT
  1070.     LOOP
  1072.  
  1073. SUB Make_Move (i AS INTEGER)
  1074.  
  1076.  
  1077. SUB Take_Back
  1078.  
  1080.  
  1081. SUB Search_One_Q (alpha AS INTEGER, beta AS INTEGER)
  1082.     Generate_Moves
  1083.     i = move_stack_index(ply)
  1084.     WHILE move_stack(i).special <> TERMINATE
  1085.         Make_Move i
  1086.         move_stack(i).score = Qsearch(alpha, beta)
  1087.         Take_Back
  1088.         i = i - 1
  1089.     WEND
  1091.  
Title: Re: Chess Programming Tutorial
Post by: TempodiBasic on March 25, 2020, 06:38:51 pm
Hi Mike
thanks to continue to show your work here.

I'm very interested to see how you build this chess engine, but I'm beginner in this kind of programming in chess engine,
so searching to follow your code has let me understand many things, starting why offset of moves of pieces that goes together a  monodimensional managing of chessboard and  a chessboard of 120 cells.

about your last code I have lost meself in the long SUB Generating_Moves  but with some time it will be clearer at my eyes.

I want to report these 2 stranges part that logically brings me to think that there is an error of typing...
Code: QB64: [Select]
  1. DIM SHARED white_target(40) AS _BYTE
  2.  
  3. DATA EMPTY,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,0,0
  4. DATA EMPTY,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EK,EK,0,OB
  5.  
  6. FOR i = 0 TO 99: READ white_target(i): NEXT
  7.  
  8.  
  9. DIM SHARED black_target(40) AS _BYTE
  10.  
  11. DATA EMPTY,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EK,EK,0,0
  12. DATA EMPTY,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,0,OB
  13.  
  14. FOR i = 0 TO 99: READ black_target(i): NEXT

Here i runs until 99 but it seems there are only 40 DATA to read and white_data() and balck_data() have 41 items

----------------
Code: QB64: [Select]
  1. DIM SHARED royal_offsets AS _BYTE
  2.  
  3. DATA 1,9,10,11,-1,-9,-10,-11
  4.  
  5. FOR i = 0 TO 7: READ royal_offsets(i): NEXT
  6.  
  7.  
  8. DIM SHARED knight_offsets AS _BYTE
  9.  
  10. DATA 8,12,19,21,-8,-12,-19,-21
  11.  
  12. FOR i = 0 TO 7: READ knight_offsets(i): NEXT
  13.  

Here instead royal_offsets and knight_offsets are not DIMmed as array...

Thanks to read
Title: Re: Chess Programming Tutorial
Post by: romichess on March 25, 2020, 07:02:26 pm
Quote from: TempodiBasic on March 25, 2020, 06:38:51 pm
Hi Mike
thanks to continue to show your work here.

I'm very interested to see how you build this chess engine, but I'm beginner in this kind of programming in chess engine,
so searching to follow your code has let me understand many things, starting why offset of moves of pieces that goes together a  monodimensional managing of chessboard and  a chessboard of 120 cells.

about your last code I have lost meself in the long SUB Generating_Moves  but with some time it will be clearer at my eyes.

I want to report these 2 stranges part that logically brings me to think that there is an error of typing...
Code: QB64: [Select]
  1. DIM SHARED white_target(40) AS _BYTE
  2.  
  3. DATA EMPTY,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,0,0
  4. DATA EMPTY,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EK,EK,0,OB
  5.  
  6. FOR i = 0 TO 99: READ white_target(i): NEXT
  7.  
  8.  
  9. DIM SHARED black_target(40) AS _BYTE
  10.  
  11. DATA EMPTY,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EP,EK,EK,0,0
  12. DATA EMPTY,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,FP,0,OB
  13.  
  14. FOR i = 0 TO 99: READ black_target(i): NEXT

Here i runs until 99 but it seems there are only 40 DATA to read and white_data() and balck_data() have 41 items

----------------
Code: QB64: [Select]
  1. DIM SHARED royal_offsets AS _BYTE
  2.  
  3. DATA 1,9,10,11,-1,-9,-10,-11
  4.  
  5. FOR i = 0 TO 7: READ royal_offsets(i): NEXT
  6.  
  7.  
  8. DIM SHARED knight_offsets AS _BYTE
  9.  
  10. DATA 8,12,19,21,-8,-12,-19,-21
  11.  
  12. FOR i = 0 TO 7: READ knight_offsets(i): NEXT
  13.  

Here instead royal_offsets and knight_offsets are not DIMmed as array...

Thanks to read

Ah yes, thank you!
Title: Re: Chess Programming Tutorial
Post by: romichess on March 25, 2020, 08:18:32 pm
Let me try to explain the move generator a little better then. Using lots of IF statements in a chess engine is a performance killer. I avoid IF statements whenever possible. In C there are two choices. A switch (SELECT CASE) statement and an array of function pointers. These days I'd use the function pointers which is called a jump table. C/C++ compilers can make jump tables out of switch statements but it is hit and miss. C/C++ compilers can also substitute IF statement for switch cases if there are not enough cases. That is why I'd use function pointer arrays to take all decisions away from the compiler. As far as I know I do not have that choice in QB64? So all I can do in QB64 is use the theoretically best approach and hope that QB64 and Mingw64 do a good job. With that said let's look at the code.

There is an array of 40 type piece. The piece[0].nxt holds the first white piece and piece[20].nxt holds the first black piece. And start_index(wtm) gives either 0 or 20.
Therefore we get the first piece like so: piece_index = next_piece(start_index(wtm)).
Okay, I see that I changed the data and did not change the code, oops. So make that: 
piece_index = piece(start_index(wtm)).nxt. I'm really sorry about that, too many senior moments. Anyway, now that we have the first piece we can find its from square: from_square = piece(piece_index).squ. When we are done with the piece we get the next piece at the end of the main loop like this: piece_index = piece(piece_index).nxt. And I have not added that yet, another oops. So yes, it would be hard to understand in such an incomplete state, my bad :(. Now that we have the from square, we look up the type of piece it is. Did I mention that on the chessboard are indexes, not piece types. That is why we have to use the piece index to look up its type: SELECT CASE piece(piece_index).typ. The pawns will take more study. Essentially they are treated as 12 different types depending on which square they are on. For example X2R is a white pawn on rank 2 or a black pawn on rank 7 on file 1 and therefore they need not check for a left capture thus the X. A white pawn on rank 2 away from an edge file is L2R. And the 2 means it can move one or two squares. This is all done to avoid a plethora of IF statements. Also, why make checks that can be avoided all at the cost of one SELECT CASE statement. In the pawn cases 2 is double move, 1 is single, E is check for en passant and P is promotion.

The knights are much more simple. The knight moves can be done in a loop executed 8 times. However, it is faster to "unroll the loop" and repeat the code 8 times.

            CASE WN
                to_square = from_square + 8 'one up and two to the left
                target = chess_board(to_square) 'EMPTY, piece_index or off-edge square
                action = white_target(target) 'exactly the action to take
                SELECT CASE action
                    CASE EMPTY_SQUARE
                        Record_Move from_square, to_square
                    CASE FRIENDLY_PIECE
                    CASE ENEMY_PIECE
                        Record_Capture from_square, to_square, target
                    CASE OFF_BOARD
                END SELECT 'on to the next offset

The sliders are more fun! Once again we unroll the outer loop.

            CASE WB
                to_square = from_square + 9 'prime first to square, up and to the left
                DO
                    target = chess_board(to_square) same as for knight
                    action = white_targets(target)
                    SELECT CASE action
                        CASE EMPTY_SQUARE
                            Record_Move from_square, to_square
                            to_square = to_square + 9 'This time we are in a do loop, next t_s
                        CASE FRIENDLY_PIECE
                            EXIT DO 'we exit the loop when we can't go further
                        CASE ENEMY_PIECE
                            Record_Capture from_square, to_square, target
                            EXIT DO
                        CASE OFF_BOARD
                            EXIT DO
                    END SELECT
                LOOP

More will become clear. For example the various record move subs will not return right away. They will call the capture only search to resolve captures and add a score to each move. This must be done at the leafs of the tree anyway and doing it for every move in the tree cost very little and has huge benefits. The first is that in the gen all moves routine there is no ENEMY_KING case because only legal moves are generated as the capture search will catch any illegal move and not record it. And having a score for move ordering is huge because the alpha-beta routine performs more spectacularly the better the move ordering is. The end result is that there will be a legal (as opposed to pseudo legal) list of moves that we can do a one pass sort to find the move with the best score to try first. And if it is the best move a huge amount of the search tree will be beta pruned.

I hope this helps. :))

 
Title: Re: Chess Programming Tutorial
Post by: romichess on March 26, 2020, 02:19:27 am
Well I got my answer about the SELECT CASE statement and how QB64 handles it. It just converts SELECT CASE to a series of IF statements. And there is no point continuing this tutorial on blazingly fast chess coding in a language that is incapable of it. It would be illusionary at best and even ((very)much) slower than carefully handcrafted IF statement blocks at worst. What would be the point of continuing? It would be disasterly slow when done. It would be better just to rewrite everything using IF statements and I can't do that, lol. However, the 120 cell board is a valuable idea and doubly linked piece list are a big performance boost especially in an endgame with few pieces left on the board.  My EarlyWork.zip file will demonstrate the power of the programming techniques in this tutorial. Sorry, they are in C and even assembler but there is an exe for each. On my i7-3930k the Godzilla example generates and makes/unmakes 65 million moves per second just using one thread. In 1.86 seconds it traverses from the original starting position all possible moves to 6 moves deep. Carnivor is an actual working chess engine that will run in the windows console. Time per move is set by st 30 for 30 seconds or sd 9 for nine moves deep. Moves are entered like e2e4 or e7e8q for queening or e1g1 for king side castling. Etc. Any Questions? Just ask!  [ This attachment cannot be displayed inline in 'Print Page' view ]  
Title: Re: Chess Programming Tutorial
Post by: romichess on March 26, 2020, 03:40:47 am
Okay, because of Steve we may be back in business. The code in temp/main.txt can be swapped with actual C/C++ source code of my choosing. If that is the case I'll just create my own jump tables. Once I have an index. I'll just insert code like this.

void wpmf(short from_square) {
// white pawn code
}

void wnmf(short from_square) {
// white knight code
}

void wbmf(short from_square) {
// white bishop code
}

void (*movegenf[]) (short) = { wpmf, wnmf, wbmf, ... };

Then to call the correct move gen function all that needs to be written is:

movegen[index](from_square);

I wonder if it will really be that simple?
Title: Re: Chess Programming Tutorial
Post by: FellippeHeitor on March 26, 2020, 08:30:53 am
No problem mixing your languages, of course. But this:

Quote
(...) there is no point continuing this tutorial on blazingly fast chess coding in a language that is incapable of it. It would be illusionary at best and even ((very)much) slower than carefully handcrafted IF statement blocks at worst. What would be the point of continuing?

Did you try using the select case block you proposed in the first post of the thread you started about SELECT CASE? Did you actually compile it and run it just to make sure it would work as slow as you expect or are you assuming it will be so slow without trying first?
Title: Re: Chess Programming Tutorial
Post by: romichess on March 26, 2020, 03:11:17 pm
Quote from: FellippeHeitor on March 26, 2020, 08:30:53 am
No problem mixing your languages, of course. But this:

Did you try using the select case block you proposed in the first post of the thread you started about SELECT CASE? Did you actually compile it and run it just to make sure it would work as slow as you expect or are you assuming it will be so slow without trying first?

Move generation, captures only generation, make move and unmake move all benefit greatly from jump tables. There are 12 cases just for the pawn. We can get to the correct pawn code by one jump that is not conditional or we can get there by IF IF IF IF IF IF IF IF IF IF IF IF until we find the correct one. The problem in chess is it is constantly in flux and predicting the outcome of any if statement tends toward 50/50 and false branch predictions drags down performance tremendously. If ones goal was to write a correct but intolerably slow chess engine then it does not matter. But in this tutorial my code does not make sense because it is counter productive to the goal of writing a fast chess engine. If statements are just not good for performance in a chess engine.
Title: Re: Chess Programming Tutorial
Post by: TerryRitchie on March 26, 2020, 03:48:53 pm
I've played some pretty quick and impressive chess games in GWBASIC back in the day on 8088 hardware. I'm sure QB64 is up to the task. Give it a try.
Title: Re: Chess Programming Tutorial
Post by: romichess on March 26, 2020, 04:27:24 pm
Quote from: TerryRitchie on March 26, 2020, 03:48:53 pm
I've played some pretty quick and impressive chess games in GWBASIC back in the day on 8088 hardware. I'm sure QB64 is up to the task. Give it a try.

I appreciate your comment and previous experience, really. My perspective is different. I've been playing in chess tournaments since I was 12yo. The first chess program that could give me any fight at all was Chessmaster 2100 on an 80386 machine. My record against Stockfish the world's strongest pc chess engine is 4 draws and 4 losses for a performance rating of 3100 which is higher than the current world champions rating. But then I know how chess engines work so I can play better against them. Also my record against Stockfish while receiving QN odds and giving SF the first move is two draws and a win. Most grandmasters can not even do that!

Okay, so I need to temper-down my opinion as to what a chess engine needs to be to the people here that might be interested. I can try to do that.
Title: Re: Chess Programming Tutorial
Post by: SMcNeill on March 26, 2020, 04:52:47 pm
Quote from: romichess on March 26, 2020, 03:11:17 pm
Move generation, captures only generation, make move and unmake move all benefit greatly from jump tables. There are 12 cases just for the pawn. We can get to the correct pawn code by one jump that is not conditional or we can get there by IF IF IF IF IF IF IF IF IF IF IF IF until we find the correct one. The problem in chess is it is constantly in flux and predicting the outcome of any if statement tends toward 50/50 and false branch predictions drags down performance tremendously. If ones goal was to write a correct but intolerably slow chess engine then it does not matter. But in this tutorial my code does not make sense because it is counter productive to the goal of writing a fast chess engine. If statements are just not good for performance in a chess engine.

You could get there with 12 IF statements, if you were a complete beginner at data interpretation.  Simply by breaking those statements into binary values, you easily reduce the maximum number of comparisons down to 4.

IF X < 7 THEN '1 TO 6
   IF X < 4 THEN '1 TO 3
      IF X < 3 THEN 'IT'S 1 OR 2
           IF X < 2 THEN 'IT'S 1   ELSE 'IT'S 2
     ELSE 'IT'S 3
     END IF
   ELSE 'IT'S 4 TO 6
        'AS ABOVE
   END IF
ELSE 'IT'S 7 TO 12
     'AS ABOVE
END IF

A maximum of 4 comparisons for up to 16 items...  It's not quite as fast as 1 to 1 jump tables, but it's not bad overall.


Remember, you can always fall back on the old ON... GOTO... statements also.

ON X GOTO 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 1100, 1200

I think those tend to be 1 to 1 jump style lists.
Title: Re: Chess Programming Tutorial
Post by: romichess on March 26, 2020, 05:23:34 pm
Quote from: SMcNeill on March 26, 2020, 04:52:47 pm
You could get there with 12 IF statements, if you were a complete beginner at data interpretation.  Simply by breaking those statements into binary values, you easily reduce the maximum number of comparisons down to 4.

IF X < 7 THEN '1 TO 6
   IF X < 4 THEN '1 TO 3
      IF X < 3 THEN 'IT'S 1 OR 2
           IF X < 2 THEN 'IT'S 1   ELSE 'IT'S 2
     ELSE 'IT'S 3
     END IF
   ELSE 'IT'S 4 TO 6
        'AS ABOVE
   END IF
ELSE 'IT'S 7 TO 12
     'AS ABOVE
END IF

A maximum of 4 comparisons for up to 16 items...  It's not quite as fast as 1 to 1 jump tables, but it's not bad overall.


Remember, you can always fall back on the old ON... GOTO... statements also.

ON X GOTO 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 1100, 1200

I think those tend to be 1 to 1 jump style lists.
Yes, of course hand crafted If blocks can be optimised. In my code though I'm using SELECT CASE because I just assumed that QB64 would write an equivalent C switch statement. I'm new to QB variant basic. The ON...GOTO statement might be the answer. I'll check it out. Thanks!
Title: Re: Chess Programming Tutorial
Post by: romichess on March 26, 2020, 07:38:10 pm
ON GOSUB is cleaner than ON GOTO. And it is even cleaner than SELECT CASE, switch() or C's jumptables. C makes one create full functions and they are outside of the calling function. Here the code is embedded in the same sub from which they are called. Very nice! And I'm not going to look at main.txt because if I do and QB64 does something jenky then I'll just get upset again, lol. Here is just the structure of the new Generate_Moves sub without the piece code so one can easily see the structure. And I did change the constants to start at 1 rather than 0 so they would work correctly with ON GOSUB.

Code: QB64: [Select]
  1. SUB Generate_Moves
  2.     piece_index = piece(start_index(wtm)).nxt
  3.     DO
  4.         from_square = piece(piece_index).squ
  5.         ON piece(piece_index).typ GOSUB WP, WN, WB, WR, WQ, WC, WK, BP, BN, BB, BR, BQ, BC, BK, TR
  6.         piece_index = piece(piece_index).nxt
  7.     LOOP
  8.     EXIT SUB
  9.     WP:
  10.     ON white_pawns(from_square) GOSUB WX2R, WL2R, WL2X, WX1R, WL1R, WL1X, WXER, WLER, WLEX, WXPR, WLPR, WLPX
  11.     END
  12.  
  13.     WX2R:
  14.  
  15.     END
  16.  
  17.     WL2R:
  18.  
  19.     END
  20.  
  21.     WL2X:
  22.  
  23.     END
  24.  
  25.     WX1R:
  26.  
  27.     END
  28.  
  29.     WL1R:
  30.  
  31.     END
  32.  
  33.     WL1X:
  34.  
  35.     END
  36.  
  37.     WXER:
  38.  
  39.     END
  40.  
  41.     WLER:
  42.  
  43.     END
  44.  
  45.     WLEX:
  46.  
  47.     END
  48.  
  49.     WXPR:
  50.  
  51.     END
  52.  
  53.     WLPR:
  54.  
  55.     END
  56.  
  57.     WLPX:
  58.  
  59.     END
  60.  
  61.     WN:
  62.  
  63.     END
  64.  
  65.     WB:
  66.  
  67.     END
  68.  
  69.     WR:
  70.  
  71.     END
  72.  
  73.     WQ:
  74.  
  75.     END
  76.  
  77.     WC:
  78.  
  79.     END
  80.  
  81.     WK:
  82.  
  83.     END
  84.  
  85.     BP:
  86.     ON black_pawns(from_square) GOSUB BX2R, BL2R, BL2X, BX1R, BL1R, BL1X, BXER, BLER, BLEX, BXPR, BLPR, BLPX
  87.     END
  88.  
  89.     BX2R:
  90.  
  91.     END
  92.  
  93.     BL2R:
  94.  
  95.     END
  96.  
  97.     BL2X:
  98.  
  99.     END
  100.  
  101.     BX1R:
  102.  
  103.     END
  104.  
  105.     BL1R:
  106.  
  107.     END
  108.  
  109.     BL1X:
  110.  
  111.     END
  112.  
  113.     BXER:
  114.  
  115.     END
  116.  
  117.     BLER:
  118.  
  119.     END
  120.  
  121.     BLEX:
  122.  
  123.     END
  124.  
  125.     BXPR:
  126.  
  127.     END
  128.  
  129.     BLPR:
  130.  
  131.     END
  132.  
  133.     BLPX:
  134.  
  135.     END
  136.  
  137.     BN:
  138.  
  139.     END
  140.  
  141.     BB:
  142.  
  143.     END
  144.  
  145.     BR:
  146.  
  147.     END
  148.  
  149.     BQ:
  150.  
  151.     END
  152.  
  153.     BC:
  154.  
  155.     END
  156.  
  157.     BK:
  158.  
  159.     END
  160.  
  161.     TR:
  162.     EXIT SUB
  163.     END
  164.  
Title: Re: Chess Programming Tutorial
Post by: romichess on April 12, 2020, 07:40:44 pm
I have not abandoned this project. It is just that I do not think in basic as easily as I think in C. So I have been writing a chess engine in C that I then will translate into basic. It is going wonderfly! And it will not be a traditional engine by any comparison. It might even be paradigm changing! My engine RomiChess was "famous" for its learning algorithm. But that was end of game learning where it stores every game it plays (or imported games) into a learn file with reinforcement learning values. The new engine will learn in real time during a game. Also it will not have a traditional evaluation function. Instead it will collect statistics from the search that it will analyze to select a move to play. Both of the above is why it will be (fingers crossed) a paradigm changer. Wish me luck. :)   
Title: Re: Chess Programming Tutorial
Post by: romichess on April 12, 2020, 08:37:08 pm
When I want to code something in basic like I would in C I have to stop what I am doing, research if basic has an equivalent, understand the syntax, learn the syntax, remember the syntax and then try to make it work. In C I just know how.

For example, when generating a capture en passant move one could simply use an IF statement like so for white:

IF to_square = ep_square then
target_square = to_square - 10 ' on a 12x10 board
ELSE
target_square = to_square
END IF
target = board(target_square)

In C one can do it like above or like this:

target_square = ts ^ ((en_passant_bit == 1 << ts) << 3);
target = board[target_square];

This uses unsigned 64 bit integers. It takes advantage of the fact that bit 4 is set for all the possible en passant squares. It works by computing the truth value of (en_passant_bit == 1 << ts) which yields a 0 or 1. Then it left shifts the 0 or 1 into bit 4 which results in either 0 or 8 that is then exclusive_ored with the 4th bit of the to_square .

This might be able to be done in basic but without doing a lot of work and experiencing much aggravation and spending a lot of time researching I just do not know if it can be.

 
   
Title: Re: Chess Programming Tutorial
Post by: Adrian on January 04, 2021, 09:58:10 am
Excellent tutorial Mike, thanks!
Text Only | Text with Attachments