In the pre­vi­ous episode, I spent a few min­utes jot­ting down some sto­ries that describe what I’m inter­ested in learn­ing in this project: I’m using GP to develop play­ers of Peter Winkler’s “Pizza Eat­ing Game”, and the algo­rith­mic part of those GP Answers will use a novel archi­tec­ture called Tag Space Machines from Lee Spec­tor. And as a kata for myself (and a bit of a tuto­r­ial for the occa­sional per­son I encounter who hasn’t done test-driven design before) I’ll be using rig­or­ous BDD, record­ing all the lit­tle messy details here.

So. I think I’ll start with some low-hanging fruit, not least because I’m wrestling with learn­ing a new text edi­tor, and try­ing to get all the fid­dly bits hooked up is prov­ing chal­leng­ing. So I think I’ll build a Pizza class first.

Look­ing over the sto­ries, I’m going to assume the pizza is just some kind of wrap­per around an Array of slice sizes, with some fancy meth­ods that per­mit initialization/reset and “eat­ing”. Let’s start with initialization/reset.

# pizza.feature
Feature: Pizza

  Background:
    Given I have a new pizza

  Scenario: pizza slicing
    Given a list of slice sizes [1,0,7,9,3,12,33,0,0,0,2.88,2.12]
    When I slice the pizza
    Then there should be 12 slices
    And the pizza should weigh 70
    And the pizza should be whole

The pizza is “whole” because Alice hasn’t eaten the first slice, and it’s going to be treated as an array with “wrap­ping” bound­aries by her yum­mi­ness function(s).

Cucum­ber reports that the first pend­ing spec is Given I have a new pizza, so I cre­ate the appro­pri­ate step definition.

# pizza_steps.rb
Given /^I have a new pizza$/ do
  @pizza = Pizza.new
end

This fails, since I have no Pizza class.

#pizza.rb
class Pizza
end

And it passes. The next pend­ing step is Given a list of slice sizes [1,0,7,9,3,12,33,0,0,0,2.88,2.12].

# pizza_steps.rb
Given /^a list of slice sizes (\[.+\])$/ do |slices|
  @slice_list = eval(slices)
end

That passes, since it’s not invok­ing the library at all, just set­ting a vari­able within the scope of the test. When I slice the pizza is next.

# pizza_steps.rb
When /^I slice the pizza$/ do
  @pizza.slice(@slice_list)
end

This calls for a tiny bit more struc­ture in the Pizza class, but not too much.

#pizza.rb
class Pizza
  attr_accessor :slices

  def slice(size_array)
    @slices = size_array
  end
end

Next pend­ing step is Then there should be 12 slices.

# pizza_steps.rb
Then /^there should be (\d+) slices$/ do |count|
  @pizza.slices.length.should == count.to_i
end

Which passes already. And the pizza should weigh 70

# pizza_steps.rb
Then /^the pizza should weigh (\d+)$/ do |weight|
  @pizza.weight.should == weight.to_f
end

That calls for another bit if Pizza struc­ture. But is it an attribute, or a method? I’m think­ing method; the slice weight array itself is already stored, and I assume the play­ers will have some sort of #eat(left_slice) method that mod­i­fies that Array directly on each turn. I’ll return the sum of all slice values.

#pizza.rb
class Pizza
...
  def weight
    @slices.inject(0) {|sum,w| sum+w}
  end
end

Last step is And the pizza should be whole.

# pizza_steps.rb
Then /^the pizza should be whole$/ do
  @pizza.should be_whole
end

Inter­est­ing ques­tion: when is Pizza#whole? going to be true? As soon as my pizza is first sliced, surely. But maybe also when it’s ini­tial­ized (“baked”)? Then again, the ini­tial­iza­tion method (which I haven’t needed yet) might be more use­ful to set up partially-eaten un-whole piz­zas for test­ing or train­ing. I’m all for postponing.

#pizza.rb
class Pizza
  attr_accessor :whole
  ...
  def slice(size_array)
    @slices = size_array
    @whole = true
  end

  def whole?
    whole
  end
end

All steps pass.

So Alice and Bob will be eat­ing par­tic­u­lar ele­ments of Pizza#slices. And the sto­ries make it clear there are two modes: the first slice, and then the left_slice vs right_slice. I sup­pose I should start with the first slice. In addi­tion to mak­ing the pizza no longer whole?, this ought to “unwrap” the cir­cle to cre­ate the left_slice and right_slice linearity.

# pizza.feature
...
Scenario: eating the first slice unfolds the circle
  Given the pizza is sliced into [1,2,3,4,5,6,7,8]
  When I take out piece 6
  Then the pizza should not be whole
  And the left slice should weigh 7
  And the right slice should weigh 5

I’ve made a new step here.

# pizza_steps.rb
Given /^the pizza is sliced into (\[.+\])$/ do |slices|
  @pizza.slice eval(slices)
end

That passes already, from work done in the pre­vi­ous sce­nario. Now When I take out piece 6 is the next pend­ing step.

# pizza_steps.rb
When /^I take out piece (\d+)$/ do |which|
  @pizza.eat_first_slice(which.to_i-1)
end

I need to add Pizza#eat_first_slice to the library, though this step doesn’t actu­ally call for it to do anything.

#pizza.rb
class Pizza
...
  def eat_first_slice(which)
  end
...

Then the pizza should not be whole

# pizza_steps.rb
Then /^the pizza should not be whole$/ do
  @pizza.should_not be_whole
end

Seems a sim­ple thing to make that pass.

#pizza.rb
class Pizza
...
  def eat_first_slice(which)
    @whole = false
  end
...

And the left slice should weigh 7. Basi­cally the “left” slice is the stub-end of the unwrapped cir­cle I get when I snip out the eaten piece, and the “right” slice is the piece remain­ing to its left. First the steps I need (both at once, just because the sym­me­try is so clear):

# pizza_steps.rb
Then /^the left slice should weigh (\d+)$/ do |weight|
  @pizza.left_slice.should == weight.to_f
end

Then /^the right slice should weigh (\d+)$/ do |weight|
  @pizza.right_slice.should == weight.to_f
end

And the library code to make these pass. I fid­dle a bit with the bounds-checking, but I think this will do.

#pizza.rb
class Pizza
...
  def eat_first_slice(which)
    open_circle = @slices[which+1..-1] + @slices[0...which]
    @slices = open_circle
    @whole = false
  end
...

And that seems to have done the trick.

This is the first in a (hope­fully short) series in which I’m prac­tic­ing my BDD in a Ruby-based exper­i­ment where I want:

• to use GP to develop strate­gies in Peter Winkler’s Pizza Eat­ing Game;
• to use Lee Spector’s Tag Space Machine sys­tem as an archi­tec­ture in my Answer Lan­guage ;
• to use a triv­ial Answer Fac­tory archi­tec­ture (ran­dom sam­pling of Answers plus some basic meta­heuris­tic moves) to explore whether there any­thing like the known opti­mal strate­gies crop up

Some sto­ries

I’m start­ing from an empty can­vas: I’ll need to think about the rep­re­sen­ta­tion of the prob­lem domain, not just the archi­tec­ture of the TSM answers and GP sys­tem. I spend some time read­ing over the arXiv paper that sparked my curios­ity and Lee’s descrip­tion of TSMs. I come up with a few sto­ries, and some notes as I jot them down.

Eat­ing the first piece isn’t like later pieces:

Before the first game move (when the pizza is whole), Alice can pick any piece at all. After she does, Bob and Alice can only pick one of the two neigh­bors of the grow­ing gap.

As I men­tioned when I launched this side-project, I’m think­ing about the way these agents play the game as being some kind of “field gen­er­a­tion” process. Their cal­cu­la­tions impose some kind of “yum­mi­ness field” on the (cur­rent) set of pizza slices, and then when that cal­cu­la­tion is done they eat the slice with the high­est yum­mi­ness value. Fur­ther, I think I want to try a local process, a sin­gle cal­cu­la­tion con­ducted with “this piece of pizza” as the focus, with ref­er­ences to the traits of other pieces being spa­tially relative.

The inter­est­ing thing of course is the topo­log­i­cal dif­fer­ence between the whole pizza and the partially-eaten one. The whole is cir­cu­lar, with “left” and “right” being well-defined all the way around. But once a piece is eaten, the thing becomes “lin­ear”, and the only choice before the agents is between the two “end” pieces of that ordered set of pieces.

In deter­min­ing the “yum­mi­ness field”, this feels like it might be impor­tant. But it’s also lim­it­ing the set of agent behav­iors: the first move is some kind of eat_first_piece, and all sub­se­quent moves are eat_left_piece or eat_right_piece.

Pizza slices have weights:

every pizza slice has a numer­i­cal weight, which can be 0

This seems pretty straight­for­ward: the goal of the play­ers is to con­sume a max­i­mum pro­por­tion of the total pizza, and “weight” seems as good as any­thing for tal­ly­ing this up. Bet­ter than “crust”, surely… though of course they will sort in the same order.

Agent decision-making:

Agents have two yumminess func­tions, one for pick­ing the first piece, and the other for later moves. The yumminess func­tion is invoked with a ref­er­ence to a spe­cific index of the cur­rent pizza, and returns a float value. One yum­mi­ness value is cal­cu­lated (in par­al­lel) for each slice.

I’m think­ing the basic yumminess cal­cu­la­tions might include some boolean logic and arith­metic; we’ll work our way up from there as needed. The index of a slice is the input, but the algo­rithm can have instruc­tions to inter­ro­gate the attrib­utes of slices, things like its index, its weight, that sort of thing. Heck, maybe the yumminess of one slice can refer to the yumminess of its neigh­bors… but that may end up being complicated.

Because of the clear topo­log­i­cal (and strate­gic) dif­fer­ence between the first slice and the later ones, I’m will­ing to start with a lit­tle extra com­plex­ity and have two sep­a­rate func­tions. This seems to imply I’m think­ing that every agent can play “Alice” or “Bob” roles in what­ever scor­ing tour­na­ment I come up with. Why not? Let’s see what happens.

Yum­mi­ness ties are bro­ken randomly:

When the max­i­mum yumminess is assigned to mul­ti­ple avail­able slices, one is picked at ran­dom with uni­form probability.

In other words: when in doubt, flip a coin or draw straws.

Yum­mi­ness func­tions are Tag Space Machines:

One for each. The appro­pri­ate ref­er­ences to exter­nal val­ues are set up based on the slice index, the TSM is run, and then the top­most [num­ber] is emit­ted as the output.

I’m not sure which “num­ber” this might be. Do I need to dif­fer­en­ti­ate between int and float? Really? I don’t have a lot of infor­ma­tion yet about what the TSM lan­guage is going to be like. Maybe this will become more appar­ent as I work on that.

TSM math instructions:

The TSM should rec­og­nize float val­ues, and have basic math instruc­tions: add, subtract, divide, multiply, min, max, maybe a few more.

Do I really need integer as a type? After all, the notion of an “index” in the tag space itself depends on the math­e­mat­i­cal “floor” func­tion. Why not use floats for indices as well, tak­ing the floor (or ceil­ing) as needed? Maybe this is just reals, and we’ll skip the dif­fer­ence until we need it.

TSM pizza instructions:

The TSM should be able to get the index and weight of the slice on which it’s applied. It can use weight_of and index_of with a numeric argu­ment (pos­i­tive or neg­a­tive) to obtain val­ues of neigh­bor­ing slices.

I have an intu­ition this may not be enough. But we’ll see. It’s not that hard to imag­ine run­ning the cal­cu­la­tions for each slice in lock-step, and let­ting one TSM inter­ro­gate its neigh­bor­ing TSM’s state, like with real_of to copy over a real from a neigh­bor­ing slice’s stack into its own. But no need to over-design yet.

TSM log­i­cal instructions:

The TSM should have basic Boolean logi­cian func­tions: and, or, not, that sort of thing.

Makes sense, because we’ll have com­par­isons to make.…

TSM com­par­i­son instructions:

The TSM should have com­par­isons like less_than, greater_than, equal and so on for reals and any other types for which they make sense.

These will cre­ate bool outputs.

TSM dynam­ics:

When the TSM is acti­vated, it pops one item from its x stack; if it’s a con­stant it’s pushed to the appro­pri­ate stack, and if it’s an instruc­tion it exe­cutes that instruc­tion imme­di­ately. This con­tin­ues until the x stack is empty.

This is just the def­i­n­i­tion of how TSMs run. But it does raise the ques­tion (from expe­ri­ence): Will there ever be TSM “pro­grams” that don’t ter­mi­nate? Will I need a step counter, and some sort of dead­line? We’ll see, I guess.

TSM tag spaces:

The tag_space stack holds tag_space instances. TSM instruc­tions for stor­age and lookup exist, and refer to the top tag_space in the stack based on numeric index. Each tag_space is a key-value pair store, sorted by numeric key. Lookup is inex­act, return­ing the value for the small­est key larger than the search tag, or the first key of no key is larger. No value is returned if the tag_space is empty.

Feels as though I’ll need to cre­ate a sub­class of Ruby’s Hash for this, main­tain­ing the sort order and deal­ing with the inex­act lookup. Shouldn’t be too com­pli­cated, but will demand some care­ful checks.

TSM tag­ging instructions:

There are instruc­tions store, store_pair and lookup for writ­ing and read­ing from the top tag_space. (see update below)

Based on Lee’s descrip­tion, it sounds as though his ts_tag imaps arise some­how from the “genome” of a TSM: that is, they appear fully-formed in the x stack before we start run­ning the code. This feels strange but inten­tional, and so I’ve asked him if I’m miss­ing something.

In the mean­time, I’m more com­fort­able hav­ing instruc­tions that make those asso­ci­a­tions from argu­ments just like other instruc­tions would use, except that the argu­ments for store and store_pair come from the x stack rather than the typed stacks. For instance, I’m imag­in­ing store pulls a “tag key” from the reals stack, and the next item from the x stack, and stores the item as a value asso­ci­ated with that key in the top­most tag_space.

What am I missing?

Well, of course I’ve not defined any­thing about how these sup­posed pizza-eating experts are going to be scored, nor how many and what kind of pizza they’ll be asked to eat, or any of that. But it feels like enough to get started with, espe­cially as I’m wait­ing for Emma Tosch and Lee to help me out of the con­fus­ing bits.

In the mean­time, I’ll start on the pizza first….

Update (later that day):

After a cou­ple of clar­i­fi­ca­tions from Lee, I’ve got a bet­ter han­dle on how the tags and tag­ging instruc­tions should work.

TSM tag­ging instructions:

There are three kinds of what I’ll call macro instruc­tions: store_at(N), lookup_at(N) and store_pair_at(N), where (N) is a fixed floating-point num­ber, not an argu­ment. These numer­i­cal val­ues can (and prob­a­bly will) vary between instances of these instruc­tions, but not over the “life” of the indi­vid­ual instruc­tion instances.

So basi­cally what’s hap­pen­ing here is that the stor­age and retrieval of items in a tag_space always includes a par­tic­u­lar address, not a numeric argu­ment. This is a design deci­sion from Lee, and seems per­fectly valid to work with.

I think I can get away with a bit of abbre­vi­a­tion when writ­ing TSM code, and use >8.2 to indi­cate the macro instruc­tion store_at(8.2), use <-3.9 to indicate lookup_at(-3.9), and >>991.55 to indicate the macro store_pair_at(991.55).