Chess engine based on Sunfish for the NumWorks. Requires usunfish_chess.py to be loaded as well in the calculator. uSunfish is an alternate spelling of μSunfish (micro Sunfish), meant to be a port of Sunfish to micropython.
from random import randint _MAX_HIST=const(10) def fb64(eb): A=eb;B='ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=';F,E=len(A)*3//4-A.count('='),0 for C in range(0,len(A),4): D=B.index(A[C])<<18|(B.index(A[C+1])&63)<<12|(B.index(A[C+2])&63)<<6|B.index(A[C+3])&63 for G in(D>>16,D>>8&255,D&255): if E<F:yield int(G);E+=1 def b(x):return bytes(fb64(x)) pst_b=b('GRkZGRkZGRksLS4rMi0uLxogHiQjICQaFB0YHBwZHBUSGRsbGhkZExMbGhYWGBkUERsXDxAVGREZGRkZGRkZGTU4MzNDODc0RURfPUdVRUJIVkZYWExVRUxMUU9OUExKRUdNS0tORkZBSElLSklIQkBCRkZGRkBBM0A/QEE9QDRBPDs9SjVGQ01VWEVGV1BKTVlIWl1NV0xWVFVYVlZTUlNSVFVUVFBRU1ZWU1JWVVNUVVJRUVFVVE5QTE1MTE1NgH+AeIGAhYSFf4WIhYeAhnyAfoCDfn57d3l7e3x2dXZwb3NydHBscG1wbXFxb3Fsam5wcXBtbGpwcXN5d3Nwb+no5s757v7u6/D35e379u7n8/D3+vjz6Ojk7ezu7eXm5OTn5+jl4+Lg5uXl5OXk4d/j6OPk5OPe3uDg5eDf390aJiQAACgtCREbJicnJhsZCRwKJAggIhELJRsYFBwZDAsODBIMDRcMDQ4OBQkREREYGRUMChQcGh0gGBUaGCMd') pst_k=b('BhAUFBYcGhQWHRwdHSIeGxsdHhweJCQcFx4fHx8hHxkUGB4fHx4bFhQYGx4eHRoWEhYaHBwaFxQLEBMWEhUTDg==') inc='\x00\x00\x00\x00\x00' def g_p(i,xor):return pst_b[i^xor]-ord(inc[0]) def g_n(i,xor):return pst_b[(i^xor)+64]+ord(inc[1]) def g_b(i,xor):return pst_b[(i^xor)+128]-ord(inc[2]) def g_r(i,xor):return pst_b[(i^xor)+192]+ord(inc[3]) def g_q(i,xor):return pst_b[(i^xor)+256]+ord(inc[4]) def g_k(i,xor):return pst_b[(i^xor)+320]+14975 def g_k_eg(i,xor):return pst_k[i^xor]+14975 pst=[g_p,g_n,g_b,g_r,g_q,g_k] _A1=const(56) _H1=const(63) _A8=const(0) _H8=const(7) _NO=const(-8) _E=const(1) _S=const(8) _W=const(-1) _P=const(0) _N=const(1) _B=const(2) _R=const(3) _Q=const(4) _K=const(5) op_mode=1 board=[11,9,10,12,13,10,9,11,8,8,8,8,8,8,8,8,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,0,0,0,0,0,0,0,0,3,1,2,4,5,2,1,3] wc_bc_ep_kp=1015936 pscore=0 directions='\x02\t\x02\x01\x01\x08\x03\n','\x03\x02\x04\x0b\x04\x1b\x03"\x01 \x00\x17\x00\x07\x01\x00','\x03\n\x03\x1a\x01\x18\x01\x08','\x02\t\x03\x12\x02\x19\x01\x10','\x02\t\x03\x12\x02\x19\x01\x10\x03\n\x03\x1a\x01\x18\x01\x08','\x02\t\x03\x12\x02\x19\x01\x10\x03\n\x03\x1a\x01\x18\x01\x08' _MT_LW=const(12680) _MT_UP=const(17320) _QS=const(14) _QS_A=const(34) _EVAL_ROUGHNESS=const(4) _MAX_QS=const(2) _MAX_DEPTH=const(40) _T_SZS=154 t_szs=0 tp_scoreh=[None]*_T_SZS tp_scored=[None]*_T_SZS*2 max_d_sc=_MAX_DEPTH+_MAX_QS nodes=0 _MAX_OP_D=const(11) op_ind=1 op=b('DifjEyIeHo4C4DEeECt+hSAhTyM+BN7S3g5wTgbgzgIhFxfyfgAeACFkPgPn4APgHgHgERDnARAE4JJRBXHgMSsWA3EBBOAeECtkIKIFMA6hLSEi4AEEZoMeAksA6EExYi4AETNO/o5uAuAgAT8wJxDpMiLg004CNeAOAuAuADcxQj5QBnMQJ0zwMjcxQiIOrrXtS/jgAAExQuAeAsTCBSHhIT9uCEXzToMxTlkOA+GuFOEeEOAuG+BKAGRzMRNXMUJ+vhIh4AROAhRiHD7G6hLSEmETFCLgPiXhERLg53LgIi52Ij6AED5QALAeDo4CQrQQEhE8ngLg6AHgcRFsHg5wHhIOUi6FA7QB/sAjr+fgIOAzERAREAPskgMugX4CA2ZHMQ6yJDsUnq6+BeHtS/75Xb5TlJAUIDaeVmQA4K4I4T4C4VcgTRBGRD4gBDu2RzPgREcRNX4TFCYc6kz9IAORAC5D4BMFACLgJ2HOp+vqIUwic5ADHhuXcYNhfh6uCSEREhEt+SeyTtdhSOzh6E4SUBEQAyKVJeAQLnAB4hHgHhPgHgYuLs4FLrwlLhXeDr6CKOjV5OAi5FLg6+U53gtbEvLhouBeHoJV4S4eguvd6OsuAk7LM+k2LgPgUvngNdvswlIuBV3hLo62vuJODk7uCOAh4F6065EyHgXh6+U13nLg5eHtUiUn4F606x4FLhAB9y4ACE0iIg4C9fER4C4AHgYevrJAE+AOn46NguAG8QYhjhEEQwjiAODrHhA44F4M5Afr4VDSEumuVD4XCecwV+QgA/IOAgA/PgTgkALhhJQxJVECAD4ADgDg5VG+8A+gAeAD4CEuGDBGHnEyIuBO0QAQHU4L8vbhHhLhESZSID4OngEuBeA+AhcSAC4EEi4DOTDgAy4RMDvvEDTgTUFBEuYBEy4D7VTgZiZeAeDeAQFuBxkX7iIhEBG36AAeASt+jl4OQhRj9AASHg3ifhF83gKG4FfkEuAm5ODS3gAADggeDOFihelWjgO3GYQ+WhIe/kMuFR1xIRvnEgETdEHlEBKRUA4euecR4Ofk9oUi6e+3IqoAOQAuJeLmABs68A4GGODr4OohTOCuAA5yPsa+COA+ses4NhKS4CtkIE4XPADAAtAuXlFuAB4CeyQeAOvevgAR4Z4C6w/pIY4ELg61YhIjMQ4BJwAhDmmehBJG4G4CQhMC3DABQh5uA3HgI+kSU3FAASHXEOJuDFcRJBPq6eHWHv4Or05uenS+C+x2AC6KTruubgshThEOBuDBYyUyAuHPUbQwCzkiECcYDgLgLglSVuTgEmSODk4CEeTg6Wv2HkGeB+s6++vg7CIRLgJOAc6Ogz95J7jgTr4etz6+BuBhNUIGjgcRzqkhDTAOCb6+DsIh4BAiTgHgfDsiREQQ') op2=b('7t4+X8/k/p/m/k4+X8/k/p/m/l4+X8/k/p/m/o4+X8/k/p/m/p4+X8/k/p/m8+Pl/P5P6f5vrj5fz+T+n+b04+X8/k/p/m9ePl/P5P6f5vnj5fz+T+n+b24+X8/k/p/m/m4+X8/k/p/m/n4+X8/k/p/m++Pl/P5P6f5vjj5fz+T+n+b84+X8/k/p/m8=') def op_get(i,op): if i>>1>=len(op):return 0 return op[i>>1]>>(i&1^1)*4&15 def parse_sibl(c_ind,d,op): B=op;A=c_ind if d>_MAX_OP_D:return[],A E=[];C=op_get(A,B) if C==14 and op_get(A+1,B)<4:C=op_get(A+1,B)+2;A+=2 elif C==15:C=0;A+=1 elif C==14 and op_get(A+1,B)==14 and A==0:C=16;A+=2 else:C=1 for F in range(C): D=op_get(A,B) if D==14 and op_get(A+1,B)>3:D=D+op_get(A+1,B)-4;A+=1 A+=1;E.append((D,A));F,A=parse_sibl(A,d+1,B) return E,A def restore(mv,dif): A=dif;global board;board[mv>>8&255]=A>>4&15;board[mv&63]=A&15 if A>65535:B=A>>16&255;board[A>>8&255]=board[B];board[B]=_R elif A>255:board[A>>8&255]=_P|8 def ghash():global board,pscore,wc_bc_ep_kp;B=board;C=bytes(B[A]<<4|B[A+1]for A in range(0,64,2));D=bytes(reversed(C));A=(hash(C)<<16|hash(D)^wc_bc_ep_kp<<16)&2147483647;return-(A&1073741823)if A&1073741824==1073741824 else A def reverse():global board;board=[A^8 for A in reversed(board)] def rotate_and_set(score,wc,bc,ep,kp,turn,nullmove=False):B=nullmove;A=turn;global board,pscore,wc_bc_ep_kp;reverse();A=A^1;pscore=-score;wc_bc_ep_kp=A<<20|bc<<18|wc<<16|(63-ep if ep!=128 and not B else 128)<<8|(63-kp if kp!=128 and not B else 128) def rotate(nullmove=False):global board,pscore,wc_bc_ep_kp;A=wc_bc_ep_kp>>20;B=wc_bc_ep_kp>>18&3;C=wc_bc_ep_kp>>16&3;D=wc_bc_ep_kp>>8&255;E=wc_bc_ep_kp&255;rotate_and_set(pscore,B,C,D,E,A,nullmove) def gen_moves(lvalue=-_MT_LW,ccheck=True): K=ccheck;J=lvalue;global board,directions,pscore,wc_bc_ep_kp;O=[];L=O.append;F=board;M=(wc_bc_ep_kp>>20)*7 for(C,G)in((B,A)for(B,A)in enumerate(F)if A<=5): E=None;dir=directions[G] for P in range(0,len(dir)-1,2): S,N=ord(dir[P])-2,ord(dir[P+1])-17;Q=C&7;A=C while True: A+=N;Q+=S if Q&~7|A&~63:break D=F[A] if D<6:break if G==_P: if N in(_NO,_NO+_NO)and D|8!=14:break if N==_NO+_NO and(C<_A1+_NO or F[C+_NO]|8!=14):break if N in(_NO+_W,_NO+_E)and D|8==14 and A not in(wc_bc_ep_kp>>8&255,wc_bc_ep_kp&255,(wc_bc_ep_kp&255)-1,(wc_bc_ep_kp&255)+1):break if _A8<=A<=_H8: for R in b'\x01\x02\x03\x04': B,E=value(None,C,A,R,G,D,M,E,K) if E==99999:return[B+32768<<14] elif B>=J:L(C<<8|A|R-1<<6|B+32768<<14) break B,E=value(None,C,A,0,G,D,M,E,K) if E==99999:return[B+32768<<14] elif B>=J:L(C<<8|A|B+32768<<14) if G in b'\x00\x01\x05'or D<14 and D&8==8:break if C==_A1 and wc_bc_ep_kp>>18&2==2 and A<63 and F[A+_E]==_K: H=A+_E;I=A+_W;B,T=value(None,H,I,0,_K,6,M,None,K) if B>=J:L(H<<8|I|B+32768<<14) break if C==_H1 and wc_bc_ep_kp>>18&1==1 and A>0 and F[A+_W]==_K: H=A+_W;I=A+_E;B,T=value(None,H,I,0,_K,6,M,None,K) if B>=J:L(H<<8|I|B+32768<<14) break O.sort();return O def move(mv,val=None): F=val;global board,pscore,wc_bc_ep_kp;B,A,J,G=mv>>8,mv&63,((mv&255)>>6)+1,wc_bc_ep_kp>>20;H=board[B];C,D,K,I=wc_bc_ep_kp>>18&3,wc_bc_ep_kp>>16&3,128,128;F,N=value(mv,B,A,J,H,None,None,None)if F is None else(F,None);M=pscore+F;E=board[B]<<4|board[A];board[A]=H;board[B]=6|G<<3;C=C&1 if B==_A1 else C&2 if B==_H1 else C;D=D&2 if A==_A8 else D&1 if A==_H8 else D if H==_K: C=0 if abs(A-B)==2:I=(B+A)//2;L=_A1 if A<B else _H1;E=L<<16|I<<8|E;board[L]=6|G<<3;board[I]=_R elif H==_P: if _A8<=A<=_H8:board[A]=J if A-B==2*_NO:K=B+_NO if A==wc_bc_ep_kp>>8&255:board[A+_S]=6|G<<3;E=A+_S<<8|E rotate_and_set(M,C,D,K,I,G);return E def value(mv,i,j,prom,p,q,xor,iscore,ccheck=True): B=iscore;A=xor;global board,pscore,wc_bc_ep_kp;D=pst;q=board[j]if q is None else q;A=(wc_bc_ep_kp>>20)*7 if A is None else A;B=D[p&7](i,A)if B is None else B;F=D[p&7](j,A);C=F-B if q<14 and q&8==8:E=63-j;C+=D[q&7](E,A) if abs(j-(wc_bc_ep_kp&255))<2 and ccheck:E=63-j;C+=g_k(E,A) if p==_K and abs(i-j)==2:C+=g_r(i+j>>1,A);C-=g_r(_A1 if j<i else _H1,A) elif p==_P: if _A8<=j<=_H8:C+=D[prom](j,A)-g_p(j,A) if j==wc_bc_ep_kp>>8&255:C+=g_p(63-(j+_S),A) B=99999 if q|8==13 else B;return C,B def s_tp(h,mv,e0,e1,d): global tp_scoreh,tp_scored,max_d_sc,t_szs if t_szs==_T_SZS and d>max_d_sc:return try:A=tp_scoreh.index(h,0,t_szs) except ValueError: if t_szs<_T_SZS:tp_scoreh[t_szs]=h;tp_scored[t_szs<<1]=mv|d<<24;tp_scored[(t_szs<<1)+1]=e0+32678<<16|e1+32768;t_szs+=1;max_d_sc=max(max_d_sc,d);return else: if d==max_d_sc:return B=0 for A in range(0,_T_SZS<<1,2): C=tp_scored[A]>>24 if d<C:tp_scoreh[A>>1]=h;tp_scored[A]=mv|d<<24;tp_scored[A+1]=e0+32678<<16|e1+32768;return else:B=max(C,B) max_d_sc=B return D=A<<1;tp_scored[D]=mv|d<<24;tp_scored[D+1]=e0+32678<<16|e1+32768 def reset_tp_score(): global tp_scored for A in range(0,t_szs<<1,2):tp_scored[A+1]=-_MT_UP+32678<<16|_MT_UP+32768 def g_sc(h,d): global tp_scoreh,tp_scored,board if d>max_d_sc:return 0,(-_MT_UP,_MT_UP) try:B=tp_scoreh.index(h) except ValueError:return 0,(-_MT_UP,_MT_UP) D=tp_scored[B<<1]>>24;A=tp_scored[B<<1]&65535 if A!=0 and board[A>>8]>5:return 0,(-_MT_UP,_MT_UP) if D!=d:return A,(-_MT_UP,_MT_UP) C=tp_scored[(B<<1)+1];E=(C>>16)-32678;F=(C&65535)-32768;return A,(E,F) def bound(g,od,cn): C=od;global nodes,history,board,pscore,wc_bc_ep_kp;nodes+=1;G=max(C,0);E=pscore if C<-_MAX_QS:return E,0 if E<=-_MT_LW:return-_MT_UP,0 D=None;H=ghash();A,D=g_sc(H,req_d-C) if D[0]>=g:return D[0],A if D[1]<g:return D[1],0 if cn and G>0 and H in history:return 0,0 I=wc_bc_ep_kp def K(): global wc_bc_ep_kp,pscore,board;nonlocal A if G>2 and cn and abs(E)<125:rotate(True),;B,L=bound(1-g,C-3,False);B=-B;rotate();wc_bc_ep_kp=I;yield(0,B) if G==0:yield(0,E) if not A and G>2:O,A=bound(g,G-3,False) M=_QS-G*_QS_A if A!=0: J,N,P=A>>8,A&63,((A&255)>>6)+1;Q,R=board[J],board[N];F,O=value(A,J,N,P,Q,R,None,None) if F>=M:H=move(A,F);B,L=bound(1-g,C-1,True);B=-B;reverse();pscore=E;wc_bc_ep_kp=I;restore(A,H);del H;yield(A,B) else:A=None K=gen_moves(M) for J in range(len(K)): D=K.pop();F=(D>>14)-32768;D=D&16383 if D==A:continue if G<0 and E+F<g:del K;yield(D,E+F if F<_MT_LW else _MT_UP);return if F>_MT_LW:yield(D,_MT_UP);return if C<=-_MAX_QS:yield(D,E+F) else: if C<=-_MAX_QS:B=pscore else:H=move(D,F);B,L=bound(1-g,C-1,True);B=-B;reverse();pscore=E;wc_bc_ep_kp=I;restore(D,H);del H yield(D,B) B=-_MT_UP;F=0 for(L,M)in K(): B=max(B,M) if B>=g:F=L;break if G>2 and B==-_MT_UP: rotate();J=gen_moves(_MT_UP-1,ccheck=False);N=len(J)==1 and J[0]&16383==0;rotate() if N:B=-_MT_LW;F=0 else:B=0;F=0 if B>=g and C>-_MAX_QS+1 and F!=0:s_tp(H,F,B,D[1],req_d-C) return B,F def mk_mv(mv): global last_mv,op_mode,op_ind,ply;ply+=1 if op_mode==1: A=[A&16383 for A in gen_moves()];A.reverse();mv=mv&16191;last_mv=A.index(mv);B,D=parse_sibl(op_ind,ply-1,op);C=[A for(A,(B,C))in enumerate(B)if B==last_mv] if C:op_ind=B[C[0]][1] else:op_mode=0 return move(mv) last_mv=-1 ply=0 def g_next_move(op): global op_ind,last_mv,op_mode,ply;C=op_ind;A,D=parse_sibl(C,ply,op) if not A:op_mode=0;return 0 B,D=A[randint(0,len(A)-1)];B=gen_moves()[-B-1]&16383;return B def search(): global nodes,req_d,tp_scored,tp_scoreh,max_d_sc,board,t_szs,pscore,pst_b,inc,op_ind;nodes=0 if op_mode==1: A=g_next_move(op) if A!=0:yield(0,pscore-4,pscore,A);return if ply==1: op_ind=0;A=g_next_move(op2) if A!=0:yield(0,pscore-4,pscore,A);return B=0 if 5 not in[A&7 for A in board]or sum(A&7 for A in board if A&7<5)<13:pst[5]=g_k_eg elif ply<10:pst[5]=g_k inc=chr(randint(0,4))+chr(randint(0,14))+chr(randint(0,6))+chr(randint(0,9))+chr(randint(0,19));t_szs=0;max_d_sc=0 for req_d in range(1,_MAX_DEPTH+1): D,E=-_MT_LW,_MT_LW while D<E-_EVAL_ROUGHNESS: C,F=bound(B,req_d,False) if C>=B:D=C if C<B:E=C yield(req_d,B,C,F);B=(D+E+1)//2 reset_tp_score() def upd_hist(): global history,pos;history.append(ghash()) if len(history)>_MAX_HIST:history.pop(0) def render(i):A,B=divmod(i-_A1,8);return chr(B+ord('a'))+str(-A+1) def render_mv(mv,turn=0): if mv==0:return'(none)' A,B=mv>>8,mv&63;C=' ' if B<8 and board[A]|8==_P+8:C=mapping[(mv>>6&3)+1] if turn==1:A,B=63-A,63-B return render(A)+render(B)+C def can_kill_king(mv,ccheck=True): C=ccheck;global board,pscore,wc_bc_ep_kp;D=pscore;A=wc_bc_ep_kp if mv!=0:E=move(mv) else:rotate() B=gen_moves(ccheck=C) if mv!=0:reverse();pscore=D;wc_bc_ep_kp,A=A,wc_bc_ep_kp;restore(mv,E) else:rotate() if len(B)==0:return False if B[0]&16383==0:return True if C:return any(abs((B&63)-(A&255))<2 for B in B) return False def threefold():global history;return history.count(ghash())>=3 def g_trn():return wc_bc_ep_kp>>20 pscore,wc_bc_ep_kp=0,int.from_bytes(b'\x0f\x80\x80','big') history=list() mapping='PNBRQK. pnbrqk. ' print('Please run usunfish_chess.py')