# Python port of Java dice game algorithm

I am in the process of learning Python (background in C++ and R). So after the obligatory "Hello World", I decided that my first non-trivial program would be a port of a Java implementation of the counter-factual regret minimization algorithm for a simple dice game called Liar Die [original source, Joodle online compiler].

The program runs a million simulations of the dice game and computes the optimal bluffing/calling frequencies. It does this by creating Node class instances for all decision points in the game, and keeping track of the various actions the player to move can make, as well as the expected values of those actions.

I then tried to translate this into Python as faithfully as possible:

import numpy as np

class LiarDieTrainer:
DOUBT, ACCEPT = 0, 1

class Node:
u, pPlayer, pOpponent = 0.0, 0.0, 0.0

def __init__(self, numActions):
self.regretSum = np.zeros(numActions)
self.strategy = np.zeros(numActions)
self.strategySum = np.zeros(numActions)

def getStrategy(self):
self.strategy = np.maximum(self.regretSum, 0)
normalizingSum = np.sum(self.strategy)
if normalizingSum > 0:
self.strategy /= normalizingSum
else:
self.strategy.fill(1.0/len(self.strategy))
self.strategySum += self.pPlayer * self.strategy
return self.strategy

def getAverageStrategy(self):
normalizingSum = np.sum(self.strategySum)
if normalizingSum > 0:
self.strategySum /= normalizingSum
else:
self.strategySum.fill(1.0/len(self.strategySum))
return self.strategySum

def __init__(self, sides):
self.sides = sides
self.responseNodes = np.empty((sides, sides+1), dtype=self.Node)
for myClaim in range(sides):
for oppClaim in range(myClaim+1, sides+1):
self.responseNodes[myClaim, oppClaim] = self.Node(1 if oppClaim == sides else 2)
self.claimNodes = np.empty((sides, sides+1), dtype=self.Node)
for oppClaim  in range(sides):
for roll in range(1, sides+1):
self.claimNodes[oppClaim , roll] = self.Node(sides - oppClaim)

def train(self, iterations):
regret = np.zeros(self.sides)
rollAfterAcceptingClaim = np.zeros(self.sides, dtype=int)
for it in range(iterations):
for i in range(len(rollAfterAcceptingClaim)):
rollAfterAcceptingClaim[i] = np.random.randint(self.sides) + 1
self.claimNodes[0, rollAfterAcceptingClaim].pPlayer = 1
self.claimNodes[0, rollAfterAcceptingClaim].pOpponent = 1

for oppClaim in range(self.sides+1):
if oppClaim > 0:
for myClaim in range(oppClaim):
node = self.responseNodes[myClaim, oppClaim]
actionProb = node.getStrategy()
if oppClaim < self.sides:
nextNode = self.claimNodes[oppClaim, rollAfterAcceptingClaim[oppClaim]]
nextNode.pPlayer += actionProb * node.pPlayer
nextNode.pOpponent += node.pOpponent

if oppClaim < self.sides:
node = self.claimNodes[oppClaim, rollAfterAcceptingClaim[oppClaim]]
actionProb = node.getStrategy()
for myClaim in range(oppClaim+1, self.sides+1):
nextClaimProb = actionProb[myClaim - oppClaim - 1]
if nextClaimProb > 0:
nextNode = self.responseNodes[oppClaim, myClaim]
nextNode.pPlayer += node.pOpponent
nextNode.pOpponent += nextClaimProb * node.pPlayer

for oppClaim in reversed(range(self.sides+1)):
if oppClaim < self.sides:
node = self.claimNodes[oppClaim, rollAfterAcceptingClaim[oppClaim]]
actionProb = node.strategy
node.u = 0.0
for myClaim in range(oppClaim+1, self.sides+1):
actionIndex = myClaim - oppClaim - 1
nextNode = self.responseNodes[oppClaim, myClaim]
childUtil = - nextNode.u
regret[actionIndex] = childUtil
node.u += actionProb[actionIndex] * childUtil
for a in range(len(actionProb)):
regret[a] -= node.u
node.regretSum[a] += node.pOpponent * regret[a]
node.pPlayer = node.pOpponent = 0

if oppClaim > 0:
for myClaim in range(oppClaim):
node = self.responseNodes[myClaim, oppClaim]
actionProb = node.strategy
node.u = 0.0
doubtUtil = 1 if oppClaim > rollAfterAcceptingClaim[myClaim] else -1
regret[self.DOUBT] = doubtUtil
node.u += actionProb[self.DOUBT] * doubtUtil
if oppClaim < self.sides:
nextNode = self.claimNodes[oppClaim, rollAfterAcceptingClaim[oppClaim]]
regret[self.ACCEPT] += nextNode.u
node.u += actionProb[self.ACCEPT] * nextNode.u
for a in range(len(actionProb)):
regret[a] -= node.u
node.regretSum[a] += node.pOpponent * regret[a]
node.pPlayer = node.pOpponent = 0

if it == iterations // 2:
for nodes in self.responseNodes:
for node in nodes:
if node:
node.strategySum.fill(0)
for nodes in self.claimNodes:
for node in nodes:
if node:
node.strategySum.fill(0)

for initialRoll in range(1, self.sides+1):
print("Initial claim policy with roll %d: %s" % (initialRoll, np.round(self.claimNodes[0, initialRoll].getAverageStrategy(), 2)))
print("\nOld Claim\tNew Claim\tAction Probabilities")
for myClaim in range(self.sides):
for oppClaim in range(myClaim+1, self.sides+1):
print("\t%d\t%d\t%s" % (myClaim, oppClaim, self.responseNodes[myClaim, oppClaim].getAverageStrategy()))
print("\nOld Claim\tRoll\tAction Probabilities")
for oppClaim in range(self.sides):
for roll in range(1, self.sides+1):
print("%d\t%d\t%s" % (oppClaim , roll, self.claimNodes[oppClaim , roll].getAverageStrategy()))

trainer = LiarDieTrainer(6)
trainer.train(1000)


Working example on the Ideone online compiler (factor of 1000 less iterations, apparently Python is way slower than even Java). Unfortunately, the algorithm works by randomly throwing dice, and the Java/Python random number generators give different sequences, and the dice game may not have a unique equilibrium anyway. This means I can't directly compare the outcomes.

Questions:

1. how can I make my code more Pythonic?
2. which other idioms / coding style should I apply?
3. which other useful libraries (besides NumPy) could I have used for this exercise?
• Was numpy really useful here? Did you try replacing it by normal Python lists? Numpy has benefits when working with a lot of data and using vectorized operations... it will lose to normal lists otherwise. Also, the typical, remarks: naming, use snake_case for variable names, method names etc. Unfortunately, I'm not familiar with the game, and it's too much code to try to figure it out from the source. – wvxvw Dec 28 '17 at 15:20
• @wvxvw thanks, the naming was literally taken from the Java source. I guess I should change that. Re NumPy: this is because I want to expand this code into something that uses matrix inversion etc. (for Bayesian updating). – TemplateRex Dec 28 '17 at 15:35

Your function names and variable names are lowerCamelCase when the convention for Python is snake_case.

You have some inconsistent spacing here:

for oppClaim  in range(sides):


A linter would catch both of these issues.

This:

        self.claimNodes[0, rollAfterAcceptingClaim].pPlayer = 1
self.claimNodes[0, rollAfterAcceptingClaim].pOpponent = 1


should use a temporary variable:

node = self.claim_nodes[0, roll_after_accepting_claim]
node.p_player = 1
node.p_opponent = 1


These two loops:

            for nodes in self.responseNodes:
for node in nodes:
if node:
node.strategySum.fill(0)
for nodes in self.claimNodes:
for node in nodes:
if node:
node.strategySum.fill(0)


can be refactored into one set of nested loops:

for node_source in (self.response_node, self.claim_nodes):
for nodes in node_source:
for node in nodes:
if node:
node.strategy_sum.fill(0)


Strings such as this:

print("\t%d\t%d\t%s" % (myClaim, oppClaim, self.responseNodes[myClaim, oppClaim].getAverageStrategy()))


are good candidates for being converted to f-strings:

ave_strategy = self.response_nodes[my_claim, opp_claim].get_average_strategy()
print(f'\t{my_claim}\t{opp_claim}\t{ave_strategy}')


You should consider adding a main function instead of calling train from global code.