riddler-bridge.py

import numpy as np
from collections import namedtuple

### Convenience functions
variables = (
    "rank",   # 0 for no bid, 1 for 1 clubs, 2 for 1 diamonds, ..., 5 for 1 no-trump, ..., 35 for 7 no-trump
    "passes", # 0 - 4 consecutive passes
    "turn",   # whose turn it is; 0 for the team who opens the bidding, 1 for the other 
    "contractor", # the team who did the last bidding; 0 for the team who opens the bidding, 1 for the other 
    "doubles" # the number of doubles (0,1,2)
)
State = namedtuple("State", variables)

statelist = []
for rank in range(0, 35+1):
    for passes in range(4+1):
        if passes == 4 and rank > 0:
            continue
        for turn in range(2):
            for contractor in range(2):
                for doubles in range(2+1):
                    if doubles > 0 and rank == 0:
                        continue
                    state = State(rank, passes, turn, contractor, doubles)
                    statelist.append(state)

states = {}
for n, state in enumerate(statelist):
    states[state] = n

def S(rank, passes, turn, contractor, doubles):
    return states[State(rank, passes, turn, contractor, doubles)]

### State buffers 

nstates = len(statelist)
print("%d states" % nstates)
matrix = np.zeros((nstates, nstates), np.bool)  # transition matrix
v = np.zeros(nstates, np.double)  # state vector
v[S(0, 0, 0, 0, 0)] = 1

### Transition definitions (without using "turn" or "contractor")

# transition for initial state
m = matrix[S(0, 0, 0, 0, 0)]
# pass
m[S(0, 1, 0, 0, 0)] = 1
# bid
for rank in range(1,35+1):
    m[S(rank, 0, 0, 0, 0)] = 1

# transition for bid states with no passes
for rank in range(1, 35+1):
    m = matrix[S(rank, 0, 0, 0, 0)]
    # pass
    m[S(rank, 1, 0, 0, 0)] = 1
    # bid
    for rank2 in range(rank+1,35+1):
        m[S(rank2, 0, 0, 0, 0)] = 1

# transitions for bid states with 1 - 2 passes
for rank in range(0, 35+1):
    for passes in range(0, 2+1):
        m = matrix[S(rank, passes, 0, 0, 0)]
        # pass
        m[S(rank, passes+1, 0, 0, 0)] = 1
        # bid
        for rank2 in range(rank+1,35+1):
            m[S(rank2, 0, 0, 0, 0)] = 1

# transitions for bid states with 3 passes after a bid (terminal)
for rank in range(1, 35+1):
    state = S(rank, 3, 0, 0, 0)
    matrix[state, state] = 1

# transitions for 3 and 4 passes before a bid
matrix[S(0, 3, 0, 0, 0), S(0, 4, 0, 0, 0)] = 1
matrix[S(0, 4, 0, 0, 0), S(0, 4, 0, 0, 0)] = 1   # (terminal)

### Running the calculation
maxiter = 3 + 4 * 35 + 1
for i in range(maxiter):
    v = v.dot(matrix)
print("%.3e trajectories" % v.sum())

"""
Now for adding state for "turn" and "contractor", 
  and repeating for every "doubles" state
  (should make no difference)
"""

### Reset state and transition buffers
v[:] = 0
matrix[:] = 0
v[S(0, 0, 0, 0, 0)] = 1

### Transition definitions
# transition for initial state
m = matrix[S(0, 0, 0, 0, 0)]
# pass
m[S(0, 1, 1, 0, 0)] = 1
# bid
for rank in range(1,35+1):
    m[S(rank, 0, 1, 0, 0)] = 1

# transition for bid states with no passes
for rank in range(1, 35+1):
    for turn in range(2):
        for contractor in range(2):
            for doubles in range(2+1):
                m = matrix[S(rank, 0, turn, contractor, doubles)]
                # pass
                m[S(rank, 1, 1-turn, contractor, doubles)] = 1
                # bid
                for rank2 in range(rank+1,35+1):
                    m[S(rank2, 0, 1-turn, turn, 0)] = 1

# transitions for bid states with 1 - 2 passes
for rank in range(0, 35+1):
    for turn in range(2):
        for contractor in range(2):
            for passes in range(0, 2+1):
                for doubles in range(2+1):
                    if doubles > 0 and rank == 0:
                        continue
                    m = matrix[S(rank, passes, turn, contractor, doubles)]
                    # pass
                    m[S(rank, passes+1, 1-turn, contractor, doubles)] = 1
                    # bid
                    for rank2 in range(rank+1,35+1):
                        m[S(rank2, 0, 1-turn, turn, 0)] = 1

# transitions for bid states with 3 passes after a bid (terminal)
for rank in range(1, 35+1):
    for turn in range(2):
        for contractor in range(2):
            for doubles in range(2+1):
                state = S(rank, 3, turn, contractor, doubles)
                matrix[state, state] = 1
            
# transitions for 3 and 4 passes before a bid
matrix[S(0, 3, 1, 0, 0), S(0, 4, 0, 0, 0)] = 1
matrix[S(0, 4, 0, 0, 0), S(0, 4, 0, 0, 0)] = 1   # (terminal)

### Re-running the calculation
for i in range(maxiter):
    v = v.dot(matrix)
print("%.3e trajectories" % v.sum())

"""
Now, add transitions for doubling 
"""

for rank in range(1, 35+1):
    for passes in range(2+1):
        for turn in range(2):
            for contractor in range(2):
                if turn != contractor: # opponent team's turn; chance to double
                    state1 = S(rank, passes, turn, contractor, 0)
                    state2 = S(rank, 0, 1-turn, contractor, 1)
                    matrix[state1, state2] = 1
                else: # declaring team's turn; chance to redouble
                    state1 = S(rank, passes, turn, contractor, 1)
                    state2 = S(rank, 0, 1-turn, contractor, 2)
                    matrix[state1, state2] = 1

### Reset state buffers
v[:] = 0
v[S(0, 0, 0, 0, 0)] = 1
maxiter = 300  # empirical

### Re-running the calculation
for i in range(maxiter):
    v = v.dot(matrix)
print("With doubling: %.3e trajectories" % v.sum())