Tag: scrabble

20
Oct

Scrabble is Big!

I ran some simulations over the weekend, and I’ve found some interesting statistics I thought I’d share with you.

After 10,000 simulated games, the average number of moves per game was 23, and the average number of choices per move (i.e. the number of moves you could actually make at each move) is around 970. This means that a graph which stored all possible configurations of the board would contain around 970^23 nodes (ignoring repetitions). That’s huge! As a contrast, chess (which is considered pretty damned hard to solve) has on average 57 moves per game (from a quick Google search, this may be inaccurate) and has a branching factor of around 35, making a graph of size 35^57.
What have I gotten myself into?!

12
Oct

Specification

One deadline out of the way! We had to hand in the specification last Thursday, and so here’s a bit of an update on where I am with the project.

Firstly, the goals of the project. Mainly, this is going to be a reasearch project, and so I will be looking a lot into the existing methodologies in computer based Scrabble agents, and trying to extend them where I can. The goals of the project are going to be to:

  • First, define what optimality means for a Scrabble strategy
  • Produce an optimal algorithm
  • Attempt to find a greedy algorithm which produces comparable results to the current world class agents

After doing this, I will hopefully find the time to attempt to generalise the findings to games of the same classification to Scrabble (imperfect information games), but this is more of a pie-in-the-sky objective.
I used LaTeX to produce the specification report, and I have to say it’s proved invaluable. It makes document production so much easier, I will definitely be using it in the future. I’ve been a bit soft and have started using TeX Shop, which takes a lot of the headache out of it (syntax highlighting, a few useful macros, and pdf production in a handy little button). Give it a go!

Update: I’ve just looked back at this, and it’s amazing how the project evolved from these somewhat optimistic initial objectives. But I suppose the majority of projects have the same form of evolution.

25
Apr

Is Scrabble Greedy?

I was killing some time playing Scrabulous, and I started thinking about strategies. I don’t really regard Scrabble as being a particularly strategy based game, but there is a certain element of it to the game – and that strategy can help you win. So this lead me to think:

Is the best strategy to adopt in Scrabble a purely greedy one?

i.e., if at each turn, you play the word which will gain you the most points, do you have more chance of winning than if you were to adopt a different strategy. For example: if I have a Q in my tile set, and the highest score I can make this turn is by playing that with an I (a legal two letter word) – is it better for me to play this and grab some points now rather than hold back the Q and hope that I get some nice letters in the next few moves to make an even higher score?

Intuitively, I would hope there is a nicer solution than a purely greedy approach – but of course one would be difficult to find. As well as this, such a strategy might involve “counting tiles” in order to calculate probabilities.

Were the Greedy solution to be adopted, I think one would have to create a compound value for each playable word – which takes into account certain things. For example, does the word leave the Triple Word Score open to your opponent? Can your opponent append something to your word and gain more points from it (by, for example, extending the word to pass over a Double or Triple score)?

I think this is quite an interesting problem – and one which I shall be thinking about each time I can’t think of a good word to put down in Scrabulous. But I thought I might open it up to the internet in the hope that someone else, more intelligent than I, would find it interesting and propose a solution. Enjoy!