 Notice. New forum software under development. It's going to miss a few functions and look a bit ugly for a while, but I'm working on it full time now as the old forum was too unstable. Couple days, all good. If you notice any issues, please contact me. |
Forum Index : Microcontroller and PC projects : TSCP chess program updated
| Author | Message | ||||
| matherp Guru  Joined: 11/12/2012 Location: United KingdomPosts: 11937 |
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 |
||||
| toml_12953 Guru Joined: 13/02/2015 Location: United StatesPosts: 726 |
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? |
||||
| matherp Guru Joined: 11/12/2012 Location: United KingdomPosts: 11937 |
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 |
||||
 Print this page |
 |
The Back Shed's forum code is written, and hosted, in Australia. | © JAQ Software 2026 |
