CONFIG // -------------------------------------------------- // Display Configuration // ST7703 LCD panel (720x720) connected via MIPI-DSI // -------------------------------------------------- DISPLAY_DRIVER ST7703 DISPLAY_BUS DSI DISPLAY_W 720 DISPLAY_H 720 DISPLAY_RST 27 // Display hardware reset pin DISPLAY_BL 26 // Backlight control pin // -------------------------------------------------- // I2C Bus Configuration // Shared I2C bus for touch controller and audio codec // -------------------------------------------------- I2C0_SDA 7 I2C0_SCL 8 I2C0_FREQ 400000 // -------------------------------------------------- // Touch Screen Configuration // GT911 capacitive touch controller // -------------------------------------------------- TOUCH_DRIVER GT911 TOUCH_I2C 0 TOUCH_RST 46 // Touch controller reset pin TOUCH_ADDR 0x5D // I2C device address // -------------------------------------------------- // Audio Codec Configuration // ES8311 audio codec // -------------------------------------------------- CODEC ES8311 CODEC_ADDR 0x18 CODEC_I2C 0 CODEC_I2S 0 // Speaker amplifier control CODEC_PA_PIN 53 CODEC_PA_ACTIVE_LOW 0 // -------------------------------------------------- // I2S Audio Interface Configuration // -------------------------------------------------- I2S_MCLK 13 I2S_BCLK 12 I2S_WS 10 I2S_DOUT 9 I2S_DIN 11 AUDIO_OUT CODEC AUDIO_IN CODEC // -------------------------------------------------- // MicroSD Card Configuration // -------------------------------------------------- SDMMC_WIDTH 4 SDMMC_CLK 43 SDMMC_CMD 44 SDMMC_D0 39 SDMMC_D1 40 SDMMC_D2 41 SDMMC_D3 42 END_CONFIG DISPLAY_INIT() // Canvas covers the WHOLE panel. Otherwise output takes the most expensive // path: a canvas smaller than the panel is composed through LVGL with a full // frame copy, and that gave 2 frames per second. With 90-degree rotation the // logical size is 1280x800. DISPLAY_INIT_CANVAS(0, 0, 1280, 800) // ---------- CONSTANTS ---------- CONST OFF = 40 // board offset from the left CONST BOFF = 80 // board offset from the top (score panel above it) CONST CELL = 80 // cell size CONST HALF = 40 // middle of a cell // Search depth in plies. Even on purpose: an odd depth ends on our own move, // the evaluation comes out optimistic, and in the model five plies LOSE to // four (12:5). CONST SDEPTH = 4 CONST QMAX = 6 // max extension on captures CONST MAXLV = 12 // search state levels CONST TBUDGET = 2000 // ms per move — a safety net, not the norm // Node budget for ONE capture-chain length count. A plain man has a huge // margin (its chains cost tens of nodes), so for it the count is exact. A // flying king can land on several squares after a capture, each one its own // continuation, and the tree grows exponentially: without a cap a single call // ate five thousand nodes and over a million statements. CONST CHBUD = 60 // ---------- VARIABLES ---------- // board: 0 empty, 1 player man, 2 player king, 3 AI man, 4 AI king VAR BRD[64] VAR DR[4] = {-1, -1, 1, 1} VAR DC[4] = {-1, 1, -1, 1} VAR SH, SA VAR sel, mustcap VAR tprev VAR gameov, winner VAR tx, ty VAR qr, qc, qi, qp, qx, qy VAR tr, tc, ti VAR pmove VAR msg$ // TRY_MOVE: in mfr,mfc,mtr,mtc ; out mok, mcap, mcidx VAR mfr, mfc, mtr, mtc, mok, mcap, mcidx, hchl VAR mdr, mdc, msr, msc, mdist, mpiece, mstep VAR mown, mnen, menr, menc, mrr, mcc, mpp // CANCAP: in kr,kc ; out kcan VAR kr, kc, kcan, kpiece, kd, kstep, krr, kcc, kpp, kfound, kdone // DRAW_CELL: in dcr,dcc VAR dcr, dcc, dcx, dcy, dcp, selcol // ANIM: in afr,afc,atr,atc,apiece VAR afr, afc, atr, atc, apiece VAR astep, asteps, anmx, anmy, acr, acc, arr, acc2, adx, ady // AI VAR naf, cpos, aidone, ai_r, ai_c, ai_i, ai_p, ai_j, ai_k // Move generator: works on board GB, puts the result into G*. VAR GB[64], GF[24], GT[24], GC[24], GX[24], GS[24] VAR gside, gn, gi, gj, gp, grw, gcol, gking, gdir, gstep VAR grr, gcc, gq, gstop, gfnd, gvic, gok, gown, gkeep, gdst, gcapn, gq2 VAR mustbeat, needchl, chl, bestchl VAR CHL[24] // Capture-chain counting. Recursion via GOSUB, state is split by depth: // six levels is more than enough. VAR CBD[64], CLT[48], CLV[48], CLN[6], CLI[6], CBS[6], CSQ[6] // What to undo at each level: from, to, who was captured and what they // were. A nested call overwrites shared variables, so this is per level. VAR CUF[6], CUT[6], CUV[6], CUP[6], CUQ[6] VAR ccd, cres, cbi, cto, cvi, cpc, cpp, cpr, cpc2, cpk, cme VAR asq, achain, aguard VAR cfrm, cvq, cbud VAR cdir, cstp, cfn, cvc, csp, crr, ccc, cq, cown // Search levels: our moves -> player replies -> our replies. // Search state is split by level: a nested call overwrites everything // shared, so each level has its own board and its own move list. VAR SB[832] VAR MF[312], MT[312], MC[312], MX[312], MS[312] VAR SD[13], SAL[13], SBE[13], SBV[13], SI[13], SN[13], SSD[13], SQ[13] VAR KF[13], KT[13] VAR sd, sval, sgi, sj, scap, sleaf, sfrom, sto, spc, sbest, sbv2, snow VAR chlv, chsq, tstart // Time spent on the search itself over the whole move — including // finishing the chain, but without pauses and animation. VAR amv0, asum, aims VAR P1F[24], P1T[24], P1C[24], P1X[24], P1S[24] VAR n1, i1, bi, bsv, pick, pickv // Scratch board for evaluating AI moves and evaluation variables. VAR TB[64] VAR ev, evi, evp, evr, evc, evv, eva, evb, evq VAR csc, bsc VAR af_, at_, acm_, acx_ TIMER_RESET GOSUB NEW_GAME WHILE 1 IF TOUCH_PRESSED = 1 AND tprev = 0 THEN tx = TOUCH_X ty = TOUCH_Y GOSUB ON_TOUCH ENDIF tprev = TOUCH_PRESSED PAUSE 20 WEND END // ================== NEW GAME ================== NEW_GAME: FOR qi = 0 TO 63 BRD[qi] = 0 NEXT FOR qr = 0 TO 2 FOR qc = 0 TO 7 IF (qr + qc) % 2 = 1 THEN BRD[qr * 8 + qc] = 3 NEXT NEXT FOR qr = 5 TO 7 FOR qc = 0 TO 7 IF (qr + qc) % 2 = 1 THEN BRD[qr * 8 + qc] = 1 NEXT NEXT sel = -1 mustcap = 0 gameov = 0 SH = 0 SA = 0 SCREEN_COLOR(#202020) GOSUB CHKBEAT GOSUB DRAW_BOARD RETURN // ================== TOUCH HANDLING ================== ON_TOUCH: IF gameov = 1 THEN GOSUB NEW_GAME RETURN ENDIF GOSUB CHKBEAT tc = FLOOR((tx - OFF) / CELL) tr = FLOOR((ty - BOFF) / CELL) IF tc < 0 OR tc > 7 OR tr < 0 OR tr > 7 THEN RETURN ti = tr * 8 + tc IF sel = -1 THEN IF BRD[ti] = 1 OR BRD[ti] = 2 THEN sel = ti GOSUB DRAW_BOARD ENDIF RETURN ENDIF // Touching the selected piece again deselects it — but not in the middle of // a capture chain: there the piece must finish, and it is too late to cancel. IF ti = sel AND mustcap = 0 THEN sel = -1 GOSUB DRAW_BOARD RETURN ENDIF mfr = FLOOR(sel / 8) mfc = sel % 8 mtr = tr mtc = tc GOSUB TRY_MOVE // If capturing is mandatory, the move must be a capture AND start a chain // of maximum length. hchl = 0 IF mcap = 1 THEN GOSUB HUMCHL IF mok = 1 AND (mustcap = 0 OR mcap = 1) AND (mustbeat = 0 OR mcap = 1) AND (mustbeat = 0 OR hchl = needchl) THEN pmove = BRD[sel] // Clear the selection BEFORE the animation: otherwise DRAW_CELL draws the // ring on the now empty cell and it stays there until the end of the move. sel = -1 // Animation: the piece slides across the board, only then the board changes. afr = mfr afc = mfc atr = mtr atc = mtc apiece = pmove GOSUB ANIM BRD[mfr * 8 + mfc] = 0 BRD[ti] = pmove IF mcap = 1 THEN BRD[mcidx] = 0 SH = SH + 1 ENDIF // Promotion to king — only on the last rank IF pmove = 1 AND mtr = 0 THEN BRD[ti] = 2 mustcap = 0 // Capture chain: if the same piece can capture again, the move continues // with it. Checked AFTER removing the captured piece and after promotion — // a king captures differently, and the chain may go another way. IF mcap = 1 THEN kr = mtr kc = mtc GOSUB CANCAP IF kcan = 1 THEN sel = ti mustcap = 1 ENDIF ENDIF GOSUB DRAW_BOARD IF mustcap = 0 THEN GOSUB CHECK_END IF gameov = 0 THEN GOSUB AI_MOVE GOSUB CHKBEAT GOSUB DRAW_BOARD GOSUB CHECK_END ENDIF ENDIF ELSE // Not a move — maybe another own piece was selected. Switching is not // allowed during a capture chain. IF mustcap = 0 AND (BRD[ti] = 1 OR BRD[ti] = 2) THEN sel = ti GOSUB DRAW_BOARD ENDIF ENDIF RETURN // ================== MOVE CHECK ================== // In: mfr, mfc (from), mtr, mtc (to). Out: mok, mcap, mcidx. // One subroutine for men and kings, for the player and for the AI. TRY_MOVE: mok = 0 mcap = 0 mcidx = -1 mdr = mtr - mfr mdc = mtc - mfc IF ABS(mdr) <> ABS(mdc) THEN RETURN IF mdr = 0 THEN RETURN IF BRD[mtr * 8 + mtc] <> 0 THEN RETURN mpiece = BRD[mfr * 8 + mfc] IF mpiece = 0 THEN RETURN msr = 1 IF mdr < 0 THEN msr = -1 msc = 1 IF mdc < 0 THEN msc = -1 mdist = ABS(mdr) // Count what lies between the start and the end of the move. mown = 0 mnen = 0 menr = -1 menc = -1 FOR mstep = 1 TO mdist - 1 mrr = mfr + msr * mstep mcc = mfc + msc * mstep mpp = BRD[mrr * 8 + mcc] IF mpiece = 1 OR mpiece = 2 THEN IF mpp = 1 OR mpp = 2 THEN mown = mown + 1 IF mpp = 3 OR mpp = 4 THEN mnen = mnen + 1 IF mpp = 3 OR mpp = 4 THEN menr = mrr IF mpp = 3 OR mpp = 4 THEN menc = mcc ELSE IF mpp = 3 OR mpp = 4 THEN mown = mown + 1 IF mpp = 1 OR mpp = 2 THEN mnen = mnen + 1 IF mpp = 1 OR mpp = 2 THEN menr = mrr IF mpp = 1 OR mpp = 2 THEN menc = mcc ENDIF NEXT // Own piece in the way or more than one enemy piece — no move. IF mown > 0 THEN RETURN IF mnen > 1 THEN RETURN IF mpiece = 2 OR mpiece = 4 THEN // A KING flies along the diagonal any distance: empty path — a plain // move, exactly one enemy piece on the path — a capture landing behind it. IF mnen = 0 THEN mok = 1 IF mnen = 1 THEN mok = 1 IF mnen = 1 THEN mcap = 1 IF mnen = 1 THEN mcidx = menr * 8 + menc ELSE // Plain man: steps forward only, captures over one piece in any direction. IF mdist = 1 AND mnen = 0 AND mpiece = 1 AND mtr < mfr THEN mok = 1 IF mdist = 1 AND mnen = 0 AND mpiece = 3 AND mtr > mfr THEN mok = 1 IF mdist = 2 AND mnen = 1 THEN mok = 1 IF mdist = 2 AND mnen = 1 THEN mcap = 1 IF mdist = 2 AND mnen = 1 THEN mcidx = menr * 8 + menc ENDIF RETURN // ---- chain length of the capture chosen by the player ---- HUMCHL: cbud = CHBUD cbi = 0 WHILE cbi < 64 CBD[cbi] = BRD[cbi] cbi = cbi + 1 WEND cpc = CBD[sel] CBD[sel] = 0 CBD[mcidx] = 0 CBD[ti] = cpc IF cpc = 1 AND mtr = 0 THEN CBD[ti] = 2 ccd = 0 CSQ[0] = ti GOSUB CHAINCNT hchl = cres + 1 RETURN // ================== CAN THE PIECE CAPTURE ================== // In: kr, kc. Out: kcan. Works for both men and kings. CANCAP: kcan = 0 kpiece = BRD[kr * 8 + kc] IF kpiece = 0 THEN RETURN FOR kd = 0 TO 3 kstep = 1 kfound = 0 kdone = 0 WHILE kdone = 0 krr = kr + DR[kd] * kstep kcc = kc + DC[kd] * kstep IF krr < 0 OR krr > 7 OR kcc < 0 OR kcc > 7 THEN kdone = 1 IF kdone = 0 THEN kpp = BRD[krr * 8 + kcc] IF kfound = 0 THEN // Still looking for a victim. Own piece — dead end. Empty // square: a king flies on, a plain man stops here. IF kpiece = 1 OR kpiece = 2 THEN IF kpp = 1 OR kpp = 2 THEN kdone = 1 IF kpp = 3 OR kpp = 4 THEN kfound = 1 ELSE IF kpp = 3 OR kpp = 4 THEN kdone = 1 IF kpp = 1 OR kpp = 2 THEN kfound = 1 ENDIF IF kpp = 0 AND kpiece <> 2 AND kpiece <> 4 THEN kdone = 1 ELSE // Victim found — an empty square is needed behind it. IF kpp = 0 THEN kcan = 1 kdone = 1 ENDIF ENDIF kstep = kstep + 1 IF kstep > 8 THEN kdone = 1 WEND NEXT RETURN // ================== MOVE ANIMATION ================== // In: afr, afc -> atr, atc, piece apiece. // Instead of the whole board, only the 3x3 cells around the previous // position are redrawn — a radius-30 circle in an 80 cell never leaves them. ANIM: asteps = 14 adx = (atc - afc) * CELL ady = (atr - afr) * CELL // Remove the piece from the start cell so it doesn't appear twice. BRD[afr * 8 + afc] = 0 dcr = afr dcc = afc GOSUB DRAW_CELL anmx = OFF + afc * CELL anmy = BOFF + afr * CELL FOR astep = 1 TO asteps // Restore the cells under the previous position acr = FLOOR((anmy + HALF - BOFF) / CELL) acc = FLOOR((anmx + HALF - OFF) / CELL) FOR arr = acr - 1 TO acr + 1 FOR acc2 = acc - 1 TO acc + 1 dcr = arr dcc = acc2 GOSUB DRAW_CELL NEXT NEXT anmx = OFF + afc * CELL + adx * astep / asteps anmy = BOFF + afr * CELL + ady * astep / asteps IF apiece = 1 OR apiece = 2 THEN DISPLAY_FILL_CIRCLE(anmx + HALF, anmy + HALF, 30, #FAFAFA) IF apiece = 3 OR apiece = 4 THEN DISPLAY_FILL_CIRCLE(anmx + HALF, anmy + HALF, 30, #1A1A1A) IF apiece = 2 OR apiece = 4 THEN DISPLAY_FILL_CIRCLE(anmx + HALF, anmy + HALF, 12, #FFD700) DISPLAY_UPDATE PAUSE 16 NEXT // Put the piece back — the caller will place it at its destination. BRD[afr * 8 + afc] = apiece RETURN // ================== ONE CELL ================== DRAW_CELL: IF dcr < 0 OR dcr > 7 OR dcc < 0 OR dcc > 7 THEN RETURN dcx = OFF + dcc * CELL dcy = BOFF + dcr * CELL IF (dcr + dcc) % 2 = 0 THEN DISPLAY_FILL_RECT(dcx, dcy, CELL, CELL, #F0D9B5) IF (dcr + dcc) % 2 = 1 THEN DISPLAY_FILL_RECT(dcx, dcy, CELL, CELL, #8B5A2B) dcp = BRD[dcr * 8 + dcc] IF dcp = 1 OR dcp = 2 THEN DISPLAY_FILL_CIRCLE(dcx + HALF, dcy + HALF, 30, #FAFAFA) IF dcp = 3 OR dcp = 4 THEN DISPLAY_FILL_CIRCLE(dcx + HALF, dcy + HALF, 30, #1A1A1A) IF dcp = 2 OR dcp = 4 THEN DISPLAY_FILL_CIRCLE(dcx + HALF, dcy + HALF, 12, #FFD700) // Selection ring — three circles in a row. The fifth (thickness) argument // of DISPLAY_CIRCLE is currently parsed as an arc, so we stick to four. // During a capture chain the ring is ORANGE: it shows at once that the // move is not finished and this same piece must keep capturing. selcol = #4CAF50 IF mustcap = 1 THEN selcol = #FF9800 IF dcr * 8 + dcc = sel THEN DISPLAY_CIRCLE(dcx + HALF, dcy + HALF, 34, selcol) IF dcr * 8 + dcc = sel THEN DISPLAY_CIRCLE(dcx + HALF, dcy + HALF, 33, selcol) IF dcr * 8 + dcc = sel THEN DISPLAY_CIRCLE(dcx + HALF, dcy + HALF, 32, selcol) RETURN // ================== AI MOVE ================== // Alpha-beta to SDEPTH plies, FULL width, with capture extensions. // // The previous search looked at the same four plies but cut the width: of // the player's replies it kept only the eight best by the generator's quick // score. The trouble is that the refutation a human uses to break the game is // usually a quiet move this score doesn't like, so it never makes the top // eight. Self-play doesn't reveal that hole: both sides are equally blind. // // Alpha-beta doesn't throw moves away. It cuts branches ALREADY proven to be // no better than what was found, and for the same cost covers the full width. // In the model — 14:5:5 against the previous search at slightly lower cost. AI_MOVE: PAUSE 300 cpos = -1 aidone = 0 asum = 0 WHILE aidone = 0 tstart = TIMER_GET FOR gi = 0 TO 63 GB[gi] = BRD[gi] NEXT gside = 3 GOSUB GEN IF gn > 0 AND GC[0] = 1 THEN GOSUB MAXCAP // During a capture chain keep only captures by the same piece. n1 = 0 FOR gj = 0 TO gn - 1 gkeep = 1 IF cpos >= 0 AND GF[gj] <> cpos THEN gkeep = 0 IF cpos >= 0 AND GC[gj] = 0 THEN gkeep = 0 IF gkeep = 1 AND n1 < 24 THEN P1F[n1] = GF[gj] P1T[n1] = GT[gj] P1C[n1] = GC[gj] P1X[n1] = GX[gj] // Randomness goes into the ORDER, not the score: equal moves are // searched in a different order so the AI doesn't repeat the same // one, while the values stay exact and the cutoff window is intact. P1S[n1] = GS[gj] + FLOOR(RND(8)) n1 = n1 + 1 ENDIF NEXT IF n1 = 0 THEN aidone = 1 ELSE // Move order at the root: the earlier a good move is found, the // narrower the window on all branches below and the more cutoffs. FOR sj = 0 TO n1 - 2 sbest = sj sbv2 = P1S[sj] FOR sgi = sj + 1 TO n1 - 1 IF P1S[sgi] > sbv2 THEN sbest = sgi IF P1S[sgi] > sbv2 THEN sbv2 = P1S[sgi] NEXT IF sbest <> sj THEN pick = P1F[sj] P1F[sj] = P1F[sbest] P1F[sbest] = pick pick = P1T[sj] P1T[sj] = P1T[sbest] P1T[sbest] = pick pick = P1C[sj] P1C[sj] = P1C[sbest] P1C[sbest] = pick pick = P1X[sj] P1X[sj] = P1X[sbest] P1X[sbest] = pick pick = P1S[sj] P1S[sj] = P1S[sbest] P1S[sbest] = pick ENDIF NEXT FOR sj = 0 TO MAXLV KF[sj] = -1 KT[sj] = -1 NEXT bi = 0 bsv = -999999 amv0 = TIMER_GET FOR i1 = 0 TO n1 - 1 FOR sgi = 0 TO 63 SB[64 + sgi] = BRD[sgi] NEXT sfrom = P1F[i1] sto = P1T[i1] spc = BRD[sfrom] SB[64 + sfrom] = 0 SB[64 + sto] = spc IF P1C[i1] = 1 THEN SB[64 + P1X[i1]] = 0 IF spc = 3 AND FLOOR(sto / 8) = 7 THEN SB[64 + sto] = 4 IF P1C[i1] = 1 THEN chlv = 1 chsq = sto GOSUB CHSB ENDIF SSD[1] = 1 SD[1] = SDEPTH - 1 SAL[1] = bsv SBE[1] = 999999 SQ[1] = QMAX sd = 1 GOSUB SEARCH sd = 0 IF sval > bsv THEN bi = i1 IF sval > bsv THEN bsv = sval NEXT asum = asum + (TIMER_GET - amv0) aims = asum af_ = P1F[bi] at_ = P1T[bi] acm_ = P1C[bi] acx_ = P1X[bi] ai_p = BRD[af_] afr = FLOOR(af_ / 8) afc = af_ % 8 atr = FLOOR(at_ / 8) atc = at_ % 8 apiece = ai_p GOSUB ANIM BRD[af_] = 0 BRD[at_] = ai_p IF acm_ = 1 THEN SA = SA + 1 BRD[acx_] = 0 ENDIF IF ai_p = 3 AND atr = 7 THEN BRD[at_] = 4 GOSUB DRAW_BOARD IF acm_ = 1 THEN PAUSE 250 kr = atr kc = atc GOSUB CANCAP IF kcan = 1 THEN cpos = at_ ELSE aidone = 1 ENDIF ELSE aidone = 1 ENDIF ENDIF WEND RETURN // ---- recursive search ---- // In: level sd, board in SB[sd*64], side SSD[sd], remaining depth SD[sd], // window SAL[sd]/SBE[sd], extension allowance SQ[sd]. // Out: position value in sval. // // Recursion via GOSUB, as in CHAINCNT. Everything shared — G*, gn, gi — is // overwritten by a nested call, so the level's move list is copied into M* // right away and sorted there. SEARCH: // Time safety net. Doesn't trigger in a normal position: four plies cost // about as much as the old search. But a position with several kings // blows up the tree many times over, and it's better to play a bit weaker // than to freeze the screen for half a minute. snow = TIMER_GET - tstart IF snow > TBUDGET THEN SD[sd] = 0 IF snow > TBUDGET THEN SQ[sd] = 0 IF sd >= MAXLV - 1 THEN SD[sd] = 0 IF sd >= MAXLV - 1 THEN SQ[sd] = 0 FOR sgi = 0 TO 63 GB[sgi] = SB[sd * 64 + sgi] NEXT gside = SSD[sd] GOSUB GEN // There is NO maximum-capture filter here, and that is deliberate. It // costs a CHLEN call on every capture, while the search already maximizes // for the side to move and will pick the long chain by itself — especially // since APPLYCH plays any capture out to the end. In the model there's no // difference: 10:9:5. The rule is enforced where a move is ACTUALLY made: // at the root and when checking the player's move. IF gn = 0 THEN // No moves — this side has lost. A near loss is worse than a distant // one, otherwise the search doesn't care whether to finish now or in // three moves, and it drags the game out. sval = 99999 - SD[sd] IF SSD[sd] = 3 THEN sval = -99999 + SD[sd] RETURN ENDIF scap = 0 IF GC[0] = 1 THEN scap = 1 // Leaf. But if a capture is pending, it can't be evaluated: the material // count is off by exactly that unplayed chain. Extend while allowance lasts. // Without this extension the search plays noticeably worse — 3:15 in the model. sleaf = 0 IF SD[sd] <= 0 THEN sleaf = 1 IF sleaf = 1 AND scap = 1 AND SQ[sd] > 0 THEN sleaf = 0 IF sleaf = 1 THEN FOR sgi = 0 TO 63 TB[sgi] = SB[sd * 64 + sgi] NEXT GOSUB EVALP sval = ev RETURN ENDIF SN[sd] = gn FOR sgi = 0 TO gn - 1 MF[sd * 24 + sgi] = GF[sgi] MT[sd * 24 + sgi] = GT[sgi] MC[sd * 24 + sgi] = GC[sgi] MX[sd * 24 + sgi] = GX[sgi] MS[sd * 24 + sgi] = GS[sgi] // Killer: a quiet move that caused a cutoff at this level usually cuts on // neighbouring branches too. A twentieth of the code, a fifth of the nodes. IF GF[sgi] = KF[sd] AND GT[sgi] = KT[sd] THEN MS[sd * 24 + sgi] = GS[sgi] + 900 NEXT SBV[sd] = -999999 IF SSD[sd] = 1 THEN SBV[sd] = 999999 SI[sd] = 0 WHILE SI[sd] < SN[sd] // In-place selection sort: the best of the remaining moves is brought // forward. No need to sort the whole list — after a cutoff the tail is unused. sbest = SI[sd] sbv2 = MS[sd * 24 + SI[sd]] FOR sgi = SI[sd] + 1 TO SN[sd] - 1 IF MS[sd * 24 + sgi] > sbv2 THEN sbest = sgi IF MS[sd * 24 + sgi] > sbv2 THEN sbv2 = MS[sd * 24 + sgi] NEXT IF sbest <> SI[sd] THEN sj = MF[sd * 24 + SI[sd]] MF[sd * 24 + SI[sd]] = MF[sd * 24 + sbest] MF[sd * 24 + sbest] = sj sj = MT[sd * 24 + SI[sd]] MT[sd * 24 + SI[sd]] = MT[sd * 24 + sbest] MT[sd * 24 + sbest] = sj sj = MC[sd * 24 + SI[sd]] MC[sd * 24 + SI[sd]] = MC[sd * 24 + sbest] MC[sd * 24 + sbest] = sj sj = MX[sd * 24 + SI[sd]] MX[sd * 24 + SI[sd]] = MX[sd * 24 + sbest] MX[sd * 24 + sbest] = sj sj = MS[sd * 24 + SI[sd]] MS[sd * 24 + SI[sd]] = MS[sd * 24 + sbest] MS[sd * 24 + sbest] = sj ENDIF // Board one level deeper and the move played on it. FOR sgi = 0 TO 63 SB[(sd + 1) * 64 + sgi] = SB[sd * 64 + sgi] NEXT sfrom = MF[sd * 24 + SI[sd]] sto = MT[sd * 24 + SI[sd]] spc = SB[(sd + 1) * 64 + sfrom] SB[(sd + 1) * 64 + sfrom] = 0 SB[(sd + 1) * 64 + sto] = spc IF MC[sd * 24 + SI[sd]] = 1 THEN SB[(sd + 1) * 64 + MX[sd * 24 + SI[sd]]] = 0 IF spc = 3 AND FLOOR(sto / 8) = 7 THEN SB[(sd + 1) * 64 + sto] = 4 IF spc = 1 AND FLOOR(sto / 8) = 0 THEN SB[(sd + 1) * 64 + sto] = 2 IF MC[sd * 24 + SI[sd]] = 1 THEN chlv = sd + 1 chsq = sto GOSUB CHSB ENDIF SSD[sd + 1] = 1 IF SSD[sd] = 1 THEN SSD[sd + 1] = 3 SD[sd + 1] = SD[sd] - 1 SAL[sd + 1] = SAL[sd] SBE[sd + 1] = SBE[sd] SQ[sd + 1] = QMAX IF SD[sd] <= 0 THEN SQ[sd + 1] = SQ[sd] - 1 sd = sd + 1 GOSUB SEARCH sd = sd - 1 IF SSD[sd] = 3 THEN IF sval > SBV[sd] THEN SBV[sd] = sval IF SBV[sd] > SAL[sd] THEN SAL[sd] = SBV[sd] ENDIF IF SSD[sd] = 1 THEN IF sval < SBV[sd] THEN SBV[sd] = sval IF SBV[sd] < SBE[sd] THEN SBE[sd] = SBV[sd] ENDIF IF SAL[sd] >= SBE[sd] THEN // Cutoff: the opponent won't choose this branch, no point going on. IF MC[sd * 24 + SI[sd]] = 0 THEN KF[sd] = MF[sd * 24 + SI[sd]] IF MC[sd * 24 + SI[sd]] = 0 THEN KT[sd] = MT[sd * 24 + SI[sd]] SI[sd] = SN[sd] ENDIF IF SI[sd] < SN[sd] THEN SI[sd] = SI[sd] + 1 WEND sval = SBV[sd] RETURN // ---- must the player capture right now ---- // The generator already drops quiet moves when captures exist, so it's // enough to look at the first move in the list. CHKBEAT: FOR gi = 0 TO 63 GB[gi] = BRD[gi] NEXT gside = 1 GOSUB GEN mustbeat = 0 needchl = 0 IF gn > 0 AND GC[0] = 1 THEN mustbeat = 1 IF mustbeat = 1 THEN GOSUB MAXCAP IF mustbeat = 1 THEN needchl = bestchl RETURN // ---- maximum capture ---- // Of the captures in G* keeps only those that start the LONGEST chain. The // rule requires capturing the maximum, not just anything: choosing a short // capture when a triple one exists is not allowed. // // Call right after GEN — CHLEN takes the board from GB. MAXCAP: bestchl = 0 FOR gq2 = 0 TO gn - 1 GOSUB CHLEN CHL[gq2] = chl IF chl > bestchl THEN bestchl = chl NEXT gdst = 0 FOR gq2 = 0 TO gn - 1 IF CHL[gq2] = bestchl THEN GF[gdst] = GF[gq2] GT[gdst] = GT[gq2] GC[gdst] = GC[gq2] GX[gdst] = GX[gq2] // Chain length goes into the move score: capturing three pieces // should rank above capturing one, otherwise the search only sees // the first jump and underestimates exchanges. GS[gdst] = GS[gq2] + CHL[gq2] * 400 gdst = gdst + 1 ENDIF NEXT gn = gdst RETURN // ================== CAPTURE CHAIN LENGTH ================== // Counts how many pieces can be captured in a row, starting from square // CSQ[ccd] on the board in CBD at offset ccd*64. Result in cres. // // Recursion via GOSUB, with all state split by depth: move lists, counters, // position, best result. Otherwise a nested call would overwrite the caller's // variables. Depth is limited to six — longer chains practically never occur // in checkers, and the stack isn't unlimited. CHAINCNT: CBS[ccd] = 0 cres = 0 IF ccd >= 5 THEN RETURN // Budget exhausted — return what we have so far. The maximum capture may // then not be determined exactly, but the rule still works and the move // doesn't hang. IF cbud <= 0 THEN RETURN cbud = cbud - 1 GOSUB CAPLIST IF CLN[ccd] = 0 THEN RETURN CLI[ccd] = 0 WHILE CLI[ccd] < CLN[ccd] // The move is made IN PLACE and then undone. Previously the whole board // was copied for every node — some two hundred statements — and since // this is called from the search on every capture, the copies burned // all of its savings. cfrm = CSQ[ccd] cto = CLT[ccd * 8 + CLI[ccd]] cvi = CLV[ccd * 8 + CLI[ccd]] cpc = CBD[cfrm] cvq = CBD[cvi] CUF[ccd] = cfrm CUT[ccd] = cto CUV[ccd] = cvi CUP[ccd] = cpc CUQ[ccd] = cvq CBD[cfrm] = 0 CBD[cvi] = 0 CBD[cto] = cpc // Promotion mid-chain: a man reaching the edge becomes a king and // captures like a king from then on. IF cpc = 3 AND FLOOR(cto / 8) = 7 THEN CBD[cto] = 4 IF cpc = 1 AND FLOOR(cto / 8) = 0 THEN CBD[cto] = 2 CSQ[ccd + 1] = cto ccd = ccd + 1 GOSUB CHAINCNT ccd = ccd - 1 // Undo. Values come from CU*, not from cto/cvi/cpc: the nested call // has already overwritten those. CBD[CUT[ccd]] = 0 CBD[CUF[ccd]] = CUP[ccd] CBD[CUV[ccd]] = CUQ[ccd] IF cres + 1 > CBS[ccd] THEN CBS[ccd] = cres + 1 CLI[ccd] = CLI[ccd] + 1 WEND cres = CBS[ccd] RETURN // ---- captures of ONE piece on square CSQ[ccd] ---- // Fills CLT/CLV for the current depth and CLN[ccd]. CAPLIST: CLN[ccd] = 0 cpp = CBD[CSQ[ccd]] IF cpp = 0 THEN RETURN cpr = FLOOR(CSQ[ccd] / 8) cpc2 = CSQ[ccd] % 8 cpk = 0 IF cpp = 2 OR cpp = 4 THEN cpk = 1 cme = 1 IF cpp = 3 OR cpp = 4 THEN cme = 3 FOR cdir = 0 TO 3 cstp = 1 cfn = 0 cvc = -1 csp = 0 WHILE csp = 0 crr = cpr + DR[cdir] * cstp ccc = cpc2 + DC[cdir] * cstp IF crr < 0 OR crr > 7 OR ccc < 0 OR ccc > 7 THEN csp = 1 IF csp = 0 THEN cq = CBD[crr * 8 + ccc] IF cfn = 0 THEN IF cq = 0 AND cpk = 0 THEN csp = 1 IF cq <> 0 THEN cown = 0 IF cme = 3 AND (cq = 3 OR cq = 4) THEN cown = 1 IF cme = 1 AND (cq = 1 OR cq = 2) THEN cown = 1 IF cown = 1 THEN csp = 1 IF cown = 0 THEN cfn = 1 IF cown = 0 THEN cvc = crr * 8 + ccc IF cown = 0 AND cpk = 0 AND cstp > 1 THEN csp = 1 ENDIF ELSE IF cq = 0 AND CLN[ccd] < 8 THEN CLT[ccd * 8 + CLN[ccd]] = crr * 8 + ccc CLV[ccd * 8 + CLN[ccd]] = cvc CLN[ccd] = CLN[ccd] + 1 ENDIF IF cq <> 0 THEN csp = 1 IF cpk = 0 THEN csp = 1 ENDIF ENDIF cstp = cstp + 1 IF cstp > 8 THEN csp = 1 WEND NEXT RETURN // ================== PLAY OUT A CAPTURE CHAIN ================== // The board is in CBD[0..63], asq is the square the capturing piece just // landed on. Plays the capture out TO THE END, picking a continuation. // // Without this the search treated a capture as a single jump, and a sacrifice // followed by a triple counter-capture looked like a gift to it: "the opponent // hung a piece". That's exactly how a human wins. In the model, chains vs. // single jumps — 23:0 with one draw, more than any increase in depth or // evaluation gave. APPLYCH: achain = 1 aguard = 0 WHILE achain = 1 aguard = aguard + 1 IF aguard > 12 THEN achain = 0 IF achain = 1 THEN ccd = 0 CSQ[0] = asq GOSUB CAPLIST IF CLN[0] = 0 THEN achain = 0 ENDIF IF achain = 1 THEN // Take the FIRST continuation, without searching for the longest. // An exact choice needed a tree on every king — 99% of the whole // move time went there — and it doesn't affect playing strength: // greedy chain vs. maximum chain gave 10:10:4 in the model. The // maximum-capture rule is enforced where a move is ACTUALLY made: // at the root (MAXCAP) and when checking the player's move (HUMCHL). cto = CLT[0] cvi = CLV[0] cpc = CBD[asq] CBD[asq] = 0 CBD[cvi] = 0 CBD[cto] = cpc IF cpc = 3 AND FLOOR(cto / 8) = 7 THEN CBD[cto] = 4 IF cpc = 1 AND FLOOR(cto / 8) = 0 THEN CBD[cto] = 2 asq = cto ENDIF WEND RETURN // ---- play out the chain on the board of level chlv ---- // The level board lives in SB, while APPLYCH works in CBD — hence two copies. // Called only on captures, and they are a minority in the tree. CHSB: cbi = 0 WHILE cbi < 64 CBD[cbi] = SB[chlv * 64 + cbi] cbi = cbi + 1 WEND asq = chsq GOSUB APPLYCH cbi = 0 WHILE cbi < 64 SB[chlv * 64 + cbi] = CBD[cbi] cbi = cbi + 1 WEND RETURN // ---- chain length for MOVE number gq2 ---- // The board is taken from GB — the same one the moves were generated on, so // call this right after GEN. // // Counting starts from the square the piece LANDS on after the first jump, // not from the starting one. The difference shows with a flying king: after // a capture it may land on any square behind the victim, but can continue // capturing only from some of them. Counting from the start square gave all // of that king's moves the same length, MAXCAP couldn't tell them apart and // allowed an incomplete capture. The player's move check (HUMCHL) always // counted from the landing square — so the rule was stricter for the human // than for the AI. CHLEN: cbud = CHBUD cbi = 0 WHILE cbi < 64 CBD[cbi] = GB[cbi] cbi = cbi + 1 WEND cpc = CBD[GF[gq2]] CBD[GF[gq2]] = 0 CBD[GX[gq2]] = 0 CBD[GT[gq2]] = cpc IF cpc = 3 AND FLOOR(GT[gq2] / 8) = 7 THEN CBD[GT[gq2]] = 4 IF cpc = 1 AND FLOOR(GT[gq2] / 8) = 0 THEN CBD[GT[gq2]] = 2 ccd = 0 CSQ[0] = GT[gq2] GOSUB CHAINCNT chl = cres + 1 RETURN // ================== MOVE GENERATOR ================== // Board in GB, side in gside (3 — AI, 1 — player). Result in GF/GT/GC/GX, // count in gn, quick move score in GS. // // Walks ALONG THE DIAGONALS from each piece. The old approach — 64 source // squares times 64 target squares — is tolerable for a single move, but with // a three-ply search the generator is called more than fifty times, and the // difference between these two methods decides whether we fit in a second // or in a minute. GEN: gn = 0 FOR gi = 0 TO 63 gp = GB[gi] gok = 0 IF gside = 3 AND (gp = 3 OR gp = 4) THEN gok = 1 IF gside = 1 AND (gp = 1 OR gp = 2) THEN gok = 1 IF gok = 1 THEN grw = FLOOR(gi / 8) gcol = gi % 8 gking = 0 IF gp = 2 OR gp = 4 THEN gking = 1 FOR gdir = 0 TO 3 gstep = 1 gfnd = 0 gvic = -1 gstop = 0 WHILE gstop = 0 grr = grw + DR[gdir] * gstep gcc = gcol + DC[gdir] * gstep IF grr < 0 OR grr > 7 OR gcc < 0 OR gcc > 7 THEN gstop = 1 IF gstop = 0 THEN gq = GB[grr * 8 + gcc] IF gfnd = 0 THEN IF gq = 0 THEN // Empty square — a quiet move, if allowed. gok = 0 IF gking = 1 THEN gok = 1 IF gking = 0 AND gstep = 1 AND gside = 3 AND grr > grw THEN gok = 1 IF gking = 0 AND gstep = 1 AND gside = 1 AND grr < grw THEN gok = 1 IF gok = 1 AND gn < 24 THEN GF[gn] = gi GT[gn] = grr * 8 + gcc GC[gn] = 0 GX[gn] = -1 GS[gn] = 0 IF gside = 3 THEN GS[gn] = grr * 4 IF gside = 1 THEN GS[gn] = (7 - grr) * 4 IF gside = 3 AND gp = 3 AND grr = 7 THEN GS[gn] = GS[gn] + 200 IF gside = 1 AND gp = 1 AND grr = 0 THEN GS[gn] = GS[gn] + 200 gn = gn + 1 ENDIF IF gking = 0 THEN gstop = 1 ELSE gown = 0 IF gside = 3 AND (gq = 3 OR gq = 4) THEN gown = 1 IF gside = 1 AND (gq = 1 OR gq = 2) THEN gown = 1 IF gown = 1 THEN gstop = 1 IF gown = 0 THEN gfnd = 1 IF gown = 0 THEN gvic = grr * 8 + gcc // A plain man captures only an adjacent piece. IF gown = 0 AND gking = 0 AND gstep > 1 THEN gstop = 1 ENDIF ELSE IF gq = 0 AND gn < 24 THEN GF[gn] = gi GT[gn] = grr * 8 + gcc GC[gn] = 1 GX[gn] = gvic GS[gn] = 500 IF GB[gvic] = 2 OR GB[gvic] = 4 THEN GS[gn] = 800 gn = gn + 1 ENDIF IF gq <> 0 THEN gstop = 1 IF gking = 0 THEN gstop = 1 ENDIF ENDIF gstep = gstep + 1 IF gstep > 8 THEN gstop = 1 WEND NEXT ENDIF NEXT // CAPTURING IS MANDATORY. The rule is built into the generator, not into // the player move check: that way it automatically applies to all search // levels too, i.e. the AI calculates lines by the same rules the human // plays by. Otherwise it would expect quiet moves from the opponent that // the opponent is not allowed to make. gcapn = 0 FOR gj = 0 TO gn - 1 IF GC[gj] = 1 THEN gcapn = gcapn + 1 NEXT IF gcapn > 0 AND gcapn < gn THEN gdst = 0 FOR gj = 0 TO gn - 1 IF GC[gj] = 1 THEN GF[gdst] = GF[gj] GT[gdst] = GT[gj] GC[gdst] = 1 GX[gdst] = GX[gj] GS[gdst] = GS[gj] gdst = gdst + 1 ENDIF NEXT gn = gdst ENDIF RETURN // ================== POSITION EVALUATION ================== // Scores board TB from the AI's point of view: higher is better for it. // A king is worth three men, advancing towards one's last rank is rewarded // (a man there becomes a king), a piece on the edge is worth a bit more — // it can't be captured, there's nothing to jump over beyond the edge. EVALP: ev = 0 FOR evi = 0 TO 63 evp = TB[evi] IF evp > 0 THEN evr = FLOOR(evi / 8) evc = evi % 8 evv = 0 IF evp = 2 OR evp = 4 THEN // King. In the centre it is stronger: longer diagonals, more // squares under attack. On the edge, half its power is lost. evv = 320 IF evc >= 2 AND evc <= 5 THEN evv = evv + 10 IF evr >= 2 AND evr <= 5 THEN evv = evv + 10 ELSE // Plain man. Advancement is counted from ITS OWN side and grows // faster near the edge: a man one step from promotion is worth // far more than one halfway there, and a linear bonus didn't // capture that. evv = 100 eva = evr IF evp = 1 THEN eva = 7 - evr evv = evv + eva * 6 IF eva >= 5 THEN evv = evv + (eva - 4) * 14 IF evc >= 2 AND evc <= 5 THEN evv = evv + 6 // One's own back rank blocks enemy promotion: while it stands, // the opponent can't get a king. Trading its pieces for trifles // is a bad deal. IF evp = 3 AND evr = 0 THEN evv = evv + 16 IF evp = 1 AND evr = 7 THEN evv = evv + 16 ENDIF // On the edge a piece can't be captured: there's nothing to jump over. IF evc = 0 OR evc = 7 THEN evv = evv + 12 // Backing from behind. A piece with an own piece behind it isn't // taken for free: the opponent lands under a counter-capture. That's // the difference between a formation and scattered singles, which a // bare material count doesn't see. evb = evr - 1 IF evp = 1 OR evp = 2 THEN evb = evr + 1 IF evb >= 0 AND evb <= 7 THEN IF evc > 0 THEN evq = TB[evb * 8 + evc - 1] IF (evp = 3 OR evp = 4) AND (evq = 3 OR evq = 4) THEN evv = evv + 7 IF (evp = 1 OR evp = 2) AND (evq = 1 OR evq = 2) THEN evv = evv + 7 ENDIF IF evc < 7 THEN evq = TB[evb * 8 + evc + 1] IF (evp = 3 OR evp = 4) AND (evq = 3 OR evq = 4) THEN evv = evv + 7 IF (evp = 1 OR evp = 2) AND (evq = 1 OR evq = 2) THEN evv = evv + 7 ENDIF ENDIF IF evp = 3 OR evp = 4 THEN ev = ev + evv IF evp = 1 OR evp = 2 THEN ev = ev - evv ENDIF NEXT RETURN // ================== GAME OVER ================== CHECK_END: gameov = 0 qr = 0 qc = 0 FOR qi = 0 TO 63 IF BRD[qi] = 1 OR BRD[qi] = 2 THEN qr = qr + 1 IF BRD[qi] = 3 OR BRD[qi] = 4 THEN qc = qc + 1 NEXT IF qc = 0 THEN gameov = 1 winner = 1 ENDIF IF qr = 0 THEN gameov = 1 winner = 2 ENDIF // A blocked side loses: it has pieces but no moves. Without this check // the game simply stalled — no end and no move. IF gameov = 0 THEN FOR gi = 0 TO 63 GB[gi] = BRD[gi] NEXT gside = 1 GOSUB GEN IF gn = 0 THEN gameov = 1 winner = 2 ENDIF ENDIF IF gameov = 0 THEN FOR gi = 0 TO 63 GB[gi] = BRD[gi] NEXT gside = 3 GOSUB GEN IF gn = 0 THEN gameov = 1 winner = 1 ENDIF ENDIF IF gameov = 1 THEN DISPLAY_FILL_RECT(140, 290, 440, 140, #101010) IF winner = 1 THEN msg$ = "You win!" ELSE msg$ = "AI wins" DISPLAY_TEXT(200, 320, msg$, #FFD700, 32) DISPLAY_TEXT(200, 370, "Score You: " + SH + " AI: " + SA, #FFFFFF, 24) DISPLAY_UPDATE ENDIF RETURN // ================== DRAW THE WHOLE BOARD ================== DRAW_BOARD: DISPLAY_FILL_RECT(0, 0, 720, 80, #202020) DISPLAY_TEXT(40, 24, "Score You: " + SH + " AI: " + SA + " think " + aims + " ms", #FFFFFF, 24) IF mustcap = 1 OR mustbeat = 1 THEN DISPLAY_TEXT(420, 24, "MUST CAPTURE", #FF9800, 24) FOR qr = 0 TO 7 FOR qc = 0 TO 7 dcr = qr dcc = qc GOSUB DRAW_CELL NEXT NEXT // The frame is pushed EXPLICITLY. With a full-screen canvas output goes as // a direct write to the framebuffer, and without DISPLAY_UPDATE nothing // reaches the screen at all — the screen stayed black. On the old // composited path LVGL refreshed by itself, so the script did without it. DISPLAY_UPDATE RETURN