Chess game project : King + Rook vs King endgame

[Adrian]

Another year, another chess project :) This time, the challenge is to write or tweak a *simple* program so that the computer is smart enough to checkmate a lone king with king and rook. This is a trivial endgame that all human chess beginners quickly learn, but strangely where weak chess engines almost always fail. As a starting point, I'll be using a stripped down version of Dean Menezes' popular chess program chess.bas bundled together with QB64. At the moment, it relies on its original AI, which has absolutely no clue how to force the simple checkmate.

Code: QB64: [Select]

1. _FULLSCREEN
2. DEFINT A-Z
3. DECLARE SUB SQUARE (A, B, C)
4. DECLARE SUB SHOWMAN (A, B, FLAG)
5. DECLARE SUB SHOWBD ()
6. DECLARE SUB IO (A, B, X, Y, RESULT)
7. DECLARE FUNCTION INCHECK (X)
8. DECLARE SUB MAKEMOVE (A, B, X, Y)
9. DECLARE SUB KING (A, B, XX(), YY(), NDX)
10. DECLARE SUB ROOK (A, B, XX(), YY(), NDX)
11. DECLARE SUB MOVELIST (A, B, XX(), YY(), NDX)
12. DECLARE FUNCTION EVALUATE (ID, PRUNE)
13. DIM SHARED BOARD(0 TO 7, 0 TO 7)
14. DIM SHARED BESTA(0 TO 7), BESTB(0 TO 7), BESTX(0 TO 7), BESTY(0 TO 7)
15. DIM SHARED LEVEL, MAXLEVEL, SCORE
16. DIM SHARED WCKSFLAG, WCQSFLAG, INTFLAG
17. DIM SHARED WCKSOLD, WCQSOLD
18. LEVEL = 0
19. MAXLEVEL = 5
20. DATA -500,0,0,0,0,0,0,-7500
21. DATA 0,0,0,0,0,0,0,0
22. DATA 0,0,0,0,0,0,0,0
23. DATA 0,0,0,0,0,0,0,0
24. DATA 0,0,0,5000,0,0,0,0
25. DATA 0,0,0,0,0,0,0,0
26. DATA 0,0,0,0,0,0,0,0
27. DATA 0,0,0,0,0,0,0,0
28. FOR X = 0 TO 7
29.     FOR Y = 0 TO 7
30.         READ Z
31.         BOARD(X, Y) = Z
32.     NEXT Y
33. NEXT X
34. A = -1
35. RESULT = 0
36. CLS
37. COLOR 15
38. PRINT
39. PRINT
40. PRINT
41. PRINT
42. PRINT "      SIMPLE CHESS ENDINGS : CHECKMATE WITH KING AND ROOK VS KING"
43. PRINT
44. PRINT
45. PRINT
46. PRINT "     In this game, you play White with only a King and I play Black "
47. PRINT "     with King and Rook. I will try to checkmate you within 50 moves."
48. PRINT "     To move the pieces on the chessboard, type in your move in "
49. PRINT "     coordinate notation, e.g. E2E3 . To exit the game, type QUIT."
50. PRINT
51. PRINT
52. PRINT
53. PRINT
54. PRINT
55. PRINT
56. PRINT
57. PRINT "                   Press any key to continue."
58. Z$ = INPUT$(1)
59. DO
60.     SCORE = 0
61.     CALL IO(A, B, X, Y, RESULT)
62.     CLS
63.     CALL SHOWBD
64.     RESULT = EVALUATE(-1, 10000)
65.     A = BESTA(1)
66.     B = BESTB(1)
67.     X = BESTX(1)
68.     Y = BESTY(1)
69. LOOP
70.  
71.  
72. FUNCTION EVALUATE (ID, PRUNE)
73.     DIM XX(0 TO 26), YY(0 TO 26)
74.     LEVEL = LEVEL + 1
75.     BESTSCORE = 10000 * ID
76.     FOR B = 7 TO 0 STEP -1
77.         FOR A = 7 TO 0 STEP -1
78.             IF SGN(BOARD(B, A)) <> ID THEN GOTO 1
79.             CALL MOVELIST(A, B, XX(), YY(), NDX)
80.             FOR I = 0 TO NDX
81.                 X = XX(I)
82.                 Y = YY(I)
83.                 OLDSCORE = SCORE
84.                 MOVER = BOARD(B, A)
85.                 TARGET = BOARD(Y, X)
86.                 CALL MAKEMOVE(A, B, X, Y)
87.                 IF (LEVEL < MAXLEVEL) THEN SCORE = SCORE + EVALUATE(-ID, BESTSCORE - TARGET + ID * (8 - ABS(4 - X) - ABS(4 - Y)))
88.                 SCORE = SCORE + TARGET - ID * (8 - ABS(4 - X) - ABS(4 - Y))
89.                 IF (ID < 0 AND SCORE > BESTSCORE) OR (ID > 0 AND SCORE < BESTSCORE) THEN
90.                     BESTA(LEVEL) = A
91.                     BESTB(LEVEL) = B
92.                     BESTX(LEVEL) = X
93.                     BESTY(LEVEL) = Y
94.                     BESTSCORE = SCORE
95.                     IF (ID < 0 AND BESTSCORE >= PRUNE) OR (ID > 0 AND BESTSCORE <= PRUNE) THEN
96.                         BOARD(B, A) = MOVER
97.                         BOARD(Y, X) = TARGET
98.                         SCORE = OLDSCORE
99.                         LEVEL = LEVEL - 1
100.                         EVALUATE = BESTSCORE
101.                         EXIT FUNCTION
102.                     END IF
103.                 END IF
104.                 BOARD(B, A) = MOVER
105.                 BOARD(Y, X) = TARGET
106.                 SCORE = OLDSCORE
107.             NEXT
108.        1 NEXT
109.     NEXT
110.     LEVEL = LEVEL - 1
111.     EVALUATE = BESTSCORE
112. END FUNCTION
113.  
114. FUNCTION INCHECK (X)
115.     DIM XX(27), YY(27), NDX
116.     FOR B = 0 TO 7
117.         FOR A = 0 TO 7
118.             IF BOARD(B, A) >= 0 THEN GOTO 6
119.             CALL MOVELIST(A, B, XX(), YY(), NDX)
120.             FOR I = 0 TO NDX STEP 1
121.                 X = XX(I)
122.                 Y = YY(I)
123.                 IF BOARD(Y, X) = 5000 THEN
124.                     PRINT "YOU ARE IN CHECK!"
125.                     PRINT " "
126.                     PRINT " "
127.                     INCHECK = 1
128.                     EXIT FUNCTION
129.                 END IF
130.             NEXT
131.        6 NEXT
132.     NEXT
133.     INCHECK = 0
134. END FUNCTION
135.  
136. SUB IO (A, B, X, Y, RESULT)
137.     DIM XX(0 TO 26), YY(0 TO 26)
138.     CLS
139.     IF A >= 0 THEN
140.         IF RESULT < -2500 THEN
141.             PRINT "I RESIGN"
142.             SLEEP
143.             SYSTEM
144.         END IF
145.         PIECE = BOARD(Y, X)
146.         CALL MAKEMOVE(A, B, X, Y)
147.         IF PIECE <> 0 THEN
148.             PRINT "I TOOK YOUR ";
149.             IF PIECE = 5000 THEN PRINT "KING"
150.         END IF
151.         NULL = INCHECK(0)
152.     END IF
153.     DO
154.         CALL SHOWBD
155.         VIEW PRINT 24 TO 24
156.         LOCATE , 33: INPUT "YOUR MOVE: ", IN$
157.         IF UCASE$(IN$) = "QUIT" THEN CLS: END
158.         IF LEN(IN$) < 4 THEN GOTO 16
159.         B = 8 - (ASC(MID$(IN$, 2, 1)) - 48)
160.         A = ASC(UCASE$(MID$(IN$, 1, 1))) - 65
161.         X = ASC(UCASE$(MID$(IN$, 3, 1))) - 65
162.         Y = 8 - (ASC(MID$(IN$, 4, 1)) - 48)
163.         IF B > 7 OR B < 0 OR A > 7 OR A < 0 OR X > 7 OR X < 0 OR Y > 7 OR Y < 0 THEN GOTO 16
164.         IF BOARD(B, A) <= 0 THEN GOTO 16
165.         IF Y = 2 AND B = 3 AND (X = A - 1 OR X = A + 1) THEN
166.             IF BOARD(B, A) = 100 AND BOARD(Y, X) = 0 AND BOARD(Y + 1, X) = -100 THEN
167.                 IF BESTB(1) = 1 AND BESTA(1) = X THEN
168.                     MOVER = BOARD(B, A)
169.                     TARGET = BOARD(Y, X)
170.                     CALL MAKEMOVE(A, B, X, Y)
171.                     BOARD(Y + 1, X) = 0
172.                     ENPASSANT = -1
173.                     GOTO 15
174.                 END IF
175.             END IF
176.         END IF
177.         CALL MOVELIST(A, B, XX(), YY(), NDX)
178.         FOR K = 0 TO NDX STEP 1
179.             IF X = XX(K) AND Y = YY(K) THEN
180.                 MOVER = BOARD(B, A)
181.                 TARGET = BOARD(Y, X)
182.                 INTFLAG = -1
183.                 CALL MAKEMOVE(A, B, X, Y)
184.                 INTFLAG = 0
185.                15 IF INCHECK(0) = 0 THEN EXIT SUB
186.                 BOARD(B, A) = MOVER
187.                 BOARD(Y, X) = TARGET
188.                 GOTO 16
189.             END IF
190.         NEXT
191.        16 CLS
192.     LOOP
193. END SUB
194.  
195. SUB KING (A, B, XX(), YY(), NDX)
196.     ID = SGN(BOARD(B, A))
197.     FOR DY = -1 TO 1
198.         IF B + DY < 0 OR B + DY > 7 THEN GOTO 12
199.         FOR DX = -1 TO 1
200.             IF A + DX < 0 OR A + DX > 7 THEN GOTO 11
201.             IF ID <> SGN(BOARD(B + DY, A + DX)) THEN
202.                 NDX = NDX + 1
203.                 XX(NDX) = A + DX
204.                 YY(NDX) = B + DY
205.             END IF
206.        11 NEXT
207.    12 NEXT
208. END SUB
209.  
210. SUB MAKEMOVE (A, B, X, Y)
211.     BOARD(Y, X) = BOARD(B, A)
212.     BOARD(B, A) = 0
213. END SUB
214.  
215. SUB MOVELIST (A, B, XX(), YY(), NDX)
216.     PIECE = INT(ABS(BOARD(B, A)))
217.     NDX = -1
218.     IF PIECE = 500 THEN CALL ROOK(A, B, XX(), YY(), NDX) ELSE CALL KING(A, B, XX(), YY(), NDX)
219. END SUB
220.  
221. SUB ROOK (A, B, XX(), YY(), NDX)
222.     ID = SGN(BOARD(B, A))
223.     FOR X = A - 1 TO 0 STEP -1
224.         IF ID <> SGN(BOARD(B, X)) THEN
225.             NDX = NDX + 1
226.             XX(NDX) = X
227.             YY(NDX) = B
228.         END IF
229.         IF (BOARD(B, X)) <> 0 THEN EXIT FOR
230.     NEXT
231.     FOR X = A + 1 TO 7 STEP 1
232.         IF ID <> SGN(BOARD(B, X)) THEN
233.             NDX = NDX + 1
234.             XX(NDX) = X
235.             YY(NDX) = B
236.         END IF
237.         IF (BOARD(B, X)) <> 0 THEN EXIT FOR
238.     NEXT
239.     FOR Y = B - 1 TO 0 STEP -1
240.         IF ID <> SGN(BOARD(Y, A)) THEN
241.             NDX = NDX + 1
242.             XX(NDX) = A
243.             YY(NDX) = Y
244.         END IF
245.         IF (BOARD(Y, A)) <> 0 THEN EXIT FOR
246.     NEXT
247.     FOR Y = B + 1 TO 7 STEP 1
248.         IF ID <> SGN(BOARD(Y, A)) THEN
249.             NDX = NDX + 1
250.             XX(NDX) = A
251.             YY(NDX) = Y
252.         END IF
253.         IF (BOARD(Y, A)) <> 0 THEN EXIT FOR
254.     NEXT
255. END SUB
256.  
257. SUB SHOWBD
258.     VIEW PRINT
259.     LOCATE 3, 30
260.     COLOR 7, 0
261.     PRINT "A  B  C  D  E  F  G  H"
262.     FOR K = 0 TO 25
263.         LOCATE 4, 28 + K
264.         COLOR 6, 0
265.         PRINT CHR$(220)
266.     NEXT
267.     FOR B = 0 TO 7
268.         LOCATE 2 * B + 5, 26
269.         COLOR 7, 0
270.         PRINT CHR$(56 - B)
271.         LOCATE 2 * B + 5, 28
272.         COLOR 6, 0
273.         PRINT CHR$(219)
274.         LOCATE 2 * B + 6, 28
275.         PRINT CHR$(219)
276.         FOR A = 0 TO 7
277.             IF ((A + B) MOD 2) <> 0 THEN
278.                 COLOUR = 2
279.             ELSE COLOUR = 15
280.             END IF
281.             CALL SQUARE(3 * A + 31, 2 * B + 5, COLOUR)
282.         NEXT
283.         LOCATE 2 * B + 5, 53
284.         COLOR 6, 0
285.         PRINT CHR$(219)
286.         LOCATE 2 * B + 6, 53
287.         PRINT CHR$(219)
288.         LOCATE 2 * B + 6, 55
289.         COLOR 7, 0
290.         PRINT CHR$(56 - B)
291.     NEXT
292.     FOR K = 0 TO 25
293.         LOCATE 21, 28 + K
294.         COLOR 6, 0
295.         PRINT CHR$(223)
296.     NEXT
297.     LOCATE 22, 30
298.     COLOR 7, 0
299.     PRINT "A  B  C  D  E  F  G  H"
300.     FOR B = 0 TO 7
301.         FOR A = 0 TO 7
302.             CALL SHOWMAN(A, B, 0)
303.         NEXT
304.     NEXT
305.     COLOR 7, 0
306. END SUB
307.  
308. SUB SHOWMAN (A, B, FLAG)
309.     IF BOARD(B, A) < 0 THEN BACK = 0
310.     IF BOARD(B, A) > 0 THEN BACK = 7
311.     FORE = 7 - BACK + FLAG
312.     IF BOARD(B, A) = 0 THEN
313.         IF ((A + B) MOD 2) <> 0 THEN BACK = 2 ELSE BACK = 15
314.         FORE = BACK + -1 * (FLAG > 0)
315.     END IF
316.     N$ = " "
317.     PIECE = INT(ABS(BOARD(B, A)))
318.     IF PIECE = 0 THEN N$ = CHR$(219)
319.     IF PIECE = 500 THEN N$ = "R"
320.     IF PIECE = 5000 OR PIECE = 7500 THEN N$ = "K"
321.     LOCATE 2 * B + 5 - (BOARD(B, A) > 0), 3 * A + 30
322.     COLOR FORE, BACK
323.     PRINT N$
324.     LOCATE 1, 1
325.     COLOR 7, 0
326. END SUB
327.  
328. SUB SQUARE (A, B, C)
329.     MT$ = CHR$(219)
330.     MT$ = MT$ + MT$ + MT$
331.     LOCATE B, A - 2
332.     COLOR C, C
333.     PRINT MT$
334.     LOCATE B + 1, A - 2
335.     PRINT MT$
336.     COLOR 7, 0
337. END SUB

[bplus]

Yes, this is the way to start real game program:

These 2 things seem imperative
#1 seek a win in next move, if that fails
#2 seek to spoil opponents win in next move

then you start playing for best positions or seeing moves ahead with recursive use of #1 and #2!

I don't think that! is in the sample Chess program that comes with QB64.