Author Topic: Chess Programming Tutorial  (Read 13372 times)

0 Members and 1 Guest are viewing this topic.

Offline romichess

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

Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial
« Reply #31 on: March 26, 2020, 03:40:47 am »
Okay, because of Steve we may be back in business. The code in temp/main.txt can be swapped with actual C/C++ source code of my choosing. If that is the case I'll just create my own jump tables. Once I have an index. I'll just insert code like this.

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

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

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

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

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

movegen[index](from_square);

I wonder if it will really be that simple?
My name is Michael, but you can call me Mike :)

FellippeHeitor

  • Guest
Re: Chess Programming Tutorial
« Reply #32 on: March 26, 2020, 08:30:53 am »
No problem mixing your languages, of course. But this:

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

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

Offline romichess

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

Offline TerryRitchie

  • Seasoned Forum Regular
  • Posts: 495
  • Semper Fidelis
    • View Profile
Re: Chess Programming Tutorial
« Reply #34 on: March 26, 2020, 03:48:53 pm »
I've played some pretty quick and impressive chess games in GWBASIC back in the day on 8088 hardware. I'm sure QB64 is up to the task. Give it a try.
In order to understand recursion, one must first understand recursion.

Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial
« Reply #35 on: March 26, 2020, 04:27:24 pm »
I've played some pretty quick and impressive chess games in GWBASIC back in the day on 8088 hardware. I'm sure QB64 is up to the task. Give it a try.

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

Okay, so I need to temper-down my opinion as to what a chess engine needs to be to the people here that might be interested. I can try to do that.
My name is Michael, but you can call me Mike :)

Marked as best answer by romichess on March 26, 2020, 01:23:44 pm

Offline SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3972
    • View Profile
    • Steve’s QB64 Archive Forum
Re: Chess Programming Tutorial
« Reply #36 on: March 26, 2020, 04:52:47 pm »
Move generation, captures only generation, make move and unmake move all benefit greatly from jump tables. There are 12 cases just for the pawn. We can get to the correct pawn code by one jump that is not conditional or we can get there by IF IF IF IF IF IF IF IF IF IF IF IF until we find the correct one. The problem in chess is it is constantly in flux and predicting the outcome of any if statement tends toward 50/50 and false branch predictions drags down performance tremendously. If ones goal was to write a correct but intolerably slow chess engine then it does not matter. But in this tutorial my code does not make sense because it is counter productive to the goal of writing a fast chess engine. If statements are just not good for performance in a chess engine.

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

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

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



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

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

I think those tend to be 1 to 1 jump style lists.
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial
« Reply #37 on: March 26, 2020, 05:23:34 pm »
You could get there with 12 IF statements, if you were a complete beginner at data interpretation.  Simply by breaking those statements into binary values, you easily reduce the maximum number of comparisons down to 4.

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

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



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

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

I think those tend to be 1 to 1 jump style lists.
Yes, of course hand crafted If blocks can be optimised. In my code though I'm using SELECT CASE because I just assumed that QB64 would write an equivalent C switch statement. I'm new to QB variant basic. The ON...GOTO statement might be the answer. I'll check it out. Thanks!
My name is Michael, but you can call me Mike :)

Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial
« Reply #38 on: March 26, 2020, 07:38:10 pm »
ON GOSUB is cleaner than ON GOTO. And it is even cleaner than SELECT CASE, switch() or C's jumptables. C makes one create full functions and they are outside of the calling function. Here the code is embedded in the same sub from which they are called. Very nice! And I'm not going to look at main.txt because if I do and QB64 does something jenky then I'll just get upset again, lol. Here is just the structure of the new Generate_Moves sub without the piece code so one can easily see the structure. And I did change the constants to start at 1 rather than 0 so they would work correctly with ON GOSUB.

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

Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial
« Reply #39 on: April 12, 2020, 07:40:44 pm »
I have not abandoned this project. It is just that I do not think in basic as easily as I think in C. So I have been writing a chess engine in C that I then will translate into basic. It is going wonderfly! And it will not be a traditional engine by any comparison. It might even be paradigm changing! My engine RomiChess was "famous" for its learning algorithm. But that was end of game learning where it stores every game it plays (or imported games) into a learn file with reinforcement learning values. The new engine will learn in real time during a game. Also it will not have a traditional evaluation function. Instead it will collect statistics from the search that it will analyze to select a move to play. Both of the above is why it will be (fingers crossed) a paradigm changer. Wish me luck. :)   
My name is Michael, but you can call me Mike :)

Offline romichess

  • Forum Regular
  • Posts: 145
    • View Profile
Re: Chess Programming Tutorial
« Reply #40 on: April 12, 2020, 08:37:08 pm »
When I want to code something in basic like I would in C I have to stop what I am doing, research if basic has an equivalent, understand the syntax, learn the syntax, remember the syntax and then try to make it work. In C I just know how.

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

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

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

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

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

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

 
   
« Last Edit: April 12, 2020, 08:56:53 pm by romichess »
My name is Michael, but you can call me Mike :)

Offline Adrian

  • Newbie
  • Posts: 39
    • View Profile
Re: Chess Programming Tutorial
« Reply #41 on: January 04, 2021, 09:58:10 am »
Excellent tutorial Mike, thanks!