MonteCarloSolver Class Reference

Memoryless solver that randomly searches the state space. More...

#include <MonteCarloSolver.hpp>

Inheritance diagram for MonteCarloSolver:

Collaboration diagram for MonteCarloSolver:

Public Member Functions
	MonteCarloSolver ()
LinkedList< GameState * >	solve (Game &game, GameState &g0)
	Explores the game tree in search of the goal state. More...
Public Member Functions inherited from Solver
double	getSecondsToSolve () const
int	getVisitedNodes () const
int	getMaxDepth () const
int	getSolutionDepth () const
bool	isSolved ()
	Solver ()
string	to_string ()
	Generates a string containing useful information from the solver run. More...

Private Member Functions
int	rnd (int max)

Private Attributes
mt19937_64	r

Additional Inherited Members
Protected Member Functions inherited from Solver
bool	isVisited (GameState &g)
	Checks whether a node has already been visited by the solver. More...
LinkedList< GameState * >	visit (GameState *current)
LinkedList< GameState * >	visit (GameState *current, bool keepVisited)
	Visit a game state, adding it to the list of visited states and returning its valid child states. More...
LinkedList< GameState * >	endSearch (GameState *currentGame, const clock_t start)
	End the search, generating the steps from the initial state to the goal. More...
Protected Attributes inherited from Solver
OrderedList< GameState * >	visited = OrderedList<GameState *>(compare)
int	visitedNodes
int	maxDepth
int	solutionDepth
float	secondsToSolve
bool	solved

Detailed Description

Memoryless solver that randomly searches the state space.

Author

Douglas De Rizzo Meneghetti (dougl.nosp@m.asri.nosp@m.zzom@.nosp@m.gmai.nosp@m.l.com)

Date

2017-7-7Memoryless solver that randomly searches the state space.

Definition at line 15 of file MonteCarloSolver.hpp.

Constructor & Destructor Documentation

MonteCarloSolver()

MonteCarloSolver::MonteCarloSolver ( )

inline

Definition at line 24 of file MonteCarloSolver.hpp.

                     {
    time_t result = time(nullptr);
    r.seed((unsigned long) std::localtime(&result));
  }

Member Function Documentation

rnd()

int MonteCarloSolver::rnd ( int  max )

inlineprivate

Definition at line 19 of file MonteCarloSolver.hpp.

                   {
    return abs((int) r() % max);
  }

solve()

LinkedList<GameState *> MonteCarloSolver::solve ( Game &  g, GameState &  gs  )

inlinevirtual

Explores the game tree in search of the goal state.

Exploration is done by applying one of the four valid actions of the 8-puzzle to intermediate, non-goal states until the goal state is reached.

Parameters

g	A description of the game.
gs	The initial state of the game.

Returns

list containing all states explored, from the initial state to the goal state.

Implements Solver.

Definition at line 29 of file MonteCarloSolver.hpp.

                                                           {
    // this algorithm has no memory, so no data structure to keep expanded states
    GameState *only_one = &g0;
    const clock_t start = clock();

    while (*game.getGoal() != *only_one) {
      LinkedList<GameState *> children = visit(only_one, false);
      only_one = children.remove(rnd(children.getSize()));

      while (! children.isEmpty()) {
        GameState *child = children.remove(0);
        delete child;
      }
    }

    solved = true;
    return endSearch(only_one, start);
  }

Here is the call graph for this function:

Here is the caller graph for this function:

Field Documentation

r

mt19937_64 MonteCarloSolver::r

private

Definition at line 17 of file MonteCarloSolver.hpp.

---

The documentation for this class was generated from the following file:

• include/MonteCarloSolver.hpp