게임 2048에 대한 최적의 알고리즘은 무엇입니까

algorithm logic artificial-intelligence 2048


나는 최근에 게임 2048을 우연히 발견했다 . 비슷한 타일을 네 방향 중 하나로 움직여 "더 큰"타일을 만듭니다. 각 이동 후, 새로운 타일은 임의의 빈 위치에 2 또는 4 의 값으로 나타납니다 . 모든 상자가 채워지고 타일을 병합 할 수있는 동작이 없거나 값이 2048 인 타일을 만들면 게임이 종료됩니다 .

하나, 목표를 달성하기 위해 잘 정의 된 전략을 따라야합니다. 그래서 나는 그것을위한 프로그램을 작성하는 것을 생각했습니다.

내 현재 알고리즘 :

while (!game_over) {
    for each possible move:
        count_no_of_merges_for_2-tiles and 4-tiles
    choose the move with a large number of merges
}

내가하고있는 일은 언제든지, 타일을 값 24 와 병합 하려고 시도 합니다. 즉, 가능한 한 최소 24 타일을 사용 하려고 합니다. 이 방법으로 시도하면 다른 모든 타일이 자동으로 병합되고 전략이 좋아 보입니다.

그러나 실제로이 알고리즘을 사용하면 게임이 끝나기 전에 약 4000 포인트 만 얻습니다. 최대 점수 AFAIK는 현재 점수보다 훨씬 큰 20,000 점을 약간 넘습니다. 위보다 더 나은 알고리즘이 있습니까?





Answer 1 nneonneo


@ovolve 알고리즘에서 사용하는 minimax 검색 대신 expectimax 최적화를 사용하여 2048 AI를 개발했습니다 . AI는 모든 가능한 움직임에 대한 최대화를 수행 한 다음 가능한 모든 타일 스폰에 대한 기대 (타일 확률에 따라 가중, 즉 4의 경우 10 %, 2의 경우 90 %)를 수행합니다. 내가 아는 한, 기대 최적화를 제거 할 수는 없으며 (매우 드물게 분기를 제거하는 것을 제외하고) 사용 된 알고리즘은 신중하게 최적화 된 무차별 대입 검색입니다.

Performance

기본 구성의 AI (최대 검색 깊이 8)는 보드 위치의 복잡성에 따라 이동을 실행하는 데 10ms에서 200ms까지 걸립니다. 테스트에서 AI는 전체 게임을 진행하는 동안 초당 평균 이동 속도가 5-10 회 달성합니다. 검색 깊이가 6 이동으로 제한되면 AI는 초당 20+ 이동을 쉽게 실행할 수있어 재미있는 시청이 가능 합니다.

AI의 점수 성능을 평가하기 위해 AI를 100 회 실행했습니다 (리모콘을 통해 브라우저 게임에 연결됨). 각 타일에 대해 해당 타일을 한 번 이상 달성 한 게임 비율은 다음과 같습니다.

2048: 100%
4096: 100%
8192: 100%
16384: 94%
32768: 36%

모든 경기에서 최소 점수는 124024입니다. 달성 한 최대 점수는 794076입니다. 평균 점수는 387222입니다. AI는 2048 타일을 얻지 못했습니다 (100 게임에서 한 번이라도 게임을 잃지 않았습니다). 실제로, 매 실행마다 적어도 한 번 8192 타일을 달성했습니다 !

최고의 실행의 스크린 샷은 다음과 같습니다.

32768 tile, score 794076

이 게임은 96 분에 걸쳐 27830 번의 이동 또는 초당 평균 4.8 개의 움직임이 필요했습니다.

Implementation

내 접근 방식은 전체 보드 (16 개 항목)를 단일 64 비트 정수 (타일이 니블, 즉 4 비트 청크)로 인코딩합니다. 64 비트 시스템에서는 전체 보드를 단일 시스템 레지스터로 전달할 수 있습니다.

비트 시프트 연산은 개별 행과 열을 추출하는 데 사용됩니다. 단일 행 또는 열은 16 비트 수량이므로 크기가 65536 인 테이블은 단일 행 또는 열에서 작동하는 변환을 인코딩 할 수 있습니다. 예를 들어, 이동은 각 이동이 단일 행 또는 열에 미치는 영향을 설명하는 사전 계산 된 "이동 효과 테이블"에 대한 4 개의 조회로 구현됩니다 (예 : "오른쪽 이동"테이블에는 "1122-> 0023"항목이 포함되어 있습니다. 행 [2,2,4,4]는 오른쪽으로 이동하면 행 [0,0,4,8]이됩니다).

스코어링은 또한 테이블 조회를 사용하여 수행됩니다. 테이블에는 가능한 모든 행 / 열에 대해 계산 된 휴리스틱 점수가 포함되며 보드의 결과 점수는 각 행과 열의 테이블 값 합계입니다.

이 보드 표현은 이동 및 스코어링을위한 테이블 조회 접근 방식과 함께 AI가 짧은 기간 (2011 년 중반 노트북의 한 코어에서 초당 10,000,000 개 이상의 게임 상태)으로 수많은 게임 상태를 검색 할 수있게합니다.

expectimax 검색 자체는 "예측"단계 (가능한 모든 타일 스폰 위치 및 값 테스트 및 각 가능성의 확률에 따라 최적화 된 점수 가중치 적용)와 "최대화"단계 (모든 가능한 이동 테스트) 사이를 번갈아 가며 반복되는 검색으로 코딩됩니다. 최고 점수를 가진 사람을 선택). 트리 검색은 이전에 본 위치 ( 조옮김 테이블 사용 )를 볼 때, 사전 정의 된 깊이 제한에 도달하거나 보드 상태가 매우 높지 않을 때 (예 : 6 "4"타일을 가져 와서 도달 한 경우) 종료됩니다. 시작 위치에서 연속해서). 일반적인 검색 깊이는 4-8 이동입니다.

Heuristics

최적화 알고리즘을 유리한 위치로 향하게하는 데 몇 가지 휴리스틱이 사용됩니다. 휴리스틱을 정확하게 선택하면 알고리즘 성능에 큰 영향을 미칩니다. 다양한 휴리스틱이 가중되고 위치 점수로 결합되어 주어진 보드 위치가 얼마나 "좋은"지를 결정합니다. 그런 다음 최적화 검색은 가능한 모든 보드 위치의 평균 점수를 최대화하는 것을 목표로합니다. 게임에 표시된 것처럼 실제 점수 는 보드 점수를 계산하는 데 사용 되지 않습니다. 지연된 병합이 큰 이점을 가져올 수있는 경우에는 타일 병합에 유리하게 가중치가 너무 높기 때문입니다.

처음에는 매우 간단한 두 가지 휴리스틱을 사용하여 열린 사각형에 "보너스"를 부여하고 가장자리에 큰 값을 지정했습니다. 이 휴리스틱은 꽤 잘 수행되어 16384를 달성하지만 32768에 도달하지는 않습니다.

Petr Morávek (@xificurk)은 AI를 가져 와서 새로운 휴리스틱을 추가했습니다. 첫 휴리스틱은 순위가 증가함에 따라 비-단조 행과 열을 갖는 것에 대한 패널티로, 작은 숫자의 비-단조 행이 점수에 큰 영향을 미치지 않을 것이지만, 큰 숫자의 비-단조 행이 점수를 크게 손상시킵니다. 두 번째 휴리스틱은 열린 공간 외에도 잠재적 병합 수 (인접 동일한 값)를 계산했습니다. 이 두 휴리스틱은 알고리즘을 단조로운 보드 (병합이 더 쉬운) 및 많은 병합이있는 보드 위치로 푸시하는 데 도움이되었습니다 (가능한 경우 병합을보다 효과적으로 적용하도록 권장).

또한 Petr는 "메타 최적화"전략을 사용하여 휴리스틱 가중치를 최적화했습니다 ( CMA-ES 라는 알고리즘 사용 ). 가중치 자체는 가능한 가장 높은 평균 점수를 얻도록 조정되었습니다.

이러한 변경의 효과는 매우 중요합니다. 알고리즘은 16384 타일을 시간의 약 13 %에서 90 % 이상 달성하는 것으로 전환했으며, 알고리즘은 1/3의 시간 동안 32768을 달성하기 시작했습니다. .

휴리스틱에 여전히 개선의 여지가 있다고 생각합니다. 이 알고리즘은 아직 "최적화"되지는 않았지만 꽤 가까워지고 있다고 생각합니다.


AI가 게임의 1/3 이상에서 32768 타일을 달성한다는 것은 큰 이정표입니다. 공식 게임에서 인간 플레이어가 32768을 달성했다면 (즉, savestates 또는 undo와 같은 도구를 사용하지 않음) 나는 놀랄 것입니다. 65536 타일이 도달 할 수 있다고 생각합니다!

AI를 직접 사용해 볼 수 있습니다. 코드는 https://github.com/nneonneo/2048-ai 에서 사용할 수 있습니다 .




Answer 2 ovolve


저는이 글에서 다른 사람들이 언급 한 AI 프로그램의 저자입니다. AI의 실제 작동 상태를 보거나 소스를 읽을 수 있습니다 .

현재이 프로그램은 랩톱 브라우저의 자바 스크립트에서 약 90 %의 승률을 달성하여 이동 당 약 100 밀리 초의 사고 시간을 제공하므로 완벽하지는 않지만 (아직 잘 수행되지는 않습니다).

게임은 개별 상태 공간, 완벽한 정보, 체스 및 체커와 같은 턴 기반 게임이므로 알파 베타 전정을 사용한 미니 맥스 검색 과 같은 게임에서 작동하는 것으로 입증 된 동일한 방법을 사용했습니다 . 이미 그 알고리즘에 대한 많은 정보가 있기 때문에 정적 평가 함수 에서 사용 하고 다른 사람들이 여기에서 표현한 많은 직관을 공식화 하는 두 가지 주요 휴리스틱에 대해 이야기 하겠습니다.

Monotonicity

이 휴리스틱은 타일의 값이 모두 왼쪽 / 오른쪽 및 위 / 아래 방향을 따라 증가 또는 감소하는지 확인하려고합니다. 이 휴리스틱만으로도 많은 다른 사람들이 언급 한 직관을 포착 할 수 있습니다. 일반적으로 값이 작은 타일이 고아가되는 것을 방지하고 작은 타일이 계단식으로 배열되어 큰 타일에 채워져 보드가 매우 체계적으로 유지됩니다.

다음은 완벽하게 단조로운 격자의 스크린 샷입니다. 나는 다른 휴리스틱을 무시하고 단 조성을 고려하기 위해 eval 함수로 알고리즘을 실행하여 이것을 얻었습니다.

A perfectly monotonic 2048 board

Smoothness

위의 휴리스틱만으로도 인접한 타일의 가치가 감소하는 구조를 만드는 경향이 있지만 물론 병합하기 위해서는 인접한 타일의 값이 동일해야합니다. 따라서 매끄러움 휴리스틱은 인접한 타일 간의 값 차이를 측정하여이 수를 최소화하려고합니다.

해커 뉴스 (Hacker News)에 대한 논평자는 그래프 이론 측면에서이 아이디어 의 흥미로운 공식화 를 제시했습니다.

이 우수한 패러디 포크 에 의해 완벽하게 매끄러운 그리드의 스크린 샷 이 있습니다.

A perfectly smooth 2048 board

프리 타일

마지막으로, 게임 보드가 너무 좁아지면 옵션이 빨리 소진 될 수 있기 때문에 무료 타일이 너무 적 으면 패널티가 부과됩니다.

그리고 그게 다야! 이러한 기준을 최적화하면서 게임 공간을 검색하면 성능이 크게 향상됩니다. 명시 적으로 코딩 된 이동 전략 대신 이와 같은 일반화 된 접근 방식을 사용하는 한 가지 장점은 알고리즘이 종종 흥미롭고 예기치 않은 솔루션을 찾을 수 있다는 것입니다. 당신이 그것을 실행하는 경우, 그것은 벽이나 구석에 갑자기 건물을 전환 같은 놀라운하지만 효과적인 움직임을 만들 것입니다.

Edit:

다음은이 접근법의 힘에 대한 데모입니다. 타일 ​​값을 풀었습니다 (그래서 2048에 도달 한 후에 계속 진행됨). 여덟 번의 시도 후에 가장 좋은 결과가 있습니다.

4096

그렇습니다. 2048과 함께 4096입니다. =) 같은 보드에서 2048 타일을 3 번 달성했습니다.




Answer 3 Ronenz


나는 하드 코딩 된 인텔리전스 (휴리스틱, 스코어링 기능 등) 가 없는 이 게임의 AI 아이디어에 관심을 갖게되었습니다 . AI는 게임 규칙 만 "알고" 게임 플레이를 "피겨"야 합니다. 이것은 게임 플레이가 본질적으로 게임에 대한 인간의 이해를 나타내는 스코어링 기능에 의해 조종되는 무차별적인 힘 (이 스레드의 것과 같은)과 대부분의 AI와 대조적입니다.

AI 알고리즘

간단하지만 놀랍게도 좋은 재생 알고리즘을 발견했습니다. 주어진 보드의 다음 움직임을 결정하기 위해 AI는 게임 끝날 때까지 임의의 움직임을 사용하여 메모리에서 게임을 재생합니다 . 이것은 최종 게임 점수를 추적하면서 여러 번 수행됩니다. 그런 다음 시작 이동 당 평균 종료 점수 가 계산됩니다. 평균 점수가 가장 높은 시작 동작이 다음 동작으로 선택됩니다.

AI는 한 번에 100 번의 런 (메모리 게임)으로 2048 타일을 80 %, 4096 타일을 50 % 달성합니다. 10000 런을 사용하면 2048 타일은 100 %, 4096 타일은 70 %, 8192 타일은 약 1 %가됩니다.

실제로보기

최고 점수는 다음과 같습니다.

best score

이 알고리즘에 대한 흥미로운 사실은 랜덤 플레이 게임은 당연히 아주 나쁘지만 최상의 (또는 가장 나쁜) 움직임을 선택하면 매우 좋은 게임 플레이로 이어진다는 것입니다. 특정 위치의 메모리 내 무작위 플레이 게임은 죽기 전에 약 40 회의 추가 움직임으로 평균 340 개의 추가 점수를 얻습니다. AI를 실행하고 디버그 콘솔을 열어서 직접 확인할 수 있습니다.

이 그래프는이 점을 보여줍니다. 파란색 선은 각 이동 후 보드 점수를 나타냅니다. 빨간색 선은 해당 위치에서 알고리즘의 최고의 랜덤 런 엔드 게임 점수를 보여줍니다 . 본질적으로 빨간색 값은 알고리즘의 가장 좋은 추측이므로 파란색 값을 위쪽으로 "풀"합니다. 빨간색 선이 각 지점에서 파란색 선보다 약간 위에있는 것을 보는 것은 흥미롭지 만 파란색 선은 계속 증가하고 있습니다.

scoring graph

나는 알고리즘이 그것을 생성하는 움직임을 선택하기 위해 실제로 좋은 게임 플레이를 예측할 필요가 없다는 것이 놀랍습니다.

나중에 검색하면이 알고리즘이 Pure Monte Carlo Tree Search 알고리즘 으로 분류 될 수 있음을 알았습니다 .

구현 및 링크

먼저 여기에서 작동 하는 JavaScript 버전을 만들었습니다 . 이 버전은 적절한 시간에 100 회의 실행을 수행 할 수 있습니다. 추가 정보를 보려면 콘솔을여십시오. ( 소스 )

나중에 더 많은 것을 즐기기 위해 @nneonneo 고도로 최적화 된 인프라를 사용하고 내 버전을 C ++로 구현했습니다. 이 버전을 사용하면 이동 당 최대 100000 회의 실행이 가능하며 인내심이있는 경우에는 1000000까지 실행할 수 있습니다. 제공된 건물 지침. 콘솔에서 실행되며 웹 버전을 재생할 수있는 리모컨도 있습니다. ( 소스 )

Results

놀랍게도, 런 수를 늘리더라도 게임 플레이가 크게 향상되지는 않습니다. 이 전략에는 4096 개의 타일과 8192 개의 타일을 달성하는 데 매우 가까운 모든 작은 타일이있는 약 80000 포인트에서 한계가있는 것 같습니다. 런 수를 100에서 100000으로 늘리면 이 점수 한도 (5 %에서 40 %)에 도달 할 가능성 이 높아지지만이를 통과하지는 않습니다.

10000을 실행하면 임계 위치 근처에서 일시적으로 1000000으로 증가하여 최대 129892와 8192 타일을 달성하는 시간의 1 % 미만으로이 장벽을 무너 뜨 렸습니다.

Improvements

이 알고리즘을 구현 한 후 min 또는 max 점수 또는 min, max 및 avg 조합을 사용하여 많은 개선을 시도했습니다. 또한 깊이를 사용하여 시도했습니다. 이동 당 K 런을 시도하는 대신 지정된 길이 (예 : "위, 위, 왼쪽")의 이동 목록 당 K 이동을 시도 하고 최고 점수 이동 목록의 첫 번째 이동을 선택했습니다.

나중에 주어진 이동 목록 다음에 이동을 할 수있는 조건부 확률을 고려한 스코어링 트리를 구현했습니다.

그러나 이러한 아이디어 중 어느 것도 간단한 첫 번째 아이디어에 비해 실질적인 이점을 보여주지 못했습니다. 이 아이디어에 대한 코드를 C ++ 코드에 주석 처리했습니다.

런 중 하나라도 실수로 다음 타일에 도달했을 때 런 수를 일시적으로 1000000으로 늘린 "딥 검색"메커니즘을 추가했습니다. 이것은 시간 향상을 제공했습니다.

인공 지능의 도메인 독립성을 유지하는 다른 개선 아이디어가있는 사람이 있다면 듣고 싶습니다.

2048 변종 및 클론

재미를 위해서 AI를 북마크릿으로 구현 하여 게임 컨트롤에 연결했습니다. 이것은 AI가 오리지널 게임과 그 변형 을 사용할 수있게합니다 .

이는 도메인의 독립적 인 AI 특성으로 인해 가능합니다. Hexagonal clone과 같은 일부 변종은 매우 다릅니다.




Answer 4 Daren


편집 : 이것은 인간의 의식적 사고 과정을 모델링하는 순진한 알고리즘이며 AI보다 AI에 비해 매우 약한 결과를 얻습니다. 응답 타임 라인 초기에 제출되었습니다.

알고리즘을 개선하고 게임을 이겼습니다! 끝이 가까워지면 운이 나빠져 실패 할 수 있습니다. 패턴을 깨 뜨리십시오), 그러나 기본적으로 고정 부분과 모바일 부분을 가지고 놀게됩니다. 이것이 당신의 목표입니다 :

Ready to finish

이것이 기본적으로 선택한 모델입니다.

1024 512 256 128
  8   16  32  64
  4   2   x   x
  x   x   x   x

선택한 모서리는 임의적이며 기본적으로 하나의 키 (금지 된 이동)를 누르지 마십시오. 그렇다면 반대를 다시 누르고 수정하십시오. 이후 타일의 경우 모델은 항상 다음 임의 타일이 2가 될 것으로 예상하고 현재 모델의 반대쪽에 나타납니다 (첫 번째 행은 불완전한 반면 첫 번째 행이 완료되면 첫 번째 행이 완료되면 왼쪽 하단에 나타남) 모서리).

여기 알고리즘이 있습니다. 약 80 %의 승리 (항상 더 많은 "전문적인"AI 기술로 승리하는 것이 가능할 것 같습니다.)

initiateModel();

while(!game_over)
{    
    checkCornerChosen(); // Unimplemented, but it might be an improvement to change the reference point

    for each 3 possible move:
        evaluateResult()
    execute move with best score
    if no move is available, execute forbidden move and undo, recalculateModel()
 }

 evaluateResult() {
     calculatesBestCurrentModel()
     calculates distance to chosen model
     stores result
 }

 calculateBestCurrentModel() {
      (according to the current highest tile acheived and their distribution)
  }

누락 된 단계에 대한 몇 가지 지침. 여기:model change

모델이 예상 모델에 가까워짐에 따라 모델이 변경되었습니다. AI가 달성하려는 모델은

 512 256 128  x
  X   X   x   x
  X   X   x   x
  x   x   x   x

그리고 거기에 도달하는 사슬은 다음과 같습니다.

 512 256  64  O
  8   16  32  O
  4   x   x   x
  x   x   x   x

O 는 금지 구역을 나타내는 ...

따라서 오른쪽을 누른 다음 다시 오른쪽을 누른 다음 (4가 생성 된 위치에 따라 오른쪽 또는 위쪽) 다음 체인이 완성 될 때까지 완료합니다.

Chain completed

이제 모델과 체인이 다시 돌아 왔습니다.

 512 256 128  64
  4   8  16   32
  X   X   x   x
  x   x   x   x

두 번째 포인터, 그것은 운이 좋지 않았고 주요 지점이 잡혔습니다. 실패 할 가능성이 있지만 여전히 달성 할 수 있습니다.

Enter image description here

모델과 체인은 다음과 같습니다.

  O 1024 512 256
  O   O   O  128
  8  16   32  64
  4   x   x   x

128에 도달하면 전체 행을 다시 얻습니다.

  O 1024 512 256
  x   x  128 128
  x   x   x   x
  x   x   x   x



Answer 5 Nicola Pezzotti


내 블로그 의 게시물 내용을 여기에 복사합니다.


내가 제안하는 솔루션은 매우 간단하고 구현하기 쉽습니다. 그럼에도 불구하고 점수는 131040입니다. 알고리즘 성능에 대한 여러 벤치 마크가 제공됩니다.

Score

Algorithm

휴리스틱 스코어링 알고리즘

내 알고리즘의 기반이되는 가정은 다소 간단합니다. 높은 점수를 얻으려면 보드를 최대한 깔끔하게 유지해야합니다. 특히, 최적의 설정은 타일 값의 선형 및 단조 감소 순서로 제공됩니다. 이 직관은 타일 값의 상한도 제공합니다.s여기서 n은 보드의 타일 수입니다.

(필요한 경우 4 타일이 2 타일 대신 무작위로 생성되면 131072 타일에 도달 할 가능성이 있습니다)

보드를 구성하는 두 가지 가능한 방법이 다음 이미지에 나와 있습니다.

enter image description here

단조로운 내림차순으로 타일의 순서를 강제하기 위해, 점수 si는 보드상의 선형화 된 값의 합에 공통 비율 r <1을 갖는 기하학적 시퀀스의 값을 곱한 것으로 계산된다.

s

s

여러 선형 경로를 한 번에 평가할 수 있으며 최종 점수는 모든 경로의 최대 점수입니다.

결정 규칙

의사 결정 규칙이 현명하지는 않지만 파이썬 코드는 다음과 같습니다.

@staticmethod
def nextMove(board,recursion_depth=3):
    m,s = AI.nextMoveRecur(board,recursion_depth,recursion_depth)
    return m

@staticmethod
def nextMoveRecur(board,depth,maxDepth,base=0.9):
    bestScore = -1.
    bestMove = 0
    for m in range(1,5):
        if(board.validMove(m)):
            newBoard = copy.deepcopy(board)
            newBoard.move(m,add_tile=True)

            score = AI.evaluate(newBoard)
            if depth != 0:
                my_m,my_s = AI.nextMoveRecur(newBoard,depth-1,maxDepth)
                score += my_s*pow(base,maxDepth-depth+1)

            if(score > bestScore):
                bestMove = m
                bestScore = score
    return (bestMove,bestScore);

minmax 또는 Expectiminimax를 구현하면 알고리즘이 확실히 향상됩니다. 보다 정교한 의사 결정 규칙은 알고리즘 속도를 늦추고 구현하는 데 약간의 시간이 필요합니다. 가까운 시일 내에 minimax 구현을 시도 할 것입니다. (계속 지켜봐주십시오)

Benchmark

  • T1-121 테스트-8 가지 경로-r = 0.125
  • T2-122 테스트-8 개의 다른 경로-r = 0.25
  • T3-132 테스트-8 가지 경로-r = 0.5
  • T4-211 테스트-2 개의 다른 경로-r = 0.125
  • T5-274 테스트-2 가지 경로-r = 0.25
  • T6-211 테스트-2 개의 다른 경로-r = 0.5

enter image description here enter image description here enter image description here enter image description here

T2의 경우 10 번의 4 번의 테스트로 평균 점수가 4096 인 타일이 생성됩니다.s42000

Code

코드는 GiHub의 다음 링크에서 찾을 수 있습니다. https://github.com/Nicola17/term2048-AI term2048을 기반으로 하며 Python으로 작성되었습니다. 가능한 빨리 C ++에서보다 효율적인 버전을 구현할 것입니다.