algorithm - 위키 - 게임 2048의 최적 알고리즘은 무엇입니까?




www 나무 위키 (10)

나는 최근에 게임 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 포인트가 약간 넘습니다. 위의 알고리즘보다 나은 알고리즘이 있습니까?


@ ovolve의 알고리즘에 사용 된 minimax 검색 대신 expectimax 최적화를 사용하여 2048 AI를 개발했습니다. AI는 모든 가능한 이동에 대해 최대화를 수행하고 가능한 모든 타일 생성에 대한 기대 (타일의 확률로 가중치, 즉 2의 경우 10 %, 2의 경우 90 %)를 수행합니다. 내가 아는 한, expectimax 최적화를 제거 할 수는 없지만 (매우 바람직하지 않은 분기를 제외하고), 알고리즘은 신중히 최적화 된 무차별 강제 검색입니다.

공연

기본 구성 (최대 탐색 깊이 8)의 AI는 보드 위치의 복잡성에 따라 이동을 실행하는 데 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 타일을 얻었습니다!

다음은 최고의 실행 스크린 샷입니다.

이 게임은 96 분 동안 27830 회 또는 초당 평균 4.8 회 이동했습니다.

이행

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

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

채점은 테이블 조회를 사용하여 수행됩니다. 테이블에는 가능한 모든 행 / 열에 대해 계산 된 경험적 점수가 포함되어 있으며 보드에 대한 결과 점수는 단순히 각 행과 열에 대한 테이블 값의 합계입니다.

이 보드 표현은 이동 및 점수 매기기를위한 테이블 조회 접근법과 함께 AI가 짧은 시간 (엄청나게 많은 2011 년 중반 랩톱의 한 코어에서 초당 10,000,000 이상의 게임 상태)에서 많은 수의 게임 상태를 검색 할 수있게 해줍니다.

기대치 검색 자체는 "예상"단계 (모든 가능한 타일 스폰 위치 및 값을 테스트하고 각 가능성의 확률로 최적화 된 점수에 가중치 부여)와 "최대화"단계 (모든 가능한 이동을 테스트) 사이에서 교대로 반복되는 검색으로 코딩됩니다. 점수가 가장 좋은 것을 선택). 트리 탐색은 이전에 본 위치를 보거나 ( 전위 테이블 사용 ) 미리 정의 된 심도 한계에 도달하거나 가능성이 희박한 보드 상태에 도달하면 종료됩니다 (예 : 6 "4"타일을 얻음으로써 도달 함) 시작 위치에서 한 행으로). 일반적인 검색 깊이는 4-8 이동입니다.

인공 지능

유리한 위치로 최적화 알고리즘을 유도하기 위해 여러 가지 경험적 방법이 사용됩니다. 휴리스틱의 정확한 선택은 알고리즘의 성능에 큰 영향을 미칩니다. 다양한 휴리스틱 스 가중치가 적용되어 위치 스코어로 결합되어 보드 위치가 "양호"한지 여부를 결정합니다. 최적화 검색은 가능한 모든 보드 위치의 평균 점수를 최대화하는 것을 목표로합니다. 게임에서 보여지는 실제 스코어는 보드 스코어를 계산하는 데 사용 되지 않습니다 . 보드 스코어를 합병하기에 너무 가중되기 때문에 (합병 지연이 큰 이익을 가져올 수있는 경우).

처음에는 열린 사각형에 "보너스"를 부여하고 가장자리에 값이 큰 두 가지 매우 간단한 경험법을 사용했습니다. 이러한 경험적 방법은 꽤 잘 수행되어 자주 16384를 달성했지만 결코 32768을 얻지 못했습니다.

Petr Morávek (@xificurk)이 AI를 사용하여 두 가지 새로운 발견 적 방법을 추가했습니다. 첫 번째 경험적 방법은 순위가 높아질수록 증가하는 비 단조 행과 열을 갖는 페널티였습니다. 단조롭지 않은 작은 숫자의 행이 점수에 크게 영향을주지는 않지만 단조롭지 않은 큰 행 수가 점수를 크게 상하게했습니다. 두 번째 경험적 방법은 열린 공간 외에도 잠재적 인 병합 수 (인접한 동일한 값)를 계산합니다. 이 두 가지 경험적 방법은 알고리즘을 단조로운 보드 (병합하기가 더 쉽다)쪽으로 밀어 내고, 많은 병합이있는 보드 포지션으로 향하게했다.

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

이러한 변화의 효과는 매우 중요합니다. 알고리즘은 16384 타일을 달성하는 데 걸린 시간의 약 13 %를 90 % 이상으로 달성했으며 알고리즘은 1/3의 시간 동안 32768을 달성하기 시작했습니다 (반면 오래된 경험적 방법은 한 번도 32768 타일을 생성하지 못했습니다) .

휴리스틱 스에 대한 개선 여지는 여전히 있다고 생각합니다. 이 알고리즘은 확실히 "최적"이 아니지만 꽤 가까워지고있는 것처럼 느껴집니다.

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

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


나는 하드 코딩 된 지능을 포함 하지 않는 이 게임에 대한 인공 지능 (즉, 인공 지능, 득점 기능 등)에 대한 아이디어에 관심을 갖게되었습니다. 인공 지능은 게임 규칙 만 "알아야 " 하고 게임 플레이를 "파악" 해야합니다. 이것은 게임 플레이가 본질적으로 게임에 대한 인간의 이해를 나타내는 채점 함수에 의해 조종되는 대부분의 인공 지능 (이 스레드와 같은)과는 대조적입니다.

인공 지능 알고리즘

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

움직임 당 100 회의 실행만으로 (즉, 메모리 게임에서) AI는 2048 타일을 80 %, 4096 타일을 50 % 달성합니다. 10000 실행을 사용하면 2048 타일은 100 %, 4096 타일은 70 %, 8192 타일은 약 1 %가됩니다.

실제 상황에서보기

최고의 점수는 다음과 같습니다 :

이 알고리즘에 대한 흥미로운 사실은 랜덤 플레이 게임이 놀랍지 않게 상당히 나쁘지만 최상의 (또는 가장 나쁜) 이동을 선택하면 아주 좋은 게임 플레이를 유도한다는 것입니다. 전형적인 AI 게임은 70000 포인트에 도달 할 수 있으며 마지막으로 3000 번의 이동이 가능합니다. 임의의 주어진 위치에서 메모리 내 임의 재생 게임은 죽기 전에 약 40 개의 추가 동작에서 평균 340 개의 추가 포인트를 산출합니다. AI를 실행하고 디버그 콘솔을 열어서 직접 확인할 수 있습니다.

이 그래프는이 점을 보여줍니다. 파란색 선은 매 이동 후 보드 점수를 표시합니다. 빨간색 선은 그 위치에서 알고리즘이 가장 잘한 랜덤 실행 종료 점수를 보여줍니다. 본질적으로, 빨강 값은 파랑 값을 위쪽 방향으로 "당기는"것이며 알고리즘의 가장 좋은 추측입니다. 빨간색 선이 각 점에서 파란색 선 위로 약간 작은 것만 보아도 흥미 롭습니다. 그러나 파란색 선은 점점 더 계속해서 커집니다.

알고리즘을 생성하는 동작을 선택하기 위해 알고리즘이 실제로 좋은 게임 플레이를 미리 예측할 필요가 없다는 것은 매우 놀라운 일입니다.

나중에이 알고리즘이 Pure Monte Carlo Tree Search 알고리즘으로 분류 될 수 있음을 발견했습니다.

구현 및 링크

처음에는 JavaScript 버전을 만들었습니다.이 버전은 여기서 실제로 볼 수 있습니다. 이 버전은 적절한 시간에 100 회의 실행을 실행할 수 있습니다. 추가 정보를 보려면 콘솔을 엽니 다. ( source )

나중에 좀 더 놀기 위해 @nneonneo를 고도로 최적화 된 인프라를 사용하고 C ++로 내 버전을 구현했습니다. 이 버전은 인내심을 가지고 있다면 움직임 당 최대 100000 회 실행하고 1000000 회까지 허용합니다. 건축 지침 제공. 콘솔에서 실행되며 웹 버전을 재생하는 원격 제어 기능도 있습니다. ( source )

결과

놀랍게도 실행 횟수를 늘려도 게임 플레이가 크게 향상되지는 않습니다. 4096 타일과 모든 작은 타일로 약 80000 포인트에서이 전략에 한계가 있으며, 8192 타일을 달성하는 데 매우 가깝습니다. 실행 횟수를 100에서 100000으로 늘리면이 점수 한도 (5 %에서 40 %)에 도달 할 확률 이 높아 지지만이를 뛰어 넘을 확률 은 높아집니다.

10000을 돌리면 임계 위치 근처에서 1000000으로 일시적으로 증가하고이 장벽을 1 % 미만으로 낮춰 최대 점수 129892와 8192 타일을 달성했습니다.

개량

이 알고리즘을 구현 한 후 min 또는 max 점수 또는 min, max 및 avg의 조합을 사용하여 많은 개선을 시도했습니다. 나는 또한 깊이를 사용하여 시도 : 이동 당 K 실행을 시도하는 대신 주어진 길이의 이동 목록 (예 : "위로, 위로, 왼쪽")에 K 개의 이동을 시도하고 가장 좋은 점수 이동 목록의 첫 번째 이동을 선택했습니다.

나중에 나는 주어진 이동 목록 후에 이동을 할 수있는 조건부 확률을 고려한 채점 트리를 구현했다.

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

어떤 실행이 우연히 다음 가장 높은 타일에 도달 할 때 실행 번호를 일시적으로 1000000으로 늘린 "Deep Search"메커니즘을 추가했습니다. 이것은 시간 개선을 제공했습니다.

AI의 도메인 독립성을 유지하는 다른 개선 아이디어가 있다면 누구든지 듣고 싶습니다.

2048 변종과 클론

재미있게 하기 위해 AI를 북마크릿으로 구현 하여 게임 컨트롤에 연결했습니다. 이를 통해 AI는 원래 게임 및 여러 변형을 처리 할 수 있습니다.

이것은 AI의 도메인 독립적 특성으로 인해 가능합니다. 일부 변형은 육각형 복제와 같이 매우 구별됩니다.


저는 다른 사람들이이 글에서 언급 한 인공 지능 프로그램의 저자입니다. AI가 action 중이거나 source 읽을 수 있습니다.

현재이 프로그램은 이동 당 100 밀리 초의 사고 시간을 감안할 때 내 노트북의 브라우저에서 자바 스크립트로 실행되는 약 90 %의 승리율을 달성하므로 완벽한 것은 아니지만 아직 잘 수행됩니다.

게임은 이산 상태 공간, 완벽한 정보, 체스와 체커와 같은 턴 기반 게임이기 때문에, 나는 그 게임에서 작동하는 것으로 입증 된 동일한 방법, 즉 알파 베타 제거 search 갖춘 minimax search 사용했습니다. 그 알고리즘에 대한 많은 정보가 이미 있으므로 정적 평가 함수 에서 사용하는 두 가지 주요 발견 방법에 대해 이야기하고 다른 사람들이 여기에서 표현한 많은 직관을 공식화합니다.

단조 로움

이 경험적 방법은 타일의 값이 모두 왼쪽 / 오른쪽 및 위 / 아래 방향을 따라 증가 또는 감소하도록합니다. 이 경험적 방법만으로도 많은 사람들이 언급 한 직관을 파악할 수 있습니다. 더 높은 가치의 타일은 구석에 모여 있어야합니다. 일반적으로 크기가 작은 타일이 고아가되는 것을 방지하고 보드를 매우 체계적으로 유지하며 작은 타일을 연쇄하여 큰 타일로 채 웁니다.

다음은 완벽하게 단조로운 그리드의 스크린 샷입니다. 나는 다른 휴리스틱 스를 무시하고 단조 로움만을 고려하여 eval 함수를 사용하여 알고리즘을 실행함으로써 이것을 얻었다.

부드러움

위의 경험적 방법만으로는 인접한 타일의 가치가 감소하는 구조를 만드는 경향이 있지만 병합하려면 인접한 타일이 동일한 값을 가져야합니다. 따라서 부드러움 발견 적 방법은 인접한 타일 간의 값 차이를 측정하여이 수를 최소화하려고합니다.

Hacker News의 주석 작성자는 그래프 이론의 관점에서이 아이디어를 흥미롭게 공식화했습니다 .

이 탁월한 패러디 포크 덕분에 완벽하게 부드러운 그리드의 스크린 샷을 보실 수 있습니다.

무료 타일

마지막으로 게임 보드가 너무 좁아지면 옵션이 빨리 사라질 수 있기 때문에 프리 타일이 너무 적어서 벌금이 부과됩니다.

그리고 그게 다야! 이러한 기준을 최적화하면서 게임 공간을 검색하면 탁월한 성능을 얻을 수 있습니다. 명시 적으로 코딩 된 이동 전략이 아닌 일반화 된 접근 방식을 사용하면 얻을 수있는 이점 중 하나는 알고리즘이 종종 흥미롭고 예기치 않은 솔루션을 찾을 수 있다는 것입니다. 시계가 실행되면 갑자기 벽이나 모퉁이가 바뀌는 것처럼 놀랍지 만 효과적 인 움직임을 보입니다.

편집하다:

여기에이 접근 방식의 힘에 대한 시연이 있습니다. 나는 타일 값을 캡핑 해제했다. (따라서 2048에 도달 한 후 계속 진행했다.) 여기 8 번의 시도 후에 최상의 결과가 나온다.

네, 그것은 2048과 나란히 4096입니다. =) 즉, 같은 보드에서 3 번에 2048 번 타일을 얻었습니다.


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

내가 제안한 솔루션은 구현이 매우 간단하고 쉽다. 비록 131040 점에 도달했습니다. 알고리즘 성능의 몇 가지 벤치 마크가 제시됩니다.

연산

경험적 득점 알고리즘

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

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

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

단조 감소 순서로 타일의 안수를 시행하기 위해, 보드상의 선형화 된 값의 합에 공통 비율 r <1 인 기하학적 시퀀스의 값을 곱한 값으로 계산됩니다.

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

의사 결정 규칙

구현 된 결정 룰은 현명하지 않습니다. 파이썬의 코드는 여기에 있습니다 :

@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 구현을 시도 할 것입니다. (계속 지켜봐주세요)

기준

  • 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

T2의 경우, 10 개의 4 가지 테스트는 4096 타일을 평균 점수 42000

암호

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


편집 : 이것은 순진한 알고리즘으로 인간의 의식적인 사고 과정을 모델링하며 AI와 비교하여 매우 약한 결과를 얻습니다. 응답 기한에 일찍 제출되었습니다.

나는 알고리즘을 세련시키고 게임을 때렸다! 마지막에 가까운 간단한 불운으로 인해 실패 할 수도 있습니다 (아래로 내려 가야합니다. 절대하지 않아야하며 타일이 가장 높은 위치에 나타납니다.) 맨 윗줄을 채우려고하면 왼쪽으로 이동하지 않습니다. 패턴을 깨뜨림), 기본적으로 고정 부분과 모바일 부분을 갖고 놀게됩니다. 이것이 당신의 목표입니다.

이것이 내가 선택한 모델입니다.

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

선택한 모서리는 임의적입니다. 기본적으로 하나의 키 (금지 된 이동)를 절대 누르지 마십시오. 금지되어 있으면 반대를 다시 눌러 수정하십시오. 미래의 타일의 경우 모델은 항상 다음 무작위 타일을 2로 예상하고 현재 모델의 반대쪽에 표시합니다 (첫 번째 행이 완료되지 않은 상태에서 오른쪽 하단의 첫 번째 행이 완료되면 왼쪽 하단에 있음). 모서리).

알고리즘은 다음과 같습니다. 약 80 %의 승리 (더 많은 "프로페셔널"인공 지능 기법으로 항상이기는 ​​것은 가능하지만, 이것에 대해서는 확실하지 않습니다.)

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)
  }

누락 된 단계에 대한 몇 가지 지침. 이리:

모델은 예상 모델에 더 가까워 졌기 때문에 바뀌 었습니다. 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가 어디에 생성되었는지에 따라 오른쪽 또는 위쪽으로) 다음 체인이 완료 될 때까지 체인을 완료합니다.

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

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

두 번째 포인터는 불운을 낳았으며 주요 지점을 차지했습니다. 실패 할 가능성이 있지만 여전히 달성 할 수 있습니다.

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

  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

내 알고리즘은 매우 잘 작동하는 알고리즘을 발견했다고 생각합니다. 종종 점수가 10000을 넘었고, 내 개인적인 베스트는 16000 정도였습니다. 솔루션은 구석에서 가장 큰 숫자를 유지하는 것이 아니라 최상위 행에 유지하는 것입니다.

아래 코드를 참조하십시오.

while( !game_over ) {
    move_direction=up;
    if( !move_is_possible(up) ) {
        if( move_is_possible(right) && move_is_possible(left) ){
            if( number_of_empty_cells_after_moves(left,up) > number_of_empty_cells_after_moves(right,up) ) 
                move_direction = left;
            else
                move_direction = right;
        } else if ( move_is_possible(left) ){
            move_direction = left;
        } else if ( move_is_possible(right) ){
            move_direction = right;
        } else {
            move_direction = down;
        }
    }
    do_move(move_direction);
}

이것은 OP의 질문에 대한 직접적인 대답이 아니며, 이것은 동일한 문제를 해결하기 위해 지금까지 시도한 것들 (실험)의 일부이며 일부 결과를 얻었으며 공유하고 싶은 몇 가지 관찰을 가지고 있습니다. 이것에 대한 더 깊은 통찰력.

난 그냥 3과 5에서 검색 트리 깊이 컷오프와 알파 베타 전정과 내 minimax 구현을 시도했다. 나는 edX 코스 ColumbiaX에 대한 프로젝트 과제로 4x4 그리드에 대한 동일한 문제를 해결하기 위해 노력했다 : CSMM.101x 인공 지능 ( AI) .

주로 직감과 위에서 논의 된 것들로부터 몇 가지 발견 적 평가 함수의 볼록한 조합 (다른 경험적 가중치를 시도했습니다)을 적용했습니다.

  1. 단조 로움
  2. 사용 가능한 여유 공간

필자의 경우 컴퓨터 플레이어는 완전히 무작위이지만 여전히 상대 설정을 가정하고 AI 플레이어 에이전트를 최대 플레이어로 구현했습니다.

게임을하기 위해 4x4 격자가 있습니다.

관측:

첫 번째 휴리스틱 함수 또는 두 번째 휴리스틱 함수에 너무 많은 가중치를 할당하면 AI 플레이어가 얻는 점수가 모두 낮아집니다. 휴리스틱 함수에 많은 가능한 가중치 할당을 사용하고 볼록 조합을 사용했지만 아주 드물게 AI 플레이어는 2048 점을 얻을 수 있습니다. 대부분의 경우 1024 또는 512로 멈 춥니 다.

나는 또한 코너의 경험적 방법을 시도했지만 어떤 이유로 그것이 결과를 나 빠지게 만들었습니다. 어떤 직관입니까?

또한 검색 깊이 컷오프를 3에서 5로 늘리려고 시도했는데 (그 공간을 검색 한 후에 허용 시간을 초과하여 더 이상 늘릴 수 없음), 인접 타일 값을보고 더 많은 휴리스틱을 추가했습니다. 병합 할 수 있다면 더 많은 점수를 얻지 만 여전히 2048을 얻을 수는 없습니다.

나는 minimax 대신에 Expectimax를 사용하는 것이 더 좋을 것이라고 생각하지만, 여전히 minimax만으로이 문제를 해결하고 2048이나 4096과 같은 높은 점수를 얻고 싶다. 내가 무엇을 놓치고 있는지 확실하지 않다.

아래 애니메이션은 AI 에이전트가 컴퓨터 플레이어와 함께 플레이 한 게임의 마지막 몇 단계를 보여줍니다.

모든 통찰력은 정말 도움이 될 것입니다, 미리 감사드립니다. (이 기사에 대한 내 블로그 게시물의 링크 : https://sandipanweb.wordpress.com/2017/03/06/using-minimax-with-alpha-beta-pruning-and-heuristic-evaluation-to-solve-2048-game-with-computer/ )

다음 애니메이션은 AI 플레이어 에이전트가 2048 점을 얻을 수있는 게임의 마지막 몇 단계를 보여줍니다. 이번에는 절대 값도 추론을 추가합니다.

다음 그림 은 플레이어 AI 에이전트가 컴퓨터를 한 단계에 대한 적으로 간주 한 게임 트리를 보여줍니다 .


하스켈에 2048 솔버를 썼습니다. 왜냐하면 저는 지금이 언어를 배우고 있기 때문입니다.

게임의 구현은 실제 게임과 약간 다릅니다. 새로운 타일은 항상 90 % 2와 10 % 4가 아닌 '2'입니다. 그리고 새로운 타일은 무작위가 아니라 항상 왼쪽 상단에서 처음으로 사용할 수있는 타일입니다. 이 변형은 Det 2048 이라고도 합니다.

따라서이 솔버는 결정적입니다.

나는 빈 타일을 선호하는 철저한 알고리즘을 사용했다. 그것은 깊이 1-4에서 꽤 빠르게 수행되지만, 깊이 5에서는 이동 당 약 1 초가 지나면 느려집니다.

아래는 해결 알고리즘을 구현하는 코드입니다. 그리드는 Integer의 16 길이 배열로 표현됩니다. 그리고 득점은 빈 사각형의 수를 세어 간단히 계산됩니다.

bestMove :: Int -> [Int] -> Int
bestMove depth grid = maxTuple [ (gridValue depth (takeTurn x grid), x) | x <- [0..3], takeTurn x grid /= [] ]

gridValue :: Int -> [Int] -> Int
gridValue _ [] = -1
gridValue 0 grid = length $ filter (==0) grid  -- <= SCORING
gridValue depth grid = maxInList [ gridValue (depth-1) (takeTurn x grid) | x <- [0..3] ]

나는 그것이 그것의 단순함을 위해 아주 성공적이라고 생각한다. 빈 그리드에서 시작하여 깊이 5에서 해결할 때 도달하는 결과는 다음과 같습니다.

Move 4006
[2,64,16,4]
[16,4096,128,512]
[2048,64,1024,16]
[2,4,16,2]

Game Over

소스 코드는 https://github.com/popovitsj/2048-haskell 에서 확인할 수 있습니다.https://github.com/popovitsj/2048-haskell


다른 대답들 중 많은 것들은 가능한 미래, 발견 적 방법, 학습 등의 계산적으로 비싼 검색과 함께 AI를 사용합니다. 이것들은 인상적이며 아마도 앞으로는 올바른 방법이지만, 나는 또 다른 아이디어를 기고 싶습니다.

좋은 게임 플레이어가 사용하는 전략을 모델로 만듭니다.

예 :

13 14 15 16
12 11 10  9
 5  6  7  8
 4  3  2  1

다음 사각형 값이 현재 값보다 커질 때까지 위에 표시된 순서대로 사각형을 읽습니다. 이것은 동일한 값의 다른 타일을이 사각형에 병합하려는 문제를 나타냅니다.

이 문제를 해결하기 위해 두 가지 방법 중 하나를 남겨 두거나 더 나쁘게 이동하지 않고 두 가지 가능성을 모두 조사하면 더 많은 문제가 즉각적으로 드러날 수 있습니다.이 방법은 의존성 목록을 구성하며 각 문제는 다른 문제를 먼저 해결해야합니다. 나는이 체인을 가지고 있거나 어떤 경우에는 다음 번 이동을 결정할 때 내부적으로 의존성이있는 트리를 가지고 있다고 생각합니다. 특히 붙어있을 때 그렇습니다.

타일은 이웃과 병합해야하지만 너무 작습니다. 이웃과 병합하십시오.

길고 큰 타일 : 주변의 작은 타일의 값을 늘립니다.

기타...

전체 접근법은 이보다 복잡하지만 더 복잡하지는 않을 것입니다. 점수, 가중치, 뉴런 및 가능성에 대한 심층 검색이 부족한 느낌의 기계적 요소 일 수 있습니다. 가능성의 나무는 심지어 어떤 분기를 필요로 할 정도로 충분히 커야합니다.


이 게임에는 이미 AI 구현이 here . here . README에서 발췌 :

알고리즘은 심도있는 첫 번째 알파 - 베타 검색을 반복적으로 반복합니다. 평가 함수는 격자의 타일 수를 최소화하면서 행과 열을 단조롭게 유지하려고합니다 (모두 감소 또는 증가).

유용하게 사용할 수있는이 알고리즘 에 대한 ycombinator 에 대한 토론도 있습니다.





2048