인공지능에서 몬테카로 트리 검색 알고리즘을 사용하여 2048(및 기타 게임) 격파

최초로 here at xtrp.io에 발표된 것은 컴퓨터 과학과 그 어떠한 프로그래밍에 관한 나의 블로그이다.
저는 최근에 오픈소스project called Jupiter를 개발했습니다. 이것은 온라인 인공지능으로 유행하는 온라인 게임2048을 물리칠 수 있습니다.
인공지능을 시험해 보자.

이 인공지능을 작성할 때, 나는 몬테카로 트리 검색(MCTS) 알고리즘이라고 불리는 기계 학습 방법을 사용하기로 결정했다.Jupiter에서 사용한 몬테카로 알고리즘은 이미 몇 개의 유명한 인공지능에서 사용되었다. DeepMindAlphaGo를 포함하여 이 알고리즘은 2017년 5월에 바둑 세계 챔피언을 이겼다.
본문에서 나는 다음과 같이 설명할 것이다.

몬테카로 방법의 작업 원리와 원인

몬테카로 알고리즘이 언제 어디에 유용한지

내가 어떻게 인공지능에서 몬테카로 방법을 사용하여 2048

을 격파하는가

JavaScript 및 기타 언어로 몬테카로 알고리즘 구현 방법

주: 몬테카로 방법으로 this StackOverflow answer 에서 2048을 격파할 생각이 났어요.

몬테카로의 방법은 무엇입니까?

몬테카로 방법의 사상은 대량의 실험의 무작위 시뮬레이션을 이용하여 실험의 최종 결과를 깊이 있게 이해하는 것이다.실험의 무작위 시뮬레이션은 통상적으로 몬테카로 시뮬레이션이라고 부른다.
예를 들어 당신이 동전을 던지고 있다고 가정하고 동전이 땅에 떨어질 확률을 계산하려고 한다.몬테카로 방법을 사용하면 우리는 10000회 동전을 던지는 것을 모의하고 동전의 머리가 땅에 떨어지는 비율을 계산할 수 있다.
다음은 그의 모습이다.

결과적으로 예상치의 50퍼센트까지 수렴되었다는 것을 알 수 있다.몬테카로 시뮬레이션의 현저한 특징은 시뮬레이션 횟수가 많을수록 정밀도가 높다는 것이다.예를 들어 만약에 우리가 두 번의 시뮬레이션만 진행했다면 두 번의 시뮬레이션에서 머리가 착륙할 확률이 매우 높았고 결과는 100%였다.50%의 예상 결과에 비하면 이것은 매우 부정확하다.
몬테카로 시뮬레이션이 효과적인 이유는 대수의 법칙, 즉

If you simulate the same experiment many times, the average of the results should converge to the expected value of the simulation.

다시 말하면 몬테카로 시뮬레이션은 주어진 실험에서 무슨 일이 일어날지 예측하는 방법으로 특정한 알고리즘이나 계발식을 실현할 필요가 없다.

몬테카로 방법은 언제 어디서 유용한가

몬테카로 방법은 게임 인공지능 개발, 금융과 경제, 진화생물학 등 다양한 분야에 사용된다.
몬테카로 방법은 임의의 인자를 가진 모든 실험에 사용할 수 있으며, 그 중에서 최종 결과는 알고리즘을 통해 예측할 수 없다.예를 들어 2048년에는 이동할 때마다 무작위 위치에 새로운 상호작용 프로그램을 추가하여 다가오는 상호작용 프로그램의 정확한 위치와 그 후의 게임 최종 결과를 계산할 수 없다.
이러한 유형의 실험에서 대량의 몬테카로 시뮬레이션을 실행하면 평균 최종 결과, 각종 사건 발생 확률과 실험 중의 변수 간의 관계를 얻을 수 있다.
예를 들어 Jupiter에서 몬테카로 방법을 사용하면 이동을 시작하거나 게임의 이동 횟수와 바둑판의 가장 좋은 평판 등 변수가 게임의 최종 결과에 어떻게 영향을 미치는지 이해할 수 있다.

내가 어떻게 주피터에서 몬테카로 방법을 사용했는지, 이것은 2048을 격파하는 인공지능이다

몇 가지 정의부터 시작합니다.

플레이트 및 타일: 4x4 메쉬, 각 메쉬 점

에 타일 옵션 배치

게임 상태: 바둑판의 타일, 특정 시간을 대표하는 바둑판

게임 점수: 바둑판의 모든 바둑판의 총계

실제 게임: 아날로그 대신 브라우저에서 플레이하고 표시하는 게임

주어진 게임 상태에서, 우리는 왼쪽, 오른쪽, 위 또는 아래의 네 가지 가능한 이동을 할 수 있다고 가정합시다.

There are indeed cases where a certain move is not possible in a given game state. Removing impossible moves can be easily added to the algorithm later.

몬테카로 방법을 사용하면 우리는 모든 동작에 대해 게임 시뮬레이션을 할 수 있다.
모든 가능한 이동에 대해 프로그램은 시뮬레이션 그룹을 시뮬레이션하고 먼저 이 그룹의 이동을 재생합니다.이후 게임의 나머지 부분은 게임이 끝날 때까지 완전히 무작위로 진행할 수 있다.
JavaScript에서 이 알고리즘은 다음과 같습니다.

// assume Game object exists
// assume currentGame variable exists as the real game

const totalSimulations = 200; // 50 simulations are played for each move 

const possibleMoves = ["left", "right", "down", "up"];
possibleMoves.forEach((move) => { // simulations for all four possible starting moves
  for(let i = 0; i < totalSimulations / 4; i++) {
    const simulation = new Game(); // create simulation
    simulation.board = currentGame.board; // copy current game state to simulation
    simulation.makeMove(move); // make initial move
    while(!simulation.gameover()) {
      simulation.makeMove(possibleMoves[Math.floor(Math.random() * 4)]);
    } // make random moves until simulation game is over
  }
});

모든 시뮬레이션이 완성된 후에 프로그램은 모든 시뮬레이션의 최종 총 점수를 수집하고 모든 동작을 평균적으로 진행할 수 있다.그리고 우리는 가장 높은 최종 게임 점수를 최적화하여 가장 좋은 이동을 찾을 수 있다.
예를 들어 왼쪽 키로 시작하는 시뮬레이션의 평균 점수가 250이고 다른 동작으로 시작하는 시뮬레이션의 평균 점수가 225라면 왼쪽 키가 가장 좋은 동작이다.
이 프로그램에서 가장 좋은 이동은 가장 높은 평균 최종 게임 점수를 가진 시뮬레이션 이동이다.

Note: I could have chosen to optimize for a different value such as the number of moves in the game.

However, this would actually make no difference in how the algorithm functions, because the number of moves in the game almost exactly predicts the game score. In 2048, the new tile added after each game move is normally a 2 tile, but has a 10% chance of being a 4 tile instead. This means the expected value of the new tile is 2.2 (2 × 90% + 4 × 10%). The total value of tiles is also preserved after every tile combination (ex: 2 tile combined with another 2 tile gives a 4 tile). As a result, game score can be calculated by multiplying the expected value of the new tile by the number of moves in the game, or with this formula: 2.2 × (real game move count + average move count).

현재 코드에 이 최적화된 최고 점수 기능을 추가하려면: 가능한 모든 이동에 시뮬레이션된 최종 총 점수 그룹을 추가하고 이 그룹의 값이 가장 높은 이동을 선택하십시오. 아래와 같습니다.

const possibleMoves = ["left", "right", "down", "up"];
const totalSimulations = 200;

let moveSimulationTotalScores = [0, 0, 0, 0];

possibleMoves.forEach((move, moveIndex) => { // simulations for all four possible starting moves
  for(let i = 0; i < totalSimulations / 4; i++) {
    const simulation = new Game(); // create simulation
    simulation.board = currentGame.board; // copy current game state to simulation
    simulation.makeMove(move); // make initial move
    while(!simulation.gameover()) {
      simulation.makeMove(possibleMoves[Math.floor(Math.random() * 4)]);
    } // make random moves until simulation game is over
    moveSimulationTotalScores[moveIndex] += simulation.getScore();
  }
});

// make best move with highest total simulation scores
let topScore = Math.max(...moveSimulationTotalScores);
let topScoreIndex = moveSimulationTotalScores.indexOf(topScore);
let bestMove = possibleMoves[topScoreIndex];

currentGame.makeMove(bestMove);

마지막으로 잘 작성된 2048 게임 클래스를 제시했는데 이 알고리즘은 실현하기 쉽다.JavaScript에서 많은 성능 업그레이드를 할 수 있습니다. 먼저 Web Workers의 병발성을 추가한 다음에 최종 게임 점수가 매우 낮은 동작을 편집할 수 있습니다.

결론

나는 당신이 이 글을 좋아하고, 당신이 자신의 프로젝트에서 몬테카로 방법을 이해하고 실시하는 데 도움이 된다는 것을 발견하기를 바랍니다.
체크아웃Jupiter과its source code.
굴러줘서 고마워요.
이 글은 최초my blog at xtrp.io에서 왔다.
- Gabriel Romualdo, 2020년 9월 12일