Block puzzle problem and searching

[Guest]

Archived from groups: comp.ai,comp.ai.games (More info?)

Hi,

I'm trying to solve the block puzzle with python.

For those of You who don't know it, here is a short description:
# a starting state of a 8-puzzle could look like the following:
# where X is the empty space
# You can move any neighbour (x-axis or y-axis) to the empty space
# ------------
# | 7 2 4 |
# | |
# | 5 X 6 |
# | |
# | 8 3 1 |
# ------------

# the goal is to reach this state:
# ------------
# | X 1 2 |
# | |
# | 3 4 5 |
# | |
# | 6 7 8 |
# ------------

Now my question is about the design. At the moment I have three
classes: Solvepuzzleagent, puzzle and binarytree.
1) Should the puzzle be extended by a tree or should there be a
seperate tree containing the states?
2) So if I have the class puzzle should I create a seperate tree where
each node is a puzzle object in a different state?
3) Which class should take care of the expansion of the fringe? The
puzzle class or the agent?
4) How do I take care of repeating states?

Thanks.

[ comp.ai is moderated. To submit, just post and be patient, or if ]
[ that fails mail your article to <comp-ai@moderators.isc.org>, and ]
[ ask your news administrator to fix the problems with your system. ]

 

[Guest]

Archived from groups: comp.ai.games (More info?)

<benjamin.cordes@blawrc.de> wrote in message
news:421103ff$1@news.unimelb.edu.au...
> I'm trying to solve the block puzzle with python.

It's called 'sliding tile puzzle.'

> For those of You who don't know it, here is a short description:
> # a starting state of a 8-puzzle could look like the following:
> # where X is the empty space
> # You can move any neighbour (x-axis or y-axis) to the empty space
> # ------------
> # | 7 2 4 |
> # | |
> # | 5 X 6 |
> # | |
> # | 8 3 1 |
> # ------------
>
> # the goal is to reach this state:
> # ------------
> # | X 1 2 |
> # | |
> # | 3 4 5 |
> # | |
> # | 6 7 8 |
> # ------------

Actually, the classic final state is:

1 2 3
8 4
7 6 5

> Now my question is about the design. At the moment I have three
> classes: Solvepuzzleagent, puzzle and binarytree.
> 1) Should the puzzle be extended by a tree or should there be a
> seperate tree containing the states?
> 2) So if I have the class puzzle should I create a seperate tree where
> each node is a puzzle object in a different state?
> 3) Which class should take care of the expansion of the fringe? The
> puzzle class or the agent?
> 4) How do I take care of repeating states?

Sorry, can't help you with Python programming. But maybe you shouldn't
bother inventing the wheel again; there is at least one freeware version
available:

http://home.chello.no/~dudley/

Cheers,
Daniel

 

[Guest]

Archived from groups: comp.ai,comp.ai.games (More info?)

<benjamin.cordes@blawrc.de> wrote in message
news:421103ff$1@news.unimelb.edu.au...
> I'm trying to solve the block puzzle with python.

It's called 'sliding tile puzzle.'

> For those of You who don't know it, here is a short description:
> # a starting state of a 8-puzzle could look like the following:
> # where X is the empty space
> # You can move any neighbour (x-axis or y-axis) to the empty space
> # ------------
> # | 7 2 4 |
> # | |
> # | 5 X 6 |
> # | |
> # | 8 3 1 |
> # ------------
>
> # the goal is to reach this state:
> # ------------
> # | X 1 2 |
> # | |
> # | 3 4 5 |
> # | |
> # | 6 7 8 |
> # ------------


Actually, the classic final state is:

1 2 3
8 4
7 6 5

> Now my question is about the design. At the moment I have three
> classes: Solvepuzzleagent, puzzle and binarytree.
> 1) Should the puzzle be extended by a tree or should there be a
> seperate tree containing the states?
> 2) So if I have the class puzzle should I create a seperate tree where
> each node is a puzzle object in a different state?
> 3) Which class should take care of the expansion of the fringe? The
> puzzle class or the agent?
> 4) How do I take care of repeating states?

Sorry, can't help you with Python programming. But maybe you shouldn't
bother inventing the wheel again; there is at least one freeware version
available:

http://home.chello.no/~dudley/

Cheers,
Daniel

[ comp.ai is moderated. To submit, just post and be patient, or if ]
[ that fails mail your article to <comp-ai@moderators.isc.org>, and ]
[ ask your news administrator to fix the problems with your system. ]

 

[Guest]

Archived from groups: comp.ai,comp.ai.games (More info?)

1. It depends. Is the "puzzle" a visual representation of the problem,
or just the problem state? I would do this with a FIFO queue of {puzzle
state + how-I-got-here path}. Pull each state off the FIFO queue in
turn, test each possible move against an estimator function h^ and if
it's not egregiously bad, push it onto the FIFO queue. Stop when the
puzzle is solved. (A good estimator might be sum(err(x)) where err(x)
is the number of positions block x is away from its "correct"
position.) Is this what you mean by a "tree containing the states"?
Then, when the puzzle is solved you'd take how-I-got-here and map it to
the visual representation of the puzzle.

2. In a word, yes. Although I'm using a FIFO queue and not a tree.

3. Eh?

4. Could use a hash table as well as the FIFO queue and check against
it before you insert into the queue.

Max Wilson

[ comp.ai is moderated. To submit, just post and be patient, or if ]
[ that fails mail your article to <comp-ai@moderators.isc.org>, and ]
[ ask your news administrator to fix the problems with your system. ]

 

[Guest]

Archived from groups: comp.ai,comp.ai.games (More info?)

Thanks so far.
1) I will be using a dictionary for the state. There is really no
difference between the visual representation and the actual state.

3) The thing is I'm praticing AI design aswell, althougth this is of
course a rather simple problem - the way I'm tackling it at least. The
problem is I'm not sure which class should take care of the methods of
getting the next possible states. Should the puzzle itself provide the
next possible moves when asked or should the agent have to take care of
finding the next state?

[ comp.ai is moderated. To submit, just post and be patient, or if ]
[ that fails mail your article to <comp-ai@moderators.isc.org>, and ]
[ ask your news administrator to fix the problems with your system. ]

 

[Guest]

Archived from groups: comp.ai,comp.ai.games (More info?)

"benjamin.cordes@blawrc.de" <benjamin.cordes@blawrc.de> wrote in
news:42180111$1@news.unimelb.edu.au:

> Thanks so far.
> 1) I will be using a dictionary for the state. There is really no
> difference between the visual representation and the actual state.
>
> 3) The thing is I'm praticing AI design aswell, althougth this is of
> course a rather simple problem - the way I'm tackling it at least. The
> problem is I'm not sure which class should take care of the methods of
> getting the next possible states. Should the puzzle itself provide the
> next possible moves when asked or should the agent have to take care of
> finding the next state?

The puzzle should know what moves can be made from one of its states, and
how to make and unmake (undo) moves.

The agent requests a move list from the puzzle, decides which moves to try,
and tells the puzzle to make or unmake particular moves.

[ comp.ai is moderated. To submit, just post and be patient, or if ]
[ that fails mail your article to <comp-ai@moderators.isc.org>, and ]
[ ask your news administrator to fix the problems with your system. ]

 

[Guest]

Archived from groups: comp.ai,comp.ai.games (More info?)

>3) The thing is I'm praticing AI design aswell, althougth this is of
>course a rather simple problem - the way I'm tackling it at least. The
>problem is I'm not sure which class should take care of the methods of
>getting the next possible states. Should the puzzle itself provide the
>next possible moves when asked or should the agent have to take care
of
>finding the next state?

Ah, I see. You're not asking about class design.

It depends upon the flavor of AI that you're making. If it's supposed
to have complete knowledge of its environment (like in chess), then it
doesn't matter which _class_ does the fringe expansion so long as the
AI can request it at will. Effectively it has to be part of the AI's
mind. I forget the terminology for this, but in Markovian terms it
means that the agent knows the state transition function f(state,
action) = {next-state, reward}. If on the other hand, you want the
agent to be ignorant of the state transition function (say you're doing
Q-learning or something) then you put the state transition function in
the environment (the puzzle), and the agent has to learn through trial
and error what the rules are for moving. Note: you still need to make
the environment give a list of next possible _actions_, but that's not
the same thing as letting it know what next-state results from each
action.

Keywords: Markov Decision Process (MDP), Q-learning.

Max Wilson

[ comp.ai is moderated. To submit, just post and be patient, or if ]
[ that fails mail your article to <comp-ai@moderators.isc.org>, and ]
[ ask your news administrator to fix the problems with your system. ]

 

[Guest]

Archived from groups: comp.ai,comp.ai.games (More info?)

Hi,
I think that this is a relatively small problem, and as your
branching factor is just 4 (i.e. at ever state of the game, you have
four possible moves), it will be very easy to solve this with Breath
First Search. In that case you will not need a tree. You said you have
a class called "puzzle". I presume that the data-structure that stores
the state of the board is in this class and the path that was taken to
reach to that state.

Now all you need is to make an huge array of pointers (implemented as
a queue) for "Puzzle" class. Now take initial state, and generate the
four possible states from that, i.e.

>From initial state puzzle class which looks like:

# ------------
# | 7 2 4 |
# | |
# | 5 X 6 |
# | |
# | 8 3 1 |
# ------------



you can have four new states as below:

1)

# ------------
# | 7 X 4 |
# | |
# | 5 2 6 |
# | |
# | 8 3 1 |
# ------------

2)

# ------------
# | 7 2 4 |
# | |
# | X 5 6 |
# | |
# | 8 3 1 |
# ------------


3)

# ------------
# | 7 2 4 |
# | |
# | 5 6 X |
# | |
# | 8 3 1 |
# ------------


4)

# ------------
# | 7 2 4 |
# | |
# | 5 3 6 |
# | |
# | 8 X 1 |
# ------------



Store each of above state in a "puzzle" class of its own and insert
them into the queue. Now once again take out the first element of the
queue and process that to produce four more states and insert these
states in the end of the queue too... At each iteration check if you
have reached the goal state, and if so, print the path and exit. You
will not only get a solution but it will be the shortest path solution.


Regards,
Bhavesh

[ comp.ai is moderated. To submit, just post and be patient, or if ]
[ that fails mail your article to <comp-ai@moderators.isc.org>, and ]
[ ask your news administrator to fix the problems with your system. ]

 

[Guest]

Archived from groups: comp.ai,comp.ai.games (More info?)

Bhavesh,

That works okay for a puzzle this small (9^4 tries max?) but what if
it's 4x4 or 5x5? Instead of strictly breadth-first search, why not
branch-and-bound? Especially if he's doing this for practice at larger
things.

Key idea: instead of ordering the proposed solutions by # of moves made
to get to this point, order by h = number of moves up to this point +
g^ = estimated number of moves to finish puzzle, where g is an
estimator function of g = optimal number of moves to finish puzzle from
this position, chosen such that g >= g^. (g^ is an optimistic
estimate.) In this case, a simple estimator function is sum(# of places
each tile is removed from its "correct" position). IIRC, this will
produce the same answer as Bhavesh's algorithm but will arrive at the
answer faster.

Keywords: branch-and-bound, dynamic programming.

Max Wilson

[ comp.ai is moderated. To submit, just post and be patient, or if ]
[ that fails mail your article to <comp-ai@moderators.isc.org>, and ]
[ ask your news administrator to fix the problems with your system. ]