The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

Designing Game Algorithms

A friend recently gave me a guest pass to try some online games at a place called Pogo (www.pogo.com).  I don't usually go in for this sort of thing, but decided to give it a try to satisfy my friend.  Surprisingly, the games were much better than I expected.

Anyhow, while trying out some of the different offerings I found myself wondering a few times about how they do certain things in some of these games.  For instance, they have one game where you have to solve jigsaw puzzles by dragging pieces around and fitting them together.  So, I wonder what sort of algorithm they might use to cut the picture into pieces, if they use any algorithm at all.  Maybe they have a number of pre-fabricated tile masks that they just choose randomly to apply to a given photo.

Another one that had me thinking was how they implement the computer opponent for a scrabble-like game called QWERTY.  It would be interesting to know how the computre opponent searches for words and optimizes board position efficiently.  Seems like it would be a very difficult problem to solve algorithmically beyond simply using a brute force approach.

So, anyone have any ideas on how these things might work?  Any other neat algorithms you've seen associated with simple online games?  I'm hooked :)
Reese Send private email
Thursday, March 01, 2007
 
 
"  Maybe they have a number of pre-fabricated tile masks that they just choose randomly to apply to a given photo."

That's an algorithm, truth be told.

You could have the pieces pre mapped, each piece with a pointer to the piece it hooks in with and graphically is complement edge shape.  Overlay on top as you said.

You could divide the image up into squares, generate random puzzle-piece like edge curves where each square meets another, hook those pieces together in memory as belonging together, then use the shape to mask out the graphics and randomize them over the screen.  When two compatible sides get close enough together as dragged by the player, "snap" them together.


As for scrabble, perhaps data structures as used by spell checkers could be adapted to spiral out from a word structure.  Also remember Scrabble's problem space is constrained by the letters you have available to play in your hand, combined with the fixed position letters on the board.
Dan Fleet Send private email
Thursday, March 01, 2007
 
 
Because of the limited number of letters in you hand the search space for scrabble is actually reasonably small. From 7 letters there's only 7! (5040) possible 7 letter words (and smaller numbers of words with less letters). Checking for all of those against a dictionary can obviously be done very quickly.

If you set up the dictionary in advance to find anagrams you don't need to check the 5040 different words, you can do it with a single lookup. You simply index the dictionary from the sorted letters of the word, and have the entry as a list of all valid anagrams.

Of course you still need to consider the various lengths of words, and the placement of the letters on the board.

An exhaustive search shouldn't take all that long. You might even have time to look a move ahead and try to maximize the difference between your score and your opponents (especially towards the end of the game when you have a better idea of what letters your opponent has).
Adam
Monday, March 05, 2007
 
 
Adam -
Part of being an excellent Scrabble player is extending words, or putting one word next to anotther (some day I must learn all the two letter words, remember that AA is a kind of lava in Hawaii).

So the search space is more than just the words you can form with your own tiles.
dot for this one
Monday, March 05, 2007
 
 
Ahh, it seems I should have expanded on the placement of letters on the board. It's possible to try every possible placement exhaustively in a reasonable time.

For each of the empty squares on the 15x15 board, you need to consider all 128 subsets (well, maybe not the empty subset) of your seven letters placed both horizontally and vertically. For each anagram of the subset see if all other words formed are valid, then calculate the score. That's only 57,600 possible different placements.

To speed things up further avoid squares which can't possibly be valid placements. It would be fairly simple to work out the allowable word lengths for each square in each direction before trying all the possibilities.

To handle the existing tiles forming part of a word just treat them as if they were in your hand for the anagram search, and reject any anagrams which don't match the actual placement of them.
Adam
Tuesday, March 06, 2007
 
 
> To handle the existing tiles forming part of a word
> just treat them as if they were in your hand for
> the anagram search, and reject any anagrams which
> don't match the actual placement of them.

Not good.  Let's suppose I have a four-letter word that's alone on a row.  This algorithm would have us check 11! permutations.  There are other reasons why it won't work.

The real Scrabble search algorithm is non-trivial. 

First, build a list of the places on the board in which it is possible to make a legal play.  If all of the tiles already on the board were blanks, and you had 7 blank tiles:  where could you play one or more tiles to form a word? 

Now you process the list of positions to see which ones can contain a word in the OSPD.  I first thought you'd do a wildcard search, e.g.

  ??CAT?

but it may be faster to do a search like this:

  [a...g][a...g]CAT[a...g]

where [a...g] are the letters in the rack; that eliminates any positions where the letters in the rack cannot possibly form a legal word. 

Now that you've pruned the positions down to a manageable number, you can start searching for real words, filling the empty cells in each position with combinations of letters from your tile rack and seeing if the result can be found in OSPD. 

Again, this is a search that can be made efficient:  If you have an F in your tile set and you find that there's no match for F??CAT? in OSPD, you don't need to check all of the ways that the remaining letters in your rack can fill the blanks, because none of them will make a word.

So now you have a list of all of the legal moves, right?  Wrong.  You now have to look at the board again.  For each position in your list, you have to look at every cell you've filled with a letter and see if the cells above or below it (or to the left/right, if the position is vertical) contain any letters.  If they do, you have to check all of the crossing sequences to make sure that they're in OSPD.  (I really have no idea if it would be better to do this search as part of the initial evaluation of positions.)

The speed of all of this is going to depend on how fast you can do pattern matches on the OSPD, and for that, I'd open up my Skiena and start reading.
Robert Rossney Send private email
Tuesday, March 06, 2007
 
 
While there are 11! (~39 million) permutations of those 11 letters there's no need to go through each one to check them all. You can find all the valid permutations with 127 lookups into an anagram dictionary. One lookup for each subset of the 7 letters in your hand.
Adam
Wednesday, March 07, 2007
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz