Draft 4_ First Assignment - RuiOrey/AI-Studies GitHub Wiki

In this assignment the objective was to implement several search algorithms applied to game-of-eight.

##Data structs

###Tabuleiro Node class that contains the actual game matrix, a reference to the father node, the depth of the node, coordinates for the emtpy position in the game, a boolean for testing if the game matrix is final, the heuristic value.

####Constructors

  • Tabuleiro(int [][] finalt) Made for the root node, defines depth at 0, saves the actual game matrix (finalt) and gets the coordinates of empty cell.

  • Tabuleiro(Tabuleiro tabp,int[][] aux,int child,int dept)(int [][] finalt) Gets a reference to the father (Tabuleiro tabp), gets the actual game matrix (int[][] aux), the direction to play (int child) and the father depth (int dept). It increases depth and it moves the empty piece in a direction according to the direction given. We must take in account that : *1 represents up *2 represents right *3 represents left *4 represents down

####Methods

  • getDepthT() - gets depth
  • getTabuleiro() - gets game matrix associated with this node
  • getvazio(X or Y) - returns x or y component of the empty space cell
  • Boolean isFinal(int[][] test) - tests if the game matrix is equal to the final one
  • Boolean isFinalH(int[][] test) - tests if the game matrix is equal to the final one. In this test for each out of place value, the global outplace variable is incremented by 1. This will be later used when creating the heuristic.
  • int compareTo(Tabuleiro compara) - compares the heuristic with another Tabuleiro's one. _ If this heurisic is lower, will returna negative value *geraHeuristica(int[][] test) - generates a heuristic. compares two _Tabuleiro_s and if a cell has a different value between them, it adds to the value of the heuristic the value returned by movesUntil. In the final, sums also the outplace variable.
  • heur() - returns the heuristic
  • heurEstr() - returns the A* heuristic - the heuristic value summed with depth.
  • int movesUntil(int alvo,int [][] tested,int x, int y) - returns the moves needed to move the target number alvo from the actual place in the game matrix to his final place.
  • int[][] tabulArray() - returns tabuleiro
  • int isPar() - for each number in the game matrix, checks if the numbers that appear in the game matrix after that one are smaller than that one. If so, the matrix parity value is incremented. This serves to test if the final and the actual game matrix have the same this value both even or odd. If they are both even or both odd, the game can be resolved. Otherwise, not.

##Arvore
Tree class that keeps record of the root Tabuleiro and the destiny _ Tabuleiro_

##Check states

##Transformations