1. 개요
이 기사에서는 MCTS(Monte Carlo Tree Search) 알고리즘 과 그 응용 프로그램을 살펴보겠습니다 .
Java로 Tic-Tac-Toe 게임을 구현하여 그 단계를 자세히 살펴보겠습니다 . 우리는 최소한의 변경으로 다른 많은 실제 응용 프로그램에서 사용할 수 있는 일반적인 솔루션을 설계할 것입니다.
2. 소개
간단히 말해서 몬테카를로 트리 검색은 확률 검색 알고리즘입니다. 엄청난 가능성이 있는 개방형 환경에서 효율적이기 때문에 고유한 의사 결정 알고리즘입니다.
Minimax 와 같은 게임 이론 알고리즘에 이미 익숙하다면 현재 상태를 평가하는 함수가 필요하며 최적의 이동을 찾기 위해 게임 트리에서 많은 수준을 계산해야 합니다.
불행하게도, 높은 분기 요인(트리 높이가 증가함에 따라 수백만 가지 가능성이 발생함)이 있는 바둑 과 같은 게임에서는 그렇게 하는 것이 가능하지 않으며 , 얼마나 좋은지 계산하는 좋은 평가 함수를 작성하기 어렵습니다. 현재 상태는.
몬테카를로 트리 탐색은 몬테카를로 방법을 게임 트리 탐색에 적용한 것입니다. 게임 상태의 무작위 샘플링을 기반으로 하므로 각 가능성에서 무차별 대입할 필요가 없습니다. 또한 평가나 좋은 휴리스틱 함수를 작성해야 하는 것은 아닙니다.
그리고 잠깐 덧붙이자면 컴퓨터 바둑의 세계에 혁명을 일으켰습니다. 2016년 3월부터 Google의 AlphaGo (MCTS 및 신경망으로 구축)가 이세돌 (바둑 세계 챔피언) 을 이겼을 때 널리 연구 주제가 되었습니다 .
3. 몬테카를로 트리 탐색 알고리즘
이제 알고리즘이 어떻게 작동하는지 살펴보겠습니다. 처음에는 루트 노드가 있는 미리보기 트리(게임 트리)를 만든 다음 무작위 롤아웃으로 계속 확장합니다. 그 과정에서 우리는 각 노드에 대한 방문 횟수와 승리 횟수를 유지할 것입니다.
결국 가장 유망한 통계를 가진 노드를 선택할 것입니다.
알고리즘은 4단계로 구성됩니다. 그들 모두를 자세히 살펴 보겠습니다.
3.1. 선택
이 초기 단계에서 알고리즘은 루트 노드에서 시작하여 최대 승률을 가진 노드를 선택하도록 자식 노드를 선택합니다. 우리는 또한 각 노드에 공평한 기회가 주어지기를 원합니다.
아이디어는 트리의 리프 노드에 도달할 때까지 최적의 자식 노드를 계속 선택하는 것입니다. 이러한 자식 노드를 선택하는 좋은 방법은 UCT(나무에 적용된 상위 신뢰도) 공식을 사용하는 것입니다.
여기서
- w i = i 번째 이동 후 승리 횟수
- n i = i 번째 이동 후 시뮬레이션 수
- c = 탐색 매개변수(이론적으로 √2와 같음)
- t = 상위 노드에 대한 총 시뮬레이션 수
이 공식은 어떤 국가도 기아의 희생자가 되지 않도록 보장하며 상대 국가보다 더 자주 유망한 지점을 재생합니다.
3.2. 확장
더 이상 UCT를 적용하여 후속 노드를 찾을 수 없으면 리프 노드에서 가능한 모든 상태를 추가하여 게임 트리를 확장합니다.
3.3. 시뮬레이션
확장 후 알고리즘은 자식 노드를 임의로 선택하고 게임의 결과 상태에 도달할 때까지 선택한 노드에서 무작위 게임을 시뮬레이션합니다. 플레이 아웃 중에 노드가 무작위로 또는 반랜덤하게 선택되는 경우 이를 라이트 플레이 아웃이라고 합니다. 품질 휴리스틱 또는 평가 함수를 작성하여 무거운 플레이 아웃을 선택할 수도 있습니다.
3.4. 역전파
이를 업데이트 단계라고도 합니다. 알고리즘이 게임의 끝에 도달하면 어떤 플레이어가 이겼는지 파악하기 위해 상태를 평가합니다. 루트까지 위쪽으로 순회하고 방문한 모든 노드의 방문 점수를 증가시킵니다. 또한 해당 위치의 플레이어가 플레이아웃에서 승리한 경우 각 노드의 승리 점수를 업데이트합니다.
MCTS는 고정된 반복 횟수 또는 고정된 시간이 될 때까지 이 네 단계를 계속 반복합니다.
이 접근 방식에서는 무작위 이동을 기반으로 각 노드의 승점을 추정합니다. 따라서 반복 횟수가 높을수록 추정치가 더 신뢰할 수 있습니다. 알고리즘 추정치는 검색 시작 시 정확도가 떨어지고 충분한 시간이 지나면 계속 개선됩니다. 다시 말하지만 전적으로 문제 유형에 따라 다릅니다.
4. 드라이런
여기에서 노드에는 총 방문/승리 점수와 같은 통계가 포함됩니다.
5. 시행
이제 Monte Carlo 트리 탐색 알고리즘을 사용하여 Tic-Tac-Toe 게임을 구현해 보겠습니다.
우리는 다른 많은 보드 게임에도 활용할 수 있는 MCTS를 위한 일반화된 솔루션을 설계할 것입니다. 기사 자체에서 대부분의 코드를 살펴보겠습니다.
설명을 명확하게 하기 위해 몇 가지 사소한 세부 사항(특히 MCTS와 관련이 없음)을 건너뛰어야 할 수도 있지만 항상 GitHub에서 전체 구현을 찾을 수 있습니다.
우선, 트리 검색 기능을 갖기 위해 Tree 및 Node 클래스에 대한 기본 구현이 필요합니다.
public class Node {
State state;
Node parent;
List<Node> childArray;
// setters and getters
}
public class Tree {
Node root;
}각 노드에는 문제의 특정 상태가 있으므로 State 클래스도 구현해 보겠습니다.
public class State {
Board board;
int playerNo;
int visitCount;
double winScore;
// copy constructor, getters, and setters
public List<State> getAllPossibleStates() {
// constructs a list of all possible states from current state
}
public void randomPlay() {
/* get a list of all possible positions on the board and
play a random move */
}
}이제 주어진 게임 위치에서 차선책을 찾는 역할을 하는 MonteCarloTreeSearch 클래스를 구현해 보겠습니다.
public class MonteCarloTreeSearch {
static final int WIN_SCORE = 10;
int level;
int opponent;
public Board findNextMove(Board board, int playerNo) {
// define an end time which will act as a terminating condition
opponent = 3 - playerNo;
Tree tree = new Tree();
Node rootNode = tree.getRoot();
rootNode.getState().setBoard(board);
rootNode.getState().setPlayerNo(opponent);
while (System.currentTimeMillis() < end) {
Node promisingNode = selectPromisingNode(rootNode);
if (promisingNode.getState().getBoard().checkStatus()
== Board.IN_PROGRESS) {
expandNode(promisingNode);
}
Node nodeToExplore = promisingNode;
if (promisingNode.getChildArray().size() > 0) {
nodeToExplore = promisingNode.getRandomChildNode();
}
int playoutResult = simulateRandomPlayout(nodeToExplore);
backPropogation(nodeToExplore, playoutResult);
}
Node winnerNode = rootNode.getChildWithMaxScore();
tree.setRoot(winnerNode);
return winnerNode.getState().getBoard();
}
}여기에서 사전 정의된 시간까지 4단계 모두를 반복하고 마지막에는 신뢰할 수 있는 통계가 포함된 트리를 얻어 현명한 결정을 내립니다.
이제 모든 단계에 대한 메서드를 구현해 보겠습니다.
UCT 구현도 필요한 선택 단계부터 시작하겠습니다 .
private Node selectPromisingNode(Node rootNode) {
Node node = rootNode;
while (node.getChildArray().size() != 0) {
node = UCT.findBestNodeWithUCT(node);
}
return node;
}public class UCT {
public static double uctValue(
int totalVisit, double nodeWinScore, int nodeVisit) {
if (nodeVisit == 0) {
return Integer.MAX_VALUE;
}
return ((double) nodeWinScore / (double) nodeVisit)
+ 1.41 * Math.sqrt(Math.log(totalVisit) / (double) nodeVisit);
}
public static Node findBestNodeWithUCT(Node node) {
int parentVisit = node.getState().getVisitCount();
return Collections.max(
node.getChildArray(),
Comparator.comparing(c -> uctValue(parentVisit,
c.getState().getWinScore(), c.getState().getVisitCount())));
}
}이 단계에서는 확장 단계에서 추가로 확장해야 하는 리프 노드를 권장합니다.
private void expandNode(Node node) {
List<State> possibleStates = node.getState().getAllPossibleStates();
possibleStates.forEach(state -> {
Node newNode = new Node(state);
newNode.setParent(node);
newNode.getState().setPlayerNo(node.getState().getOpponent());
node.getChildArray().add(newNode);
});
}다음으로 랜덤의 노드를 선택하고 임의 재생을 시뮬레이트하는 코드를 작성합니다. 또한 리프에서 루트로 시작하여 점수와 방문 수를 전파하는 업데이트 기능이 있습니다 .
private void backPropogation(Node nodeToExplore, int playerNo) {
Node tempNode = nodeToExplore;
while (tempNode != null) {
tempNode.getState().incrementVisit();
if (tempNode.getState().getPlayerNo() == playerNo) {
tempNode.getState().addScore(WIN_SCORE);
}
tempNode = tempNode.getParent();
}
}
private int simulateRandomPlayout(Node node) {
Node tempNode = new Node(node);
State tempState = tempNode.getState();
int boardStatus = tempState.getBoard().checkStatus();
if (boardStatus == opponent) {
tempNode.getParent().getState().setWinScore(Integer.MIN_VALUE);
return boardStatus;
}
while (boardStatus == Board.IN_PROGRESS) {
tempState.togglePlayer();
tempState.randomPlay();
boardStatus = tempState.getBoard().checkStatus();
}
return boardStatus;
}이제 MCTS 구현이 끝났습니다. 필요한 것은 Tic-Tac-Toe 특정 Board 클래스 구현입니다. 우리의 구현으로 다른 게임을 플레이하려면; Board 클래스를 변경하기만 하면 됩니다 .
public class Board {
int[][] boardValues;
public static final int DEFAULT_BOARD_SIZE = 3;
public static final int IN_PROGRESS = -1;
public static final int DRAW = 0;
public static final int P1 = 1;
public static final int P2 = 2;
// getters and setters
public void performMove(int player, Position p) {
this.totalMoves++;
boardValues[p.getX()][p.getY()] = player;
}
public int checkStatus() {
/* Evaluate whether the game is won and return winner.
If it is draw return 0 else return -1 */
}
public List<Position> getEmptyPositions() {
int size = this.boardValues.length;
List<Position> emptyPositions = new ArrayList<>();
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (boardValues[i][j] == 0)
emptyPositions.add(new Position(i, j));
}
}
return emptyPositions;
}
}우리는 방금 Tic-Tac-Toe에서 이길 수 없는 AI를 구현했습니다. AI VS AI의 결과가 항상 무승부임을 보여주는 단위 사례를 작성해 보겠습니다.
@Test
public void givenEmptyBoard_whenSimulateInterAIPlay_thenGameDraw() {
Board board = new Board();
int player = Board.P1;
int totalMoves = Board.DEFAULT_BOARD_SIZE * Board.DEFAULT_BOARD_SIZE;
for (int i = 0; i < totalMoves; i++) {
board = mcts.findNextMove(board, player);
if (board.checkStatus() != -1) {
break;
}
player = 3 - player;
}
int winStatus = board.checkStatus();
assertEquals(winStatus, Board.DRAW);
}6. 장점
- 반드시 게임에 대한 전술적 지식이 필요하지는 않습니다.
- 일반적인 MCTS 구현은 거의 수정하지 않고 여러 게임에 재사용할 수 있습니다.
- 게임에서 승리할 확률이 더 높은 노드에 집중
- 가능한 모든 분기에서 계산을 낭비하지 않기 때문에 분기 계수가 높은 문제에 적합합니다.
- 알고리즘은 구현하기가 매우 간단합니다.
- 실행은 언제든지 중지할 수 있으며 지금까지 계산된 다음으로 가장 좋은 상태를 제안합니다.
7. 단점
MCTS를 아무런 개선 없이 기본 형태로 사용하면 합리적인 움직임을 제시하지 못할 수 있습니다. 노드가 적절하게 방문되지 않아 부정확한 추정이 발생하는 경우 발생할 수 있습니다.
그러나 일부 기술을 사용하여 MCTS를 개선할 수 있습니다. 여기에는 도메인 특정 기술과 도메인 독립적 기술이 포함됩니다.
도메인별 기술에서 시뮬레이션 단계는 확률적 시뮬레이션보다 더 현실적인 플레이 아웃을 생성합니다. 게임 특정 기술과 규칙에 대한 지식이 필요하지만.
8. 요약
언뜻 보기에 무작위 선택에 의존하는 알고리즘이 스마트 AI로 이어질 수 있다는 것을 믿기 어렵습니다. 그러나 MCTS의 신중한 구현은 실제로 의사 결정 문제뿐만 아니라 많은 게임에서 사용할 수 있는 솔루션을 제공할 수 있습니다.
항상 그렇듯이 알고리즘의 전체 코드는 GitHub 에서 찾을 수 있습니다 .
