A simply 3 x 3 bingo simulator!

bingo_simulator.py

# -*- coding: utf-8 -*-
"""
Zeeshan Ali Sayyed
Oct 27, 2017

Challenge: Create a 3x3 bingo board using integers in [1,20]. You may use the same integer more than once.													
													
We will then play bingo as follows:													
In each turn of the game, we will roll two six sided dice and add the results. We will mark one square on your 
bingo board if you have at least one unmarked square that is a multiple of the total rolled (if more than one unmarked 
square is a multiple of the total, we will pick one at random). We will take turns until at least one board has 
bingo (3 marks in a row, horizontal, vertical, or diagonal). Each player whose board has bingo gets a share of the win 
(if n players get bingo, then each gets 1/n wins). We will simulate 10,000 games using all the bingo boards submitted.
The goal is to get the most wins out of all contestants.													
					
Submit your answer as an integer vector of length 9 - where the first element is placed in the top left box on the bingo
board and then reading left to right across the top row and then left to right across the middle row and then left to
right across the bottom row. Also submit a very brief description of how you arrived at your answer and why you think your
board will win.  We are interested in your thought process and how you considered different angles to the game as much as
how well your submission does compared with other contestants.
"""

import numpy as np
from pandas import Series
from scipy.stats import rv_discrete
from collections import Counter
import cPickle as pickle

def factors(n):
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

def generate_die_distribution(dice_low=1, dice_high=6, n_dice=2):
    """
    Generates probability distribution of the total value when 'n_dice' die
    are thrown. dice_low is the lowest value on the dice and dice_high is
    the highest value on the dice. All the numbers in between are assumed
    to be present on the dice
    """
    die_range = np.arange(dice_low * n_dice, dice_high * n_dice + 1)
    dist = Series(data=np.zeros_like(die_range), index=die_range)
    for i in range(100000):
        dice_total = np.sum(np.random.randint(dice_low, dice_high+1, size=n_dice))
        dist[dice_total] += 1
    dist /= np.linalg.norm(dist, ord=1)
    return dist
    
def generate_bingo_distribution(bingo_low=1, bingo_high=20):
    """
    Generates the probability distribution of all the valid numbers
    in a given bingo board. 'low' is the lowest number allowed in the 
    bingo board and 'high' is the highest number allowed on the 
    bingo board. It is assumed that all numbers in between are also 
    valid
    """  
    bingo_range = range(bingo_low, bingo_high + 1)
    die_dist = generate_die_distribution()
    bingo_dist = Series(data=np.zeros_like(bingo_range), index=bingo_range,
                        dtype='float64')
    for i in bingo_dist.keys():
        a = list(factors(i))
        for j in a:
            if j in die_dist:
                bingo_dist[i] += die_dist[j]
    bingo_dist /= np.linalg.norm(bingo_dist, ord=1)
    return bingo_dist

# Simulation code begins here.
# We will have a dictionary called boards = {}. Keys will be board IDs and 
# values will be actually 3 x 3 numpy arrays representing numbers
# We will have another dictionary called marked_boards={}. The keys will be
# the same as those of boards. The values are also 3 x 3 numpy array. But instead
# of numbers on a bingo board, they will only have 1's and 0's denoting whether 
# a number was marked or not.

    
def generate_random_boards(low=1, high=20, board_size=9, dist='custom', n=100):
    """
    This is an ongoing implementation. For now it genrates 'n' number of random
    boards. These boards have the specified low and high values and the
    board size. Finally, currently the boards aren't generated randomly.
    But they are generated according to the probability distrubtion 
    returned by `generate_bingo_distribution`
    params dict has 3 keys:
        'b' -> boards dictionary
        'mb' -> marked_boards dictionary
        's' -> scores dictionary
    """
    boards = {}
    marked_boards = {}
    scores = {}
    if dist == 'custom':
        dist = generate_bingo_distribution(bingo_low=low, bingo_high=high)
    xk = range(1, 21)
    pk1 = (0, 0.01, 0.019, 0.038, 0.038, 0.075, 0.057, 0.083, 0.056, 0.074, 0.019,
          0.112, 0, 0.066, 0.056, 0.083, 0, 0.112, 0, 0.102)
    pk2 = [1/16.] * 20
    pk2[0], pk2[12], pk2[16], pk2[18] = [0.0]  * 4
    generator = rv_discrete(name='custom', values=(xk, pk2))
    for i in range(n):
        boards[i] = generator.rvs(size=board_size)
        marked_boards[i] = np.zeros(board_size)
        scores[i] = 0.0
    params = {}
    params['b'] = boards
    params['mb'] = marked_boards
    params['s'] = scores
    return params
    
def add_custom_board(a, params):
    """
    Once you have a set of boards generated for simulation, you can add your
    own board to the set. Just pass in a python list in a and the params
    dictionary containing the generated boards
    for e.g. add_custom_board([1, 2, 3, 4, 5, 6, 7, 8, 9], my_params)
    The function returns the ID of your board. Note it down to see results
    """
    i = len(params['b'])
    params['b'][i] = np.array(a)
    params['mb'][i] = np.zeros(len(params['mb'][0]))
    params['s'][i] = 0.0
    return i
    
def reset_params(params, what='marks'):
    """
    This function takes in a dictionary called params, which itself contains
    3 more dictionaries: boards, marked_boards and scores. It keeps all the
    indices and boards, same as before. It only resets all marked_boards 
    and scores to zeros again ! Then returns the params
    """
    b = params['b']
    board_size = len(b[0])
    mb = params['mb']
    s = params['s']
    for i in b.keys():
        if what == 'marks':
            mb[i] = np.zeros(board_size)
        elif what == 'scores':
            s[i] = 0.0
        elif 'both':
            mb[i] = np.zeros(board_size)
            s[i] = 0.0

def check_board(board_marks):
    """
    This function checks whether the passes array has achieved bingo!
    It takes a numpy array of shape (9,). I know this is a weird shape.
    But if you generate something without specifying a complete shape,
    this is what you get. for e.g. np.zeros(9) or
    np.random.randint(0, 2, size=9)
    """
    assert(board_marks.shape == (9,))
    board_marks = board_marks.reshape(3, 3)
    if 3 in np.sum(board_marks, axis=0):
        return True
    elif 3 in np.sum(board_marks, axis=1):
        return True
    elif np.trace(board_marks) == 3:
        return True
    elif np.trace(np.fliplr(board_marks)) == 3:
        return True
    else:
        return False
        
def check_bingo(marked_boards):
    """
    This function checks all the marked_boards in the the dictionary
    which is input and returns a list of all the indices which have reached 
    Bingo! If none of the boards has reached bingo, it will return an 
    an empty list
    """
    bingo_boards = []
    for index in marked_boards.keys():
        if check_board(marked_boards[index]):
            bingo_boards.append(index)
    return bingo_boards
        
        
def simulate_turn(boards, marked_boards, dice_score):
    """
    # Given a 1x9 numpy array this method
    # will roll 2 dice and mark an index as 1
    # board will be board[i]
    # marked_board will be marked_board[i]
    """
    for i in boards:
        choices = []
        for j in range(len(boards[i])):
            if boards[i][j] % dice_score == 0:
                choices.append(j)
        if len(choices) > 0:
            choice = np.random.choice(choices)
            marked_boards[i][choice] = 1

def simulate_game(params, dice_low=1, dice_high=6, n_dice=2):
    boards = params['b']
    marked_boards = params['mb']
    scores = params['s']
    bingo_boards = []
    while len(bingo_boards) == 0:
        dice_total = np.sum(np.random.randint(dice_low, dice_high+1, size=n_dice))
        simulate_turn(boards, marked_boards, dice_total)
        bingo_boards = check_bingo(marked_boards)
    update = 1./len(bingo_boards)
    for i in bingo_boards:
        scores[i] += update
    return scores

def run_simulation(params, nrounds=10, verbose=False):
    reset_params(params, what='scores')
    for i in range(nrounds):
        if verbose:
            if i % 100 == 0:
                print i,
        current_scores = simulate_game(params)
        reset_params(params, what='marks')
    return params['s']

def print_results(params, top=10):
    """
    Prints results i.e. ID, board and scores of the 'top' boards
    """
    winners = Counter(params['s']).most_common(top)
    for i in winners:
        print i, params['b'][i[0]]
        
def test():
    p = generate_random_boards(n=5)
    return run_simulation(p)
#    Out[453]: 
#    Counter({0: 21.333333333333332,
#         1: 6.5,
#         2: 35.0,
#         3: 27.499999999999996,
#         4: 9.666666666666668})


# The following will be moved onto the main method later on
if __name__ == "__main__":
    all_params = []
    for i in range(3):
        print "Simulation number:",str(i), "-> ", 
        params = generate_random_boards(n=100)
        add_custom_board([12] * 9, params)
        add_custom_board([18] * 9, params)
        add_custom_board([6,12,14,10,18,8,7,20,16], params)
        run_simulation(params, nrounds=10000, verbose=True)
        all_params.append(params)
    print ""

    

print_results(p1)
(45, 216.94266289266213) [20 3 5 18 14 15 8 7 12]
(59, 208.36725635475568) [10 14 14 11 15 18 4 5 16]
(20, 201.48861555111552) [14 6 11 8 14 6 12 3 20]
(55, 198.00392883260508) [14 14 16 20 12 11 4 18 9]
(23, 197.14629953379918) [15 6 18 20 7 18 8 16 12]
(8, 196.77758352758292) [ 9 7 10 20 18 14 8 12 8]
(33, 196.72906578715398) [11 8 2 20 9 12 5 14 3]
(102, 194.35566418875197) [ 6 12 14 10 18 8 7 20 16]
(87, 188.51435549744343) [15 7 12 18 8 12 11 15 14]
(6, 186.93929722238525) [ 9 15 12 11 15 14 8 8 6]

print_results(all_params[1])
(65, 330.27185910494677) [16 9 18 12 20 11 14 3 10]
(41, 282.5223137973133) [11 7 8 3 9 6 8 7 10]
(54, 250.85656288156284) [16 8 11 6 12 7 10 9 10]
(64, 236.70412504162476) [ 9 11 8 6 7 18 10 18 10]
(25, 233.9058746808747) [11 20 14 16 9 12 12 3 2]
(102, 232.15322177822165) [ 6 12 14 10 18 8 7 20 16]
(81, 202.93526514335284) [14 20 18 16 8 14 11 3 16]
(26, 202.4422188922188) [ 5 11 14 12 20 8 2 14 5]
(11, 191.29030691530693) [15 12 18 16 11 8 14 2 15]
(90, 184.35274627333416) [14 10 12 8 18 2 12 4 14]

print_results(all_params[2])
(16, 284.8392102780256) [ 7 14 18 6 16 11 18 4 10]
(19, 252.5251539095575) [10 12 9 8 11 14 16 7 14]
(88, 231.4567071817065) [10 18 18 16 18 11 7 18 6]
(25, 218.97254222385777) [ 3 7 12 2 14 16 7 7 20]
(102, 208.34714631773443) [ 6 12 14 10 18 8 7 20 16]
(61, 198.3003653209527) [16 15 5 10 14 18 11 11 12]
(23, 193.39920773670744) [ 7 9 11 12 11 11 8 20 20]
(94, 191.70930180930145) [ 8 6 3 8 18 14 10 11 5]
(73, 191.34558497058484) [ 3 8 6 7 20 20 11 18 2]
(98, 183.49528567837348) [12 11 10 4 12 9 4 11 14]