hayato @ ICFP Programming Contest 2012

icfp2012.Main.scala

package icfp2012

import scala.io.Source
import scala.collection.mutable

import my.util.logging.Logger
import sun.misc.Signal
import sun.misc.SignalHandler

object Main extends App {
  import sun.misc.SignalHandler
  import sun.misc.Signal

  import io.Source
  val source = Source.stdin
  val mapData = source.getLines.mkString("\n")
  val (parameter, state) = Reader.readBoard(mapData)
  val bot = SABot()

  Signal.handle(new Signal("INT"), new SignalIntHandler)
  class SignalIntHandler extends SignalHandler {
    def handle(sig: Signal) {
      val moves = bot.bestMoves
      println(Core.dumpMoves(moves))
      sys.exit(0)
    }
  }

  val moves = bot.run(parameter, state)
  println(Core.dumpMoves(moves))
}

case class Position(x: Int, y: Int) {
  def manhattanDistanceTo(other: Position): Int = math.abs(other.x - x) + math.abs(other.y - y)
  def nextPositions: List[Position] = List(Position(x - 1, y), Position(x + 1, y), Position(x, y - 1), Position(x, y + 1))
  def to(next: Position): Move = {
    if (x + 1 == next.x) Right
    else if (x - 1 == next.x) Left
    else if (y + 1 == next.y) Up
    else if (y - 1 == next.y) Down
    else if (this == next) Wait
    else throw new GameException()
  }
}

abstract class Move
case object Up extends Move
case object Down extends Move
case object Right extends Move
case object Left extends Move
case object Abort extends Move
case object Wait extends Move
case object Sci extends Move

object Core {
  val log = Logger[this.type]

  var shoudDebug = false

  type Board = Seq[Seq[Char]]

  def updated(map: Board, x: Int, y: Int, c: Char): Board = {
    map.updated(x, map(x).updated(y, c))
  }

  val SPACE = ' '
  val ROBOT = 'R'
  val ROCK = '*'
  val WALL = '#'
  val LIFT = 'L'
  val EARTH = '.'
  val LAMBDA = '\\'
  val BEARD = 'W'
  val RAZOR = '!'
  val HIGH_ROCK = '@'

  def isTrampoline(c: Char) = 'A' <= c && c <= 'I'
  def isTarget(c: Char) = '1' <= c && c <= '9'

  def dumpMap(map: Board): String = {
    val X = map.size
    val Y = map(0).size
    (for {
      y <- (1 until (Y - 1)).reverse
      x <- 1 until X - 1
    } yield (if (x == X - 2) map(x)(y) + "\n" else map(x)(y))
    ).mkString("")
  }

  def toMoves(moves: String): List[Move] = {
    (for (move <- moves) yield move match {
      case 'U' => Up
      case 'D' => Down
      case 'L' => Left
      case 'R' => Right
      case 'W' => Wait
      case 'A' => Abort
      case 'S' => Sci
      case _ => throw new GameException()
    }).toList
  }

 def dumpMoves(moves: List[Move]): String = {
    moves.map(_ match {
      case Up => "U"
      case Down => "D"
      case Left => "L"
      case Right => "R"
      case Abort => "A"
      case Wait => "W"
      case Sci => "S"
    }).mkString
  }

  def rocklike(c: Char) = c == ROCK || c == HIGH_ROCK || walllike(c)
  def walllike(c: Char) = c == WALL || c == LIFT

  def normalize(oldMap: Board): Board = {
    var map = oldMap
    val X = map.size
    val Y = map(0).size
    def highestRock: Int = {
      for {
        y <- (1 until (Y - 1)).reverse
        x <- 1 until X - 1
        if (map(x)(y) == ROCK || map(x)(y) == HIGH_ROCK)
      } return y
      -1
    }
    val highY = highestRock
    if (highY != -1) {
      for {
        y <- (highY + 1) until Y - 1
        x <- 1 until X - 1
        if (map(x)(y) == EARTH)
      } map = updated(map, x, y, SPACE)
    }
    // if (map != oldMap) {
    //   println("Remove Earth:\n" + dumpMap(oldMap))
    //   println("Done:\n" + dumpMap(map))
    // }

    // Move unmovable rocks to WALL.
    // #*#
    //  #

    //?**?
    //####  -> No - Rock Slide. # See the bellow.

    //  ***
    //  ###

    // ->
    //  *#*
    //  ###


    for {
      y <- 1 until Y - 1
      x <- 1 until X - 1
      if (map(x)(y) == ROCK)  // TODO HighRock
      if (rocklike(map(x - 1)(y)) && rocklike(map(x)(y)) && rocklike(map(x + 1)(y)) &&
          walllike(map(x - 1)(y - 1)) && walllike(map(x)(y - 1)) && walllike(map(x + 1)(y - 1)))
    } {
      // println("Conveting:\n" + dumpMap(map))
      map = updated(map, x, y, WALL)
      // println("Conveted:\n" + dumpMap(map))
    }
    if (map != oldMap)
      normalize(map)
    else
      map
  }
}

sealed abstract class Condition
case object NormalCondition extends Condition
case object AbortCondition extends Condition
case object WinningCondition extends Condition
case object LosingCondition extends Condition

case class State(map: Seq[Seq[Char]] = null, robot: Position = null,
                 lambda: Int = 0, steps: Int=0, inWater: Int = 0, razors: Int = 0,
                 condition: Condition = NormalCondition) {

  def X = map.size
  def Y = map(0).size

  def dump: String = {
    List(Core.dumpMap(map), "score: " + evalScore, condition).mkString("\n")
  }

  def evalScore: Int = condition match {
    case NormalCondition => lambda * 50 - steps
    case AbortCondition => lambda * 50 - steps
    case WinningCondition => lambda * 75 - steps
    case LosingCondition => lambda * 25 - steps
  }

  def score = evalScore

}


class GameException extends Exception

case class Trampoline(c: Char)
case class Target(c: Char)

case class Parameter (X: Int, Y: Int, lambda: Int = 0, water: Int = 0, flooding: Int = 0, waterproof: Int = 10,
                      trampolinePosition: mutable.Map[Trampoline, Position] = mutable.Map.empty[Trampoline, Position],
                      targetPosition: mutable.Map[Target, Position] = mutable.Map.empty[Target, Position],
                      trampolineToTarget: mutable.Map[Trampoline, Target] = mutable.Map.empty[Trampoline, Target],
                      targetToTrampolines: mutable.Map[Target, List[Trampoline]] = mutable.Map.empty[Target, List[Trampoline]],
                      growth: Int = 25) {
  val log = Core.log
}

case class Simulator(parameter: Parameter) {
  import Core._
  val log = Logger[this.type]
  var X = parameter.X
  var Y = parameter.Y

  def simulate(state: State, moves: List[Move]): State = {
    log.debug("Strting simulation: " + parameter)
    simulateMoves(state, moves)
  }

  def simulate(state: State, moves: String): State = simulate(state, toMoves(moves))

  def simulateMoves(state: State, moves: List[Move]): State = {
    debug(state, moves)
    state.condition match {
      case NormalCondition => moves match {
        case move :: tail => simulateMoves(simulateMove(state, move), tail)
        case Nil => state
      }
      case _  =>  {
        // if (!moves.isEmpty)
        //   log.error("move remains: " + moves)
        state
      }
    }
  }

  def updateMap(state: State): State = {
    var map = state.map
    var newmap = map
    var crash = false
    for {
      y <- 1 until (Y - 1)
      x <- 1 until (X - 1)
      c = map(x)(y)
      if (c == ROCK || c == HIGH_ROCK)
    } {
      if (map(x)(y - 1) == SPACE) {
        newmap = updated(newmap, x, y, SPACE)
        newmap = updated(newmap, x, y - 1, c)
        if (map(x)(y - 2) == ROBOT)
          crash = true
        else if (c == HIGH_ROCK && (map(x)(y-2) != SPACE))
          newmap = updated(newmap, x, y - 1, LAMBDA)
      } else if (map(x)(y - 1) == ROCK || map(x)(y - 1) == HIGH_ROCK) {
        if (map(x + 1)(y) == SPACE && map(x + 1)(y - 1) == SPACE) {
          newmap = updated(newmap, x, y, SPACE)
          newmap = updated(newmap, x + 1, y - 1, c)
          if (map(x + 1)(y - 2) == ROBOT)
            crash = true
          else if (c == HIGH_ROCK && (map(x + 1)(y - 2) != SPACE))
            newmap = updated(newmap, x + 1, y - 1, LAMBDA)
        } else if (map(x - 1)(y) == SPACE && map(x - 1)(y - 1) == SPACE) {
          newmap = updated(newmap, x, y, SPACE)
          newmap = updated(newmap, x - 1, y - 1, c)
          if (map(x - 1)(y - 2) == ROBOT)
            crash = true
          else if (c == HIGH_ROCK && (map(x - 1)(y - 2) != SPACE))
            newmap = updated(newmap, x + 1, y - 1, LAMBDA)
        }
      } else if (map(x)(y - 1) == LAMBDA && map(x + 1)(y) == SPACE && map(x + 1)(y - 1) == SPACE) {
        newmap = updated(newmap, x, y, SPACE)
        newmap = updated(newmap, x + 1, y - 1, c)
        if (map(x + 1)(y - 2) == ROBOT)
          crash = true
        else if (c == HIGH_ROCK && (map(x + 1)(y - 2) != SPACE))
          newmap = updated(newmap, x + 1, y - 1, LAMBDA)
      }
    }
    if (map != newmap) {
      newmap = normalize(newmap)
    }
    if (crash)
      state.copy(map=newmap, condition=LosingCondition)
    else
      waterCheck(growBeard(state.copy(map=newmap)))
  }

  def growBeard(state: State): State = {
    if (state.steps % parameter.growth == 0) {
      val map = state.map
      var newmap = map
      for {
        y <- 1 until (Y - 1)
        x <- 1 until (X - 1)
        if (map(x)(y) == BEARD)
        nx <- (x - 1) to (x + 1)
        ny <- (y - 1) to (y + 1)
        if (newmap(nx)(ny) == SPACE)
      } newmap = updated(newmap, nx, ny, BEARD)
      state.copy(map=newmap)
    } else {
      state
    }
  }

  def waterCheck(state: State): State = {
    // log.info(">>> waterCheck: state:\n" + state.dump)
    val waterLevel = parameter.water +
      (if (parameter.flooding != 0) state.steps / parameter.flooding
       else 0)
    if (state.robot.y <= waterLevel)
      if (state.inWater == parameter.waterproof)
        state.copy(condition=LosingCondition)
      else
        state.copy(inWater=state.inWater + 1)
    else
      state.copy(inWater=0)
  }

  def moveRobot(state: State, newRobot: Position, move: Move): State = {
    val map = state.map
    var newmap = state.map
    val nx = newRobot.x
    val ny = newRobot.y
    map(nx)(ny) match {
      case SPACE => {
        newmap = updated(newmap, nx, ny, ROBOT)
        newmap = updated(newmap, state.robot.x, state.robot.y, SPACE)
        updateMap(state.copy(map=newmap, robot=newRobot))
      }
      case EARTH => {
        newmap = updated(newmap, nx, ny, ROBOT)
        newmap = updated(newmap, state.robot.x, state.robot.y, SPACE)
        updateMap(state.copy(map=newmap, robot=newRobot))
      }
      case RAZOR => {
        newmap = updated(newmap, nx, ny, ROBOT)
        newmap = updated(newmap, state.robot.x, state.robot.y, SPACE)
        updateMap(state.copy(map=newmap, robot=newRobot, razors=state.razors + 1))
      }
      case LAMBDA => {
        newmap = updated(newmap, nx, ny, ROBOT)
        newmap = updated(newmap, state.robot.x, state.robot.y, SPACE)
        updateMap(state.copy(map=newmap, robot=newRobot, lambda=state.lambda + 1))
      }
      case LIFT => {
        if (state.lambda == parameter.lambda) {
          newmap = updated(newmap, nx, ny, ROBOT)
          newmap = updated(newmap, state.robot.x, state.robot.y, SPACE)
          state.copy(map=newmap, condition=WinningCondition, robot=newRobot)
        } else
          updateMap(state)
      }
      case ROCK => move match {
        case Right => {
          if (map(nx + 1)(ny) == SPACE) {
            newmap = updated(newmap, nx, ny, ROBOT)
            newmap = updated(newmap, state.robot.x, state.robot.y, SPACE)
            newmap = updated(newmap, nx + 1, ny, ROCK)
            updateMap(state.copy(map=newmap, robot=newRobot))
          } else
            updateMap(state)
        }
        case Left => {
          if (map(nx - 1)(ny) == SPACE) {
            newmap = updated(newmap, nx, ny, ROBOT)
            newmap = updated(newmap, state.robot.x, state.robot.y, SPACE)
            newmap = updated(newmap, nx - 1, ny, ROCK)
            updateMap(state.copy(map=newmap, robot=newRobot))
          } else
            updateMap(state)
        }
        case _ => updateMap(state)
      }
      case WALL => updateMap(state)
      case BEARD => updateMap(state)
      case c if isTrampoline(c) => {
        val trampoline = Trampoline(c)
        val target = parameter.trampolineToTarget(trampoline)
        var targetPosition = parameter.targetPosition(target)

        newmap = updated(newmap, targetPosition.x, targetPosition.y, ROBOT)
        newmap = updated(newmap, state.robot.x, state.robot.y, SPACE)
        for (trampoline <- parameter.targetToTrampolines(target)) {
          val pos = parameter.trampolinePosition(trampoline)
          newmap = updated(newmap, pos.x, pos.y, SPACE)
        }
        updateMap(state.copy(map=newmap, robot=targetPosition))
      }
      case c if isTarget(c) => updateMap(state)
      case _ => throw new GameException()
    }
  }

  def useRazor(state: State): State = {
    if (state.razors == 0)
      updateMap(state)
    else {
      val map = state.map
      var newmap = state.map
      for {
        nx <- (state.robot.x - 1) to (state.robot.x + 1)
        ny <- (state.robot.y - 1) to (state.robot.y + 1)
        if (map(nx)(ny) == BEARD)
      } newmap = updated(newmap, nx, ny, SPACE)
      updateMap(state.copy(map=newmap, razors=state.razors - 1))
    }
  }

  def simulateMove(state: State, move: Move): State = {
    // log.info(">>> simulateMove: state:\n" + state.dump + "\nMove: " + move)

    state.condition match {
      case AbortCondition => state
      case WinningCondition => state
      case LosingCondition => state
      case NormalCondition => {
        val robot = state.robot
        val newstate = state.copy(steps=state.steps + 1)
        move match {
          case Up => moveRobot(newstate, robot.copy(y=robot.y + 1), move)
          case Down => moveRobot(newstate, robot.copy(y=robot.y - 1), move)
          case Left => moveRobot(newstate, robot.copy(x=robot.x - 1), move)
          case Right => moveRobot(newstate, robot.copy(x=robot.x + 1), move)
          case Abort => state.copy(condition=AbortCondition)
          case Wait => updateMap(newstate)
          case Sci => useRazor(newstate)
        }
      }
    }
  }

  def debug(state: State, moves: List[Move]) {
    log.debug("state:\n" + state.dump)
    log.debug("moves: " + dumpMoves(moves))
  }

}

object Reader {
  import Core._

  def readBoard(str: String): Tuple2[Parameter, State] = {
    val log = Logger[this.type]
    val lines = str.split("\n")

    var (mapLines, parameterLines) = lines.span(!_.isEmpty)
    mapLines.foreach { line => log.debug("map: " + line) }
    parameterLines.foreach { line => log.debug("parameter: " + line) }

    mapLines = mapLines.reverse

    val X = mapLines.map(_.size).max + 2
    val Y = mapLines.size + 2

    var parameter = Parameter(X=X, Y=Y)

    val map = IndexedSeq.tabulate[Char](X, Y)((x, y) => {
      if (x == 0 || x == X - 1) WALL
      else if (y == 0 || y == Y - 1) WALL
      else if (x - 1 < mapLines(y - 1).size) mapLines(y - 1)(x - 1)
      else SPACE
    })

    var robot: Position = null

    for (x <- 0 until X) {
      for (y <- 0 until Y) {
        map(x)(y) match {
          case ROBOT => {
            robot = Position(x, y)
          }
          case LAMBDA => parameter = parameter.copy(lambda=parameter.lambda + 1)
          case HIGH_ROCK => parameter = parameter.copy(lambda=parameter.lambda + 1)
          case c if isTrampoline(c) => parameter.trampolinePosition(Trampoline(c)) = Position(x, y)
          case c if isTarget(c) => parameter.targetPosition(Target(c)) = Position(x, y)
          case _ => Unit
        }
      }
    }

    var razors = 0
    for {
      line <- parameterLines
      trimmed = line.trim
      if !trimmed.isEmpty
      array = trimmed.split(SPACE)
      if array.size != 0
    } array(0) match {
      case "Water" => parameter = parameter.copy(water=array(1).toInt)
      case "Flooding" => parameter = parameter.copy(flooding=array(1).toInt)
      case "Waterproof" => parameter = parameter.copy(waterproof=array(1).toInt)
      case "Trampoline" => {
        assert(array.size == 4)
        assert(array(1).length == 1)
        val trampoline = Trampoline(array(1)(0))
        assert(array(2) == "targets")
        assert(array(3).length == 1)
        val target = Target(array(3)(0))
        parameter.trampolineToTarget(trampoline) = target
        if (parameter.targetToTrampolines.contains(target))
          parameter.targetToTrampolines(target) = trampoline :: parameter.targetToTrampolines(target)
        else
          parameter.targetToTrampolines(target) = List(trampoline)
      }
      case "Growth" => parameter = parameter.copy(growth=array(1).toInt)
      case "Razors" => razors=array(1).toInt
    }

    assert(parameter.growth > 0)
    Tuple2(parameter, State(map=normalize(map), robot=robot, razors=razors))
  }
}

abstract class Bot {

  val log = Logger[this.type]
  def run(parameter: Parameter, state: State): List[Move]

  var bestMoves: List[Move] = Nil

  def path2moves(path: List[Position]): List[Move] = path match {
    case Nil => Nil
    case head :: Nil => Nil
    case head :: next :: tail =>  head.to(next) :: path2moves(next :: tail)
  }

  val moveCommands = List(Up, Down, Left, Right)
}

case class SABot(maxIteration: Int = 10000000) extends Bot {
  import Core._

  override def run(parameter: Parameter, state: State): List[Move] = {
    val simulator = Simulator(parameter)
    val start = state.robot

    var iteration = 0

    val StopSearch = -100000000

    def hScore(parameter: Parameter, state: State): Int = state.condition match {
      case WinningCondition => 0
      case LosingCondition => 0
      case AbortCondition => 0
      case NormalCondition => calulucateHScore(parameter, state)
    }

    def calulucateHScore(parameter: Parameter, state: State): Int = {
      val start = state.robot
      val map = state.map
      val X = state.X
      val Y = state.Y
      val lambdaRemains = parameter.lambda - state.lambda
      val maxDistance = X + Y

      def passMaybe(pos: Position): Boolean = {
        val c = map(pos.x)(pos.y)
        // Todo: More huelistic.
        !walllike(c) || c == LIFT
      }

      case class Node(pos: Position, distance: Int)

      def distanceToObjectsScore: Int = {
        val visited = mutable.Set.empty[Position]
        val queue = mutable.Queue.empty[Node]
        var distanceToLambdas = List.empty[Int]
        var distanceToInterestings = List.empty[Int]

        queue += Node(start, 0)
        visited += start
        while (queue.nonEmpty) {
          val Node(pos, dist) = queue.dequeue()
          val c = map(pos.x)(pos.y)
          (if (isTrampoline(c)) {
            val trampoline = Trampoline(c)
            val target = parameter.trampolineToTarget(trampoline)
            val next = parameter.targetPosition(target)
            List(next)
          } else {
            pos.nextPositions
          }).filter(passMaybe).foreach(next => {
            if (!visited.contains(next)) {
              visited += next
              queue += Node(next, dist + 1)
              // TODO(hayato): Handle lift separately???
              val nextC = map(next.x)(next.y)
              if (nextC == LAMBDA || nextC == LIFT || nextC == HIGH_ROCK)
                distanceToLambdas = dist :: distanceToLambdas
            }
          })
        }
        if (distanceToLambdas.isEmpty)
          return StopSearch

        if (lambdaRemains + 1 != distanceToLambdas.size) {
          // Penalty to unreachable lambada or lift.
          // println("Unreachable")
          // println("state: \n" + state.dump)
          // println("lambda: " + distanceToLambdas)
          return -10000
        }

        // TODO(hayato): Improve. Increase score if the number of remaining lambda is small.
        var score = distanceToLambdas.map(d => (50 - d).max(0)).sum

        // Like Simulate Annulate...?
        // score = score * math.max(300 - iteration, 100) / 100
        // score += distanceToInterestings.map(d => (10 - d).max(0)).sum
        score
      }

      distanceToObjectsScore
    }

    def nextDestinationChadidates(state: State): List[List[Move]] = {
      sealed abstract class SearchMode
      object ConsumeSpace extends SearchMode
      object ConsumeEarth extends SearchMode
      object Start extends SearchMode
      object Reached extends SearchMode
      case class Node(pos: Position, mode: SearchMode, moves: List[Move]) {
        def key: Key = Key(pos, mode)
      }
      case class Key(pos: Position, mode: SearchMode)

      val map = state.map
      var candidates: List[List[Move]] = Nil

      val visited = mutable.Set.empty[Key]
      val queue = mutable.Queue.empty[Node]
      val startPos = state.robot
      val start = Node(state.robot, Start, Nil)
      queue += start
      visited += start.key

      def addIf(node: Node) {
        if (!visited.contains(node.key)) {
          queue += node
          visited += node.key
        }
      }

      def supportsRock(pos: Position): Boolean = {
        map(pos.x)(pos.y + 1) == ROCK || map(pos.x - 1)(pos.y) == ROCK || map(pos.x + 1)(pos.y) == ROCK
      }

      def addCandidate(movesReversed: List[Move]) { candidates = movesReversed.reverse :: candidates }

      while (queue.nonEmpty) {
        val Node(pos, mode, moves) = queue.dequeue()
        pos.nextPositions.filterNot(_ == startPos).foreach(nextPos => {
          val move = pos.to(nextPos)
          val c = map(nextPos.x)(nextPos.y)
          (mode, c) match {
            case (Start, SPACE) => addIf(Node(nextPos, ConsumeSpace, move :: moves))
            case (Start, EARTH) => {
              if (supportsRock(nextPos))
                addCandidate(move :: moves)
              else
                addIf(Node(nextPos, ConsumeEarth, move :: moves))
            }
            case (ConsumeSpace, SPACE) => addIf(Node(nextPos, ConsumeSpace, move :: moves))
            case (ConsumeEarth, EARTH) => {
              if (supportsRock(nextPos))
                addCandidate(move :: moves)
              else
                addIf(Node(nextPos, ConsumeEarth, move :: moves))
            }
            case (_, WALL) => Unit
            // Todo: Only we can push rock.
            // case (_, ROCK) => Unit
            case (_, nextC) => addCandidate(move :: moves)
          }
        })
      }
      candidates
    }

    case class Key(map: Board)

    // Todo: Emphasis h on the first ...
    case class Node(state: State, score: Int, h: Int, moves: List[Move]) extends Ordered[Node] {
      override def compare(other: Node) = {
        if (score + h < other.score + other.h) -1
        else if (score + h > other.score + other.h) 1
        else 0
      }
      def key: Key = Key(map=state.map)
      def dump: String = "state:\n"  + state.dump + "\nScore:\n" + score + "\nhScore:\n" + h + "\nmoves:\n" + dumpMoves(moves).reverse
    }


    // TODO(hayato): Fix it.
    def canMove(pos: Position, state: State): Boolean = true

    val startNode = Node(state, state.score, hScore(parameter, state), Nil)

    // val visited = mutable.Set.empty[Key]
    val visited = mutable.Map.empty[Key, Int]

    val queue = mutable.PriorityQueue.empty[Node]
    queue += startNode
    visited(startNode.key) = startNode.score

    bestMoves = Nil
    var bestScore = 0

    while (queue.nonEmpty && iteration < maxIteration) {
      iteration += 1
      val node = queue.dequeue()
      val Node(state, score, h, moves) = node
      if (score > bestScore) {
        // println("iteration: " + iteration)
        // println("Best Score Found:" + score)
        // println("queue.size:" + queue.size)
        bestScore = score
        bestMoves = moves
      }
      // if (iteration % 1000 == 0) {
      //   println("iteration: " + iteration)
      //   println("node: \n" + node.dump)
      // }
      var candidates = nextDestinationChadidates(state)
      // println("candidates " + candidates.map(dumpMoves(_)))
      candidates.foreach(nextMoves => {
        val nextState = simulator.simulateMoves(state, nextMoves)

        // Todo: Omit caluculate hscore. Order is wrong.
        val nextHScore = hScore(parameter, nextState)
        val nextNode = Node(nextState, nextState.score, nextHScore, moves ::: nextMoves)
        nextHScore match {
          case StopSearch => Unit
          case _ =>  visited.get(nextNode.key) match {
            case Some(previousScore) => {
              if (nextNode.score > previousScore) {
                queue += nextNode
                visited(nextNode.key) = nextNode.score
              }
            }
            case None => {
              queue += nextNode
              visited(nextNode.key) = nextNode.score
          }
          }
        }
      })
    }
    bestMoves
  }
}