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:
- Rebuild my ECJ (the Genetic Programming program) Java files to make the output exactly as I wish it to be.
- Re-run ECJ, giving me the new output.
- Run the tree builder on the resulting population output file.
- 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.