8
\$\begingroup\$

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[0]].pPlayer = 1
            self.claimNodes[0, rollAfterAcceptingClaim[0]].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[1] * 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?
\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – wvxvw Dec 28 '17 at 15:20
  • \$\begingroup\$ @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). \$\endgroup\$ – TemplateRex Dec 28 '17 at 15:35
2
\$\begingroup\$

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[0]].pPlayer = 1
        self.claimNodes[0, rollAfterAcceptingClaim[0]].pOpponent = 1

should use a temporary variable:

node = self.claim_nodes[0, roll_after_accepting_claim[0]]
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}')

Also, since you're printing tabular data, you should apply fixed field widths to both your heading string and your row strings. To learn more about field widths, read about the Format Specification Mini-Language.

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.