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

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.

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)

#### (3) Functions described but not implemented by Strachey

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

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.

def test(verbose=False):
    """This is a set of test cases for the checkers program.
>>> 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])

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

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

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

## 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)))
def 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 doctest
    return doctest.testmod(optionflags=doctest.NORMALIZE_WHITESPACE, verbose=verbose)