Looney Labs Icehouse Mailing list Archive

Re: [Icehouse] The *real* numbers of Treehouse

  • FromJonas Kölker <jonaskoelker@xxxxxxx>
  • DateSat, 1 Aug 2009 21:06:01 +0200
Here are some new and updated numbers on Treehouse.  These supercede my
previous numbers, which included several miscounts.

First, a brief explanation of terminology:

 - "moves" means the (number of) pairs of positions such that the type of move
   in question allows one to move from the first position to the second
 - "average out-degree" basically is how many positions you can move to
   (assuming positions to move from are equally likely)
 - "no-move positions" is the number of positions where you might be able to
   move the house (i.e. you can't change your own trio)
 - "unreachable" positions are positions you can't move to (with the
   particular type of move)

That said, here are some numbers:

positions: 204

moves not shared with any: 84
moves shared with AIM: 348
moves, total: 432
average out-degree: 2.117647
no-move positions: 48
unreachable positions: 24

moves shared with TIP: 348
moves not shared with any: 360
moves shared with DIG: 336
moves, total: 1044
average out-degree: 5.117647
no-move positions: 6
unreachable positions: 6

moves shared with AIM: 336
moves not shared with any: 558
moves shared with HOP: 90
moves, total: 984
average out-degree: 4.823529
no-move positions: 24
unreachable positions: 48

moves shared with DIG: 90
moves not shared with any: 594
moves shared with SWAP: 180
moves, total: 864
average out-degree: 4.235294
no-move positions: 48
unreachable positions: 48

moves shared with HOP: 180
moves not shared with any: 432
moves, total: 612
average out-degree: 3.000000
no-move positions: 0
unreachable positions: 0

WILD moves: 2982

If we order them by total moves, we get this:

AIM: 1044
DIG: 984
HOP: 864
SWAP: 612
TIP: 432

If we perturb the numbers a bit (by 36 at most, which is less than 6% of the
relatively most perturbed number) and divide them by their greatest common
divisor, we get the sequence [4, 6, 8, 9, 10].  That is, the most flexible*
move (AIM) is about 2.5 times as flexible as the least flexible (TIP), and the
more flexible types are less different in flexibility than the least flexible

(* if we measure flexibility as simply the number of moves of each type, i.e.
taking each position as equally likely to be in, which probably isn't true)

I have also confirmed what I have previously hypothesized and argued: that it
takes four moves to go from the starting position to the ending position, but
only two moves in the other direction.

More completely, the numbers of pairs of positions such that it takes d moves
to go from the first to the second, grouped and sorted by d, are these:

0: 204
1: 2970
2: 14706
3: 19716
4: 3996
5: 24

(for d=0, this obviously has to be the number of possible positions)

Note that these numbers are divisible by 6, as there are 6 different size
permutations; in particular, there are only 4 "truly different" pairs of
positions which are 5 moves apart.  They are:

 - 1L 2U 3U to 2R 3L 1R
 - 1L 2U 3R to 2R 3L 1R
 - 1L 2U 3R to 3L 1R 2L
 - 1U 2U 3R to 3L 1R 2L

(by this notation, the default house is 2L 1U 3R; I hope this explains it)

Even if one feels that games are too short, we see that the only way to make
the shortest games longer means having to remember some not-so-nice positions.
So kudos to Andy for making a good design choice :)

That's it for now; If anyone wants the 318 lines of python code which does
this counting, let me know.

I think I need to move from looking at the game as a graph to looking at the
game as a markov decision process to come up with more interesting numbers.  I
might, but I make no promises.  If anyone wants to beat me to it, feel free :)

Jonas Kölker <jonaskoelker@xxxxxxx> <URL:http://jonaskoelker.ignorelist.com>

Attachment: signature.asc
Description: Digital signature