Author Topic: Chess Programming Tutorial  (Read 13737 times)

0 Members and 1 Guest are viewing this topic.

Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial: Lesson 5, Search
« Reply #15 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
  14.  
  15. SUB Search_control
  16.     legal = Move_Generator
  17.     FOR depth = 1 TO max_depth
  18.         FOR i = move_stack_index(ply) TO move_stack_index(ply - 1) + 1 STEP -1
  19.             Make_Move (i)
  20.             move_stack(i).score = Search(-10000, 10000, depth - 1)
  21.             Take_Back
  22.             IF move_stack(i).score > best THEN
  23.                 best = score
  24.                 move = move_stack(i)
  25.             END IF
  26.         NEXT
  27.         ' Sort_Root_Moves
  28.     NEXT
My name is Michael, but you can call me Mike :)

Offline anttiylikoski

  • Newbie
  • Posts: 25
    • View Profile
Re: Chess Programming Tutorial
« Reply #16 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


Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial: Lesson 6, castling
« Reply #17 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.  
« Last Edit: January 29, 2020, 07:46:09 pm by romichess »
My name is Michael, but you can call me Mike :)

Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial: Lesson 7, Going forward
« Reply #18 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!
« Last Edit: January 29, 2020, 08:21:23 pm by romichess »
My name is Michael, but you can call me Mike :)

Offline SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3972
    • View Profile
    • Steve’s QB64 Archive Forum
Re: Chess Programming Tutorial
« Reply #19 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)!
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial: Lesson 8, First Official Code
« Reply #20 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
  7.  
  8. CONST TERMINATE = 0
  9.  
  10. DIM SHARED move_stack(8000) AS moves
  11.  
  12. SUB Search_One_Q (alpha AS INTEGER, beta AS INTEGER)
  13.     Generate_Moves
  14.     i = move_stack_index(ply)
  15.     while move_stack(i).special <> TERMINATE
  16.         Make_Move i
  17.         move_stack(i).score = Qsearch(alpha, beta)
  18.         Take_Back
  19.         i = i - 1
  20.     WEND
  21.  
« Last Edit: January 29, 2020, 09:43:41 pm by romichess »
My name is Michael, but you can call me Mike :)

Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial
« Reply #21 on: January 29, 2020, 09:31:41 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. 
My name is Michael, but you can call me Mike :)

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: Chess Programming Tutorial
« Reply #22 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.
You're not done when it works, you're done when it's right.

Offline romichess

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

Offline TempodiBasic

  • Forum Resident
  • Posts: 1792
    • View Profile
Re: Chess Programming Tutorial
« Reply #24 on: March 17, 2020, 08:23:04 pm »
Bump
:-)
Programming isn't difficult, only it's  consuming time and coffee

Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial
« Reply #25 on: March 25, 2020, 02:05:43 pm »
Bump
:-)
I thought it would go quietly into the night. My apologies! I'll start devoting some time to the project.
My name is Michael, but you can call me Mike :)

Offline romichess

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

Offline TempodiBasic

  • Forum Resident
  • Posts: 1792
    • View Profile
Re: Chess Programming Tutorial
« Reply #27 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
Programming isn't difficult, only it's  consuming time and coffee

Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial
« Reply #28 on: March 25, 2020, 07:02:26 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!
My name is Michael, but you can call me Mike :)

Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial
« Reply #29 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. :))

 
My name is Michael, but you can call me Mike :)