Simulating Games

Sample Game Simulation Results

Sample Game Simulation Results

Update: I made a huge mistake in the first version (it skipped some possible strategies). In fixing it I realized that writing it off the top of my head made it awful to use and even worse to modify. So, I re-wrote the whole thing. The version below is the new version.

Working at a university lets me take courses for free. So, I’m taking a grad-level economics game theory course. Naturally I got ADD and decided to do assignments I made up in my head rather than the actual assignments. Which, this weekend, ended up being “make a Python script that will solve simple games”. So here it is.

I still haven’t trimmed it down at all and there are definitely some places it could be more efficient and/or concise. It was basically written as I thought it up so, yeah…

To use this you’ll need the matplotlib module and my table layout class if you use the printGame() method to pretty-print your game matrix to stdout. You can go ahead and grab that from here.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157

# simple game simulation ver. 2
 
import random
import tablelayout as tl
import matplotlib.pyplot as plt
 
# classes
 
class Player:
    "a single player"
    def __init__(self, s):
        self.strategy = s
        self.score = 0
    def __cmp__(self, other):
        return self.score - other.score
    def __str__(self):
        return str(self.strategy)
 
class Population:
    "a group of players"
    def __init__(self, s, name, n=100):
        self.strategies = s
        self.name = name
        self.size = n
        self.members = list()
        self.__populate()
    def __populate(self):
        "create players with each of choices up to size"
        i = 0
        while len(self.members) < self.size:
            self.members.append(Player(self.strategies[i]))
            i += 1
            if i >= len(self.strategies):
                i = 0
    def evolve(self, low=.05, mutate=.01):
        "evolve the population"
        # prune the population
        self.members.sort()
        n = int(round(low * self.size))
        self.members = self.members[n:]
        # rebuild the population
        i = 0
        self.members.sort()
        self.members.reverse()
        while len(self.members) < self.size:
            if random.random() > mutate:
                self.members.append(Player(self.members[i].strategy))
            else:
                self.members.append(Player(random.choice(self.strategies)))
            i += 1 # can never overrun end so no check
        # reset all members to zero
        for player in self.members:
            player.score = 0
    def get_data(self):
        "get the current counts and average score for each strategy"
        # do counts
        counts = dict()
        for s in self.strategies:
            counts[s] = 0
        for m in self.members:
            counts[m.strategy] += 1
        # do average scores
        scores = dict()
        for s in self.strategies:
            scores[s] = 0
        for m in self.members:
            scores[m.strategy] += m.score
        for s in self.strategies:
            # prevent division by zero, can only happen on first gen
            if counts[s] != 0:
                scores[s] = scores[s] / counts[s]
            else:
                scores[s] = 0
        # finished
        return counts, scores
 
class Simulation:
    "a simulation consisting of populations and a game"
    def __init__(self, g, ps=100):
        self.game = g
        self.popsize = ps
        self.populations = list()
        self.generation = 0
        # data we track
        self.counts = list()
        self.scores = list()
        # simulation settings
        self.drop_pct = .05 # % to drop
        self.mutate_pct = .01 # % to mutate
        self.round_count = 10 # avg. rounds each player in biggest pop should play
    def __update_data(self):
        "updates count and score data"
        for i, pop in enumerate(self.populations):
            counts, scores = pop.get_data()
            for s in pop.strategies:
                self.counts[i][s].append(counts[s])
                self.scores[i][s].append(scores[s])
    def addPopulation(self, strats, name):
        "adds a population to the simulation"
        self.populations.append(Population(strats, name, self.popsize))
        newcounts = dict()
        newscores = dict()
        for s in strats:
            newcounts[s] = list()
            newscores[s] = list()
        self.counts.append(newcounts)
        self.scores.append(newscores)
    def simulate(self, n):
        "play n total games randomly within each population"
        # run through rounds
        for i in xrange(n):
            players = [random.choice(p.members) for p in self.populations]
            scores = self.game.play(players)
            for r in map(None, players, scores):
                r[0].score += r[1]
        # update counts and scores data
        self.__update_data()
        # evolve the population
        for pop in self.populations:
            pop.evolve(self.drop_pct, self.mutate_pct)
        # we now have the new generation
        self.generation += 1
    def run(self, n):
        "run the simulation for n generations"
        rounds = max([p.size for p in self.populations]) * self.round_count
        for i in xrange(n):
            self.simulate(rounds)
    def get_count_data(self):
        "get all count data for populations"
        output = ''
        for i, pop in enumerate(self.populations):
            output += '%sn' % pop.name
            output += 't'.join(pop.strategies) + 'n'
            for k in xrange(self.generation):
                for s in pop.strategies:
                    output += '%it' % self.counts[i][s][k]
        return output
    def graph(self, p=None, legend=7):
        "create a pretty graph of the current state of population p"
        #TODO: make this take a population name instead of number
        # since number is sensitive to order populations were added
        pop = self.populations[p]
        for s in pop.strategies:
            plt.plot(self.counts[p][s], label='%s: %s' %(pop.name, s))
        plt.ylabel('Size in Population')
        plt.xlabel('Generations')
        plt.title('Population %i Through %i Generations' % (p, self.generation))
        xmax = self.generation
        ymax = max([p.size for p in self.populations])
        plt.axis([0, xmax, 0, ymax])
        plt.legend(loc=legend)
        plt.draw()
    def graph_all(self):
        "quick hack method to graph all on one plot, title will be wrong"
        for i, pop in enumerate(self.populations):
            self.graph(i)
        plt.show()

It basically consists of three classes. One for a game itself (which handles payoffs), one for a player (which handles strategies) and one for a population of players which takes care of everything else. I’m going to make some changes to add a simulation class that will contain a n populations and n games to allow the simulations to be more complex.

Right now the population class also has the output methods. The getDemographics() method gives you a tab-delimited table of the population results so far. The createPlot() method uses matplotlib to generate a very nice line plot of the size of each type of player through the generations.

I am using a very simple agent-based evolutionary model. The players within the population are chosen at random, they play the game (with each playing a pure strategy that can differ depending on which side of the game they are on) and then a new pair is chosen. Once they have played a certain number of games the population is ordered and trimmed by some amount (in this case 50 players or 10%). Then the empty spots are filled with the best-performing players, although 1% of the time the new player mutates to a different strategy combination.

The code to generate the image at the top is given below:

class TestGame1:
    "testing game"
    def __init__(self):
        self.matrix = {'a': {'a':(73,25), 'b':(57,42), 'c':(66,32)},
                       'b': {'a':(80,26), 'b':(35,12), 'c':(32,54)},
                       'c': {'a':(28,27), 'b':(63,31), 'c':(54,29)}}
    def play(self, players):
        "plays the game"
        return self.matrix[players[0].strategy][players[1].strategy]
 
def test1():
    sim1 = Simulation(TestGame1())
    strats = ['a', 'b', 'c']
    sim1.addPopulation(strats, 'rows')
    sim1.addPopulation(strats, 'cols')
    sim1.run(500)
    print sim1.get_count_data()
    sim1.graph_all()
 
test1()

This will produce some raw output of the results to stdout plus a nice graph.

February 16, 2009 • Tags: , , • Posted in: code, python • No Comments

Make your screensaver surf the tubes

Awhile ago I saw this post and made my screensaver print out lines of Linux kernel source code. I made some changes to skip comments and such but overall I thought it was a nifty idea.

So then I thought it would be neat to make the screensaver do other stuff. So I wrote a couple little Python scripts to produce different output for the Phosphor screensaver.

To use either of these, just replace the ‘cat’ line in the tutorial with a call to one of these.

Twitter

Invoke this one as such: ‘python /path/to/script name1 name2 …’

It will download several of the most recent tweets each of the accounts listed have posted.

Yahoo Search

Invoke either as ‘python /path/to/script’ or ‘python /path/to/script /path/to/dict’ depending on where your dictionary file is. If you’re running Ubuntu Hardy, or another distro that keeps a link to its dictionary in /usr/share/dict/words use the first one. Otherwise you need to give the script a path to a dictionary or another file containing a list of search terms to choose from. Multi-word terms are fine if you’d like to make a custom file.

Download both scripts.

Screenshot.

August 10, 2008 • Posted in: code, python, ubuntu • No Comments

simple class to handle command line arguments in python

Despite the fact that there are already a couple ways to parse command line arguments in Python I thought it would be fun to create another one.

My method is implemented in a single class that you instantiate by passing the contents of sys.argv along with three dictionaries containing the arguments you want to look for. The three dictionaries correspond to switches (-f), single value (-f somefile.txt) and multiple value (-f file1.txt file2.txt). Of course the multiple value can also take a single value but I wanted to separate them so that eventually I could make the class check to make sure the numbers are all correct. In other words you can limit an argument to one value.

Once the arguments have been parsed, they are referred to by their switch (-f, etc.) The values in the dictionaries passed when the class is instantiated are descriptions of what each parameter does. In this way the class allows the program to self-document.

Eventually I may add support for long switches (–file), referencing by descriptive name (file rather than -f), the ability to add arguments in a more fluid manner and just general error handling and stuff.

Here’s the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

# handler.py
# very simple command line argument handler class
# give it a list of things you want to look for and a sys.argv
# and it gives you an easy way to access what it found
 
# by: george lesica
# date: 11/2007
 
class handler:
	"""class to handle simple command line arguments settings, supports
	3 types of switch/argument combinations:
		1. simple switches (true/false, etc.)
		2. switch + single argument (-f somefilename.txt)
		3. switch + multiple arguments (-f file1.txt file2.txt)
	constructor takes 4 arguments, a raw copy of sys.argv, 1 dictionary
	for each type of argument listed above (respectively) with the
	switches as keys and optional descriptions as values
	stores a single ivar, a dictionary of results"""
	def __init__(self, args, simple, single, multiple):
		"""constructor, this is where most of the work gets done
		we parse the args, pulling out what we need then just chill
		until somebody asks for it"""
		self.__argDefs = {}
		self.__argDefs.update(simple)
		self.__argDefs.update(single)
		self.__argDefs.update(multiple) # so we can print out info
		self.__argData = {}
		self.__junkData = [] # whatever is left in args after parsing
		args.pop(0) # kill the filename
		# first do the simple args, they get true/false values
		for arg in simple.keys():
			self.__argData[arg] = False # false by default
			if arg in args:
				args.pop(args.index(arg)) # remove it
				self.__argData[arg] = True
		# now the single args
		for arg in single.keys():
			self.__argData[arg] = '' # default is empty string (allows boolean use)
			if arg in args:
				self.__argData[arg] = args.pop(args.index(arg) + 1) # get rid of "value" and save it
				args.pop(args.index(arg)) # get rid of switch
		# now the multiple args (this is the hardest one)
		for arg in multiple.keys():
			self.__argData[arg] = [] # empty list by default
			if arg in args:
				thisKey = args.index(arg)
				while(len(args) > thisKey + 1 and args[thisKey + 1] not in multiple):
					self.__argData[arg].append(args.pop(thisKey + 1))
		self.__junkData = args
	def __str__(self):
		"""returns the arg definitions and descriptions as a formatted string"""
		out = ''
		for item in self.__argDefs.items(): out += ' : '.join(item) + '\n'
		return out
	def getValue(self, arg):
		"""returns the value associated with the given arg, a boolean
		if it was a simple arg, a string if it was a single arg and
		a list of strings if it was a multiple arg
		if the given arg wasn't passed it returns false, empty string or
		empty list (respectively) which all evaluate to False"""
		return self.__argData[arg]
	def getData(self):
		"""returns the entire dict of data parsed from the sys.argv including empties"""
		return self.argData
	def getJunk(self):
		"""returns the entire junk data list"""
		return self.__junkData
November 13, 2007 • Posted in: code, python • No Comments

Eternal Updates

Recently I upgraded to Gutsy Gibbon and decided to use the occasion to change the way my hard drives are partitioned. Rather than Putting the whole OS on a single partition I moved /home to its own large partition and made the rest of the system separate. This will let me more easily install and use testing releases and other distros.

In any event, a fresh install is also nice because it lets you clean the crap out of your machine by, well, erasing it all. One of the things that got erased were my ugly virtual machines. Previously I had been using VMware Server (the free thingy) since the version of VirtualBox in the Feisty repos was a bit buggy.

Having destroyed all my virtual machines, I decided to give VirtualBox another go. First up was my Windows XP VM. I have this mostly so I can use Office when needed and because I already own a license so I may as well use it.

After a pleasant install of XP Home on the new VM (after finding the new version of VirtualBox much improved) I began the process of installing Windows Updates.

After the first 20 minutes or so I still hadn’t really paid much attention other than clicking ‘restart’ when prompted. But after awhile I got to thinking that it was taking a really long time. Now, granted, this is several years worth of updates including two service packs but still, why should updating an operating system take over an hour and countless restarts? As I’m typing this I’m watching XP install 81 updates after having rebooted like 5 times and I anticipate at least another round after this.

Why is it that patches can’t be applied all in one go like they can be in every GNU/Linux distro I’m aware of? Seems like poor planning on the part of Microsoft… oh well, almost done, hopefully.

October 27, 2007 • Posted in: linux, software • No Comments

now with image galleries

New image gallery (also a link on the right) so I can post wallpapers I make mostly. Also whatever randomness ends up there.

September 28, 2007 • Posted in: images • No Comments

consider the source?

Had to point this one out.

Iranian President Mahmoud Ahmadinejad speaking at Columbia University, answering a question about Iran’s treatment of homosexuals:

“In Iran we do not have this phenomenon,” he continued. “I do not know who has told you we have it.”

Apparently this statement drew laughter and ridicule from the audience. But honestly how is his statement any different than many of the statements our leaders make that we take very seriously. Like when our leaders tell other countries that they have to change their laws so that our companies won’t lose money, or that we don’t torture prisoners (despite having made it abundantly clear that we do, unless of course you use their home-brewed ultra-narrow definition of torture).

Honestly, we should be learning from Ahmadinejad, not cursing him.

Not learning in the sense of taking his ideas to heart of course, but learning in the sense that he is a mirror in which, if we look closely, we can see ourselves reflected, we can see ourselves as much of the world sees us.

Next time you watch a news conference with an American leader, pretend instead that it is Mahmoud Ahmadinejad and consider how you would feel about what is being said then.

September 25, 2007 • Posted in: society • No Comments

Why we should all be wary of electronic voting

Apparently TD Ameritrade customers have been getting stock-related spam sent to their email addresses. The company had a security audit done and found “unauthorized code” in their trading system that was allowing someone back door access to at least parts of their customer database.

In other news, another salvo was fired in the ongoing back-and-forth over electronic voting (or e-Voting for those of you who can only understand buzzwords). The Information Technology and Innovation Foundation (bit of a mouthful, eh?) released a report claiming that paper trails aren’t the magic bullet we all thought they were and will not solve our e-Voting woes (the horror).

So, now we have a brokerage firm with billions of dollars in assets at stake that can’t even protect its own source code and a (purportedly unbiased) report stating that paper trails will not fix electronic voting.

If TD Ameritrade can’t protect its code, how are the little old ladies who work the polling places supposed to, given the apparent ease with which e-Voting machines can be compromised? And if paper trails won’t solve the problem what are we to do?

I’m certainly not the first to suggest this, but I submit that the only answer is to simply go back to paper ballots while we still can, before a sizable industry develops around e-Voting and prevents us from changing course.

The old punch card-style ballots may be a broken system (if I ever read about hanging chads in a newspaper again I’ll puke) but there are a number of other technologies in existence that could be used and would provide voter-verifiable and machine readable paper ballots that could be counted easily and uncontroversially.

Given the ease with which computer systems can be compromised and the scale of a US election I think we should all be very concerned if our leaders continue down the current e-Voting path.

UPDATE: Here is the full ITIF report. Give the report a read. I did and I certainly don’t agree with some of the author’s assumptions, specifically the claim that distrust of technology “flies in the face of our digital culture” given that we trust computers with our banking, etc. I wonder if the author is aware of a little thing called “identity theft” that has become a big topic as of late. I have personally had my bank account numbers compromised twice in the past three years. So no, I really do not trust technology to keep important information secure. But read it for yourself.

UPDATE 2: I decide to post some other little tidbits from the report.

Not the author’s fault, but I just love hearing people make arguments that simply don’t make sense but are accepted as legitimate by the public and the press simply because they come from sources that should, one would think, be legitimate themselves. It’s like when a CEO claims his company “had nothing to do with <insert embarrassing event/fact here>” yet their logo is plastered all over it. Love it and hate it all at once.

From the report:

They also fear that individual reviewers will make unsubstantiated claims against their voting systems prior to an election simply to undermine the public’s confidence in the voting systems.

So what they’re saying is that if they release the source code people might not have confidence in their machines. But if they do not release the source code people will not have confidence in their machines. How can people take this seriously? I just don’t get it.

Now, on the subject of paper receipts. The author cited some pretty strong evidence that paper receipts don’t work but then he tried to go even further and fell on his face.

From the report:

The fact that both machines would use audio technology would mean that everyone, including people with disabilities, could independently verify the audit trail. In contrast, paper audit trails would not allow blind or illiterate voters to verify their ballots independently.

So what you’re saying is that deaf people don’t vote? According to the NIH there are roughly 28 million people with hearing loss. According to the American Foundation for the Blind there are 10 million blind people. Either way a whole lot of people are going to need special accommodation and then the election becomes only as secure as those accommodations.

Should have just left that little bit out. :)

When a comparison isn’t a comparison

I was browsing through this post on Linux.com and got to thinking that no matter how in-depth, fair-minded they are, or what conclusion they reach, comparisons between Open Office and Microsoft Office are all basically moot because of one fact: Open Office is not 100% compatible with MS Office file formats.

Basically, in any comparison, MS Office automatically wins, the game is over before it begins. Only Microsoft can support the dominant file format completely so for most users the Microsoft products are basically irreplaceable.

Even basic documents (no reviewing, data fields or other high-end features) don’t save properly in MS formats under OOo. Margins, headers/footers and foot/end notes all act a little different, but different enough to matter.

While it is unfortunate that until very recently there was little or no standardization in this area of computing, it is a fact that the only document file formats that really matter for the vast majority of computer users are the MS Office formats and until OOo can adequately duplicate those (or until ODF becomes more widely used, which may or may not happen) comparing MS Office and OOo is a largely pointless exercise.

September 11, 2007 • Posted in: tech • 1 Comment

On Blueprint

Reading Reddit Programming this morning I noticed a link to Blueprint, a CSS “Framework” for web designers.

This caught my eye because I’ve commented before that CSS, while it can do any number of wonderful things, has had two effects that I consider negative or at least dubious:

  1. CSS has “good” (unique, browser-compatible, nice-looking) web design out of reach for many people. The choice is now between forgoing standards-compliance (in addition to all the neat-o stuff CSS can do) and using old-fashioned techniques like layout tables and spending a large amount of time learning the intricacies of CSS.

    I consider myself computer-literate. I have no problem learning basics of programming languages and computing and technology topics come pretty easy to me. Yet the whole of CSS still eludes me. Browser incompatibilities, <div> tag tricks, :after, etc. all confuse me.

    Maybe I just haven’t put enough effort into it, but why should I? I’m not a professional web designer and I really don’t even demand professional results, I just want my web pages to be compatible and reasonably “pretty”.

    Given all this, I think my experience has been fairly typical: CSS is easy to grasp if it’s your job, but difficult (for some) if it’s your hobby. Which leads into my next point…

  2. The web has become somewhat homogenized because of the barriers (and capabilities) introduced by CSS (and other web technologies, but we aren’t talking about them right now).Ever noticed how almost every weblog looks pretty much like almost every other weblog?

    They all look damn nice, but they all look the same. Sometimes right down to the header images.This isn’t necessarily a bad thing, many people don’t want to worry about design, they just want to communicate their thoughts to the world and this is absolutely a-ok peachy in my book. In fact, that’s what the interwebs are for in some sense.

    However, I’ve noticed that even weblogs of people who might be considered “geeky”, people who one would think would want to poke around at the “code” underlying their web site, suffer from this condition. I can only hypothesize that at least some of these people are choosing “stock” designs because they don’t want to invest the time in messing with the CSS themselves, compatibility trumps curiosity perhaps.

Of course I could be wrong about everything I’ve just said. I have no data and no concrete examples other than my own experiences. But if I’m even a tiny bit right, then I think something like Blueprint could be a blessing for a great many people by removing some of the highest hurdles standing in the way of those who would like to tinker with their web designs but don’t have the time/determination/food supply to attain full-blown CSS-mastery.

In any event, Blueprint is certainly an interesting experiment and it will be interesting to see if the concept catches on; and if it does, with whom.

August 7, 2007 • Posted in: interweb, tech • No Comments

Stupid Poll



stupid poll, originally uploaded by oldmanstan.

Apparently this wasn’t a scientific study… :)

Either there’s some hardcore selection bias (maybe CNN viewers / readers really are liberal?) or else a whole lot of people lied…

Or I guess their “estimates” could just be complete crap, but you’d think they would do their homework. They ARE a “news” network afterall so they know how to do research… right?

July 27, 2007 • Posted in: Uncategorized • No Comments