질문자 :nitish712
나는 최근에 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 }
내가하고있는 일은 어느 시점에서나 타일을 값 2 와 4 로 병합하려고 시도하는 것입니다. 즉, 가능한 최소 2 와 4 이런 식으로 시도하면 다른 모든 타일이 자동으로 병합되고 전략이 좋은 것 같습니다.
하지만 실제로 이 알고리즘을 사용하면 게임이 종료되기 전까지 4000점 정도밖에 얻을 수 없습니다. 최대 점수 AFAIK는 현재 점수보다 훨씬 큰 20,000점보다 약간 높습니다. 위의 것보다 더 나은 알고리즘이 있습니까?
@ovolve 알고리즘에서 사용하는 minimax 검색 대신 expectimax 최적화를 사용하여 2048 AI를 개발했습니다. AI는 단순히 가능한 모든 이동에 대해 최대화를 수행한 다음 가능한 모든 타일 생성에 대한 기대를 수행합니다(타일의 확률에 따라 가중치가 부여됨, 즉 4의 경우 10%, 2의 경우 90%). 내가 아는 한, 예상 최대 최적화를 제거하는 것은 불가능하며(매우 가능성이 낮은 분기를 제거하는 것을 제외하고) 사용된 알고리즘은 신중하게 최적화된 무차별 대입 검색입니다.
성능
기본 구성(최대 검색 깊이 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개의 조회로 구현됩니다(예: "오른쪽으로 이동" 테이블에는 행 [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 라는 알고리즘 사용)을 사용하여 발견적 가중치를 최적화했습니다. 여기서 가중치 자체는 가능한 가장 높은 평균 점수를 얻도록 조정되었습니다.
이러한 변화의 효과는 매우 중요합니다. 알고리즘은 시간의 약 13%에서 16384 타일을 달성하는 데 시간의 90% 이상을 달성했으며 알고리즘은 시간의 1/3에 걸쳐 32768을 달성하기 시작했습니다. .
휴리스틱에 대해서는 아직 개선의 여지가 있다고 생각합니다. 이 알고리즘은 아직 "최적"이 아니지만 꽤 가까워지고 있는 것 같습니다.
AI가 게임의 3분의 1 이상에서 32768 타일을 달성했다는 것은 엄청난 이정표입니다. 인간 플레이어가 공식 게임에서 32768을 달성했다면(즉, 상태 저장 또는 실행 취소와 같은 도구를 사용하지 않고) 듣고 놀랄 것입니다. 65536 타일이 손이 닿는 곳에 있다고 생각합니다!
AI를 직접 체험할 수 있습니다. 코드는 https://github.com/nneonneo/2048-ai 에서 사용할 수 있습니다.
저는 다른 사람들이 이 스레드에서 언급한 AI 프로그램의 작성자입니다. 작동 중인 AI를 보거나 소스를 읽을 수 있습니다.
현재 이 프로그램은 이동당 약 100밀리초의 생각 시간이 주어지면 랩톱의 브라우저에서 자바스크립트로 실행되는 약 90%의 승률을 달성하므로 완벽하지는 않지만(아직!) 꽤 잘 수행됩니다.
게임은 이산 상태 공간, 완벽한 정보, 체스 및 체커와 같은 턴 기반 게임이기 때문에 해당 게임에서 작동하는 것으로 입증된 것과 동일한 방법, 즉 알파 베타 가지치기를 사용한 미니맥스 검색을 사용했습니다. 해당 알고리즘에 대한 정보가 이미 많이 있으므로 정적 평가 함수 에서 사용하고 다른 사람들이 여기에서 표현한 많은 직관을 공식화하는 두 가지 주요 경험적 방법에 대해 이야기하겠습니다.
단조로움
이 휴리스틱은 타일의 값이 모두 왼쪽/오른쪽 및 위/아래 방향을 따라 증가하거나 감소하는지 확인하려고 합니다. 이 휴리스틱만으로도 많은 다른 사람들이 언급한, 더 높은 가치의 타일이 한 구석에 모여 있어야 한다는 직관을 포착합니다. 일반적으로 더 작은 값의 타일이 고아가 되는 것을 방지하고 더 작은 타일이 계단식으로 연결되어 더 큰 타일로 채워지도록 보드를 매우 체계적으로 유지합니다.
다음은 완벽하게 단조로운 그리드의 스크린샷입니다. 다른 휴리스틱을 무시하고 단조성만 고려하도록 설정된 eval 함수로 알고리즘을 실행하여 이것을 얻었습니다.
부드러움
위의 휴리스틱만으로는 인접한 타일의 가치가 감소하는 구조를 만드는 경향이 있지만, 물론 병합하기 위해서는 인접한 타일의 값이 같아야 합니다. 따라서 부드러움 휴리스틱은 이 개수를 최소화하기 위해 인접한 타일 간의 값 차이를 측정합니다.
Hacker News의 논평자는 그래프 이론의 관점에서 이 아이디어를 흥미롭게 공식화했습니다.
다음은 완벽하게 매끄러운 그리드의 스크린샷입니다.
무료 타일
마지막으로, 게임 보드가 너무 비좁을 때 옵션이 빠르게 소진될 수 있기 때문에 여유 타일이 너무 적으면 패널티가 있습니다.
그리고 그게 다야! 이러한 기준을 최적화하면서 게임 공간을 검색하면 매우 좋은 성능을 얻을 수 있습니다. 명시적으로 코딩된 이동 전략보다 이와 같은 일반화된 접근 방식을 사용할 때의 한 가지 이점은 알고리즘이 종종 흥미롭고 예상치 못한 솔루션을 찾을 수 있다는 것입니다. 달리는 모습을 지켜보면 갑자기 어떤 벽이나 모서리에 쌓이게 되는지 갑자기 전환하는 것과 같이 놀랍지만 효과적인 움직임을 보일 것입니다.
편집하다:
다음은 이 접근 방식의 위력을 보여줍니다. 타일 값의 상한선을 해제했는데(2048에 도달한 후에도 계속 유지됨) 다음은 8번의 시도 후에 최상의 결과입니다.
예, 2048과 함께 4096입니다. =) 즉, 동일한 보드에서 찾기 힘든 2048 타일을 세 번 달성했다는 의미입니다.
나는 하드 코딩된 지능 (즉, 휴리스틱, 득점 기능 등)이 포함되지 않은 이 게임의 AI 아이디어에 관심을 갖게 되었습니다. AI는 게임 규칙만 "알고" 게임 플레이를 "파악"해야 합니다. 이것은 게임 플레이가 본질적으로 게임에 대한 인간의 이해를 나타내는 득점 기능에 의해 조종되는 무차별 대입(brute force)인 대부분의 AI(이 스레드에 있는 것과 같은)와 대조적입니다.
AI 알고리즘
간단하지만 놀랍도록 좋은 플레이 알고리즘을 찾았습니다. 주어진 보드의 다음 움직임을 결정하기 위해 AI는 게임 이 끝날 때까지 임의의 움직임을 사용하여 메모리에서 게임을 합니다. 이것은 최종 게임 점수를 추적하면서 여러 번 수행됩니다. 그런 다음 시작 이동당 평균 종료 점수가 계산됩니다. 평균 최종 점수가 가장 높은 시작 동작이 다음 동작으로 선택됩니다.
이동당 단 100번의 실행(즉, 메모리 게임에서)으로 AI는 80%의 경우 2048 타일을 달성하고 50%의 경우 4096 타일을 달성합니다. 10000번 실행하면 2048 타일은 100%, 4096 타일은 70%, 8192 타일은 약 1%가 됩니다.
실제 보기
최고 달성 점수는 다음과 같습니다.
이 알고리즘에 대한 흥미로운 사실은 랜덤 플레이 게임이 놀랍지 않게 상당히 나쁘지만 가장 좋은(또는 가장 덜 나쁜) 동작을 선택하면 매우 좋은 게임 플레이로 이어진다는 것입니다. 주어진 위치에서 메모리 내 무작위 플레이 게임은 죽기 전에 약 40개의 추가 이동에서 평균 340점의 추가 점수를 산출합니다. (AI를 실행하고 디버그 콘솔을 열어 직접 확인할 수 있습니다.)
이 그래프는 이 점을 보여줍니다. 파란색 선은 각 이동 후의 보드 점수를 보여줍니다. 빨간색 선은 해당 위치에서 알고리즘의 최고의 무작위 실행 최종 게임 점수를 보여줍니다. 본질적으로 빨간색 값은 알고리즘의 최선의 추측이므로 파란색 값을 위쪽으로 "끌어당깁니다". 빨간색 선이 각 지점에서 파란색 선보다 약간 위에 있지만 파란색 선은 계속해서 점점 더 증가하는 것을 보는 것이 흥미롭습니다.
나는 알고리즘이 그것을 생성하는 움직임을 선택하기 위해 실제로 좋은 게임 플레이를 예측할 필요가 없다는 것이 매우 놀랍습니다.
나중에 검색해보니 이 알고리즘이 Pure Monte Carlo Tree Search 알고리즘으로 분류될 수 있다는 것을 알았습니다.
구현 및 링크
먼저 여기에서 실제로 볼 수 있는 JavaScript 버전을 만들었습니다. 이 버전은 적절한 시간에 100번의 실행을 실행할 수 있습니다. 추가 정보를 보려면 콘솔을 여세요. ( 출처 )
나중에 좀 더 놀기 위해 @nneonneo 고도로 최적화된 인프라를 사용하고 내 버전을 C++로 구현했습니다. 이 버전에서는 이동당 최대 100000회, 인내심이 있다면 1000000회까지 실행할 수 있습니다. 건물 지침이 제공됩니다. 콘솔에서 실행되며 웹 버전을 재생할 수 있는 리모컨도 있습니다. ( 출처 )
결과
놀랍게도 런 수를 늘려도 게임 플레이가 크게 향상되지 않습니다. 이 전략에는 4096 타일과 모든 작은 타일이 8192 타일 달성에 매우 근접한 약 80000 포인트에서 제한이 있는 것 같습니다. 런 수를 100에서 100000으로 늘리면 이 점수 제한(5%에서 40%)에 도달하지만 이를 넘지 못할 확률이 높아집니다.
임계 위치 근처에서 일시적으로 1000000으로 증가하여 10000번을 달리면 129892점과 8192점 타일의 최대 점수를 달성한 경우의 1% 미만으로 이 장벽을 깰 수 있었습니다.
개량
이 알고리즘을 구현한 후 최소 또는 최대 점수 또는 최소, 최대 및 평균의 조합을 사용하여 많은 개선을 시도했습니다. 나는 또한 깊이를 사용해 보았습니다. 이동당 K개의 실행을 시도하는 대신 지정된 길이의 이동 목록 당 K개의 이동을 시도하고(예: "위, 위, 왼쪽") 최고 득점 이동 목록의 첫 번째 동작을 선택했습니다.
나중에 나는 주어진 이동 목록 이후에 이동을 할 수 있는 조건부 확률을 고려한 득점 트리를 구현했습니다.
그러나 이러한 아이디어 중 어느 것도 단순한 첫 번째 아이디어보다 실질적인 이점을 보여주지 못했습니다. 이러한 아이디어에 대한 코드를 C++ 코드에 주석 처리했습니다.
실행 중 하나가 실수로 다음으로 높은 타일에 도달했을 때 실행 수를 일시적으로 1000000으로 늘리는 "Deep Search" 메커니즘을 추가했습니다. 이것은 시간 개선을 제공했습니다.
AI의 영역 독립성을 유지하는 다른 개선 아이디어가 있는지 듣고 싶습니다.
2048 변종 및 클론
재미로 AI를 북마크릿으로 구현 하여 게임 컨트롤에 연결했습니다. 이를 통해 AI는 원본 게임 및 여러 변형 과 함께 작업할 수 있습니다.
이는 AI의 도메인 독립적 특성으로 인해 가능합니다. Hexagonal 클론과 같은 일부 변종은 매우 뚜렷합니다.
편집: 이것은 인간의 의식적 사고 과정을 모델링하는 순진한 알고리즘이며 한 타일 앞만 보기 때문에 모든 가능성을 검색하는 AI에 비해 매우 약한 결과를 얻습니다. 응답 일정에 일찍 제출되었습니다.
알고리즘을 다듬고 게임을 이겼다! 마지막에 가까운 단순한 불운으로 인해 실패 할 수 있습니다 (당신은 절대 해서는 안되는 아래로 이동해야하며 가장 높은 위치에 타일이 나타납니다. 맨 윗줄을 채우려고 노력하십시오. 왼쪽으로 이동하면 패턴 깨기) 기본적으로 고정 부품과 가동 부품을 가지고 놀게 됩니다. 이것이 당신의 목표입니다:
기본적으로 선택한 모델입니다.
1024 512 256 128 8 16 32 64 4 2 xx xxxx
선택한 모서리는 임의적이며 기본적으로 하나의 키(금지된 동작)를 누르지 않으며, 누르면 반대를 다시 누르고 수정하려고 합니다. 미래 타일의 경우 모델은 항상 다음 무작위 타일이 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) }
누락된 단계에 대한 몇 가지 지침. 여기:
예상 모델에 더 가까워진 행운으로 모델이 변경되었습니다. AI가 달성하고자 하는 모델은
512 256 128 x XX xx XX xx xxxx
그리고 거기에 도달하는 사슬은 다음과 같습니다.
512 256 64 O 8 16 32 O 4 xxx xxxx
O 는 금지된 공간을 나타냅니다...
따라서 오른쪽을 누른 다음 다시 오른쪽을 누른 다음(4가 생성된 위치에 따라 오른쪽 또는 위쪽) 다음이 될 때까지 체인을 완료합니다.
이제 모델과 체인이 다음으로 돌아갑니다.
512 256 128 64 4 8 16 32 XX xx xxxx
두 번째 포인터는 운이 나빴고 주요 지점을 차지했습니다. 실패할 가능성이 높지만 여전히 달성할 수 있습니다.
모델과 체인은 다음과 같습니다.
O 1024 512 256 OOO 128 8 16 32 64 4 xxx
128에 도달하면 전체 행을 다시 얻습니다.
O 1024 512 256 xx 128 128 xxxx xxxx
내 블로그 게시물 의 내용을 여기에 복사합니다.
내가 제안하는 솔루션은 매우 간단하고 구현하기 쉽습니다. 그러나 131040점에 도달했습니다. 알고리즘 성능에 대한 여러 벤치마크가 제공됩니다.
연산
휴리스틱 채점 알고리즘
내 알고리즘의 기반이 되는 가정은 다소 간단합니다. 더 높은 점수를 얻으려면 보드를 가능한 한 깔끔하게 유지해야 합니다. 특히, 최적의 설정은 타일 값의 선형 및 단조 감소 차수에 의해 주어집니다. 이 직관은 타일 값의 상한도 제공합니다. 
여기서 n은 보드의 타일 수입니다.
(필요 시 2타일 대신 4타일을 랜덤으로 생성하면 131072타일에 도달할 가능성이 있음)
보드를 구성하는 두 가지 가능한 방법은 다음 이미지에 나와 있습니다.
타일의 배열을 단조 감소 순서로 적용하기 위해 보드의 선형화된 값의 합과 공통 비율 r<1인 기하학적 시퀀스의 값을 곱한 값 si를 계산했습니다.
%20*%20r%5En)
여러 선형 경로를 한 번에 평가할 수 있으며 최종 점수는 모든 경로의 최대 점수가 됩니다.
결정 규칙
구현된 결정 규칙은 그다지 똑똑하지 않습니다. Python의 코드는 다음과 같습니다.
@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를 구현하면 확실히 알고리즘이 향상됩니다. 분명히 더 정교한 결정 규칙은 알고리즘의 속도를 늦추고 구현하는 데 약간의 시간이 필요할 것입니다. 가까운 시일 내에 최소 최대 구현을 시도할 것입니다. (계속 지켜봐주세요)
기준
- 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을 기반으로 하며 Python으로 작성되었습니다. 가능한 한 빨리 C++로 더 효율적인 버전을 구현하겠습니다.
저는 이 스레드에서 언급된 다른 프로그램보다 더 나은 점수를 받은 2048 컨트롤러의 작성자입니다. 컨트롤러의 효율적인 구현은 github에서 사용할 수 있습니다. 별도의 리포지토리 에는 컨트롤러의 상태 평가 기능을 교육하는 데 사용되는 코드도 있습니다. 훈련 방법은 논문에 설명되어 있습니다.
컨트롤러는 시간차 학습 (강화 학습 기술)의 변형에 의해 처음부터(인간의 전문 지식 없이) 학습된 상태 평가 기능과 함께 기대 최대 검색을 사용합니다. 상태-값 함수는 기본적으로 보드에서 관찰되는 패턴의 가중 선형 함수인 n-튜플 네트워크를 사용합니다. 총 10억 개 이상의 가중치가 포함되었습니다.
성능
1 이동/초에서: 609104 (평균 100게임)
10개의 이동/초에서: 589355 (평균 300게임)
3플라이(약 1500무브/초): 511759 (평균 1000경기)
10 이동/초에 대한 타일 통계는 다음과 같습니다.
2048: 100% 4096: 100% 8192: 100% 16384: 97% 32768: 64% 32768,16384,8192,4096: 10%
(마지막 줄은 주어진 타일을 동시에 보드에 놓는 것을 의미합니다).
3겹의 경우:
2048: 100% 4096: 100% 8192: 100% 16384: 96% 32768: 54% 32768,16384,8192,4096: 8%
그러나 65536 타일을 얻는 것을 본 적이 없습니다.
내 시도는 위의 다른 솔루션과 마찬가지로 expectimax를 사용하지만 비트보드는 사용하지 않습니다. Nneonneo의 솔루션은 6개의 타일이 남아 있고 4개의 이동이 가능(2*6*4) 4 인 약 4 깊이인 1000만 이동을 확인할 수 있습니다. 제 경우에는 이 깊이를 탐색하는 데 너무 오래 걸리므로 남은 여유 타일 수에 따라 예상 최대 검색 깊이를 조정합니다.
depth = free > 7 ? 1 : (free > 4 ? 2 : 3)
보드의 점수는 다음과 같이 2D 그리드의 내적과 자유 타일 수의 제곱의 가중치 합으로 계산됩니다.
[[10,8,7,6.5], [.5,.7,1,3], [-.5,-1.5,-1.8,-2], [-3.8,-3.7,-3.5,-3]]
왼쪽 상단 타일에서 일종의 뱀처럼 타일을 내림차순으로 구성하도록 강제합니다.
아래 또는 github 에 있는 코드:
var n = 4, M = new MatrixTransform(n); var ai = {weights: [1, 1], depth: 1}; // depth=1 by default, but we adjust it on every prediction according to the number of free tiles var snake= [[10,8,7,6.5], [.5,.7,1,3], [-.5,-1.5,-1.8,-2], [-3.8,-3.7,-3.5,-3]] snake=snake.map(function(a){return a.map(Math.exp)}) initialize(ai) function run(ai) { var p; while ((p = predict(ai)) != null) { move(p, ai); } //console.log(ai.grid , maxValue(ai.grid)) ai.maxValue = maxValue(ai.grid) console.log(ai) } function initialize(ai) { ai.grid = []; for (var i = 0; i < n; i++) { ai.grid[i] = [] for (var j = 0; j < n; j++) { ai.grid[i][j] = 0; } } rand(ai.grid) rand(ai.grid) ai.steps = 0; } function move(p, ai) { //0:up, 1:right, 2:down, 3:left var newgrid = mv(p, ai.grid); if (!equal(newgrid, ai.grid)) { //console.log(stats(newgrid, ai.grid)) ai.grid = newgrid; try { rand(ai.grid) ai.steps++; } catch (e) { console.log('no room', e) } } } function predict(ai) { var free = freeCells(ai.grid); ai.depth = free > 7 ? 1 : (free > 4 ? 2 : 3); var root = {path: [],prob: 1,grid: ai.grid,children: []}; var x = expandMove(root, ai) //console.log("number of leaves", x) //console.log("number of leaves2", countLeaves(root)) if (!root.children.length) return null var values = root.children.map(expectimax); var mx = max(values); return root.children[mx[1]].path[0] } function countLeaves(node) { var x = 0; if (!node.children.length) return 1; for (var n of node.children) x += countLeaves(n); return x; } function expectimax(node) { if (!node.children.length) { return node.score } else { var values = node.children.map(expectimax); if (node.prob) { //we are at a max node return Math.max.apply(null, values) } else { // we are at a random node var avg = 0; for (var i = 0; i < values.length; i++) avg += node.children[i].prob * values[i] return avg / (values.length / 2) } } } function expandRandom(node, ai) { var x = 0; for (var i = 0; i < node.grid.length; i++) for (var j = 0; j < node.grid.length; j++) if (!node.grid[i][j]) { var grid2 = M.copy(node.grid), grid4 = M.copy(node.grid); grid2[i][j] = 2; grid4[i][j] = 4; var child2 = {grid: grid2,prob: .9,path: node.path,children: []}; var child4 = {grid: grid4,prob: .1,path: node.path,children: []} node.children.push(child2) node.children.push(child4) x += expandMove(child2, ai) x += expandMove(child4, ai) } return x; } function expandMove(node, ai) { // node={grid,path,score} var isLeaf = true, x = 0; if (node.path.length < ai.depth) { for (var move of[0, 1, 2, 3]) { var grid = mv(move, node.grid); if (!equal(grid, node.grid)) { isLeaf = false; var child = {grid: grid,path: node.path.concat([move]),children: []} node.children.push(child) x += expandRandom(child, ai) } } } if (isLeaf) node.score = dot(ai.weights, stats(node.grid)) return isLeaf ? 1 : x; } var cells = [] var table = document.querySelector("table"); for (var i = 0; i < n; i++) { var tr = document.createElement("tr"); cells[i] = []; for (var j = 0; j < n; j++) { cells[i][j] = document.createElement("td"); tr.appendChild(cells[i][j]) } table.appendChild(tr); } function updateUI(ai) { cells.forEach(function(a, i) { a.forEach(function(el, j) { el.innerHTML = ai.grid[i][j] || '' }) }); } updateUI(ai); updateHint(predict(ai)); function runAI() { var p = predict(ai); if (p != null && ai.running) { move(p, ai); updateUI(ai); updateHint(p); requestAnimationFrame(runAI); } } runai.onclick = function() { if (!ai.running) { this.innerHTML = 'stop AI'; ai.running = true; runAI(); } else { this.innerHTML = 'run AI'; ai.running = false; updateHint(predict(ai)); } } function updateHint(dir) { hintvalue.innerHTML = ['↑', '→', '↓', '←'][dir] || ''; } document.addEventListener("keydown", function(event) { if (!event.target.matches('.r *')) return; event.preventDefault(); // avoid scrolling if (event.which in map) { move(map[event.which], ai) console.log(stats(ai.grid)) updateUI(ai); updateHint(predict(ai)); } }) var map = { 38: 0, // Up 39: 1, // Right 40: 2, // Down 37: 3, // Left }; init.onclick = function() { initialize(ai); updateUI(ai); updateHint(predict(ai)); } function stats(grid, previousGrid) { var free = freeCells(grid); var c = dot2(grid, snake); return [c, free * free]; } function dist2(a, b) { //squared 2D distance return Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2) } function dot(a, b) { var r = 0; for (var i = 0; i < a.length; i++) r += a[i] * b[i]; return r } function dot2(a, b) { var r = 0; for (var i = 0; i < a.length; i++) for (var j = 0; j < a[0].length; j++) r += a[i][j] * b[i][j] return r; } function product(a) { return a.reduce(function(v, x) { return v * x }, 1) } function maxValue(grid) { return Math.max.apply(null, grid.map(function(a) { return Math.max.apply(null, a) })); } function freeCells(grid) { return grid.reduce(function(v, a) { return v + a.reduce(function(t, x) { return t + (x == 0) }, 0) }, 0) } function max(arr) { // return [value, index] of the max var m = [-Infinity, null]; for (var i = 0; i < arr.length; i++) { if (arr[i] > m[0]) m = [arr[i], i]; } return m } function min(arr) { // return [value, index] of the min var m = [Infinity, null]; for (var i = 0; i < arr.length; i++) { if (arr[i] < m[0]) m = [arr[i], i]; } return m } function maxScore(nodes) { var min = { score: -Infinity, path: [] }; for (var node of nodes) { if (node.score > min.score) min = node; } return min; } function mv(k, grid) { var tgrid = M.itransform(k, grid); for (var i = 0; i < tgrid.length; i++) { var a = tgrid[i]; for (var j = 0, jj = 0; j < a.length; j++) if (a[j]) a[jj++] = (j < a.length - 1 && a[j] == a[j + 1]) ? 2 * a[j++] : a[j] for (; jj < a.length; jj++) a[jj] = 0; } return M.transform(k, tgrid); } function rand(grid) { var r = Math.floor(Math.random() * freeCells(grid)), _r = 0; for (var i = 0; i < grid.length; i++) { for (var j = 0; j < grid.length; j++) { if (!grid[i][j]) { if (_r == r) { grid[i][j] = Math.random() < .9 ? 2 : 4 } _r++; } } } } function equal(grid1, grid2) { for (var i = 0; i < grid1.length; i++) for (var j = 0; j < grid1.length; j++) if (grid1[i][j] != grid2[i][j]) return false; return true; } function conv44valid(a, b) { var r = 0; for (var i = 0; i < 4; i++) for (var j = 0; j < 4; j++) r += a[i][j] * b[3 - i][3 - j] return r } function MatrixTransform(n) { var g = [], ig = []; for (var i = 0; i < n; i++) { g[i] = []; ig[i] = []; for (var j = 0; j < n; j++) { g[i][j] = [[j, i],[i, n-1-j],[j, n-1-i],[i, j]]; // transformation matrix in the 4 directions g[i][j] = [up, right, down, left] ig[i][j] = [[j, i],[i, n-1-j],[n-1-j, i],[i, j]]; // the inverse tranformations } } this.transform = function(k, grid) { return this.transformer(k, grid, g) } this.itransform = function(k, grid) { // inverse transform return this.transformer(k, grid, ig) } this.transformer = function(k, grid, mat) { var newgrid = []; for (var i = 0; i < grid.length; i++) { newgrid[i] = []; for (var j = 0; j < grid.length; j++) newgrid[i][j] = grid[mat[i][j][k][0]][mat[i][j][k][1]]; } return newgrid; } this.copy = function(grid) { return this.transform(3, grid) } }
body { font-family: Arial; } table, th, td { border: 1px solid black; margin: 0 auto; border-collapse: collapse; } td { width: 35px; height: 35px; text-align: center; } button { margin: 2px; padding: 3px 15px; color: rgba(0,0,0,.9); } .r { display: flex; align-items: center; justify-content: center; margin: .2em; position: relative; } #hintvalue { font-size: 1.4em; padding: 2px 8px; display: inline-flex; justify-content: center; width: 30px; }
<table title="press arrow keys"></table> <div class="r"> <button id=init>init</button> <button id=runai>run AI</button> <span id="hintvalue" title="Best predicted move to do, use your arrow keys" tabindex="-1"></span> </div>
나는 종종 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); }
여기에 이미 이 게임에 대한 AI 구현이 있습니다 . README에서 발췌:
알고리즘은 반복 심화 깊이 우선 알파-베타 검색입니다. 평가 함수는 그리드의 타일 수를 최소화하면서 행과 열을 단조롭게 유지하려고 합니다(모두 감소 또는 증가).
또한 Hacker News 에 유용하다고 생각할 수 있는 이 알고리즘에 대한 토론이 있습니다.
연산
while(!game_over) { for each possible move: evaluate next state choose the maximum evaluation }
평가
Evaluation = 128 (Constant) + (Number of Spaces x 128) + Sum of faces adjacent to a space { (1/face) x 4096 } + Sum of other faces { log(face) x 4 } + (Number of possible next moves x 256) + (Number of aligned values x 2)
평가 내용
128 (Constant)
이것은 기준선 및 테스트와 같은 다른 용도로 사용되는 상수입니다.
+ (Number of Spaces x 128)
공간이 많을수록 상태가 더 유연해집니다. 128개의 면으로 채워진 그리드가 최적의 불가능한 상태이기 때문에 128(중앙값)을 곱합니다.
+ Sum of faces adjacent to a space { (1/face) x 4096 }
여기서 우리는 병합될 가능성이 있는 면을 평가합니다. 역으로 평가하여 타일 2는 값 2048이 되고 타일 2048은 2로 평가됩니다.
+ Sum of other faces { log(face) x 4 }
여기에서 우리는 여전히 누적된 값을 확인해야 하지만 유연성 매개변수를 방해하지 않는 더 적은 방법으로 { x in [4,44] }의 합계를 얻습니다.
+ (Number of possible next moves x 256)
상태는 가능한 전환의 자유가 더 많으면 더 유연합니다.
+ (Number of aligned values x 2)
이것은 미리 보지 않고 해당 상태 내에서 병합 가능성에 대한 단순화된 확인입니다.
참고: 상수는 조정할 수 있습니다.
이것은 OP의 질문에 대한 직접적인 대답이 아닙니다. 이것은 내가 지금까지 동일한 문제를 해결하기 위해 시도하고 일부 결과를 얻었으며 공유하고 싶은 관찰이 있는 것입니다. 이것에서 추가 통찰력.
방금 검색 트리 깊이 컷오프가 3과 5인 알파-베타 가지치기로 미니맥스 구현을 시도했습니다. edX 과정 ColumbiaX: CSMM.101x 인공 지능( AI) .
나는 주로 직관과 위에서 논의한 것들로부터 몇 가지 발견적 평가 함수의 볼록 조합(다른 발견적 가중치를 시도함)을 적용했습니다.
- 단조로움
- 사용 가능한 여유 공간
필자의 경우 컴퓨터 플레이어는 완전히 무작위이지만 여전히 적대적인 설정을 가정하고 AI 플레이어 에이전트를 최대 플레이어로 구현했습니다.
게임을 하기 위한 4x4 그리드가 있습니다.
관찰:
첫 번째 발견적 기능이나 두 번째 발견적 기능에 너무 많은 가중치를 할당하면 두 경우 모두 AI 플레이어가 얻는 점수가 낮습니다. 나는 휴리스틱 함수에 가능한 많은 가중치 할당을 사용하고 볼록 조합을 사용했지만 AI 플레이어가 2048을 기록할 수 있는 경우는 매우 드뭅니다. 대부분의 경우 1024 또는 512에서 멈춥니다.
나도 코너 휴리스틱을 시도했지만 어떤 이유에서 결과를 악화, 어떤 직관 왜?
또한 검색 깊이 컷오프를 3에서 5로 늘리려고 했고(가지치기를 해도 허용된 시간을 초과하는 공간을 검색하기 때문에 더 늘릴 수 없음) 인접한 타일의 값을 보고 병합할 수 있으면 더 많은 점수를 얻을 수 있지만 여전히 2048을 얻을 수 없습니다.
미니맥스 대신에 익스피티맥스를 쓰면 더 좋을 것 같지만 그래도 미니맥스만으로 이 문제를 풀고 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/ 및 youtube 비디오: https://www.youtube.com/watch?v=VnVFilfZ0r4 )
다음 애니메이션은 AI 플레이어 에이전트가 2048점을 얻을 수 있는 게임의 마지막 몇 단계를 보여줍니다. 이번에는 절대값 휴리스틱도 추가됩니다.
다음 그림은 플레이어 AI 에이전트가 컴퓨터를 적으로 간주하여 단 한 단계만 탐색한 게임 트리를 보여줍니다.
저는 주로 지금 이 언어를 배우고 있기 때문에 Haskell에서 2048 솔버를 작성했습니다.
내 게임 구현은 새 타일이 항상 '2'(90% 2 및 10% 4가 아닌)라는 점에서 실제 게임과 약간 다릅니다. 그리고 새 타일은 무작위가 아니라 항상 왼쪽 상단에서 사용 가능한 첫 번째 타일입니다. 이 변종은 Det 2048 이라고도 합니다.
결과적으로 이 솔버는 결정적입니다.
빈 타일을 선호하는 철저한 알고리즘을 사용했습니다. 깊이 1-4에서는 매우 빠르게 수행되지만 깊이 5에서는 이동당 약 1초로 다소 느려집니다.
다음은 해결 알고리즘을 구현하는 코드입니다. 그리드는 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 에서 찾을 수 있습니다.
이 알고리즘은 게임에서 승리하는 데 최적은 아니지만 필요한 코드 양과 성능 측면에서 상당히 최적입니다.
if(can move neither right, up or down) direction = left else { do { direction = random from (right, down, up) } while(can not move in "direction") }
다른 많은 답변은 가능한 미래, 휴리스틱, 학습 등의 계산 비용이 많이 드는 검색과 함께 AI를 사용합니다. 이것들은 인상적이고 아마도 올바른 방향일 것입니다. 그러나 저는 다른 아이디어에 기여하고 싶습니다.
게임을 잘하는 플레이어가 사용하는 전략을 모델링하십시오.
예를 들어:
13 14 15 16 12 11 10 9 5 6 7 8 4 3 2 1
다음 제곱 값이 현재 값보다 클 때까지 위에 표시된 순서대로 제곱을 읽습니다. 이것은 같은 값의 다른 타일을 이 사각형에 병합하려는 문제를 나타냅니다.
이 문제를 해결하기 위해 두 가지 이동 방법이 있으며 두 가지 가능성을 모두 검토하면 더 많은 문제가 즉시 드러날 수 있습니다. 이는 종속성 목록을 형성하며 각 문제는 먼저 다른 문제를 해결해야 합니다. 내 다음 움직임을 결정할 때, 특히 막혔을 때 내부적으로 이 사슬 또는 어떤 경우에는 종속성 트리가 있다고 생각합니다.
타일이 이웃과 병합되어야 하지만 너무 작습니다. 다른 이웃을 이 이웃과 병합합니다.
더 큰 타일 방해: 더 작은 주변 타일의 값을 높입니다.
등...
전체 접근 방식은 이보다 더 복잡할 수 있지만 훨씬 더 복잡하지는 않습니다. 점수, 가중치, 뉴런 및 가능성에 대한 깊은 탐색이 부족한 느낌이 기계적일 수 있습니다. 가능성의 나무는 분기가 전혀 필요하지 않을 만큼 충분히 커야 합니다.
출처 : http:www.stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048