but it wouldn't shock me to discover that the person that goes second can always win.

I originally thought so too, but it turns out that the person who goes first can always win. (That is, if he makes a move to 0-3-5-6, 1-3-4-6, or 2-3-4-5. Those positions are unwinable if the game is played perfectly.)

John