# More games at ti84calcwiz.com
Ab='YOU %d  CPU %d  TIE %d'
Aa='CHECKERS'
AZ='HOW TO PLAY'
AY='_capvals'
AE='win'
AD='lose'
AC='piece'
AB='promo'
u=bool
k='draw'
j='nomove'
i=Exception
Y='cur'
X='last'
W='path'
T=list
S=set
Q='quit'
P='grid'
O='caps'
N=len
K='sel'
J=False
I=True
F='targets'
E=None
D=range
try:import ti_draw as A,ti_system as d,gc,time as v;w=I
except ImportError:w=J
import random as AF
B=0
L,e=1,-1
B0,B1=1,2
AG,l=1,2
AH,x=-1,-2
AI=(-1,-1),(-1,1),(1,-1),(1,1)
def R(p):return L if p>0 else e if p<0 else 0
def U(p):return p==l or p==x
def AJ(side):return((-1,-1),(-1,1))if side>0 else((1,-1),(1,1))
def AK(p):return AI if U(p)else AJ(R(p))
def AL():
	C=[[B]*8 for A in D(8)]
	for A in D(8):
		for E in D(8):
			if(A+E)%2==1:
				if A<3:C[A][E]=AH
				elif A>4:C[A][E]=AG
	return C
def B2(r,c):return 0<=r<8 and 0<=c<8 and(r+c)%2==1
def m(path,caps,promo,piece):return{W:path,O:caps,AB:promo,AC:piece}
def n(g,r,c):
	A=g[r][c]
	if A==B:return[]
	K=R(A);E=[]
	for(F,G)in AK(A):
		H,I,C,D=r+F,c+G,r+2*F,c+2*G
		if not(0<=C<8 and 0<=D<8):continue
		if g[C][D]!=B:continue
		J=g[H][I]
		if J!=B and R(J)!=K:E.append((C,D,H,I))
	return E
def y(g,r,c):
	D=g[r][c]
	if D==B:return[]
	E=[]
	for(F,G)in AK(D):
		A,C=r+F,c+G
		if 0<=A<8 and 0<=C<8 and g[A][C]==B:E.append((A,C))
	return E
def z(side):return 0 if side>0 else 7
def Ac(g,sr,sc):
	C=g[sr][sc]
	if C==B:return[]
	F=R(C);G=[];H=[(sr,sc,[(sr,sc)],[],U(C))]
	while H:
		N,O,P,E,K=H.pop();Z=S(E);a=AI if K else AJ(F);Q=J
		for(T,V)in a:
			L,M,A,D=N+T,O+V,N+2*T,O+2*V
			if not(0<=A<8 and 0<=D<8):continue
			if not(g[A][D]==B or(A,D)==(sr,sc)):continue
			if(L,M)in Z:continue
			W=g[L][M]
			if W==B or R(W)==F:continue
			b=not K and A==z(F);X=P+[(A,D)];Y=E+[(L,M)]
			if b:G.append(m(X,Y,I,C))
			else:H.append((A,D,X,Y,K))
			Q=I
		if not Q and E:G.append(m(P,E,J,C))
	return G
def Z(g,side):
	F=side;G=[]
	for C in D(8):
		for E in D(8):
			A=g[C][E]
			if A!=B and R(A)==F:
				H=Ac(g,C,E)
				if H:G.extend(H)
	if G:return G
	I=[]
	for C in D(8):
		for E in D(8):
			A=g[C][E]
			if A!=B and R(A)==F:
				for(J,K)in y(g,C,E):L=not U(A)and J==z(F);I.append(m([(C,E),(J,K)],[],L,A))
	return I
def AM(g,side):
	for A in D(8):
		for C in D(8):
			E=g[A][C]
			if E!=B and R(E)==side and n(g,A,C):return I
	return J
def A0(g,m):
	C=m[W];D,E=C[0];I,J=C[-1];A=g[D][E];g[D][E]=B;F=[]
	for(G,H)in m[O]:F.append(g[G][H]);g[G][H]=B
	m[AY]=F
	if m[AB]:A=l if A>0 else x
	g[I][J]=A
def AN(g,m):
	A=m[W];C,D=A[0];E,F=A[-1];g[E][F]=B;g[C][D]=m[AC]
	for((G,H),I)in zip(m[O],m[AY]):g[G][H]=I
def B3(g,side):return u(Z(g,side))
def AO(g):
	A=B=0
	for D in g:
		for C in D:
			if C>0:A+=1
			elif C<0:B+=1
	return A,B
f=100000
o=[0]
AP=[0]
Ad=8
class AQ(i):pass
def Ae(g):
	A=0;E=F=0
	for C in D(8):
		for G in D(8):
			H=g[C][G]
			if H==B:continue
			I=1 if 2<=C<=5 and 2<=G<=5 else 0;J=1 if G==0 or G==7 else 0
			if H==AG:
				E+=1;A+=100+(7-C)*5+I*2
				if C==7:A+=8
			elif H==l:E+=1;A+=180+I*8-J*6
			elif H==AH:
				F+=1;A-=100+C*5+I*2
				if C==0:A-=8
			else:F+=1;A-=180+I*8-J*6
	K=E-F
	if K:A+=K*(24-E-F)
	return A
def AR(g,side,depth,a,b,ply):
	E=depth;D=ply;C=side;o[0]+=1
	if o[0]>AP[0]:raise AQ()
	A=Z(g,C)
	if not A:return-(f-D)
	F=u(A[0][O])
	if D>=Ad or E<=0 and not F:return C*Ae(g)
	if F and N(A)>1:A.sort(key=lambda m:-N(m[O]))
	B=-f*2
	for G in A:
		A0(g,G);H=-AR(g,-C,E-1,-b,-a,D+1);AN(g,G)
		if H>B:B=H
		if B>a:a=B
		if a>=b:break
	return B
def Af(g,side,depth):
	A=Z(g,side)
	if not A:return
	if A[0][O]and N(A)>1:A.sort(key=lambda m:-N(m[O]))
	F=-f*2;C=[];D=-f*2
	for E in A:
		A0(g,E);B=-AR(g,-side,depth-1,-f*2,-D,1);AN(g,E);C.append((B,E))
		if B>F:F=B
		if B>D:D=B
	G=max(A for(A,B)in C);return[B for(A,B)in C if A==G]
def Ag(g,side,max_depth,budget,rng,blunder=.0):
	G=blunder;F=budget;C=rng;B=Z(g,side)
	if not B:return
	if G>0 and C.randint(0,99)<int(G*100):return B[C.randint(0,N(B)-1)]
	if w:gc.collect()
	K=[A[:]for A in g];A=E
	try:
		for L in D(1,max_depth+1):
			o[0]=0;AP[0]=F
			try:H=Af(g,side,L)
			except(AQ,RuntimeError):break
			if H:A=H
			if o[0]>F:break
	finally:
		for I in D(8):
			M,O=g[I],K[I]
			for J in D(8):M[J]=O[J]
	if not A:A=B
	P=A[C.randint(0,N(A)-1)]if A and A[0]else E;return P
if w:
	def A1(k):
		try:return int(k)
		except(ValueError,TypeError):return 0
	A2,p,q,g,A3=25,34,24,26,105;A4=45,
	def r():
		while A1(d.get_key(0))!=0:pass
		while I:
			A=A1(d.get_key(0))
			if A!=0:
				while A1(d.get_key(0))!=0:pass
				return A
	M,a=A.get_screen_dim();s=24;G=min(M//8,(a-s)//8);Ah=(M-G*8)//2;Ai=s+(a-s-G*8)//2;A5=G//2-3;A6=232,214,178;AS=128,92,58;Aj=168,150,70;Ak=150,120,70;A7,Al=(208,58,48),(120,22,16);A8,Am=(56,58,66),(150,152,165);h=240,200,70;An=70,190,90;Ao=255,226,40;b=18,22,30
	def C(col):B=col;A.set_color(B[0],B[1],B[2])
	def c(st,r,c):
		H=st;D,E=Ah+c*G,Ai+r*G;N=(r+c)%2==0
		if H.get(K)==(r,c):L=Aj
		elif(r,c)in H.get(X,()):L=Ak if not N else A6
		else:L=A6 if N else AS
		C(L);A.fill_rect(D,E,G,G);M=H[P][r][c]
		if M!=B:
			I,J=D+G//2,E+G//2;O,Q=(A7,Al)if M>0 else(A8,Am);C(Q);A.fill_circle(I,J,A5);C(O);A.fill_circle(I,J,A5-2)
			if U(M):C(h);A.draw_circle(I,J,A5-4);A.fill_circle(I,J,2)
		if(r,c)in H.get(F,{}):C(An);A.fill_circle(D+G//2,E+G//2,4)
		if H.get(Y)==(r,c):C((10,10,14));A.draw_rect(D+1,E+1,G-3,G-3);A.draw_rect(D+2,E+2,G-5,G-5);C(Ao);A.draw_rect(D+3,E+3,G-7,G-7)
	def AT(st):
		C(b);A.fill_rect(0,0,M,a)
		for B in D(8):
			for E in D(8):c(st,B,E)
	def V(st,cells):
		for(A,B)in cells:
			if 0<=A<8 and 0<=B<8:c(st,A,B)
	t=[E]
	def A9(msg,sub=E):
		D=msg;B=sub
		if t[0]==(D,B):return
		t[0]=D,B;C((28,34,48));A.fill_rect(0,0,M,s);C((235,238,248));A.draw_text(6,22,D)
		if B:E=M-(N(B)*10-2)-6;C((150,190,235));A.draw_text(E,22,B)
	def Ap(r,c,key):
		A=key
		if A==A2:r=max(0,r-1)
		elif A==p:r=min(7,r+1)
		elif A==q:c=max(0,c-1)
		elif A==g:c=min(7,c+1)
		return r,c
	def AU(st,side):
		A=st;C=A[P];M=Z(C,side)
		if not M:return j,J
		X=S(A[W][0]for A in M);a=u(M[0][O]);A[K]=E;A[F]={};N=J;b=J
		while I:
			G=r()
			if G in A4:
				if A[K]is not E and not N:D=[A[K]]+T(A[F].keys());A[K]=E;A[F]={};V(A,D);continue
				if A[K]is E:return Q,J
				continue
			if G in(A2,p,q,g):D=A[Y];A[Y]=Ap(D[0],D[1],G);V(A,[D,A[Y]]);continue
			if G!=A3:continue
			B=A[Y]
			if A[K]is E:
				if B in X:
					A[K]=B
					if a:A[F]={(A,B):(C,D)for(A,B,C,D)in n(C,*B)}
					else:A[F]={A:E for A in y(C,*B)}
					V(A,[B]+T(A[F].keys()))
				continue
			if B in A[F]:
				h=T(A[F].keys());c=A[F][B];H=A[K];R=C[H[0]][H[1]];d=not U(R)and B[0]==z(side);L=[c]if c else[];i=m([H,B],L,d,R);A0(C,i);e=[H,B]+L+h
				if L or not U(R):b=I
				f=n(C,B[0],B[1])if L and not d else[];A[K]=E;A[F]={}
				if f:A[K]=B;A[F]={(A,B):(C,D)for(A,B,C,D)in f};N=I;V(A,e+T(A[F].keys()));continue
				V(A,e);return'moved',b
			if B in X and not N:
				D=[A[K]]+T(A[F].keys());A[K]=B
				if a:A[F]={(A,B):(C,D)for(A,B,C,D)in n(C,*B)}
				else:A[F]={A:E for A in y(C,*B)}
				V(A,D+[B]+T(A[F].keys()))
	def Aq(t):
		try:v.sleep(t)
		except i:
			A=v.monotonic()+t
			while v.monotonic()<A:pass
	Ar=.32
	def As(st,m):
		A=st;C=A[P];E=m[W];R=S(m[O]);H,I=E[0];M=C[H][I];C[H][I]=B;c(A,H,I)
		for J in D(1,N(E)):
			T,U=E[J-1];F,G=E[J];Q=J==N(E)-1;C[F][G]=(l if M>0 else x)if Q and m[AB]else M;c(A,F,G);K,L=(T+F)//2,(U+G)//2
			if(K,L)in R:C[K][L]=B;c(A,K,L)
			if not Q:Aq(Ar);C[F][G]=B;c(A,F,G)
	def At(st,side,max_depth,budget,blunder,rng):
		B=st;C=B[P]
		if not Z(C,side):return j,J
		A9('CPU thinking...',E);A=Ag(C,side,max_depth,budget,rng,blunder)
		if A is E:return j,J
		D=u(A[O])or not U(A[AC]);As(B,A);B[X]=S([A[W][0],A[W][-1]]);V(B,T(B[X]));return'moved',D
	AV='CHKREC'
	def Au():
		try:A=[int(A)for A in T(d.recall_list(AV))];return(A+[0,0,0])[:3]
		except i:return[0,0,0]
	def Av(v):
		try:d.store_list(AV,[float(A)for A in v])
		except i:pass
	def H(y,txt,col=(235,238,248)):C(col);A.draw_text((M-(N(txt)*10-2))//2,y,txt)
	def Aw():
		C(b);A.fill_rect(0,0,M,a);H(24,AZ,h);D='Move diagonally to an empty','dark square.','JUMP an enemy to the free','square just past it = capture.','Capturing is FORCED: if you','can jump, you MUST.','Multi-jumps chain in one turn.','Reach the far row -> KING,','which moves both directions.','Win: capture or trap all foes.';C((222,226,235));B=42
		for E in D:A.draw_text(8,B,E);B+=16
		H(206,'any key = back',(140,150,180));r()
	AA=[('EASY',2,450,.6),('MEDIUM',3,450,.22),('HARD',3,450,.0)]
	def Ax(rec,mode,di):
		G=rec;E=di;B=mode
		def K():
			C(b);A.fill_rect(0,0,M,a);B,J,E=18,(M-72)//2,20
			for F in D(4):
				for I in D(4):C(A6 if(F+I)%2==0 else AS);A.fill_rect(J+I*B,E+F*B,B,B)
			for(F,I,K)in((3,0,A7),(3,2,A7),(0,1,A8),(0,3,A8)):C(K);A.fill_circle(J+I*B+B//2,E+F*B+B//2,6)
			H(E+98,Aa,h)
			if G[0]or G[1]or G[2]:H(E+120,Ab%tuple(G),(200,205,225))
		def L(di):C(b);A.fill_rect(0,166,M,15);H(184,'DIFFICULTY:  '+AA[di][0],h)
		def J(mode,di):
			C(b);A.fill_rect(0,143,M,66)
			if mode==0:H(164,'1 PLAYER',(220,226,242));L(di);H(204,'L/R:mode  U/D:level  ENTER:go',(125,155,195))
			elif mode==1:H(170,'2 PLAYERS',(220,226,242));H(196,'L/R:mode      ENTER:go',(125,155,195))
			else:H(170,AZ,(220,226,242));H(196,'L/R:mode      ENTER:read',(125,155,195))
		K();J(B,E)
		while I:
			F=r()
			if F in A4:return
			elif F in(q,g):B=(B+(1 if F==g else-1))%3;J(B,E)
			elif F in(A2,p)and B==0:E=(E+(1 if F==p else-1))%N(AA);L(E)
			elif F==A3:
				if B==2:Aw();K();J(B,E);continue
				return B,E
	def AW(title_txt,rec,show_rec):
		C(b);A.fill_rect(0,0,M,a);H(50,Aa,h);H(84,title_txt,(245,245,250))
		if show_rec:H(112,Ab%tuple(rec),(200,205,225))
		H(146,'ENTER = play again',(150,160,195));H(168,'<- -> menu',(150,160,195));H(190,'CLEAR = quit',(150,160,195))
		while I:
			B=r()
			if B==A3:return'again'
			if B in(q,g):return'menu'
			if B in A4:return Q
	AX=80
	def Ay(di,rng):
		A={P:AL(),Y:(5,0),K:E,F:{},X:S()};t[0]=E;AT(A);H,J,M,N=AA[di];C=0;B=L
		while I:
			O,R=AO(A[P])
			if B==L:T=AM(A[P],L);A9('YOUR MOVE - JUMP!'if T else'YOUR MOVE','%s  R%d B%d'%(H,O,R));D,G=AU(A,L)
			else:D,G=At(A,e,J,M,N,rng)
			if D==Q:return Q
			if D==j:return AD if B==L else AE
			C=0 if G else C+1
			if C>=AX:return k
			A[X]=S()if B==L else A.get(X,S());B=e if B==L else L
	def Az(rng):
		B={P:AL(),Y:(5,0),K:E,F:{},X:S()};t[0]=E;AT(B);C=0;A=L
		while I:
			H,J=AO(B[P]);D='RED TO MOVE'if A==L else'WHITE TO MOVE'
			if AM(B[P],A):D+=' - JUMP!'
			A9(D,'R%d W%d'%(H,J));G,M=AU(B,A)
			if G==Q:return Q
			if G==j:return'red'if A==e else'white'
			C=0 if M else C+1
			if C>=AX:return k
			A=e if A==L else L
	def A_():
		N='DRAW';F=AF
		try:F=AF.Random()
		except i:pass
		C=Au();G,H=0,1
		while I:
			M=Ax(C,G,H)
			if M is E:break
			G,H=M;D=I
			while D:
				if G==0:
					B=Ay(H,F)
					if B==Q:D=J;continue
					C[{AE:0,AD:1,k:2}[B]]+=1;Av(C);K={AE:'YOU WIN!',AD:'CPU WINS',k:N}[B];L=AW(K,C,I)
				else:
					B=Az(F)
					if B==Q:D=J;continue
					K={'red':'RED WINS!','white':'WHITE WINS!',k:N}[B];L=AW(K,C,J)
				if L==Q:D=J
				elif L=='menu':D=J
		A.clear()
	A_()