Nolan’s Birthday Party

SNW played at Nolan’s birthday party:

• 01
• 02
• 03
• 04
• 05
• 06
• 07
• 08
• 09
• 10
• 11
• 12
• 13
• 14 - When You Love
• 15
• 16 - Layers
• 17
• 18
• 19
• 20

The session was pretty good. We were solid, pretty together, and groovy. My biggest problem with it is that we sounded a lot more like a “jam band” than usual. I have a conjecture: pot + guitar = jam band.

That said, #14 is cool (there’s an 8 minute solo psychedelic keyboard intro, followed by a groove with a nice feel). #15 has great energy and #16 is soulful.

UPDATE And of course I forget to give credit to the many musicians involved:

• Eric, Luke, Evan — The usual
• Nolan McFadden — Guitar, vocals
• Devon — Guitar
• Willow — Vocals
• Chris Mandel — Clarinet

Typesetting Fractals

You don’t need any fancy graphics plotter to draw fractals. You can just use Mathematica’s (fancy-schmancy) typesetter. I entered the following into Mathematica:

And I got this.

Highly Composite SQL

I’m just learning about SQL. I have this query:

SELECT div.number
FROM divisors div
WHERE 0 = (SELECT COUNT(*)
	   FROM divisors t
	      , numdivisors(div.number) djn
	   WHERE t.number < div.number
	     AND numdivisors(t.number) >= djn)
GROUP BY div.number

Where numdivisors is defined as:

CREATE FUNCTION numdivisors(integer)
  RETURNS bigint AS $$
	SELECT COUNT(*) FROM divisors WHERE number = $1
$$ LANGUAGE SQL;

And divisors is just a table which relates number, divisor, multiplicity in the obvious way. It stores numbers from 2 to 100 (so it has about 382 rows).

The problem is that this query takes about two seconds to run (on postgres). I don’t understand why. The equivalent Haskell (for lenient definitions of “equivalent”):

divisors :: Integer -> [(Integer, Int)]
divisors n = divisors' d mul
    where
    divisors' d mul
        | d <= n  =
            if n `mod` d^(mul+1) == 0
                then divisors' d (n+1)
                else (if mul > 0 then [(d,mul)] else [])
                          ++ divisors' (d+1) 0
        | otherwise = []

numDivisors :: Integer -> Int
numDivisors = length . divisors

filter (\div ->
    let nd = numDivisors div in
        null $ filter (\t -> numDivisors t >= nd) [2..div-1])
    [2..100]

Is almost instantaneous. And if I had to make a bet, I’d say that the Haskell version is doing more work because it’s computing the divisors on the fly, too, whereas my SQL table already held them. But then it’s always hard to tell how much work Haskell is actually doing because of its laziness and my lack of understanding thereof.

How do I speed up that SQL?…

Oh, I should probably say, this query is computing the Highly Composite Numbers.

Template Haskell to the rescue!

I just posted an article where I needed to use the (ugh) C preprocessor in a Haskell program. Well, thank the gud lawd that’s not true. I remembered learning about the existence of Template Haskell some time ago. That means I can abstract the whole Accessor thing out into another module. I will soon be able to generate accessors automatically based on the state declaration!

Anyway, the modified files are here:

• Accessor.hs
• nicegame.hs

Making Haskell nicer for game programming

Last week I tried to create a board game programming architecture in Haskell. The idea was to base the architecture around specifying an abstract state machine for the game. As we discussed in GameDev this week, abstract state machines aren’t exactly appropriate for games, but they’re close enough that you can make a few modifications to the idea and get something cool (the biggest modification being that your set of rules is part of your state).

Haskell was a joy to work with in this sense. I made a monad which handled the transactional nature of ASMs; I differentiated between rules and actions in order to enforce the if condition then action structure which makes reasoning about ASMs easy. It was cool stuff, and it took about 100 lines of code.

Then I set out to write my first game with it. Just a simple bidding game I found somewhere; I don’t remember what it was called. And it hit me: games are stateful, definitely abstract state machines are stateful, and Haskell sucks when it comes to content programming for stateful systems. I was trying to show how easy it would be to specify a game with dynamically changing rules, and all I could think about was how to refactor the horribly ugly code that ensued.

For the first time ever, I used C macros in a Haskell program. There are a lot of good reasons not to do this. But it did make working with stateful data much easier. Here’s the idea:

First, let’s make our game state object:

data GameState
    = GameState { _p1bid :: Int
                , _p2bid :: Int
                , _score :: Int
                }

Because very few Haskellers read this blog, I’ll explain. That essentially declares a new class with three member variables, whose names you should be able to extract.

Now we make the monad in which we will perform game computations:

type Game a = StateT GameState IO a

When we perform a computation inside the Game monad, there is a “global” GameState at our disposal. But we also need to interact with the user (the computation is not “pure” in that sense), so we glob on the IO monad.

That was all fairly straightforward. Here’s the new stuff. Define an “Accessor” class, which abstracts over the ability of data inside the state to be read and written:

data Accessor a
    = Accessor { readVal :: Game a
               , writeVal :: a -> Game ()
               }

Again, it’s just a class—actually a template class abstracted over the type a—with two members, readVal and writeVal. Except this time the members have more complex data types. readVal performs a computation given no input (namely, to return the value), and writeVal performs a computation given an a as input (namely, to store the value back into the game state). We will define an Accessor object for each data member in our state, each with different implementations of readVal and writeVal.

Here’s where the macros come in. The implementations are different, but they are regularly different, but not abstractable due to limitations which ultimately boil down to Haskell’s type system (no partial records). We define a macro to define an accessor for us:

#define ACCESSOR(NAME) \
NAME = Accessor { readVal = fmap _ ## NAME get \
                , writeVal = \n -> get >>= \s -> put $ s { _ ## NAME = n } \
                }

Wow, that’s ugly. Fortunately it’s the last of the ugly we will see. For non Haskellers… I’m not going to explain that in detail. Suffice to say that it defines an Accessor object called NAME which does the right thing. It assumes that the element in our state being referenced is called NAME with an underscore prepended.

Now we define a few accessors:

ACCESSOR(p1bid)
ACCESSOR(p2bid)
ACCESSOR(score)

And now we can start defining some familiar procedural operations, like := (which we must spell =: because operators that start with a colon have a special meaning) and +=.

a =: x  =  writeVal a x

a += x  = do
    a_ <- readVal a   -- I would have called it a', but the C preprocessor doesn't like that
    a =: (a_ + x)

a -= x  =  a += (-x)

-- etc. etc.

If we were making this into a library, we would probably define the precedences to be saner, so we wouldn’t have to, for example, parenthesize (a_ + x) above.

And then you can go on defining your game:

main :: IO ()
main = flip evalStateT (GameState 0 0 0) $ loop $ do
    liftIO $ putStr "Player 1, bid: "
    bid <- liftIO readLn
    p1bid =: bid
    -- ...
    cmp <- liftM2 compare (readVal p1bid) (readVal p2bid)
    case cmp of
        LT -> score -= 1
        EQ -> return ()
        GT -> score += 1

Which feels an awful lot nicer. For comparison, score -= 1 would otherwise have been written:

get >>= (s -> put $ s { _score = _score s - 1 })

It still ain’t perfect. I don’t like that I have to read values from the state into temporary variables (well, I don’t have to, but I do if I want anything to be near readable). There’s really no way around that, except for more preprocessing!… which I’m not going to do.

Ladder Scoring

I was thinking about game ladder scoring recently. I recall being frustrated at Supreme Commander for putting me lower on the ladder than someone I’ve beaten. I want a ladder algorithm that won’t allow that.

In particular, I want a ladder function l: (P × P → Z) × P → R which assigns to each player a number and satisfies the following properties [P is the set of players, Z is the integers, R is the reals; the first argument to l is the set of games played: given two players p and q, it returns how many times p has defeated q]:

1. If g(p,q) > g(q,p) then l(g,p) > l(g,q) (if I’ve beaten you more times than you’ve beaten me, then I have a higher ladder score than you).
2. If for all players q, g(p,q) = h(p,q) and g(q,p) = h(q,p), then l(g,p) = l(h,p) (your score doesn’t change if you haven’t played any games).

Of course, property #1 already causes problems. Let’s say p has defeated q once, q has defeated r once, and r has defeated p once; the vice-versas are zero. Then l(g,p) > l(g,q) > l(g,r) > l(g,p), which is impossible. I really had no right to be mad at Supreme Commander for ranking someone I had defeated above me; it’s impossible to avoid.

That doesn’t solve the problem though. Saying it’s unsolvable isn’t a solution… we’ve got to find the best solvable solution.

I could relax the constraint in rule #1 to be ≥ rather than >, but then the problem becomes too solvable. A plethora of trivial solutions emerges: l(g,p) = 0 for all p, l(g,p) = 0 for all p but the one person who has beaten every player more times than he has been beaten by them, etc. We need to add another property to get rid of these trivial solutions.

The ≥ constraint forces every player in a cycle to be assigned the same number. We can’t get around that. So maybe we can try to say that if you’re not in a cycle with a player, then your score is distinct from his.

I knew I put that second property in there for a reason. That, too, is impossible. Picture two cycles of size, say, 50. Pick one element p from the first cycle, q from the second. Can you change a bunch of arrows, as long as you don’t change any arrows to or from p or q to make the two cycles one big cycle? Of course you can. By our axiom, p’s and q’s scores were distinct, but now they’re in a cycle together, so one of them must have changed. But neither p nor q needed to play any games for that to happen. This violates our second property.

So basically you can’t even get close to the two properties I stated above. The fact is that player rankings are nothing like real numbers, so don’t try to force them in.

You can satisfy the second property without the first by summing over all players q the function f(p,q) where f is defined by:

f(p,q) = 1 if g(p,q) > g(q,p), -1 if g(p,q) < g(q,p), and 0 otherwise.

Which has the nice property that you can have many rematches without taking advantage of the scoring. But, of course, it doesn’t have the other nice properties that I want…

Abstract State Machines for Game Rule Specification

Jude has been working on the design of a general board game programming engine. We brainstormed a bit, and I remembered something I had read about a little while ago: Abstract state machines.

An ASM is really nothing more than a formalization of a simultaneous chain of if-then statements. A common example is Conway’s life: given a lattice and a countNeighbors function you could define the rules for Conway’s life as an ASM as follows:

letDie(cell, n) =
  if status(cell) = Alive and (n < 2 or n > 3) then
    status(cell) := Dead
letLive(cell, n) =
  if status(cell) = Dead and n = 3 then
    status(cell) := Alive

gameOfLife =
  forall cell in cells do
    letDie(cell, countNeighbors(cell))
    letLive(cell, countNeighbors(cell))

e only thing this is getting us over any type of program specification is the parallelism. But the idea of a list of rules, each of which has a condition and an action, is the right level of abstraction to make a board game engine.

We have to tweak a few things to get it just right. For example, you could have must and may combinators, which specify which moves are available to the player.

Let’s look at Pente. First, we assume a linked-list style lattice, where each cell has eight pointers indexed by direction (they could be abstract or just numbers or whatever), and then a link(direction, n) function gives us the cell in a particular neighbor. Then we could specify pente something like this (Haskellesque syntax now):

move s player =
  if color s == Empty then may $ do
    color s := player
    mapM_ capture directions
  where
  capture d = do
    let oneAway = link d s
    let twoAway = link d oneAway
    let threeAway = link d twoAway
    if color oneAway == color twoAway == otherPlayer player && color threeAway == player then do $
      color oneAway := Empty
      color twoAway := Empty

There are still a few issues to solve as far as expressing “you must do either A or B, then you must do C”. I actually used very little of the ASM model (just one may combinator) in expressing pente. Okay, idea on the backburner, let’s see what else comes.

Rehashing the Boilerplate

I’m about to start a big flash project, so I was looking at Flex. I watched their video demo, and besides obviously leaving out some key steps (such as where the hell that side panel came from—they didn’t make that during the video!), I didn’t really like the RoResque boilerplate approach that they took.

In fact, I don’t like boilerplates at all. It’s against my coding philosophy. Sure, it’s nice not to have to type something that doesn’t need to be there, but if it doesn’t need to be there, why is it there at all? It’s a bunch of garbage the reader needs to muck through.

This bit me the first time I wanted to distribute a Perl module. h2xs gives you a module distribution template, but I didn’t know about h2xs at the time. So I opened up one of Damian’s modules to see what I needed. I opened Makefile.PL and started copying by hand¹. I didn’t understand some of it; some of the empty definitions seemed unnecessary, but I obliged and copied anyway. Little did I know that what I copied was almost the exact boilerplate. Why was all that crap there? Why didn’t Makefile.PL look like this?

    use ExtUtils::MakeMaker;
    WriteMakeFile {
        name => 'Parse::RecDescent',
    };

That has all the information you need. “Oh, that’s straightforward” I would think, as opposed to “hmm, what’s this here for, hmm, this seems unnecessary, hmm, this seems unnecesary, hmm, this seems unnecessary”.

Boilerplates are a sad excuse for inheritance. I mean, that’s what it is, isn’t it? “I want everything the same as it was in this other project, except this thing.” But we know that it’s not a good idea to just copy an old project and start modifying it. What if there was a bug in the one you copied; there’s now a bug in the new one! So why are boilerplates any better?

“Well, because they’re small enough that you can verify that all the bugs are out of them.” I doubt that. But let’s suppose that’s true for this paragraph. That’s not the only benefit of inheritance. If you refactored some functionality into a convenience feature to the project you copied, you don’t benefit from it in your new project. If you added support for some slick graphical slide in in one project, you have to re-implement (or copy-paste again, and think of the bugs man, think of the bugs!) in the other.

Needing a boilerplate for a library, be it Flex or Ruby on Rails or whatever, is not a good thing. It’s an indication of a bad library design: a library that makes you specify more than you need to think about. If a project requires loading up a boilerplate and changing one line, the size of this project should be three lines, not the 500 from the boilerplate:

1. Use the library
2. What to override
3. The thing you override it with

You get some benefits this way. First, readers of your code who are familiar with the library can immediately see what your program does without having to read through the whole boilerplate (or diff against the boilerplate). Second, you are free to change anything in the library code and the benefits will filter down into client programs (again, without forcing them to do a diff/patch).

But boilerplates do have their advantages, too. For example, in the library design I just presented, the library designer has to be aware of everything you’ll want to override. Now, that’s sort of a good thing, because the library designer is aware of what his interface is so he knows what will and what won’t break backward compatibility. But this is also sort of a bad thing, because library designers generally suck at deciding that. They think their word is absolute, “you shouldn’t have changed that part, it belongs to me“, when at the end of the day what matters is whether your application got written. If you need to change a configuration timeout that was stored in a source file of the library and not abstraction (see RakNet :-), you’re pretty much boned.

To do a boilerplate in an efficient manner, you have to have excellent version control support. svk can do the job, git probably can too (I actually haven’t looked into it). Basically, your codebase needs to be a branch of the boilerplate’s codebase. This means that when the guy who wrote the boilerplate (even if it’s you) changes something, you can integrate the changes back into your application. Merge conflicts will tell you when you need to rethink how part of your application works because someone rethought how the boilerplate worked.

Using version control like that is like using prototype-based OO on the entire project scale. Prototype OO tends to be high on flexibility and low on abstraction. Which is okay, but when you try to make a project that uses components from two branched projects, you have a lot of work ahead of you.

There really is no process excuse for writing code the right way. You can get some of what you want by using boilerplates and version control, but your code’s reusability will eventually suffer. At some point, you have to be a mathematician: you have to think about the essential algebra of your program and factor that into a core, and program the fluff functionality as plugins. Not soft-coding: keep general extensions in a Turing-complete language. But there is no substitute for good ol’ modular, well-thought-out design².

Preachy rants for everyone!

¹I never use copy/paste when I’m programming. In this case it means that I have to read what I’m putting in my code base, so I can start to understand it instead of just relying on “it works, leave it be”. In cases where I know what I’m doing, it forces me to refactor and abstract because I get tired of typing.

²Please note that I did not say object-oriented. Object oriented design is a great methodology to achieve modularity most of the time. But being object oriented neither implies being modular nor vice versa.

Incompleteness Razor

I’ve been wondering about “levels of incompleteness”. There might be some cool decidability theory hiding in here. I started the exploration with a few definitions (and haven’t gotten very far):

A recursive set of sentences A is called weakly incomplete if A is incomplete and there is a recursive set of sentences S ⊃ A which is complete.

A recursive set of sentences is called strongly incomplete if it is incomplete and not weakly incomplete.

We know that number theory (+,*,exp) is strongly incomplete by these definitions; i.e. it is incomplete, and if you try to complete it, its incompleteness will just pop up somewhere else. This is Gödel’s incompleteness theorem. The question is the converse: is every strongly incomplete set of sentences strong enough to contain number theory (Turing complete)?

Here is an easy theorem:

Theorem: all models of a strongly incomplete set of sentences are infinite.

Proof: Let A be a strongly incomplete set. Call the number of finite models of A n. Note that n is finite. Let φ be a sentence independent of A. There is a model of A in which φ holds and a model in which ¬φ holds. Pick one according to your favorite football team. Add φ or ¬φ to A, and note that n has just decreased by at least one. Repeat until one of these holds:

1. There is exactly one finite model of A. By the completeness theorem, A is now complete. However, the above was a finite process, so A is still recursive, so it was actually weakly incomplete.
2. There are no finite models of A. The last φ or ¬φ we chose must not have been independent of A; in fact we just proved its negation. So this case is impossible. If there were no finite models to start with, then we’re done because we were trying to prove that.

EDIT This theorem is invalid. When I say “note that n is finite”, I have made an error. There needn’t be finitely many finite models. I conject that the theorem is still true, but I have to find a different proof.

I could have sworn that when I went on a walk today to think about this stuff, I had a proof that if every strongly incomplete set embeds number theory then there is a decision procedure for determining whether a sentence is independent of a weakly incomplete set. I can’t remember it now!

Green Globs

When I was going to Fairview High School, I spent a lot of time in the basement math annex, a computer lab for math classes which was empty most of the time (except for me and my nerdy friends). There was a game installed on that computer called Green Globs, a little math game about graphing equations. I spent many, many hours playing this addictive game, and it also gave me a nice graphical mathematical intuition.

I recently started learning Flash (w/ActionScript 3.0) because I want to start prototyping games like a madman. As a learning project I cloned this game. This is an early version, but the nice thing about Flash is that it’s really easy to polish things. So this game is tolerable even though I’ve only worked on it for a couple days.

Here’s the link: Revenge of Green Globs.