Philosophy Forums
Forums Links Articles Gallery Chat
Style:


Calendar Quick Links open HelpRegister
Philosophy Forums » Logic and Philosophy of Math » Logic Homework » Improving a Search Heuristic for symmetric number-board game » Improving a Search Heuristic for symmetric number-board game

Improving a Search Heuristic for symmetric number-board game
Logic Heuristic Search

printPrint


Improving a Search Heuristic for symmetric number-board game
Shaitan00
Initiate

Usergroup: Members
Joined: Feb 09, 2008
Total Topics: 2
Total Posts: 3
Posted 03/10/08 - 10:28 PM:
Subject: Improving a Search Heuristic for symmetric number-board game 		quote post
#1
Board (4x3)
A B C D
E F G H
I J K L

You have 11 chips [1,1,1,1], [2,2,2,2], [3,3], [4] (for example) placed randomly on the 4x3 board in slots A,...,L and one empty slot (that moves) that we'll call X, the movements are done similarly to the 8-puzzle game where X (empty) can move either up/down/left/right.

The Goal is to ensure that the top row and bottom row are symmetric (middle row is irrelevant) - so the following would be valid solutions:
1 1 2 2
3 3 4 X
1 1 2 2
or
1 1 2 3
X 2 4 2
1 1 2 3
As you can see in both cases the TOP and BOTTOM rows are symmetric (identical)...

So - just to help understand the game a little - assume you have the following flow from initial state to goal state:
STATE(0)
3 3 1 1
4 2 1 2
3 3 1 X
--> Move LEFT

STATE(1)
3 3 1 1
4 2 1 2
3 3 X 1
--> Move UP

STATE(2)
3 3 1 1
4 2 X 2
3 3 1 1
!!! GOAL !!!

Therefore - my problem is to find out what is the BEST MOVE (up, down, left, right) to make.
Assume you are at STATE(0) in the example above, where do you move X to get the best result thus leading you closer to a GOAL? X could be moved UP or LEFT (two options) so why pick one over the other? The solution is to evaluate the two possible outcomes and pick the better one ... this is the part where I need help, the EVALUATION algorithm needed to choose the next best move.

My current method works rather well but not well enough to win first place (I think - needs to be under 3-seconds to solve puzzle) - I call it "Number of non-Symmetric Pairs" and it works as follows:
- For each state calculate the number of non-symmetric pairs and make the move that gives you the lowest number
- If you have equal lowest-numbers then choose one at random

Let me illustrate - for starters this would be the value for the states listed in the example above:
STATE(0) = 1 (as the 4th pair isn't symmetrical)
STATE(1) = 1 (as the 3rd pair isn't symmetrical)
STATE(2) = 0 (as all pairs are symmetrical)

Where this works - assume we are at STATE(1), we have 3 choices: LEFT, UP, RIGHT - which would each yield the following values:
STATE(1)->LEFT = 2
STATE(1)->UP = 0
STATE(1)->RIGHT = 1
Therefore the lowest number is 0 and we should move UP because that will generates less non-symmetrical pairs (and lucky for us in this case it is also the goal).

Where this doesn't work so well - assume we are at STATE(0), we have 2 choices: LEFT, UP - which would each yield the following values:
STATE(0)->UP = 1
STATE(0)->LEFT = 1
As you can see the values are identical, so in this case I cannot determine which move is best so I must try both routes, which in turns costs me a lot of time I was hoping I wouldn't have to waste.


With that said - I am looking to find a more "informed" (efficient, intelligent) function/algorithm to help me solve my problem quicker and in less moves which therefore yields a more favorable results.
Along the same lines I am trying to see if there is another or better way to evaluate how close one move is to a goal when compared to another...

Any ideas, hints, help you might come up with would be much appreciated.
Note that the cells could have words, colors, numbers - this was just an example to help illustrate how it works.

Thanks,
Download thread as


You don't have permission to post.

Please login or register.

Contact the Administration

Powered by WSN Forum

16 total queries
This page was created in 0.65 seconds
Memory used: 6145512 bytes
Server Status: time since last reboot is 111 days, 21:20, load average: 0.65, 0.80, 1.19