스칼라로 바둑 인공지능을 만들었다.

바둑 인공지능을 만들때는 대부분 MCTS를 사용한다. MCTS는 몬테카를로 트리 서치의 약자인데, 트리를 생성하며 몬테카를로법을 효율적으로 적용하는 알고리즘이라고 보면 된다. select, expand, simulate, backpropagate의 네 단계로 구성된다. 자세한 설명은 위키백과를 참고하자.

이번에는 MCTS를 함수형으로 구현해볼 것이다. (재미로)

(참고) 바둑에 MCTS를 적용할 때의 주의점

게임이 끝나는 조건을 구현하는게 빡세다. 왜냐하면 바둑은 규칙 상 두 선수가 동의하여 게임을 끝내는 것을 전제하기 때문이다. 그래서 휴리스틱을 적용해야 한다. 나는 돌의 세기를 집과 함께 계산하여 특정 시점에 (ex 200수 경과) 점수가 높은 선수가 승리하는 것으로 했다. 이 부분을 만들 때에는 바둑 지식이 꼭 필요하다.

절차형으로 만들면

절차형으로 만들고 싶다면 알고리즘의 네 단계를 그대로 코드에 옮기면 된다. 아무 생각 없이 만들면 된다.

함수형으로 만들면

세 가지 함수를 정의한다. 간단하게 표현하면 다음과 같다. select(state, node) = (updated_node, winner) expand(state, node) = (updated_node, winner) simulate(state) = winner 현 상태와 노드를 받고 각 단계를 실행한 후의 새로 업데이트된 노드를 반환하는 것이다. 모두 순수함수이며 외부 상태에 의존하지 않는다. 그런데 backpropagate() 함수가 없다. 잘 생각해 보면 당연한데, backpropagate는 노드의 상태를 업데이트하는 단계이다. 즉, 함수형으로 작성하면 위의 세 가지 함수가 새로운 트리를 반환하는 것으로 대체한다.

코드 (더러움)

object MCTS {
  private val c = 1.5f
  case class MCTSNode(move: Move, turn: Int, children: List[MCTSNode], moves: List[Move], n: Int = 0, q: Float = 0) {
    val fullyExpanded: Boolean = moves.isEmpty

    def eval(p: Int): Float = q / n + c * math.sqrt(math.log(p).toFloat / n).toFloat

    override def toString: String = f"$move: $q / $n"
  }

  private def getBestNMoves(game: Baduk, n: Int, color: Int): List[Move] = {
    val size = game.get_board.size
    val moves =
      if (game.movesCount > 5) game.get_moves()
      else if (game.movesCount > 3) game.get_moves().filterNot(m=> m.x == 0 || m.x == size - 1 || m.y == 0 || m.y == size - 1)
      else game.get_moves().filterNot(m=> m.x <= 1 || m.x >= size - 2 || m.y <= 1 || m.y >= size - 2)

    val scoresPair = moves.map(m => (Eval(game.go(m)).valueBy(color), m))
    scoresPair.sortBy(tup => -tup._1).slice(0, Math.min(n, moves.length-1)).map(tup => tup._2)
  }

  private def filterMoves(moves: List[Move], game: Baduk): List[Move] = {
    val size = game.get_board.size
    val moves =
      if (game.movesCount > 5) game.get_moves()
      else if (game.movesCount > 3) game.get_moves().filterNot(m => m.x == 0 || m.x == size - 1 || m.y == 0 || m.y == size - 1)
      else game.get_moves().filterNot(m => m.x <= 1 || m.x >= size - 2 || m.y <= 1 || m.y >= size - 2)

    moves
  }

  @tailrec
  private def simulate(state: Baduk, limit: Int): Int = {
    if (state.end() || limit <= 0)
      Eval(state).getWinner
    else {
      val moves = filterMoves(state.get_moves(), state)
      val next_state = state.go(moves(Random.nextInt(moves.length)))
      simulate(next_state, limit - 1)
    }
  }

  private def expand(state: Baduk, node: MCTSNode): (MCTSNode, Int, List[Move]) = {
    val move = node.moves(Random.nextInt(node.moves.length))
    val next_state = state.go(move)
    val winner = simulate(next_state, 100)
    val policyMoves = Policy(next_state).moves
    (MCTSNode(move, state.get_turn, List(), filterMoves(policyMoves.toList, next_state)/*getBestNMoves(next_state, 10, next_state.get_turn)*/, n = 1,
      q = if (winner == state.get_turn) 1 else if (winner == 0) 0.5f else 0), winner,
      node.moves.filterNot(elm => elm == move))
  }

  def select(state: Baduk, node: MCTSNode): (MCTSNode, Int) = {
    val delta_q = (winner: Int) => if (winner == node.turn) 1 else if (winner==0) 0.5f else 0
    if (state.end()) {
      val winner = state.winner()._1
      val new_node = node.copy(n=node.n+1, q=node.q + delta_q(winner))
      (new_node, winner)
    }
    else if (!node.fullyExpanded) {
      val (child, winner, moves) = expand(state, node)
      val new_node = node.copy(children= child::node.children, moves=moves, n=node.n+1, q=node.q + delta_q(winner))
      (new_node, winner)
    }
    else {
      val (max_child, max_index) = node.children.zipWithIndex.maxBy(_._1.eval(node.n))
      val (child, winner) = select(state.go(max_child.move), max_child)
      val new_node = node.copy(children = node.children.updated(max_index, child), n = node.n + 1, q= node.q + delta_q(winner))
      (new_node, winner)
    }
  }

  @tailrec
  private def searchNTimes(root_state: Baduk, node: MCTSNode, n: Int, visitSkip: Boolean=true, totalVisits: Int): MCTSNode = {
    //if (n % 1000 == 0)
    //  print('.')
    if (n == 0) node
    else
    {
      if (visitSkip && node.children.length >= 2 && n % 100 == 0) {
        val max = node.children.maxBy(c => c.n)
        val second = node.children.filterNot(c => c == max).maxBy(c => c.n)
        val distance = max.n - second.n
        if (distance > totalVisits){
          node
        }
        else {
          searchNTimes(root_state, select(root_state, node)._1, n - 1, totalVisits = totalVisits - 1)

        }
      } else{
        searchNTimes(root_state, select(root_state, node)._1, n - 1, totalVisits = totalVisits - 1)

      }
    }
  }
  def getContinuesMCTSRootNodeAndMaxFunction(rootTemp: MCTSNode, game: Baduk, visits: Int, totalVisits: Int): (MCTSNode, Move) = {
    val root =
      if (rootTemp == null)
        MCTSNode(game.null_move(), game.get_turn * -1, List(), Policy(game).moves.toList)
      else
        rootTemp
    val searchedRoot = searchNTimes(game, root, visits, totalVisits = totalVisits)
    //for(c <- searchedRoot.children) println(s"Move ${c.move}: ${c.q} / ${c.n}")
    val best_child = searchedRoot.children.maxBy(_.n)
    //println(s"Move ${best_child.move}: ${best_child.q} / ${best_child.n} (${(best_child.q / best_child.n * 100).round}%)")
    (searchedRoot, best_child.move)
  }
}

그래서 잘 둠?

9줄 바둑에서 실행해보면 2~3 만 회 서치했을 때 바둑 좀 배운 초딩 수준으로 둔다. 그래도 별 다른 휴리스틱이나 인공신경망 없이 이 정도만 되어도 대단하다고 생각한다.

(참고) UCT 함수의 이상한 점

private val c = 1.5f
def eval(p: Int): Float = q / n + c * math.sqrt(math.log(p).toFloat / n).toFloat

여기서 c값을 1.5로 해놨다. 그런데 보통 c 값은 루트2 아닌가? 사실은 1~3 사이 아무 값이나 상관 없다고 한다. 루트2를 쓰게 된 배경은 논문에서 증명하기 편한 숫자 아무거나 쓴 거라고 한다. 그러니 루트2로 할 이유는 전혀 없고 몇번 테스트해보아서 좋은 숫자로 하면 된다.