implementing hill climbing search for tic-tac-toe demo in java

[1ladki]

Hi, I am new to java and I am having troubles in implementing hillclimbing search in tic-tac-toe in java. I would appreciate any pointers to resolve the errors i am getting. Bellow is the error
TicTacToe Demo

Exception in thread "main" java.lang.Error: Unresolved compilation problem:
The method HillClimbingSearch(GameState) in the type TicTacToe is not applicable for the arguments ()

at TicTacToeDemo.hillclimbingDemo(TicTacToeDemo.java: 28)
at TicTacToeDemo.main(TicTacToeDemo.java:16)

here is my code

/*
* Created on Feb 15, 2005
*
*/
/*package aima.games;*/

/**
* @author Ravi Mohan
*
*/
public class TicTacToeDemo {
public static void main(String[] args) {
System.out.println("TicTacToe Demo");
System.out.println("");

hillclimbingDemo();

}

private static void hillclimbingDemo() {
System.out.println("HILL CLIMBING ");
System.out.println("");
TicTacToe t4 = new TicTacToe();
while (!(t4.hasEnded())) {
System.out.println("\n" + t4.getPlayerToMove(t4.getState())
+ " playing ... ");

t4.HillClimbingSearch();
GameState presentState = t4.getState();
TicTacToeBoard board = t4.getBoard(presentState);
board.print();
}
System.out.println("HILL CLIMBING DEMO done");
}

}

[WingedPanther]

You don't appear to have defined main.

[wim DC]

The error suggests that

t4.HillClimbingSearch();

needs a parameter, most likely like:

t4.HillClimbingSearch(t4.getState());

But that's quite stupid parameter as you do HillClimbingSearch from t4, and would get the state from t4.
So you can just make it with no parameters, and get the state in the TicTacToe class yourself, rather than asking a parameter.

(There's a main right there, the 1st line of the class)

[1ladki]

You don't appear to have defined main.

main is already defined as the first function in TicTacToe class. Its the way the hill climbing function gets called which gives me an error.

[1ladki]

The error suggests that

t4.HillClimbingSearch();

needs a parameter, most likely like:

t4.HillClimbingSearch(t4.getState());

But that's quite stupid parameter as you do HillClimbingSearch from t4, and would get the state from t4.
So you can just make it with no parameters, and get the state in the TicTacToe class yourself, rather than asking a parameter.

(There's a main right there, the 1st line of the class)

oxano, i tried passing null as parameter, but doesn't work. this example was a tutorial on aima ai website, the game was initially implemented with minimax search algorithm. i have to implement the same game using hill climbing now.
here is the hill climbing search class.
public class HillClimbingSearch extends NodeExpander implements Search {

public enum SearchOutcome {
FAILURE, SOLUTION_FOUND
};

private SearchOutcome outcome = SearchOutcome.FAILURE;

private Object lastState = null;

public HillClimbingSearch() {
}

// function HILL-CLIMBING(problem) returns a state that is a local maximum
// inputs: problem, a problem
public List search(Problem p) throws Exception {
clearInstrumentation();
outcome = SearchOutcome.FAILURE;
lastState = null;
// local variables: current, a node
// neighbor, a node
// current <- MAKE-NODE(INITIAL-STATE[problem])
Node current = new Node(p.getInitialState());
Node neighbor = null;
// loop do
while (true) {
List children = expandNode(current, p);
// neighbor <- a highest-valued successor of current
neighbor = getHighestValuedNodeFrom(children, p);

// if VALUE[neighbor] <= VALUE[current] then return STATE[current]
if ((neighbor == null)
|| (getValue(p, neighbor) <= getValue(p, current))) {
if (p.isGoalState(current.getState())) {
outcome = SearchOutcome.SOLUTION_FOUND;
}
lastState = current.getState();
return SearchUtils.actionsFromNodes(current.getPathFromRo ot());
}
// current <- neighbor
current = neighbor;
}
}

public SearchOutcome getOutcome() {
return outcome;
}

public Object getLastSearchState() {
return lastState;
}

private Node getHighestValuedNodeFrom(List children, Problem p) {
double highestValue = Double.NEGATIVE_INFINITY;
Node nodeWithHighestValue = null;
for (int i = 0; i < children.size(); i++) {
Node child = (Node) children.get(i);
double value = getValue(p, child);
if (value > highestValue) {
highestValue = value;
nodeWithHighestValue = child;
}
}
return nodeWithHighestValue;
}

private double getValue(Problem p, Node n) {
return -1 * getHeuristic(p, n); // assumption greater heuristic value =>
// HIGHER on hill; 0 == goal state;
}

private double getHeuristic(Problem p, Node aNode) {
return p.getHeuristicFunction().getHeuristicValue(aNode.g etState());
}
}

[1ladki]

oxano, i tried passing null as parameter, but doesn't work. this example was a tutorial on aima ai website, the game was initially implemented with minimax search algorithm. i have to implement the same game using hill climbing now.
here is the hill climbing search class.
public class HillClimbingSearch extends NodeExpander implements Search {

public enum SearchOutcome {
FAILURE, SOLUTION_FOUND
};

private SearchOutcome outcome = SearchOutcome.FAILURE;

private Object lastState = null;

public HillClimbingSearch() {
}

// function HILL-CLIMBING(problem) returns a state that is a local maximum
// inputs: problem, a problem
public List search(Problem p) throws Exception {
clearInstrumentation();
outcome = SearchOutcome.FAILURE;
lastState = null;
// local variables: current, a node
// neighbor, a node
// current <- MAKE-NODE(INITIAL-STATE[problem])
Node current = new Node(p.getInitialState());
Node neighbor = null;
// loop do
while (true) {
List children = expandNode(current, p);
// neighbor <- a highest-valued successor of current
neighbor = getHighestValuedNodeFrom(children, p);

// if VALUE[neighbor] <= VALUE[current] then return STATE[current]
if ((neighbor == null)
|| (getValue(p, neighbor) <= getValue(p, current))) {
if (p.isGoalState(current.getState())) {
outcome = SearchOutcome.SOLUTION_FOUND;
}
lastState = current.getState();
return SearchUtils.actionsFromNodes(current.getPathFromRo ot());
}
// current <- neighbor
current = neighbor;
}
}

public SearchOutcome getOutcome() {
return outcome;
}

public Object getLastSearchState() {
return lastState;
}

private Node getHighestValuedNodeFrom(List children, Problem p) {
double highestValue = Double.NEGATIVE_INFINITY;
Node nodeWithHighestValue = null;
for (int i = 0; i < children.size(); i++) {
Node child = (Node) children.get(i);
double value = getValue(p, child);
if (value > highestValue) {
highestValue = value;
nodeWithHighestValue = child;
}
}
return nodeWithHighestValue;
}

private double getValue(Problem p, Node n) {
return -1 * getHeuristic(p, n); // assumption greater heuristic value =>
// HIGHER on hill; 0 == goal state;
}

private double getHeuristic(Problem p, Node aNode) {
return p.getHeuristicFunction().getHeuristicValue(aNode.g etState());
}
}

and this is how the problem parameter needs to be defined for hill climbing search.
A problem can be defined formally by four components: 1) Initial State. 2)
* Successor Function. 3) Goal Test. 4) Path Cost.
what will be the values for these parameters for a tictactoe game problem. I guess if i pass these correct values, it may work.
thnks in advance.

[wim DC]

HillClimbingSearch() is the constructor. You can't every call the constructor like t4.HillClimbingSearch();
A constructor gets called if you do
HillClimbingSearch hcs = new HillClimbingSearch();
And that's the only way a constructor is supposed to be called.

[1ladki]

HillClimbingSearch() is the constructor. You can't every call the constructor like t4.HillClimbingSearch();
A constructor gets called if you do
HillClimbingSearch hcs = new HillClimbingSearch();
And that's the only way a constructor is supposed to be called.

thanks oxano. but still how to solve tictactoe using Hill Climbing search, any idea. I am totally new to both AI and Java. any help will be appreciated. thnks

[wim DC]

Well, writing the algorithm should be your job. Just put a grid in front of you fill some X's and O's in it. And then decide where you are going to place the next X, and think WHY you would put an X at spot A and not at spot B.

I suggest you write a method that calculates a "score" from a certain spot at position x,y.
For example:

Score      EXPLANATION
0          Nothing, first move
1          if placed, this move will be next to the player's symbol, blocking him.
2          if placed, this move will be next to the computer's symbol. Now having 2 symbols in a row
3          if placed, this move will block the player of having 3 in a row and winning
4          if placed, this move will cause the computer to win.

This method will probably be the hardest thing to code.

Once you got this method. You can use the hill climbing stuff to decide which spot to take by looping trough all grid spots, and remembering the one with the highest score.

int score=-1;
int chosenRow, chosenColumn;

for(int row=0 ; row<3 ; row++){
  for(int column=0 ; column<3 ; column++){
    int tempScore = getScore(row, column);
    if(tempScore > score)
      score = tempScore;
      chosenRow = row;
      chosenColumn = column;
  }
}

And i hope that is hill climbing.. if not then i totally didn't understand what wikipedia just thaught me

[1ladki]

Well, writing the algorithm should be your job. Just put a grid in front of you fill some X's and O's in it. And then decide where you are going to place the next X, and think WHY you would put an X at spot A and not at spot B.

I suggest you write a method that calculates a "score" from a certain spot at position x,y.
For example:

Score      EXPLANATION
0          Nothing, first move
1          if placed, this move will be next to the player's symbol, blocking him.
2          if placed, this move will be next to the computer's symbol. Now having 2 symbols in a row
3          if placed, this move will block the player of having 3 in a row and winning
4          if placed, this move will cause the computer to win.

This method will probably be the hardest thing to code.

Once you got this method. You can use the hill climbing stuff to decide which spot to take by looping trough all grid spots, and remembering the one with the highest score.

int score=-1;
int chosenRow, chosenColumn;

for(int row=0 ; row<3 ; row++){
  for(int column=0 ; column<3 ; column++){
    int tempScore = getScore(row, column);
    if(tempScore > score)
      score = tempScore;
      chosenRow = row;
      chosenColumn = column;
  }
}

And i hope that is hill climbing.. if not then i totally didn't understand what wikipedia just thaught me

thnks a lot oxano for detailed explanation, i hope i can crack it.