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:

"""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. """

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

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) )§ """

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) + ")"}}

## (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))

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)

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

>>> 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

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

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