number of Blokus games?
Mood: awake
Posted on 2008-02-28 13:50:00
Tags: math
Words: 253

Last night we were playing Blokus and I wondered how many possible games of Blokus there were. Todd said it shouldn't be too hard to figure out, so I'm gonna start working on a script to calculate it. I'm assuming the colors all start in a fixed corner and normal rules apply (except you have to play a piece if you can), and I'm counting the number of games and not the number of board positions because it seems easier.

How many possible games do you think there are? For reference, there are somewhere around 10¹⁴ legal board positions in Connect 4, 10⁵⁰ board positions in Chess and 10¹⁷¹ board positions in 19x19 Go (from this Wikipedia article, which unfortunately doesn't list the number of games) I'm going to guess something like 10⁸⁰ which, come to think of it, means it might not be possible to count them all in a reasonable length of time. Still, worth a shot!

Thousands of people might be infected with Hepatitis C or HIV in Las Vegas. From the article,

The virus may have been spread when clinic staff reused syringes and used a single dose of anesthesia medication on multiple patients, the district said.

To retain its state license and Medicare certification, the center faces increased on-site inspections and fines yet to be determined.

3 comments

Comment from medryn:
2008-02-28T14:57:00+00:00
I would think board positions is easier. But the problem seems wicked hard. I'd just find a crude upper bound and call it a day :-)

Comment from gregstoll:
2008-02-28T15:05:28+00:00
It seems like an easier process just to generate all legal moves from a board position and go from there.

Plus, is it possible to generate a board position that's legal but couldn't actually be reached from a real game? I was thinking yes (which would make counting board positions very tricky) but now I'm thinking maybe not, which would at least make it a little easier.

Comment from djedi:
2008-02-29T11:18:18+00:00
The rules are so simple (each player plays a piece one at a time and they must touch your own pieces precisely diagonally), that I'd be seriously surprised if there was a legal end game board that wasn't reachable by play. In fact, I'm pretty sure every end game board is reachable. At the end, every player's pieces have room and touch diagonally and you cuold pick them all up and then play them all down again, "legally" (except you are taking all your turns at once instead of alternating, but it doesn't matter if you already have an assigned place to play...you KNOW you aren't interfering with anyone else's play).

The issue is that any given end game board configuration technically WILL have many ways to reach it. Essentially, your plays are a graph with a root node on the corner of the board. I was going to say you have a tree (the graph of the connections between the pieces), but you could have cycles so it's a ....cycle containing tree, which is just a regular group with a "special" node. Going from a GIVEN board configuration, you could count the number of different games that end that way, but it's highly dependent on the actual connections of the pieces for each player.

I agree Medryn, my thought was just quickly toss out a crude bound and go home happy. :)

This backup was done by LJBackup.