Continued Thesis Progress

After my last thesis post, I decided to start building my tree builder program, and I chose C++ as the language to use in this case, as I already had a binary tree class built from my undergraduate days.  After working on it for a while yesterday, I can report success.  Success!

This tree builder goes through my pop.stat file, reading in information and eventually reading in the tree.  I had to build in a recursive function into the tree to get it to work correctly—admittedly a no-no, but one I don’t care about at the moment.  During this process, I also taught myself how to use vectors instead of allocating dynamic arrays.  In my four years at Dayton, I never used a vector, and that is a sad story.  At any rate, they were easy to pick up on and I built the tree.  After that, I threw in two additional functions:  a pruner function and a singleton function.  The pruner function prunes according to a logic table that I built.  For example, if first_move is true (i.e., it is the first move of the game), then all of the other functions must be false, and if any other function is true, first_move must be false.

So let’s say that we have this setup:  first_move is the top level and has two children, with opp_ever_def (if the opponent has ever defected) and good_res (if the last result was a good one) being the left and right child, respectively.  opp_ever_def returns d if true and c if false.  good_res returns c if true and c if false (so it always returns c).

The function would start with first_move, and then look at opp_ever_def.  Because first_move has to be true in order to reach opp_ever_def, there is no way that opp_ever_def could be true.  As a result, only the false branch (c) could ever be reached, so my program deletes the true branch.  But there’s no use for a tree with just one branch, so I then go ahead and shift everything up one level, getting rid of opp_ever_def and replacing it with c.  On the right side, things stay the same.

My new tree is now shorter than the old one:  first_move is the root again.  But c is the left child (i.e., cooperate if true), and good_res, c/c is the right branch.  At this point, I unleash my Singleton function.  In the case of good_res, there is really only one result:  cooperate.  Because of this, there’s no need to do a check for good_res, and we can delete it.  So when this program is finished, it looks like:

first_move c c

But the astute viewer will note that this could be Singleton’d down even further, down to just c.  And, in fact, because Singleton is a recursive function, it does that.  So really, the tree looks like:


As a realistic example shows, there is a lot of scope for big savings.  Here is one of my later trees (which, in fact, was the best-performing tree of the lot):

(own_prev x (opp_ever_def (opp_prev x (own_prev2
x d)) (own_prev (own_prev2 (opp_ever_def
(opp_prev x (own_prev2 (own_prev2 x c) d))
(opp_ever_def d (opp_prev2 (good_res x x)
c))) d) (opp_ever_def (opp_ever_def (own_prev
x x) (good_res (opp_prev d c) (own_prev (opp_ever_def
(opp_prev x (own_prev2 (opp_ever_def (good_res
(opp_prev2 (good_res x x) c) x) (opp_prev2
(own_prev2 x c) c)) d)) (opp_ever_def (own_prev
x x) (own_prev2 (good_res (own_prev x x)
(own_prev (opp_ever_def (own_prev2 x c) (good_res
(opp_ever_def (good_res d d) (own_prev2 x
c)) x)) (good_res x x))) c))) (good_res x
(own_prev (own_prev x x) (opp_ever_def (opp_prev
x (own_prev2 (own_prev (good_res (good_res
d d) (opp_ever_def (good_res d d) (own_prev2
x c))) (opp_prev2 (good_res x x) c)) d))
(own_prev2 x c))))))) (own_prev2 x c)))))

That’s a lot of stuff.  But it can be summarized as:

(own_prev  x  (opp_ever_def  (opp_prev  x  (own_prev2  x  d))) (own_prev2  x  c))

And that’s what I call savings.

So now my to-do list for today looks like:

  1. Rebuild my ECJ (the Genetic Programming program) Java files to make the output exactly as I wish it to be.
  2. Re-run ECJ, giving me the new output.
  3. Run the tree builder on the resulting population output file.
  4. Begin to collect some rudimentary statistics, such as the number of non-defecting processes in each generation.

After I do this, I’ll have a chance to recognize where I am and what I need to do, so I should get to work on it.


One thought on “Continued Thesis Progress

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s