I'm trying to build up a program comparing number of strokes of algorithms BFS and two different A* (which has two heuristics) on a game of fifteen.
My issue is that counter count the same result for the three arrays of counters of BFS and and A*. Yet, I'm actually using three different arrays from a main (class Project) and I'm assigning three different variables for those strokes.
I think the problem comes from A*. For each of them I start with the father, then computing its heuristic and adding him to the frontier.
While the frontier isn't empty, I look if the initial state is the final state of the game of fifteen, else I remove it from the frontier and we search for his sons. I set their g value for all of them, I compute each of their heuristic to finally get their f value. If they aren't already in the frontier, I add them to it. Then I compare the F value of the first one in the frontier with each one within the frontier and instantiate the one with the best F value as the current_state.
int best_f_value=frontier.get(0).getFValue();
for(State s : frontier){
if(s.getFValue()<=best_f_value){
best_f_value=s.getFValue();
current_state=s;
}
}
Yet when looking for the counter, I always have the same number of strokes for BFS and A* with the heuristic of the number of misplaced tiles and A* with the heuristic of the Manhatan distance. This may appears once, but not always!!
I think the problem lies in the function of A* rather than the one used to compute its heuristic. Therfore here is the code of the second A*, he lookalike the first one with the misplaced tiles heurisitc.
public State aStar2(){
State child;
System.out.println("we entered A_star with Manhattan distance");
System.out.println("final:\n"+finalState);
/** current state of dfs algorithm **/
State current_state;
current_state = initialState;
current_state.computeHeuristic2();
current_state.computeValueF2();
//int best_f_value= current_state.getFValue();
int current_state_g_value = 0;
System.out.println(initialState);
// get alwhile(!frontier.isEmpty()){l possible actions from the given node
List<Action> actions = current_state.getActions();
//frontier is a Stack displaying not currently explored nodes
LinkedList<State> frontier = new LinkedList<State>();
// frontier already contains the first node
frontier.push(initialState);
// explored_nodes contains all explored nodes.
LinkedList<State> explored_nodes = new LinkedList<State>();
// this List is used to show the path
LinkedList<State> path = new LinkedList<State>();
while(!frontier.isEmpty()){
number_of_strokes_A2+=1;
// we found the goal
if(goal_test(current_state)){
for(State visited :path){
System.out.println(visited);
}
array_number_of_strokes_A2.add(number_of_strokes_A2);
System.out.println("nombre de coups A2 : " + number_of_strokes_A2);
number_of_strokes_A2=0;
System.out.println("on a réussi : \n" + current_state);
return current_state;
}
// We remove the current state from the frontier
// VERIFY THIS IS OKAY !!!
frontier.remove(current_state);
// We get all possible actions from the current state
actions = current_state.getActions();
// We add the current state to already explored nodes
explored_nodes.add(current_state);
//System.out.println(current_state);
path.add(current_state);
current_state_g_value = current_state.getValueG();
// We create every child
for (Action action : actions){
// we get a child from the execution of the current_state
child = current_state.execute(action);
child.setValueG(current_state_g_value);
child.computeHeuristic2();
child.computeValueF2();
if(!explored_nodes.contains(child)&&!frontier.contains(child)){
// This child not being already explored nor int the frontier we add it to the last one
frontier.add(0,child);
}
}
int best_f_value=frontier.get(0).getFValue();
for(State s : frontier){
if(s.getFValue()<=best_f_value){
best_f_value=s.getFValue();
current_state=s;
}
}
}
return finalState;
}
Ask me if the first A* is needed to compare. Here follows the heuristics.
They are in another file. I don't think they are guilty of anything.
public void computeValueF(){
// to be completed
f_value = getValueG() + getHeuristic();
}
public void computeValueF2(){
// to be completed
f_value = getValueG() + getHeuristic2();
}
public int getFValue(){
return f_value;
}
@Override
public int getFValue2(){
return f_value;
}
public int getHeuristic(){
return h_value;
}
public int getHeuristic2(){
//somme de la distance de Manhattan entre lemplacement couvrant de chaque case � sa position finale
int h2=0;
for(int i=0;i<9;i++){
h2+=Integer.valueOf(puzzle.charAt(i))%3-i%3+Integer.valueOf(puzzle.charAt(i))/3-i/3;
}
return h2;
// to be completed
}
@Override
public int compareTo(Searchable<Puzzle, PuzzleAction> o) {
// TODO Auto-generated method stub
if(this.getHeuristic()> o.getHeuristic());
return 0;
}
@Override
public void setValueG(int cost) {
// TODO Auto-generated method stub
g_value = cost+1;
}
@Override
public int getValueG() {
// TODO Auto-generated method stub
return g_value;
}
@Override
public void computeHeuristic() {
// TODO Auto-generated method stub
//nombre de cases mal placees
for(int i=0;i<9;i++){
if((Integer.valueOf(puzzle.charAt(i))-i)!=0){
h_value+=1;
}
}
}
@Override
public void computeHeuristic2() {
// TODO Auto-generated method stub
int h2=0;
for(int i=0;i<9;i++){
h2+=Integer.valueOf(Math.abs(puzzle.charAt(i))%3-i%3)+Math.abs(Integer.valueOf(puzzle.charAt(i))/3-i/3);
}
this.h2_value=h2;
}
Here are the results in number of strokes:
strokes BFS : [9, 7, 33, 33, 53, 53, 51]
strokes AStar1[9, 7, 33, 33, 53, 53, 51]
strokes AStar2[9, 7, 33, 33, 53, 53, 51]
This question is similar to this one answered by Ishamael but different as far as it was rather about a difference in implementing BFS and DFS
Ishmael is right about my heuristics that stays the same. Therefore I tried to modify the heuristic calculation method in order to reference to the current state and not to something that would never change. here is the method in Puzzle.java
@Override
public void computeHeuristic1(String s) {
// TODO Auto-generated method stub
//nombre de cases mal placees
h1_value=0;
for(int i=0;i<9;i++){
if((Integer.valueOf(s.charAt(i))-i)!=0){
h1_value+=1;
}
}
}
That we would use here in Problem.java
child.computeHeuristic1(child.toString());
I can add some more code if needed.
And I get those heuristics :
array_heuritics_1 : [9, 9, 9, 9, 9, 9, 9, 9
array_heuritics_2 : [130, 131, 131, 129, 129, 128, 1
The last one is aberrant as far as each tile can bring at most a 3+3 heuristic value. Therefore having something with a heuristic > 51 is untenable.
So I tried to show what the test is doing and I found something interresting:
the child.toString :
1 2 5
3 4 .
6 7 8
the value :
i : 0 & s.charAt(i) : 1
i : 1 & s.charAt(i) : .
i : 2 & s.charAt(i) : 2
i : 3 & s.charAt(i) :
i : 4 & s.charAt(i) :
i : 5 & s.charAt(i) :
i : 6 & s.charAt(i) :
i : 7 & s.charAt(i) : 6
i : 8 & s.charAt(i) : 7
i : 0 & s.charAt(i) : 1
i : 1 & s.charAt(i) : .
i : 2 & s.charAt(i) : 2
i : 3 & s.charAt(i) :
i : 4 & s.charAt(i) :
i : 5 & s.charAt(i) :
i : 6 & s.charAt(i) :
i : 7 & s.charAt(i) : 6
i : 8 & s.charAt(i) : 7
Actually we are not doing the test numbers by numbers but char by char and there is some blank space!
First, let's consider what would happen if your A* didn't use any heuristic (as it, if getFValue just returned getValueG). Note that when the algorithm starts it only has one node in the frontier, so it will be chosen. On each consecutive iteration the values in the frontier will be sorted by cost in a descending order (you can prove it by induction if you draw couple examples on paper), and the cost of the first element in the frontier will be either equal to the cost of the last or one bigger. Now as you run your loop that selects state, you will always end up choosing the very last element, because it will have the smallest FValue, and among such you always choose the last one. In other words, if the heuristic was not in place, your A* would behave exactly like your BFS (which already just chooses the last element).
Now let's say your heuristic was just a constant, e.g your getFValue was implemented as return getValueG + constant. You can show again that it would just behave as if it was just BFS by following very similar logic as above -- if you add a constant to values you compare, they will compare the same way.
Finally, it is easy to show that both your heuristics always return the same value. Note that they only depend on the puzzle, which is constant. In no way they depend on the current position of the agent. The manhattan distance heuristic should be adding up manhattan distances from the current position to all the goal positions on the map (or rather just to the closest one would be more meaningful as the heuristic). Instead it computes something that does not depend on the current position at all, which is wrong. And since the value it returns is always the same, it behaves like the BFS, due to the reasons I provided above.