|
<Grundy number>
Grundy number, written as Gi,j, is associated with any game board including Chess. It plays an important role in combinatorial games such as 'Corner the Queen', next. If we make the following definitions
the Grundy number is given by
where mex(S) is minimum excluded element of the set S and 'move p' means moving p closer to the corner (origin) in one of three ways: along i-axis, along j-axis, and along an inclined line of 45°.
|
<Task>
The task is to calculate Gi,j for all (i,j) of the given board. A strategy is suggested in queen2 (in Japanese). First we must realize that the equation in left is that for Gi,j's and that their values can be obtained quickly if p is chosen in appropriate order: The closer it is to the origin and diagonal, the earlier it is dealt with.
|
| ＜Python (Object Oriented Programming)＞
[Main] Main_CornerTheQueen.py
# Corner The Queen, 8-25-2023
from scipy import *
import numpy as np
import matplotlib.pyplot as plt
import CornerTheQueen as CQ
print('\x1b[38;2;5;86;243m'+'Queen'+'\x1b[0m') #blue
print('\x1b[38;2;255;0;0m'+'Queen'+'\x1b[0m') #red
print()
isDn = False
pr = CQ.calcGrundy(9)
print(pr)
print()
pr.outGr(isDn)
[Module] CornerTheQueen.py
# Corner The Queen, 8-25-2023
# gives Grundy numbers for the game of "Corner The Queen"
import numpy as np
boardSize = 31
maxMember = 2*boardSize
toChk = False
def intToStr(i,n):
s = str(i)
le = len(s)
while le<n:
s = " " + s
le += 1
return s
def sumLists(a, b, c):
p=[]
for q in a:
p.append(q)
for q in b:
p.append(q)
for q in c:
p.append(q)
p.sort()
return p
def mex(gList):
wList = []
for i in range(maxMember):
wList.append(i)
if toChk:
print('wholeList=',wList)
for p in gList:
if wList.count(p)>0:
wList.remove(p)
else:
if toChk:
print(p," is not in list")
if toChk:
print('work list=',wList)
k = 0
while(True):
if wList.count(k)>0: # print('min=',k)
break
k += 1
if k>maxMember:
k=-1 # strange result!
break
return k
class calcGrundy:
def __init__(self, N):
self.Gr = np.zeros((boardSize,boardSize),dtype=int)
self.N = N
def moveH(x,y):
mySet = []
for xx in range(x):
mySet.append(self.Gr[xx,y])
return mySet
def moveV(x,y):
mySet = []
for yy in range(y):
mySet.append(self.Gr[x,yy])
return mySet
def moveT(x,y):
mySet = []
tn = min(x,y)
for tt in range(tn):
mySet.append(self.Gr[x-tn+tt,y-tn+tt])
return mySet
for z in range(N):
self.Gr[z,0] = z
self.Gr[0,z] = z
######## Execution starts here ########
for n in range(N-1):
nn = n + 1 # nn=1..N-1
for x in range(nn):
xSet
= sumLists(moveH(x,nn), moveV(x,nn), moveT(x,nn))
self.Gr[x,nn] = mex(xSet)
for y in range(nn):
ySet
= sumLists(moveH(nn,y), moveV(nn,y), moveT(nn,y))
self.Gr[nn,y] = mex(ySet)
tSet
= sumLists(moveH(nn,nn), moveV(nn,nn), moveT(nn,nn))
self.Gr[nn,nn] = mex(tSet)
####### Execution finished here ########
####### Output of Grundy values ########
print('Grundy values for board size = ', N)
for j in range(N):
for i in range(N):
print(" ",self.Gr[i,j],end="")
print()
print()
######## End of Grundy value out ########
######## Methods ##########
def outGr(self,isDn):
sR0 = '\x1b[38;2;255;0;0m'
sR1 = '\x1b[0m'
print('Grundy values for board size = ', self.N)
print('----------------------------------------')
def printArray(j):
print(intToStr(j,3),"] ", end="")
for i in range(self.N):
w = self.Gr[i,j]
s = intToStr(w,3)
if w==0:
s = sR0 + s + sR1
print(s,end="")
print()
if isDn:
print(' ',end="")
for i in range(self.N):
s = intToStr(i,3)
print(s,end="")
print()
print('----------------------------------------')
for j in range(self.N):
printArray(j)
else:
for j in range(self.N):
jj=self.N - 1 - j
printArray(jj)
print('----------------------------------------')
print(' ',end="")
for i in range(self.N):
s = intToStr(i,3)
print(s,end="")
print()
|
<Modula-2 (Structured Programming)>
[MAIN] CornerTheQueen.MOD
･･･
BEGIN
openTextWin(W1,'Graphic Application');
initXDSgraph(_big);
prepareWholeSet();
WrStr(' Calculating Grundy values for maximum board size, ');
WrInt(_boardSize,1); WrLn;
initGrundy(Gr);
calcGrundy(Gr);
listOfZeros();
･･･
[SUB] SubQueenGame.MOD
PROCEDURE mex(Set: gSetTp): INTEGER;
VAR
i: INTEGER;
BEGIN
prepareWholeSet();
minComplementSet(Set,i);
RETURN i;
END mex;
PROCEDURE moveH(x,y: INTEGER): gSetTp;
VAR
xx: INTEGER;
mySet : gSetTp;
BEGIN
mySet := gSetTp{};
FOR xx:=0 TO x-1 DO
INCL(mySet, Gr[xx,y]);
END;
RETURN mySet;
END moveH;
PROCEDURE moveV(x,y: INTEGER): gSetTp;
VAR
yy: INTEGER;
mySet : gSetTp;
BEGIN
mySet := gSetTp{};
FOR yy:=0 TO y-1 DO
INCL(mySet, Gr[x,yy]);
END;
RETURN mySet;
END moveV;
PROCEDURE moveT(x,y: INTEGER): gSetTp;
VAR
tt,tn : INTEGER;
mySet : gSetTp;
BEGIN
mySet := gSetTp{};
tn := min(x,y);
FOR tt:= 0 TO tn-1 DO
INCL(mySet, Gr[x-tn+tt,y-tn+tt]);
END;
RETURN mySet;
END moveT;
PROCEDURE calcGrundy(VAR Gr: grundyTp);
VAR
x,y,z,n,xx,yy,N: INTEGER;
mySet : gSetTp;
BEGIN
N := _boardSize;
Gr[0,0]:= 0;
numA:= 0; numB:= 0;
FOR n:=1 TO N-1 DO (* circumference*)
FOR x:=0 TO n-1 DO
mySet := moveH(x,n) + moveV(x,n) + moveT(x,n);
Gr[x,n]:= mex(mySet);
IF Gr[x,n]=0 THEN
IF x<n THEN
zeroA[numA].x:= x; zeroA[numA].y:= n; INC(numA);
ELSE
zeroB[numB].x:= x; zeroB[numB].y:= n; INC(numB);
END;
END;
END;
FOR y:=0 TO n-1 DO
mySet := moveH(n,y) + moveV(n,y) + moveT(n,y);
Gr[n,y]:= mex(mySet);
IF Gr[n,y]=0 THEN
IF n<y THEN
zeroA[numA].x:= n; zeroA[numA].y:= y; INC(numA);
ELSE
zeroB[numB].x:= n; zeroB[numB].y:= y; INC(numB);
END;
END;
mySet := moveH(n,n) + moveV(n,n) + moveT(n,n);
Gr[n,n]:=mex(mySet);
IF Gr[n,n]=0 THEN
WinAuxIO.hitKey('Zero in diagonal posision, OK?');
END;
END;
END calcGrundy;
|
