Chess Programming Tutorial

[romichess]

Well I got my answer about the SELECT CASE statement and how QB64 handles it. It just converts SELECT CASE to a series of IF statements. And there is no point continuing this tutorial on blazingly fast chess coding in a language that is incapable of it. It would be illusionary at best and even ((very)much) slower than carefully handcrafted IF statement blocks at worst. What would be the point of continuing? It would be disasterly slow when done. It would be better just to rewrite everything using IF statements and I can't do that, lol. However, the 120 cell board is a valuable idea and doubly linked piece list are a big performance boost especially in an endgame with few pieces left on the board.  My EarlyWork.zip file will demonstrate the power of the programming techniques in this tutorial. Sorry, they are in C and even assembler but there is an exe for each. On my i7-3930k the Godzilla example generates and makes/unmakes 65 million moves per second just using one thread. In 1.86 seconds it traverses from the original starting position all possible moves to 6 moves deep. Carnivor is an actual working chess engine that will run in the windows console. Time per move is set by st 30 for 30 seconds or sd 9 for nine moves deep. Moves are entered like e2e4 or e7e8q for queening or e1g1 for king side castling. Etc. Any Questions? Just ask!

EarlyWork.zip

[romichess]

Okay, because of Steve we may be back in business. The code in temp/main.txt can be swapped with actual C/C++ source code of my choosing. If that is the case I'll just create my own jump tables. Once I have an index. I'll just insert code like this.

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

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

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

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

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

movegen[index](from_square);

I wonder if it will really be that simple?

[FellippeHeitor]

No problem mixing your languages, of course. But this:

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

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

[romichess]

No problem mixing your languages, of course. But this:

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

Move generation, captures only generation, make move and unmake move all benefit greatly from jump tables. There are 12 cases just for the pawn. We can get to the correct pawn code by one jump that is not conditional or we can get there by IF IF IF IF IF IF IF IF IF IF IF IF until we find the correct one. The problem in chess is it is constantly in flux and predicting the outcome of any if statement tends toward 50/50 and false branch predictions drags down performance tremendously. If ones goal was to write a correct but intolerably slow chess engine then it does not matter. But in this tutorial my code does not make sense because it is counter productive to the goal of writing a fast chess engine. If statements are just not good for performance in a chess engine.

[TerryRitchie]

I've played some pretty quick and impressive chess games in GWBASIC back in the day on 8088 hardware. I'm sure QB64 is up to the task. Give it a try.

[romichess]

I've played some pretty quick and impressive chess games in GWBASIC back in the day on 8088 hardware. I'm sure QB64 is up to the task. Give it a try.

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

Okay, so I need to temper-down my opinion as to what a chess engine needs to be to the people here that might be interested. I can try to do that.

[SMcNeill]

Move generation, captures only generation, make move and unmake move all benefit greatly from jump tables. There are 12 cases just for the pawn. We can get to the correct pawn code by one jump that is not conditional or we can get there by IF IF IF IF IF IF IF IF IF IF IF IF until we find the correct one. The problem in chess is it is constantly in flux and predicting the outcome of any if statement tends toward 50/50 and false branch predictions drags down performance tremendously. If ones goal was to write a correct but intolerably slow chess engine then it does not matter. But in this tutorial my code does not make sense because it is counter productive to the goal of writing a fast chess engine. If statements are just not good for performance in a chess engine.

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

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

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


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

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

I think those tend to be 1 to 1 jump style lists.

[romichess]

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

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

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


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

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

I think those tend to be 1 to 1 jump style lists.

Yes, of course hand crafted If blocks can be optimised. In my code though I'm using SELECT CASE because I just assumed that QB64 would write an equivalent C switch statement. I'm new to QB variant basic. The ON...GOTO statement might be the answer. I'll check it out. Thanks!

[romichess]

ON GOSUB is cleaner than ON GOTO. And it is even cleaner than SELECT CASE, switch() or C's jumptables. C makes one create full functions and they are outside of the calling function. Here the code is embedded in the same sub from which they are called. Very nice! And I'm not going to look at main.txt because if I do and QB64 does something jenky then I'll just get upset again, lol. Here is just the structure of the new Generate_Moves sub without the piece code so one can easily see the structure. And I did change the constants to start at 1 rather than 0 so they would work correctly with ON GOSUB.

Code: QB64: [Select]

1. SUB Generate_Moves
2.     piece_index = piece(start_index(wtm)).nxt
3.     DO
4.         from_square = piece(piece_index).squ
5.         ON piece(piece_index).typ GOSUB WP, WN, WB, WR, WQ, WC, WK, BP, BN, BB, BR, BQ, BC, BK, TR
6.         piece_index = piece(piece_index).nxt
7.     LOOP
8.     EXIT SUB
9.     WP:
10.     ON white_pawns(from_square) GOSUB WX2R, WL2R, WL2X, WX1R, WL1R, WL1X, WXER, WLER, WLEX, WXPR, WLPR, WLPX
11.     END
12.  
13.     WX2R:
14.  
15.     END
16.  
17.     WL2R:
18.  
19.     END
20.  
21.     WL2X:
22.  
23.     END
24.  
25.     WX1R:
26.  
27.     END
28.  
29.     WL1R:
30.  
31.     END
32.  
33.     WL1X:
34.  
35.     END
36.  
37.     WXER:
38.  
39.     END
40.  
41.     WLER:
42.  
43.     END
44.  
45.     WLEX:
46.  
47.     END
48.  
49.     WXPR:
50.  
51.     END
52.  
53.     WLPR:
54.  
55.     END
56.  
57.     WLPX:
58.  
59.     END
60.  
61.     WN:
62.  
63.     END
64.  
65.     WB:
66.  
67.     END
68.  
69.     WR:
70.  
71.     END
72.  
73.     WQ:
74.  
75.     END
76.  
77.     WC:
78.  
79.     END
80.  
81.     WK:
82.  
83.     END
84.  
85.     BP:
86.     ON black_pawns(from_square) GOSUB BX2R, BL2R, BL2X, BX1R, BL1R, BL1X, BXER, BLER, BLEX, BXPR, BLPR, BLPX
87.     END
88.  
89.     BX2R:
90.  
91.     END
92.  
93.     BL2R:
94.  
95.     END
96.  
97.     BL2X:
98.  
99.     END
100.  
101.     BX1R:
102.  
103.     END
104.  
105.     BL1R:
106.  
107.     END
108.  
109.     BL1X:
110.  
111.     END
112.  
113.     BXER:
114.  
115.     END
116.  
117.     BLER:
118.  
119.     END
120.  
121.     BLEX:
122.  
123.     END
124.  
125.     BXPR:
126.  
127.     END
128.  
129.     BLPR:
130.  
131.     END
132.  
133.     BLPX:
134.  
135.     END
136.  
137.     BN:
138.  
139.     END
140.  
141.     BB:
142.  
143.     END
144.  
145.     BR:
146.  
147.     END
148.  
149.     BQ:
150.  
151.     END
152.  
153.     BC:
154.  
155.     END
156.  
157.     BK:
158.  
159.     END
160.  
161.     TR:
162.     EXIT SUB
163.     END
164.  
165. END SUB

[romichess]

I have not abandoned this project. It is just that I do not think in basic as easily as I think in C. So I have been writing a chess engine in C that I then will translate into basic. It is going wonderfly! And it will not be a traditional engine by any comparison. It might even be paradigm changing! My engine RomiChess was "famous" for its learning algorithm. But that was end of game learning where it stores every game it plays (or imported games) into a learn file with reinforcement learning values. The new engine will learn in real time during a game. Also it will not have a traditional evaluation function. Instead it will collect statistics from the search that it will analyze to select a move to play. Both of the above is why it will be (fingers crossed) a paradigm changer. Wish me luck. :)   

[romichess]

When I want to code something in basic like I would in C I have to stop what I am doing, research if basic has an equivalent, understand the syntax, learn the syntax, remember the syntax and then try to make it work. In C I just know how.

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

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

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

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

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

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

 
   

[Adrian]

Excellent tutorial Mike, thanks!