To run the program on your machine, you will need to have an installation of Python and the files checkers.py, cpl.g, yapps2.py, and yappsrt.py.
Now on to the program:
checkers.py"""Strachey's Checkers program from 1966
There are four parts to this program:
(1) Strachey's checkers program in CPL:
OriginalCPLprogram is the original program, verbatim
ModifiedCPLprogram fixes a typo and two small conceptual problems
(2) A parser for the CPL language. This is encoded in the external
file 'cpl.g', which is then processed by yapps2.py to produce cpl.py,
which we then import, allowing us to use cpl.parse on ModifiedCPLprogram.
(3) Functions described but not implemented by Strachey (such as Null and Shift).
(4) Variable definitions and functions not listed by Strachey.
(5) Test cases.
"""
(1) Strachey's checkers program in CPL
OriginalCPLprogram = """
ChosenPosition(P) = value of
§ let L = LegalPositionsFrom(P)
if Null(L) then Resign
let (p,v) = BestPosition(NIL, - ∞,L,0)
result is p §
BestPosition(P,V,L,d) = Null(L) → (P,V), value of
§ let (p, l) = Next(L)
let v = - PositionValue(p,d + 1)
result is (v > V) → BestPosition(p,v,l,d),
BestPosition(P,V,l,d) §
PositionValue(P,d) = Terminal(P,d) → TerminalValue(P), value of
§ let L = LegalPositionsFrom(P)
let (p,v) = BestPosition(NIL,- ∞,L,d)
result is v §
LegalPositionsFrom(P) = value of
§ let L = RemainingPositionList(P,Capture,5)
result is Null(L)→RemainingPositionList(P,NonCapture,5),L §
RemainingPositionList(P,C,s) =
PartialPositionList(P,C,s,FindMoveList(P,C,s))
PartialPositionList(P,C,s,L) =
Null(L)→( (s = -5)→NIL,
RemainingPositionList(P,C,NextMoveDirection(s) ),
value of
§ let Φ = SingleDigitFrom(L)
let Ip = MakeMove(P,C,s,Φ)
let l = (C = Capture)→CaptureTree(Ip),
FinalPosition(Ip)
result is Join(l,PartialPositionList(P,C,s, L - Φ))§
NextMoveDirection(s) = (s = 5) → 4, ( (s = 4) → - 4, -5)
FindMoveList(P,C,s) = value of
§ let (X,Y,K,σ) = P
let Empty = ~ X ∧ ~ Y ∧ Board
let ψ = (C = Capture) → (Shift(Empty,σs) ∧ Y), Empty
let Φ = Shift(ψ, σs) ∧ X
result is (s > 0) → Φ, Φ ∧ K §
MakeMove(P,C,s,Φ) = value of
§ let (X,Y,K,σ) = P
let ψ = (C = Capture) → Shift(Φ, - σs), NIL
let θ = (C = Capture) → Shift(ψ, - σs),
Shift(Φ, - σs)
let Xk = Null(Φ ∧ K) → (θ ∧ LastRows), (θ - Φ)
result is ((X - Φ + θ), (Y - ψ), (K - ψ ∧ K + Xk),σ,θ)§
FinalPosition(Ip) = value of
§ let (X,Y,K,σ,Φ) = Ip
result is (Y,X,K, - σ)§
CaptureTree(Ip) = value of
§ let L = PartialCapturePositionList(Ip)
result is Null(L) → (FinalPosition(Ip) ),
CombineCaptureTrees(L) §
PartialCapturePositionList(Ip) = value of
§ let (X,Y,K,σ,Φ) = Ip
let P = (X,Y,K,σ)
result is MinList(PCP(P,Φ,5),PCP(P,Φ,4),
PCP(P,Φ ∧ K, - 4), PCP(P,Φ ∧ K, - 5) )§
PCP(P,Φ,s) = value of
§ let (X,Y,K,σ) = P
let ψ = Shift(Φ, - σs) ∧ Y
let Empty = ~ X ∧ ~ Y ∧ Board
let θ = Shift(ψ, - σs) ∧ Empty
let Xk = Null(Φ ∧ K) → (θ ∧ LastRows), (θ - Φ)
result is Null(θ) → NIL,
((X - Φ + θ),(Y - ψ),(K - ψ ∧ K + Xk),σ,θ)§
CombineCaptureTrees(L) = Null(L) → NIL, value of
§ let (Ip,l) = Next(L)
result is Join(CaptureTree(Ip),CombineCaptureTrees(l) )§
""" I couldn't get the program above to run. Below is a slightly modified version. I added one missing parenthesis, changed one instance of NIL to Zero, and modified the handling of kings.
ModifiedCPLprogram = """
ChosenPosition(P) = value of
§ let L = LegalPositionsFrom(P)
if Null(L) then Resign
let (p,v) = BestPosition(NIL, - ∞,L,0)
result is p §
BestPosition(P,V,L,d) = Null(L) → (P,V), value of
§ let (p, l) = Next(L)
let v = - PositionValue(p,d + 1)
result is (v > V) → BestPosition(p,v,l,d),
BestPosition(P,V,l,d) §
PositionValue(P,d) = Terminal(P,d) → TerminalValue(P), value of
§ let L = LegalPositionsFrom(P)
let (p,v) = BestPosition(NIL,- ∞,L,d)
result is v §
LegalPositionsFrom(P) = value of
§ let L = RemainingPositionList(P,Capture,5)
result is Null(L)→RemainingPositionList(P,NonCapture,5),L §
RemainingPositionList(P,C,s) =
PartialPositionList(P,C,s,FindMoveList(P,C,s))
PartialPositionList(P,C,s,L) =
Null(L)→( (s = -5)→NIL,
RemainingPositionList(P,C,NextMoveDirection(s) )), ## added )
value of
§ let Φ = SingleDigitFrom(L)
let Ip = MakeMove(P,C,s,Φ)
let l = (C = Capture)→CaptureTree(Ip),
FinalPosition(Ip)
result is Join(l,PartialPositionList(P,C,s, L - Φ))§
NextMoveDirection(s) = (s = 5) → 4, ( (s = 4) → - 4, -5)
FindMoveList(P,C,s) = value of
§ let (X,Y,K,σ) = P
let Empty = ~ X ∧ ~ Y ∧ Board
let ψ = (C = Capture) → (Shift(Empty,σs) ∧ Y), Empty
let Φ = Shift(ψ, σs) ∧ X
result is (s > 0) → Φ, Φ ∧ K §
MakeMove(P,C,s,Φ) = value of
## changed NIL to Zero in ψ modified kings in Xk and result
§ let (X,Y,K,σ) = P
let ψ = (C = Capture) → Shift(Φ, - σs), Zero
let θ = (C = Capture) → Shift(ψ, - σs),
Shift(Φ, - σs)
let Xk = Null(Φ ∧ K) → (θ ∧ LastRows), θ
result is ((X - Φ + θ), (Y - ψ), (K - ψ - Φ + Xk),σ,θ)§
FinalPosition(Ip) = value of
§ let (X,Y,K,σ,Φ) = Ip
result is (Y,X,K, - σ)§
CaptureTree(Ip) = value of
§ let L = PartialCapturePositionList(Ip)
result is Null(L) → (FinalPosition(Ip) ),
CombineCaptureTrees(L) §
PartialCapturePositionList(Ip) = value of
§ let (X,Y,K,σ,Φ) = Ip
let P = (X,Y,K,σ)
result is MinList(PCP(P,Φ,5),PCP(P,Φ,4),
PCP(P,Φ ∧ K, - 4), PCP(P,Φ ∧ K, - 5) )§
PCP(P,Φ,s) = value of
## modified kings in Xk and result
§ let (X,Y,K,σ) = P
let ψ = Shift(Φ, - σs) ∧ Y
let Empty = ~ X ∧ ~ Y ∧ Board
let θ = Shift(ψ, - σs) ∧ Empty
let Xk = Null(Φ ∧ K) → (θ ∧ LastRows), (θ - Φ)
result is Null(θ) → NIL,
((X - Φ + θ),(Y - ψ),(K - ψ - Φ + Xk),σ,θ)§
CombineCaptureTrees(L) = Null(L) → NIL, value of
§ let (Ip,l) = Next(L)
result is Join(CaptureTree(Ip),CombineCaptureTrees(l) )§
"""(2) A parser for the CPL language I used the YAPPS2 parser-generator system to create a translator that converts CPL code into Python. Once you have downloaded YAPPS2, here is what you need to generate a CPL translator, translate Strachey's CPL program into Python, and load the Python code:
def convert_cpl(program):
"Return Python code (as text); you can exec the result."
import yapps2
yapps2.generate('cpl.g')
import cpl
reload(cpl)
return cpl.parse('program', program + " //EOF")
exec convert_cpl(ModifiedCPLprogram)
And here is the contents of the CPL grammar, from the file cpl.g:
def convert(x, table={'=':'==', '∨':'|', '∧':'&', ':=':'='}):
if x in table: return table[x]
if x.startswith('&') and x.endswith(';'): return x[1:-1]
return x
%%
parser cpl:
ignore: '\\s+|#.*'
token NUM: '[0-9]+'
token ID: '[a-z]|[A-Z][a-zA-Z0-9_]*|&(theta|psi|Phi|sigma|infin);'
token OP: '[-+*/=><]|∨|∧'
token UNARY: '[-+~]'
token RARR: '→'
token SECT: '§'
token STR: '"([^\\"]+|\\\\.)*"'
rule program: {{defs = []}}
(ID arglist "=" expr
{{defs.append("def " + ID + arglist + ":\n return " + expr)}})+
'//EOF' {{return '\n'.join(defs)}}
rule expr: "value" "of" SECT expr SECT {{return expr}}
| "result" "is" expr {{return expr}}
| "let" lhs "=" expr {{e1 = expr}} expr
{{return '(lambda %s=%s:\n %s)()' % (lhs, e1, expr)}}
| "if" expr {{e1 = expr}} "then" expr {{e2 = expr}} expr
{{return e2 + " if " + e1 + " else " + expr}}
| UNARY expr {{return UNARY + expr}}
| factor (OP expr {{factor += convert(OP) + expr}})*
[RARR expr {{e2 = expr}} "," expr
{{return '('+e2+' if '+factor+' else '+expr+')'}}]
{{return factor}}
rule lhs: ID {{return convert(ID)}}
| arglist {{return arglist}}
rule factor: STR {{return repr(STR)}}
| NUM {{return convert(NUM)}}
| ID {{id = convert(ID)}}
( ID {{id += '*' + convert(ID)}} )* ## implicit multiplication
[arglist {{id += arglist}}] ## function call
{{return id}}
| arglist {{return arglist}}
rule arglist: "[(]" {{e = []}}
( expr {{e.append(expr)}} [","])*
"[)]" {{return "(" + ', '.join(e) + ")"}}
(3) Functions described but not implemented by Strachey Strachey describes three classes of utility programs. Here are my implementations. Note that the brief descriptions Strachey gives are often wrong; I have documented each function with the correct description. (For example, the function Null does not just test for the empty list, it also tests for the empty bit string.)
## (a) List Functions
def Null(L):
"True if L is the empty list, or the zero bit string, or other 'not' value."
return not L
def Next(L):
"A tuple of the head and the tail of the list L."
return L[0], L[1:]
def Join(L1, L2):
"A single list from the elements of L1 (which can be a list or an element) and L2."
if not isinstance(L1, list): L1 = [L1]
return L1 + L2
def MinList(*items):
"Append all items, remove duplicates, don't include Nulls."
# I sorted to make the result be deterministic
return list(sorted(set(x for x in items if not Null(x))))
## (b) Bit-String Functions
class Logical(object):
"Class to represent logical bitstrings."
def __init__(self, v): self.v = (sum(1 << i for i in v) if isinstance(v, list) else int(v))
def __repr__(self): return 'Logical(%s)' % [b for b in range(64) if self & (1 << b)]
def __int__(self): return self.v
def __and__(self, y): return Logical(self.v & int(y))
def __or__(self, y): return Logical(self.v | int(y))
def __add__(self, y): return Logical(self.v | int(y))
def __sub__(self, y): return Logical(self.v & ~int(y))
def __neg__(self): return Logical(-self.v)
def __eq__(self, y): return isinstance(y, Logical) and self.v == y.v
def __cmp__(self, y): return cmp(self.v, int(y))
def __invert__(self): return Logical(~self.v)
def __nonzero__(self): return self.v != 0
def __getitem__(self, i):return 1 if (self.v & 1 << i) else 0
def SingleDigitFrom(x):
"Return a bit string with a single 1 in a position where x has a 1."
return x & -x
def Shift(x, n):
"x shifted n places to the right (or left if n < 0)."
return Logical(int(x) >> n if (n>0) else int(x) << -n)
def BitCount(x):
"The number of 1 bits in x."
x = int(x)
return 0 if x == 0 else 1 + BitCount(x - SingleDigitFrom(x))
## (c) Strategy Functions
def Terminal(P, d):
"P is terminal if depth exceeds DepthLimit or player has no moves or opponent has no pieces."
(X,Y,K,sigma) = P
return d > DepthLimit or not any(LegalPositionsFrom(P)) or Y == Zero
def TerminalValue(P):
"""You lose if you can't make a move; win if opponent pieces are gone;
otherwise count up the pieces (4 points for a King)."""
(X,Y,K,sigma) = P
def playercount(Z): return BitCount(Z) + 4 * BitCount(Z&K)
return (-infin if not any(LegalPositionsFrom(P)) else
+infin if Y == Zero else
playercount(X) - playercount(Y))
(4) Variable definitions and functions not listed by Strachey First we show the variables that are needed for representing positions and playing a game.
We introduce a simple function PrintPosition for showing the board. In a real game we would have a fancier, prettier format for output and for the input of moves.
We also introduce a function to play a game of checkers; Strachey never quite got around to that, although once you have the ChosenPosition and LegalPositionsFrom functions, you're nearly there.
DepthLimit = 2
Resign, Capture, NonCapture = 'Resign', 'Capture', 'NonCapture'
infin = 1000000000
Zero = Logical(0)
NIL = []
board = range(5, 13) + range(14, 22) + range(23, 31) + range(32, 40)
Board = Logical(board) # 1s on board squares
LastRows = Logical([5,6,7,8,36,37,38,39])
Black, White = +1, -1
StartPosition = (Logical(range(18))&Board, Logical(range(27,40))&Board, Logical(0), Black)
def PrintPosition(P=StartPosition, format='|\n'.join(4 * [4 * '| |%s', 4 * '|%s| ']) + '|'):
"Print a simple representation of a checkers board in this position."
(X,Y,K,o) = P
(B, W) = (X, Y) if o == Black else (Y, X)
print format % tuple('%2d%s' % (s, ' bBwW'[K[s]+B[s]+3*W[s]]) for s in board)
print ('Black' if o == Black else 'White'), ' to play.'
def Play(strategies={Black:ChosenPosition, White:ChosenPosition}, P=StartPosition, trace=True):
"""Play a game of checkers. Pass in a dict of strategies; one for black and one for white.
A strategy is a function that maps from a position to the chosen next position. Play returns
two values: the winning player (Black or White) and the final position."""
while LegalPositionsFrom(P):
if trace: PrintPosition(P)
(X,Y,K,o) = P
result = strategies[o](P)
if result == Resign or result not in LegalPositionsFrom(P): break
P = result
if trace: PrintPosition(P)
return (-player, P)
(5) Test cases We put all the tests in the documentation string (docstring) of a single function, test, which invokes the doctest framework to execute the tests. In the presentation below we break that docstring into pieces, interspersing comments about what the tests cover.
def test(verbose=False):
"""This is a set of test cases for the checkers program.
First we cover some of the primitive functions on lists and bit strings—the Logical data type. (Remember, all the test code you see below is inside the docstring for the test function.)
>>> Null([]) True >>> Null(Logical(0)) True >>> Null([1, 2, 3]) False >>> Next([1, 2, 3]) (1, [2, 3]) >>> SingleDigitFrom(Logical([3,5,7])) Logical([3]) >>> SingleDigitFrom(Logical([0])) Logical([0]) >>> Logical([1,2,3,4,5]) - Logical([2,4,6]) Logical([1, 3, 5]) >>> Logical(1023) Logical([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) >>> Logical(1024) Logical([10]) >>> BitCount(Logical([1,2,4,8,11])) 5 >>> Logical([4, 2, 1, 0]) == Logical(0b10111) True >>> Shift(Logical([5,6,7]), 4) Logical([1, 2, 3]) >>> Shift(Logical([5,6,7]), -4) Logical([9, 10, 11])Now we will introduce the playing board, using Strachey's representation.
>>> board
[5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 23,
24, 25, 26, 27, 28, 29, 30, 32, 33, 34, 35, 36, 37, 38, 39]
>>> Board
Logical([5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 23,
24, 25, 26, 27, 28, 29, 30, 32, 33, 34, 35, 36, 37, 38, 39])
>>> StartPosition
(Logical([5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17]),
Logical([27, 28, 29, 30, 32, 33, 34, 35, 36, 37, 38, 39]),
Logical([]),
1)
>>> PrintPosition(StartPosition)
| | 5b| | 6b| | 7b| | 8b|
| 9b| |10b| |11b| |12b| |
| |14b| |15b| |16b| |17b|
|18 | |19 | |20 | |21 | |
| |23 | |24 | |25 | |26 |
|27w| |28w| |29w| |30w| |
| |32w| |33w| |34w| |35w|
|36w| |37w| |38w| |39w| |
Black to play.
Now we're ready to start making moves. It was pleasant to find that I had to make very few changes to Strachey's code to pass the following tests. (Just the missing parenthesis and a slight confusion over bitstrings and lists, particularly NIL).
## Black moves from 15 to 19 >>> P2 = FinalPosition(MakeMove(StartPosition, NonCapture, 4, Logical([15]))) >>> P2 (Logical([27, 28, 29, 30, 32, 33, 34, 35, 36, 37, 38, 39]), Logical([5, 6, 7, 8, 9, 10, 11, 12, 14, 16, 17, 19]), Logical([]), -1) >>> PrintPosition(P2) | | 5b| | 6b| | 7b| | 8b| | 9b| |10b| |11b| |12b| | | |14b| |15 | |16b| |17b| |18 | |19b| |20 | |21 | | | |23 | |24 | |25 | |26 | |27w| |28w| |29w| |30w| | | |32w| |33w| |34w| |35w| |36w| |37w| |38w| |39w| | White to play. ## White moves from 27 to 23 >>> P3 = FinalPosition(MakeMove(P2, NonCapture, 4, Logical([27]))) >>> P3 (Logical([5, 6, 7, 8, 9, 10, 11, 12, 14, 16, 17, 19]), Logical([23, 28, 29, 30, 32, 33, 34, 35, 36, 37, 38, 39]), Logical([]), 1) >>> PrintPosition(P3) | | 5b| | 6b| | 7b| | 8b| | 9b| |10b| |11b| |12b| | | |14b| |15 | |16b| |17b| |18 | |19b| |20 | |21 | | | |23w| |24 | |25 | |26 | |27 | |28w| |29w| |30w| | | |32w| |33w| |34w| |35w| |36w| |37w| |38w| |39w| | Black to play. ## Consider what positions can be reached from a position >>> plist = LegalPositionsFrom(StartPosition) >>> len(plist) 7 >>> PrintPosition(plist[0]) | | 5b| | 6b| | 7b| | 8b| | 9b| |10b| |11b| |12b| | | |14 | |15b| |16b| |17b| |18 | |19b| |20 | |21 | | | |23 | |24 | |25 | |26 | |27w| |28w| |29w| |30w| | | |32w| |33w| |34w| |35w| |36w| |37w| |38w| |39w| | White to play. >>> plist [(Logical([27, 28, 29, 30, 32, 33, 34, 35, 36, 37, 38, 39]), Logical([5, 6, 7, 8, 9, 10, 11, 12, 15, 16, 17, 19]), Logical([]), -1), (Logical([27, 28, 29, 30, 32, 33, 34, 35, 36, 37, 38, 39]), Logical([5, 6, 7, 8, 9, 10, 11, 12, 14, 16, 17, 20]), Logical([]), -1), (Logical([27, 28, 29, 30, 32, 33, 34, 35, 36, 37, 38, 39]), Logical([5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 17, 21]), Logical([]), -1), (Logical([27, 28, 29, 30, 32, 33, 34, 35, 36, 37, 38, 39]), Logical([5, 6, 7, 8, 9, 10, 11, 12, 15, 16, 17, 18]), Logical([]), -1), (Logical([27, 28, 29, 30, 32, 33, 34, 35, 36, 37, 38, 39]), Logical([5, 6, 7, 8, 9, 10, 11, 12, 14, 16, 17, 19]), Logical([]), -1), (Logical([27, 28, 29, 30, 32, 33, 34, 35, 36, 37, 38, 39]), Logical([5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 17, 20]), Logical([]), -1), (Logical([27, 28, 29, 30, 32, 33, 34, 35, 36, 37, 38, 39]), Logical([5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 21]), Logical([]), -1)] ## Now let's see if we can choose good positions ## We'll introduce 'do' to choose the next position, printing before and after >>> def do(P): PrintPosition(P); P1 = ChosenPosition(P); PrintPosition(P1); return P1 >>> do(StartPosition) | | 5b| | 6b| | 7b| | 8b| | 9b| |10b| |11b| |12b| | | |14b| |15b| |16b| |17b| |18 | |19 | |20 | |21 | | | |23 | |24 | |25 | |26 | |27w| |28w| |29w| |30w| | | |32w| |33w| |34w| |35w| |36w| |37w| |38w| |39w| | Black to play. | | 5b| | 6b| | 7b| | 8b| | 9b| |10b| |11b| |12b| | | |14 | |15b| |16b| |17b| |18 | |19b| |20 | |21 | | | |23 | |24 | |25 | |26 | |27w| |28w| |29w| |30w| | | |32w| |33w| |34w| |35w| |36w| |37w| |38w| |39w| | White to play. (Logical([27, 28, 29, 30, 32, 33, 34, 35, 36, 37, 38, 39]), Logical([5, 6, 7, 8, 9, 10, 11, 12, 15, 16, 17, 19]), Logical([]), -1) ## Now see if we can choose a jump move (19 to 27, jumping 23) >>> P4 = do(P3) | | 5b| | 6b| | 7b| | 8b| | 9b| |10b| |11b| |12b| | | |14b| |15 | |16b| |17b| |18 | |19b| |20 | |21 | | | |23w| |24 | |25 | |26 | |27 | |28w| |29w| |30w| | | |32w| |33w| |34w| |35w| |36w| |37w| |38w| |39w| | Black to play. | | 5b| | 6b| | 7b| | 8b| | 9b| |10b| |11b| |12b| | | |14b| |15 | |16b| |17b| |18 | |19 | |20 | |21 | | | |23 | |24 | |25 | |26 | |27b| |28w| |29w| |30w| | | |32w| |33w| |34w| |35w| |36w| |37w| |38w| |39w| | White to play. >>> P4 (Logical([28, 29, 30, 32, 33, 34, 35, 36, 37, 38, 39]), Logical([5, 6, 7, 8, 9, 10, 11, 12, 14, 16, 17, 27]), Logical([]), -1) ## See if we can choose a triple jump ## (5 to 15 to 23 to 33, jumping 10, 19, and 28) >>> do((Logical([5]), Logical([10,19,28]), Zero, Black)) | | 5b| | 6 | | 7 | | 8 | | 9 | |10w| |11 | |12 | | | |14 | |15 | |16 | |17 | |18 | |19w| |20 | |21 | | | |23 | |24 | |25 | |26 | |27 | |28w| |29 | |30 | | | |32 | |33 | |34 | |35 | |36 | |37 | |38 | |39 | | Black to play. | | 5 | | 6 | | 7 | | 8 | | 9 | |10 | |11 | |12 | | | |14 | |15 | |16 | |17 | |18 | |19 | |20 | |21 | | | |23 | |24 | |25 | |26 | |27 | |28 | |29 | |30 | | | |32 | |33b| |34 | |35 | |36 | |37 | |38 | |39 | | White to play. (Logical([]), Logical([33]), Logical([]), -1) ## While we're here, verify that White has no moves: >>> LegalPositionsFrom((Logical([]), Logical([33]), Logical([]), -1)) [] ## Try a triple jump (5 to 15 to 25 to 35) >>> Pt = (Logical([5,7]), Logical([10,19,28,12,21]), Zero, Black) >>> do(Pt) | | 5b| | 6 | | 7b| | 8 | | 9 | |10w| |11 | |12w| | | |14 | |15 | |16 | |17 | |18 | |19w| |20 | |21w| | | |23 | |24 | |25 | |26 | |27 | |28w| |29 | |30 | | | |32 | |33 | |34 | |35 | |36 | |37 | |38 | |39 | | Black to play. | | 5 | | 6 | | 7b| | 8 | | 9 | |10 | |11 | |12w| | | |14 | |15 | |16 | |17 | |18 | |19 | |20 | |21w| | | |23 | |24 | |25 | |26 | |27 | |28 | |29 | |30 | | | |32 | |33b| |34 | |35 | |36 | |37 | |38 | |39 | | White to play. (Logical([12, 21]), Logical([7, 33]), Logical([]), -1)One technical note: for the function LegalPositionsFrom, what is important is the positions that are returned, not the order. I didn't want my test cases to enforce any particular order, so I wrote the tests to compare elements in sorted order, not order returned by LegalPositionsFrom.
We are now ready to start dealing with kings. This is where I had problems with tests failing, and had to modify the code for MakeMove and PCP.
## Check the legal positions form here.
## Use list(sorted(...)) because order of positions doesn't matter.
>>> list(sorted(LegalPositionsFrom(Pt)))
[(Logical([12, 21]), Logical([7, 33]), Logical([]), -1),
(Logical([10, 19, 28]), Logical([5, 25]), Logical([]), -1)]
## Now let's concentrate on Kings
## First make sure that a non-king has 2 moves, a king 4
>>> list(sorted(LegalPositionsFrom((Logical([24]), Zero, Zero, Black))))
[(Logical([]), Logical([28]), Logical([]), -1),
(Logical([]), Logical([29]), Logical([]), -1)]
>>> list(sorted(LegalPositionsFrom((Logical([24]), Zero, Logical([24]), Black))))
[(Logical([]), Logical([19]), Logical([19]), -1),
(Logical([]), Logical([20]), Logical([20]), -1),
(Logical([]), Logical([28]), Logical([28]), -1),
(Logical([]), Logical([29]), Logical([29]), -1)]
## Now see if we can promote a piece to a king
>>> do((Logical([33]), Zero, Zero, Black))
| | 5 | | 6 | | 7 | | 8 |
| 9 | |10 | |11 | |12 | |
| |14 | |15 | |16 | |17 |
|18 | |19 | |20 | |21 | |
| |23 | |24 | |25 | |26 |
|27 | |28 | |29 | |30 | |
| |32 | |33b| |34 | |35 |
|36 | |37 | |38 | |39 | |
Black to play.
| | 5 | | 6 | | 7 | | 8 |
| 9 | |10 | |11 | |12 | |
| |14 | |15 | |16 | |17 |
|18 | |19 | |20 | |21 | |
| |23 | |24 | |25 | |26 |
|27 | |28 | |29 | |30 | |
| |32 | |33 | |34 | |35 |
|36 | |37 | |38B| |39 | |
White to play.
(Logical([]), Logical([38]), Logical([38]), -1)
## See if we can promote by jumping
>>> do((Logical([28]), Logical([32,33]), Zero, Black))
| | 5 | | 6 | | 7 | | 8 |
| 9 | |10 | |11 | |12 | |
| |14 | |15 | |16 | |17 |
|18 | |19 | |20 | |21 | |
| |23 | |24 | |25 | |26 |
|27 | |28b| |29 | |30 | |
| |32w| |33w| |34 | |35 |
|36 | |37 | |38 | |39 | |
Black to play.
| | 5 | | 6 | | 7 | | 8 |
| 9 | |10 | |11 | |12 | |
| |14 | |15 | |16 | |17 |
|18 | |19 | |20 | |21 | |
| |23 | |24 | |25 | |26 |
|27 | |28 | |29 | |30 | |
| |32w| |33 | |34 | |35 |
|36 | |37 | |38B| |39 | |
White to play.
(Logical([32]), Logical([38]), Logical([38]), -1)
## Test if Black Kings can jump (a 6-fold jump)
>>> Ptk = (Logical([5, 6]), Logical([10, 11, 19, 20, 28, 29, 30]), Logical([5, 6]), 1)
>>> do(Ptk)
| | 5B| | 6B| | 7 | | 8 |
| 9 | |10w| |11w| |12 | |
| |14 | |15 | |16 | |17 |
|18 | |19w| |20w| |21 | |
| |23 | |24 | |25 | |26 |
|27 | |28w| |29w| |30w| |
| |32 | |33 | |34 | |35 |
|36 | |37 | |38 | |39 | |
Black to play.
| | 5 | | 6B| | 7B| | 8 |
| 9 | |10 | |11 | |12 | |
| |14 | |15 | |16 | |17 |
|18 | |19 | |20 | |21 | |
| |23 | |24 | |25 | |26 |
|27 | |28 | |29 | |30w| |
| |32 | |33 | |34 | |35 |
|36 | |37 | |38 | |39 | |
White to play.
(Logical([30]), Logical([6, 7]), Logical([6, 7]), -1)
## Try a 7-fold jump
>>> do((Logical([9,12]), Logical([14,15,16,23,25,32,33,34]), Logical([9]), Black))
| | 5 | | 6 | | 7 | | 8 |
| 9B| |10 | |11 | |12b| |
| |14w| |15w| |16w| |17 |
|18 | |19 | |20 | |21 | |
| |23w| |24 | |25w| |26 |
|27 | |28 | |29 | |30 | |
| |32w| |33w| |34w| |35 |
|36 | |37 | |38 | |39 | |
Black to play.
| | 5 | | 6 | | 7 | | 8 |
| 9B| |10 | |11 | |12 | |
| |14 | |15 | |16 | |17 |
|18 | |19 | |20B| |21 | |
| |23 | |24 | |25 | |26 |
|27 | |28 | |29 | |30 | |
| |32w| |33 | |34 | |35 |
|36 | |37 | |38 | |39 | |
White to play.
(Logical([32]), Logical([9, 20]), Logical([9, 20]), -1)
## Actually, I had expected the black king at 9 to make the jump,
## leaving only the white piece at 34. The move above is rated higher
## because it leaves Black with two kings, not one. According to my reading
## of the rules of checkers, the move above is illegal, because the piece
## is kinged (and thus allowed to move backwards) in the middle of the move,
## whereas I believe kinging should only happen at the end. But I accept that
## Strachey has implemented a variant of the rules rather than that he has a bug.
>>> list(sorted(LegalPositionsFrom((Logical([9,12]),
Logical([14,15,16,23,25,32,33,34]), Logical([9]), Black))))
[(Logical([14, 15, 23]), Logical([9, 36]), Logical([9, 36]), -1),
(Logical([15, 16, 25]), Logical([12, 39]), Logical([39]), -1),
(Logical([32]), Logical([9, 20]), Logical([9, 20]), -1),
(Logical([23, 32, 33]), Logical([12, 39]), Logical([39]), -1),
(Logical([34]), Logical([12, 19]), Logical([19]), -1),
(Logical([34]), Logical([12, 19]), Logical([19]), -1)]
At this point I was satisfied with the program. If I were programming professionally, I would be more careful about test coverage. (I would also worry about the efficiency of my program, a factor that Strachey did not stress, and I would look to improve my TerminalValue function to make it smarter.)
As one last aid to the reader, more so than as a test case, you can see the Python code generated by the CPL parser. It corresponds very closely to the CPL code; the main difference is that Python uses
where CPL uses(lambda x=10: x+x)()
value of
§ let x=10
result is x+x §
## Now let's look at the output of the CPL parser
>>> print convert_cpl(ModifiedCPLprogram)
Input Grammar: cpl.g
Output File: cpl.py
def ChosenPosition(P):
return (lambda L=LegalPositionsFrom(P):
Resign if Null(L) else (lambda (p, v)=BestPosition(NIL, -infin, L, 0):
p)())()
def BestPosition(P, V, L, d):
return ((P, V) if Null(L) else (lambda (p, l)=Next(L):
(lambda v=-PositionValue(p, d+1):
(BestPosition(p, v, l, d) if (v>V) else BestPosition(P, V, l, d)))())())
def PositionValue(P, d):
return (TerminalValue(P) if Terminal(P, d) else (lambda L=LegalPositionsFrom(P):
(lambda (p, v)=BestPosition(NIL, -infin, L, d):
v)())())
def LegalPositionsFrom(P):
return (lambda L=RemainingPositionList(P, Capture, 5):
(RemainingPositionList(P, NonCapture, 5) if Null(L) else L))()
def RemainingPositionList(P, C, s):
return PartialPositionList(P, C, s, FindMoveList(P, C, s))
def PartialPositionList(P, C, s, L):
return (((NIL if (s==-5) else RemainingPositionList(P, C, NextMoveDirection(s)))) if Null(L) else (lambda Phi=SingleDigitFrom(L):
(lambda Ip=MakeMove(P, C, s, Phi):
(lambda l=(CaptureTree(Ip) if (C==Capture) else FinalPosition(Ip)):
Join(l, PartialPositionList(P, C, s, L-Phi)))())())())
def NextMoveDirection(s):
return (4 if (s==5) else ((-4 if (s==4) else -5)))
octestdef FindMoveList(P, C, s):
return (lambda (X, Y, K, sigma)=P:
(lambda Empty=~X&~Y&Board:
(lambda psi=((Shift(Empty, sigma*s)&Y) if (C==Capture) else Empty):
(lambda Phi=Shift(psi, sigma*s)&X:
(Phi if (s>0) else Phi&K))())())())()
def MakeMove(P, C, s, Phi):
return (lambda (X, Y, K, sigma)=P:
(lambda psi=(Shift(Phi, -sigma*s) if (C==Capture) else Zero):
(lambda theta=(Shift(psi, -sigma*s) if (C==Capture) else Shift(Phi, -sigma*s)):
(lambda Xk=((theta&LastRows) if Null(Phi&K) else theta):
((X-Phi+theta), (Y-psi), (K-psi-Phi+Xk), sigma, theta))())())())()
def FinalPosition(Ip):
return (lambda (X, Y, K, sigma, Phi)=Ip:
(Y, X, K, -sigma))()
def CaptureTree(Ip):
return (lambda L=PartialCapturePositionList(Ip):
((FinalPosition(Ip)) if Null(L) else CombineCaptureTrees(L)))()
def PartialCapturePositionList(Ip):
return (lambda (X, Y, K, sigma, Phi)=Ip:
(lambda P=(X, Y, K, sigma):
MinList(PCP(P, Phi, 5), PCP(P, Phi, 4), PCP(P, Phi&K, -4), PCP(P, Phi&K, -5)))())()
def PCP(P, Phi, s):
return (lambda (X, Y, K, sigma)=P:
(lambda psi=Shift(Phi, -sigma*s)&Y:
(lambda Empty=~X&~Y&Board:
(lambda theta=Shift(psi, -sigma*s)&Empty:
(lambda Xk=((theta&LastRows) if Null(Phi&K) else (theta-Phi)):
(NIL if Null(theta) else ((X-Phi+theta), (Y-psi), (K-psi-Phi+Xk), sigma, theta)))())())())())()
def CombineCaptureTrees(L):
return (NIL if Null(L) else (lambda (Ip, l)=Next(L):
Join(CaptureTree(Ip), CombineCaptureTrees(l)))())
"""
import d
return doctest.testmod(optionflags=doctest.NORMALIZE_WHITESPACE, verbose=verbose)
Peter Norvig
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4