tile_puzzle: A Python tile puzzle emulator with simple solver

During the last couple of months I have been attending a module on artificial intelligence and machine learning in games. One of the basic algorithms the course looks at is the best-first search for making in-game decisions such as the next move in chess. In class, we used A* search (finding the shortest possible path from one node to another – an extension of best-first search) to solve a puzzle like the one below – a selection of sliding tiles in a housing that allows for one tile to move at a time.

A 15-tile puzzle with 16 spaces, also known as a fifteen-puzzle.

Beginning with a scrambled (but legal) board state, the algorithm uses a heuristic to assign values to every possible next state, puts them in a list of open states, and then picks one of those states to move to. Then it does the same thing again, adding new board states to the open list and already-used states to the closed list. This continues until it has reached a predefined goal state – in this case, the start state. The heuristic takes into account not just the closeness of the state to the goal, but also how many moves it took to get to the state. That is what allows it to find the shortest path every time.

I liked this algorithm when I heard it the first time, but it wasn’t as clear to me as I would have liked. This time, I decided to make sure I understood – by implementing it in real code. I began with emulating the tiled board. The board state is simply a two-dimensional list, which is generated in the start (or goal state). Random legal moves are then made on the state to generate a random, legal, board state.

The other part of the program is a solver, which creates an instance of the board and randomises it. Then it uses the algorithm described above to attempt a solution. I say ‘attempt’ because even at the 15-puzzle level, complicated board states can take more than a few hours to solve. The 24-puzzle is considerably more complex, so I don’t even consider it here, although the code will work for a square board of any size from two upwards.

I enjoyed this project because it was fun to use Python in a new context – solving heuristic problems. Previously I had only done this with Java. I learned a lot about how A* algorithms work, and got some experience with designing for general solutions. I designed the code to work with any size board, and made it possible to solve different problems using the same solver.

The code is available on GitHub. Below is a fairly simple execution log of a 24-puzzle with 20 random moves on it.


Size: 5
Random iterations: 20
Randomising: 20 iterations
Tiles out of place: 11
Isolated moves from goal state: 39
1
2
3
4
5
6
7
8
9
10
Found it after 10 moves
Total children added to open list: 21691

| 1| 2| 3| 4| 5|
| 6| 7| 8| 9|10|
|11|12|13|14|15|
|16|17|18|19|20|
|21|22|23|24| 0|

| 1| 2| 3| 9| 4|
| 6| 7|13| 8| 5|
|11|12|18|14|10|
|16|17|19| 0|15|
|21|22|23|24|20|

| 1| 2| 3| 9| 4|
| 6| 7|13| 8| 5|
|11|12|18|14|10|
|16|17| 0|19|15|
|21|22|23|24|20|

| 1| 2| 3| 9| 4|
| 6| 7|13| 8| 5|
|11|12| 0|14|10|
|16|17|18|19|15|
|21|22|23|24|20|

| 1| 2| 3| 9| 4|
| 6| 7| 0| 8| 5|
|11|12|13|14|10|
|16|17|18|19|15|
|21|22|23|24|20|

| 1| 2| 3| 9| 4|
| 6| 7| 8| 0| 5|
|11|12|13|14|10|
|16|17|18|19|15|
|21|22|23|24|20|

| 1| 2| 3| 0| 4|
| 6| 7| 8| 9| 5|
|11|12|13|14|10|
|16|17|18|19|15|
|21|22|23|24|20|

| 1| 2| 3| 4| 0|
| 6| 7| 8| 9| 5|
|11|12|13|14|10|
|16|17|18|19|15|
|21|22|23|24|20|

| 1| 2| 3| 4| 5|
| 6| 7| 8| 9| 0|
|11|12|13|14|10|
|16|17|18|19|15|
|21|22|23|24|20|

| 1| 2| 3| 4| 5|
| 6| 7| 8| 9|10|
|11|12|13|14| 0|
|16|17|18|19|15|
|21|22|23|24|20|

| 1| 2| 3| 4| 5|
| 6| 7| 8| 9|10|
|11|12|13|14|15|
|16|17|18|19| 0|
|21|22|23|24|20|

| 1| 2| 3| 4| 5|
| 6| 7| 8| 9|10|
|11|12|13|14|15|
|16|17|18|19|20|
|21|22|23|24| 0|

Did it in 10 moves.

Advertisements

Posted on 1 November, 2012, in Blatant self-indulgence, Coursework, Game Development, Links, Main, Open Source, Portfolio. Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Zeouterlimits's Blog

Just another WordPress.com weblog

Smaointe Lambo

Lambo's thoughts on Lambo's intrests.

Colm's Blog

Full of games, programming and overblown opinions

jester252

Just another WordPress.com site

xtremesolutionsie

Just another WordPress.com site

Project Management Blog

Learning in the module

Paul's Plethora of Peculiar Posts

Here be dragons (made of bad jokes, puns and weird imagery.)

Sophie O'Gara's blog

Creativity shall make dreams soar

Les Divagations d'une Jeunesse Imaginative

The ramblings of an imaginative youth

Phil's Blog

A blog about Philip and his opinions on Video Games, Art and just general Navel Gazing

Conor Murphy

Not sure if you know this but, I’m kind of a big deal

Some general vizardry

A novice programmer's musings

andruQuinn

Problem solving in programming. A blog to give new views into problem solving

Player Two

Ludology from a developer

William Laffan

A Portfolio blog

Not Your Blog

Let's go in there and take out that dragon!

Lukes-Site

Gravity-It's not just a good idea, it's the LAW!

wi11iamcb

The quite mutterings of a madman

%d bloggers like this: