chessiter.zip

The MMBasic only version of tscp chess worked on some firmware builds and not others. In fact it wasn't working safely on any build as it was exceeding the size of the C stack and if it worked it was only because the stack check wasn't picking it up and the area of memory the stack was corrupting wasn't critical in that build. In addition there were two serious "Chess" bugs in the code which are now fixed.

1. Pawn attacks missed on the c, e and g files

In attack():
If (i And 7)And(i-9=sq) Then        ' white pawn
If (i And 7)And(i+7=sq) Then        ' black pawn
AND in MMBasic is bitwise, and a comparison gives 1. So the test works out as file And 1, which is only true when the file number is odd: the b, d, f and h files. For a pawn on the c, e or g file (2, 4 and 6) it is 2 And 1 = 0, so the attack is never seen. The line next to each one, ((i And 7)<>7)And(...), does the comparison first and works.

What's missed: a white pawn on c, e or g attacking diagonally left (e4 → d5), and a black pawn on c, e or g attacking diagonally left as White sees the board (e5 → d4). On the board, attack() returned 0 for both of those cases before the fix and 1 after.

Effect on play: attack() is what in_check() and the castling test use. So for those pawns:

Illegal moves accepted. A king could move onto, or stay on, a square one of those pawns attacks, both in the engine's search and in moves you type.
Checks and mates not recognised. A check from such a pawn got no check extension in the search, and a mate given by one was never detected.
Illegal castling allowed. Castling out of such a check, or through a square such a pawn attacks, was permitted.

2. En passant missed onto the c, e and g files
The same mistake appears in four lines in gen and gen_caps: (ep And 7)And(H(x)=LI)And(P(x)=PN). When the en passant square is on the c, e or g file, a capture from the b, d or f file is never generated.

Effect on play: the engine never considered those captures. Typing one gave "Illegal move.", because parse_move only accepts moves that gen produced. On the board, the fixed version generates the capture in both colour tests (24 and 32 moves against 23 and 31).


To solve the stack issue the new code is changed as follows:

The idea
When search called itself, each call stored the caller's state on the interpreter's stack: its locals (alpha, beta, depth, i, …) and where to carry on after the call returned. The loop version keeps that state itself, in four small arrays, so there is one search call however deep the search goes.

The arrays need no stack pointer of their own, because the program already has one: ply. makemove adds 1 to it and takeback subtracts 1, so a node's ply is its depth in the tree. The saved state for ply n goes in element n:


Dim ss_alpha(MAX_PLY),ss_beta(MAX_PLY),ss_depth(MAX_PLY),ss_move(MAX_PLY) 'search stack
TSCP already kept each ply's move list in gd() between first_move(ply) and first_move(ply+1). So the move list was never on the call stack in the first place, only the four values above.

Why four values are enough
alpha, beta, depth, i (the index of the move being searched) are what the parent needs after its child returns, so they have to be saved.
Node type. search with depth 0 just called quiesce at the same ply, and quiesce only ever calls quiesce. So depth=0 is a quiesce node, and its children also get depth 0. No flag is needed.
c (in check) and f (a legal move was found) are only used at the end of a node, when it had no legal moves (f=0). That means the node never searched a child, so nothing has overwritten its c. When a child returns, the parent just sets f=1.
x, j, from, too only hold values for a moment and don't need saving.

How the loop works
search(a,b,d) keeps its name and arguments, so think is unchanged. The body is one loop with three parts.

1. Enter a node. This is the start of the old search or quiesce: count the node, check the timer, set pvl(ply).

A search node (depth > 0) checks for repetition, applies the check extension, then calls gen.
A quiesce node (depth 0) evaluates the position first, and stops at once if that score is already at least beta. Otherwise it calls gen_caps.
A node that ends here (repetition, MAX_PLY, or that early stop in quiesce) sets its value v and goes straight to part 3.
Otherwise it calls sort_pv if needed and sets i=first_move(ply).
2. Try the next move. Find the first move from i on that makemove accepts. If there is one, this replaces the recursive call:

ss_alpha(ply-1)=alpha:ss_beta(ply-1)=beta
ss_depth(ply-1)=depth:ss_move(ply-1)=i
x=alpha:alpha=-beta:beta=-x
If depth Then Inc depth,-1
Exit Do          ' back to part 1, now for the child
makemove has already added 1 to ply, so the parent's state goes in element ply-1. The child's window is (-beta, -alpha) and its depth is one less, as in the old search(-beta,-alpha,depth-1) call. If no moves are left, the node's value is worked out as before: mate or stalemate, the fifty-move rule, or alpha.

3. Return v to the parent. If ply=ply0, this was the root, so the function returns v to think. Otherwise this replaces the old return:

takeback()
x=-v
alpha=ss_alpha(ply):beta=ss_beta(ply)
depth=ss_depth(ply):i=ss_move(ply):f=1
After that comes the same code that used to follow x=-search(...): the history bonus (search nodes only), then either a beta cutoff or a new alpha with the PV copy. A beta cutoff makes the parent finish with beta, so part 3 runs again one level up. Otherwise i goes up by 1 and part 2 carries on with the parent's next move.

How the old code maps to the new
Recursive version Loop version
x=-search(-beta,-alpha,depth-1) save 4 values at ply-1, swap and negate the window, depth-1, enter the child
a call's own LOCALs that ply's elements of the ss_ arrays
search=quiesce(alpha,beta) the same node carries on as a quiesce node (depth=0)
quiesce=beta:exitF=1:Exit For v=beta:done=1, then return to the parent
return to the caller takeback, restore the 4 values, x=-v
timer stop: every level returns without takeback Exit Function at once
On a timer stop, the board is left with moves still made in both versions. think already handled that with its Do: If ply=0 Then Exit: takeback(): Loop, so it needed no change.

What it gains
Stack: the deepest chain is now 7 calls at any ply: main → bench → think → search → makemove → in_check → attack. gen → gen_push → gen_promote and eval_ → eval_light_king → eval_lkp are the same length. The recursive version needed about 24 at ply 16. The arrays take 4 × 17 integers, 544 bytes of heap.
No recursion inside loops. The loops left in search (the Do While over the moves and the For j that copies the PV) never call search, so the program stays within what your manual supports. That is why it gives the right answers under V7 with compile on, where the recursive version doesn't.
Speed: each node used to cost a FUNCTION call with 3 arguments and about 10 LOCALs created and freed. Now it is 4 array writes going down and 4 reads coming back. At depth 1 on 6.02.01 the loop version was 4% faster: 3,693 ms against 3,846 ms.

Edited 2026-10-04 19:49 by matherp

---

  matherp said  

chessiter.zip

The MMBasic only version of tscp chess worked on some firmware builds and not others. In fact it wasn't working safely on any build as it was exceeding the size of the C stack and if it worked it was only because the stack check wasn't picking it up and the area of memory the stack was corrupting wasn't critical in that build. In addition there were two serious "Chess" bugs in the code which are now fixed.

I have a PicoCalc with LCD display. I deleted the MODE 2 instruction. Now on line 1050 I get

Error : Not available on physical display

What kind of display is SPRITE LOADBMP used on?

For a non VGA/HDMI build you need to create a framebuffer and point all the writes to it. Then do a framebuffer copy at the appropriate points in the code

@toml_12953
Please post the program adapted for PicoCalc here.
A chess program for the PicoCalc would be great.

Just to mention:

On RP2040 VGA design 2, it does not run on V7.00.00rc3 (out of memory), but works on rc5. But it is abismal slow compared to compiled TSCP.
Compiled TSCP plays a full game against itself in less time this version calculates 1 move for 1 player.

Volhout
Edited 2026-10-05 16:58 by Volhout

This version should run on any lcd based system as well as VGA and HDMI

TSCPChess.zip

As Volhout says the version with a coprocessor is MUCH better. I just sorted this one out because it was raised as not working and analysis showed it should never have worked.
I'm going to try mmb2csub to convert the hot routines and see if that can handle it.
Edited 2026-10-05 17:26 by matherp

This version should work on all builds and now uses a csub for the engine.
It is only 210x faster though on the RP2040 and 47x faster than the compiled RP2350 version
The csub was automatically created using the mmb2csub python script in the release, note this includes a small bug fix that converting the chess program identified. There was some small code refactoring needed as global variables were defined inside functions which breaks the converter model

chessiter.zip
Edited 2026-10-05 18:30 by matherp

Hi Peter,
I've tried out your new iterative chess and it looks good. Personally I think the speed of the CSub version is now such that it gives a playable game, the Benchmark used to take at least half an hour, for a cut back ply depth, your CSub version now does the whole benchmark PLY 16 in 60 Seconds, not quite up to Compiled C at 15 Seconds, but definately playable.
I have one question, was the bug you found to do with the Pawn attack in c,e & g also a bug in the original C code? because the Bench now gives slightly different results to the results that your Compiled C version gave and the Fuzix Compiled Basic version, which was also giving the same results as the Compiled C.
If you look at your results for compiled C and look at the number of nodes searched for PLY 4 and PLY 5 In C it's 141367 and 550778, but now the CSub version gives 141331 and 550727, not much of a difference I know, and the end result of the move selected is the same, but different from the "Master"
Regards Kevin.

I haven't checked but I don't think it is likely it was in the C version. The issue was specific to how MMbasic does the AND logical

Ok, well maybe your new iterative version is slightly more efficient then?
Anyway it seems to play a decent game in a much more reasonable amount of time, it's now even faster then the fully compiled Fuzix conversion which was taking just over 2 minutes to run the full bench, so you must have been able to optimise the compiler quite significantly since the last version of Fuzix.
Thanks for all these fantastic improvements.
Regards Kevin.

Found the issue, the Basic was running a slightly different version of tscp. Try the attached which is also 19% faster as I changed the optimisation of the compiler

chessiter.zip