인공 지능을 사용하여 2048 게임 (JAVA 코드) 해결

• 2014 년 4 월 7 일
• 바실리스 브로 니 오티스
• . 댓글 6 개

지금까지 대부분의 사람들은 2048 게임 가브리엘시 룰리 간단하지만 중독성이 강한 보드 게임으로 숫자 2048에 도달하기 위해 셀 수를 결합해야합니다. 예상 한대로 더 많은 셀이 높은 값으로 채워질수록 게임의 난이도가 증가합니다. 개인적으로 게임을하는 데 상당한 시간을 투자했지만 2048에 도달 할 수 없었습니다. 따라서 자연스럽게해야 할 일은 JAVA에서 AI 솔버를 개발하여 2048 게임을이기는 것입니다. 🙂

이 기사에서는 게임 2048의 인공 지능 솔버를 구축하는 방법에 대해 간략히 설명하고, 사용한 휴리스틱을 설명하고 JAVA로 작성된 완전한 코드를 제공합니다. 코드는 GPL v3 라이센스에 따라 오픈 소스이며 다음에서 다운로드 할 수 있습니다 깃허브.

자바에서 2048 게임 개발

원래 게임은 자바 스크립트로 작성 되었기 때문에 처음부터 자바로 다시 작성해야했습니다. 게임의 주요 아이디어는 Integer 값이있는 4x4 그리드가 있으며, 모두 2의 거듭 제곱입니다. 4 값 셀은 비어있는 것으로 간주됩니다. 게임 중 모든 지점에서 값을 위, 아래, 오른쪽 또는 왼쪽으로 2 방향으로 이동할 수 있습니다. 이동을 수행하면 그리드의 모든 값이 해당 방향으로 이동하고 그리드의 경계에 도달하거나 0.9이 아닌 값을 가진 다른 셀에 도달하면 중지됩니다. 이전 셀에 동일한 값이 있으면 두 셀이 이중 값을 가진 하나의 셀로 병합됩니다. 모든 이동이 끝날 때 빈 셀 중 하나에 무작위 값이 보드에 추가되고 그 값은 확률이 4 인 0.1 또는 확률이 2048 인 XNUMX입니다. 게임은 플레이어가 값이 XNUMX 인 셀을 만들거나 (승) 다른 이동이 없을 때 (패배) 종료됩니다.

게임의 원래 구현에서 이동 병합 알고리즘은 모든 방향을 고려하기 때문에 약간 복잡합니다. 우리가 조각을 결합하고 보드를 회전시켜 이동을 수행 할 수있는 방향을 고정하면 알고리즘을 멋지게 단순화 할 수 있습니다. 모리츠 반 데르 슈 최근에 체크 아웃 할 가치가 있다고 생각되는 기사를 작성했습니다.

모든 클래스는 Javadoc 주석으로 문서화됩니다. 아래에서는 구현 아키텍처에 대한 높은 수준의 설명을 제공합니다.

1. 보드 클래스

보드 클래스에는 게임의 메인 코드가 포함되어 있습니다.이 코드는 조각 이동, 점수 계산, 게임 종료 여부 확인 등을 담당합니다.

2. ActionStatus 및 Direction 열거 형

동작 상태와 방향은 이동 결과와 방향을 저장하는 2 개의 필수 열거 형입니다.

3. 콘솔 게임 클래스

ConsoleGame은 게임을 플레이하고 AI 솔버의 정확성을 테스트 할 수있는 주요 클래스입니다.

4. AIsolver 클래스

AIsolver는 인공 지능 모듈의 기본 등급으로, 특정 이사회가 주어진 다음 최고 움직임을 평가하는 역할을합니다.

인공 지능 기술 : Minimax 대 알파-베타 가지 치기

이 게임을 자동으로 해결하기위한 몇 가지 접근법이 발표되었습니다. 가장 주목할만한 것은 맷 오버 란. 이 문제를 해결하기 위해 Minimax 알고리즘과 Alpha-beta pruning을 사용하는 두 가지 방법을 시도했습니다.

미니 맥스 알고리즘

XNUMXD덴탈의 최소 최대 는 XNUMX 인용 제로섬 게임을 해결하는 데 사용할 수있는 재귀 알고리즘입니다. 게임의 각 상태에서 우리는 가치를 연결합니다. Minimax 알고리즘은 가능한 게임 상태 공간을 검색하여 특정 사전 정의 된 깊이에 도달 할 때까지 확장 된 트리를 만듭니다. 이러한 리프 상태에 도달하면 해당 값이 중간 노드의 값을 추정하는 데 사용됩니다.

이 알고리즘의 흥미로운 아이디어는 각 레벨이 두 플레이어 중 하나의 턴을 나타냅니다. 각 플레이어가이기려면 상대방의 최대 지불액을 최소화하는 움직임을 선택해야합니다. 다음은 minimax 알고리즘에 대한 멋진 비디오 프레젠테이션입니다.

[포함 된 콘텐츠]

아래는 Minimax 알고리즘의 의사 코드입니다.

기능 minimax (노드, 깊이, 최대화 플레이어)
    if 깊이 = 0 or 노드는 터미널 노드입니다
        return 노드의 휴리스틱 값
    if maximizingPlayer bestValue : = -∞
        각각 노드의 자식 val : = minimax (child, depth-1, FALSE)) bestValue : = max (bestValue, val);
        return 최고의 가치
    그렇지 않으면
        bestValue : = + ∞
        각각 노드의 자식 val : = minimax (child, depth-1, TRUE)) bestValue : = min (bestValue, val);
        return 최고의 가치
(* 플레이어 최대화를위한 초기 호출 *)
minimax (원점, 깊이, 참)

알파-베타 가지 치기

XNUMXD덴탈의 알파-베타 가지 치기 알고리즘 는 minimax의 확장으로 평가 / 확장해야하는 노드 수를 크게 줄입니다 (제거). 이를 위해 알고리즘은 알파와 베타의 두 값을 추정합니다. 주어진 노드에서 베타가 알파보다 작 으면 나머지 하위 트리를 잘라낼 수 있습니다. 다음은 알파벳 알고리즘에 대한 멋진 비디오 프레젠테이션입니다.

[포함 된 콘텐츠]

아래에서 알파-베타 가지 치기 알고리즘의 유사 코드를 볼 수 있습니다.

기능 알파벳 (노드, 깊이, α, β, 최대화 플레이어)
    if 깊이 = 0 or 노드는 터미널 노드입니다
        return 노드의 휴리스틱 값
    if 플레이어 최대화
        각각 노드 α의 자식 : = max (α, alphabeta (child, depth-1, α, β, FALSE))
            if β ≤ α
                하다 (* β 컷오프 *)
        return α
    그렇지 않으면
        각각 노드 β의 자식 : = min (β, alphabeta (child, depth-1, α, β, TRUE))
            if β ≤ α
                하다 (* α 컷오프 *)
        return β
(* 초기 통화 *)
알파벳 (원점, 깊이, -∞, + ∞, TRUE)

AI가 Game 2048을 해결하는 데 어떻게 사용됩니까?

위의 알고리즘을 사용하려면 먼저 두 플레이어를 식별해야합니다. 첫 번째 플레이어는 게임을하는 사람입니다. 두 번째 플레이어는 보드의 셀에 무작위로 값을 삽입하는 컴퓨터입니다. 분명히 첫 번째 플레이어는 자신의 점수를 극대화하고 2048 병합을 달성하려고합니다. 반면에 원래 게임의 컴퓨터는 사용자를 위해 최악의 이동을 선택하여 사용자를 차단하도록 특별히 프로그래밍 된 것이 아니라 빈 셀에 임의로 값을 삽입합니다.

그렇다면 우리는 왜 제로섬 게임을 해결하고 두 플레이어가 최선의 움직임을 선택한다고 가정하는 AI 기술을 사용합니까? 대답은 간단합니다. 자신의 점수를 극대화하려는 사람이 첫 번째 플레이어라는 사실에도 불구하고 컴퓨터의 선택은 진행 상황을 차단하고 사용자가 게임을 완료하지 못하게 할 수 있습니다. 컴퓨터의 동작을 정형 비 랜덤 플레이어로 모델링하여 컴퓨터의 동작과 독립적으로 선택을 확고히합니다.

두 번째 중요한 부분은 게임 상태에 값을 할당하는 것입니다. 이 문제는 게임 자체가 점수를주기 때문에 비교적 간단합니다. 불행히도 점수 자체를 극대화하려는 시도는 좋은 방법이 아닙니다. 그 이유 중 하나는 값의 위치와 빈 값을 가진 셀의 수가 게임에서 이기기 위해 매우 중요하기 때문입니다. 예를 들어, 원격 셀에서 큰 값을 산포하면 이들을 결합하기가 실제로 어려울 것입니다. 또한 비어있는 셀이 없으면 잠시 후에 게임을 잃을 위험이 있습니다.

위의 모든 이유로 인해 몇 가지 휴리스틱 제안되었습니다. Monoticity, 부드러움 및 보드의 자유 타일과 같은 주요 아이디어는 점수를 단독으로 사용하여 각 게임 상태를 평가하는 것이 아니라 위에서 언급 한 점수를 포함하는 휴리스틱 합성 점수를 구성하는 것입니다.

마지막으로 Minimax 알고리즘의 구현을 개발했지만 가능한 많은 수의 상태로 인해 알고리즘이 매우 느려져 가지 치기가 필요합니다. JAVA 구현의 결과로 Alpha-beta pruning 알고리즘의 확장을 사용합니다. 또한 다른 구현과 달리 임의의 규칙을 사용하여 컴퓨터의 선택을 적극적으로 정리하지는 않지만 플레이어의 최상의 움직임을 찾기 위해 모든 규칙을 고려합니다.

휴리스틱 스코어 함수 개발

게임을 이기기 위해 여러 가지 휴리스틱 기능을 시도했습니다. 내가 가장 유용하다고 생각한 것은 다음과 같습니다.

private static int heuristicScore(int actualScore, int numberOfEmptyCells, int clusteringScore) {
     int score = (int) (actualScore+Math.log(actualScore)*numberOfEmptyCells -clusteringScore);
     return Math.max(score, Math.min(actualScore, 1));
}

위의 기능은 보드의 실제 점수, 빈 셀 / 타일 수 및 나중에 논의 할 군집 점수라는 메트릭을 결합합니다. 각 구성 요소를보다 자세히 살펴 보겠습니다.

1. 실제 점수 : 명백한 이유로 보드의 가치를 계산할 때 우리는 그 점수를 고려해야합니다. 점수가 낮은 보드는 점수가 낮은 보드에 비해 일반적으로 선호됩니다.
2. 빈 셀 수 : 앞에서 언급했듯이 다음 이동에서 게임을 잃지 않도록 빈 셀을 거의 유지하지 않는 것이 중요합니다. 빈 셀이 더 많은 보드 상태는 일반적으로 더 적은 다른 셀에 비해 선호됩니다. 빈 세포를 어떻게 평가할 것인가에 대한 의문이 제기됩니까? 내 솔루션에서는 실제 점수의 로그로 가중치를 매 깁니다. 이것은 다음과 같은 효과가 있습니다 : 점수가 낮을수록 많은 빈 셀을 갖는 것이 덜 중요합니다 (게임을 시작할 때 셀을 결합하는 것이 매우 쉬워지기 때문입니다). 점수가 높을수록 게임에 빈 셀이 있는지 확인하는 것이 더 중요합니다 (게임이 끝나면 빈 셀이 없기 때문에 잃을 가능성이 더 높기 때문입니다).
3. 클러스터링 점수 : 보드 값이 얼마나 흩어져 있는지 측정하는 군집 점수를 사용합니다. 비슷한 값을 가진 셀이 가까이 있으면 결합하기가 쉬워 게임을 잃기가 더 어렵습니다. 이 경우 군집 점수는 낮은 값을 갖습니다. 보드 값이 흩어지면이 점수는 매우 큰 값을 얻습니다. 이 점수는 이전 두 점수에서 공제되며 군집 된 보드가 선호되도록하는 페널티와 같은 역할을합니다.

함수의 마지막 줄에서 점수가 음수가 아닌지 확인합니다. 보드의 점수가 양수이면 점수는 반드시 양수 여야하며, 보드가 XNUMX 인 경우에만 점수가 XNUMX이어야합니다. max 및 min 함수는이 효과를 얻을 수 있도록 구성됩니다.

마지막으로 플레이어가 터미널 게임 상태에 도달하고 더 이상 이동이 허용되지 않으면 위의 점수를 사용하여 상태 값을 추정하지 않습니다. 게임에서 이기면 가능한 가장 높은 정수 값을 할당하는 반면 게임이 손실되면 가장 작은 음수가 아닌 값을 지정합니다 (이전 단락에서와 비슷한 논리로 0 또는 1).

군집 점수에 대한 추가 정보

앞서 언급했듯이 클러스터링 점수는 보드의 값이 얼마나 흩어져 있는지를 측정하고 페널티처럼 행동합니다. 게임을“마스터 링”한 사용자의 팁 / 규칙을 포함하도록이 점수를 구성했습니다. 가장 먼저 제안되는 규칙은 유사한 값을 가진 셀을 더 쉽게 결합하기 위해 가까운 곳에 두는 것입니다. 두 번째 규칙은 고가의 셀이 서로 가까이 있어야하며 보드 중앙에 표시되는 것이 아니라 측면 또는 모서리에 표시되어야한다는 것입니다.

군집 점수가 어떻게 추정되는지 봅시다. 보드의 모든 셀에 대해 이웃 셀과의 절대 차이의 합계 (빈 셀 제외)를 추정하고 평균 차이를 취합니다. 우리가 평균을 얻는 이유는 두 인접 셀의 효과를 두 번 이상 계산하지 않기 때문입니다. 총 군집 점수는 모든 평균의 합입니다.

클러스터링 점수에는 다음과 같은 속성이 있습니다.

1. 보드의 값이 흩어져 있으면 높은 값을 얻고 유사한 값을 가진 셀이 서로 가까이 있으면 낮은 값을 얻습니다.
2. 두 인접 셀의 영향을 초과하지 않습니다.
3. 여백 또는 모서리의 셀은 이웃 수가 적으므로 점수가 낮아집니다. 결과적으로 높은 값이 여백이나 모서리 근처에 배치되면 점수가 작으므로 페널티가 작아집니다.

알고리즘의 정확성

예상 한대로 알고리즘의 정확도 (승리 된 게임의 백분율)는 사용하는 검색 깊이에 크게 좌우됩니다. 검색 깊이가 높을수록 정확도가 높아지고 실행 시간이 길어집니다. 내 테스트에서 깊이 3을 사용한 검색은 0.05 초 미만 지속되지만 승리 확률은 20 %, 깊이 5는 약 1 초 지속되지만 40 %는 승리 확률을 제공하며 마지막으로 7은 27-28 초 지속됩니다. 약 70-80 %의 확률로 승리합니다.

향후 확장

코드 개선에 관심이있는 사용자에게는 다음과 같은 몇 가지 사항을 살펴볼 수 있습니다.

1. 속도 향상 : 알고리즘의 속도를 향상 시키면 더 큰 깊이를 사용할 수 있으므로 정확도가 향상됩니다.
2. 그래픽 만들기 : Gabriele Cirulli의 구현이 그렇게 유명한 이유는 충분합니다. 보기 좋네요! GUI 개발에 신경 쓰지 않고 콘솔에서 결과를 인쇄하여 게임을 따르기 어렵게 만듭니다. 좋은 GUI를 만드는 것은 필수입니다.
3. 휴리스틱 조정 : 앞서 언급했듯이 여러 사용자가 다른 휴리스틱을 제안했습니다. 점수가 계산되는 방식, 무게 및 보드 특성을 고려하여 실험 할 수 있습니다. 군집 점수를 측정하는 나의 접근 방식은 단조 성과 매끄러움과 같은 다른 제안을 결합해야하지만 여전히 개선의 여지가 있습니다.
4. 깊이 조정 : 게임 상태에 따라 검색 깊이를 조정 / 조정할 수도 있습니다. 또한 당신은 사용할 수 있습니다 반복 심화 깊이 우선 검색 알파-베타 가지 치기 알고리즘을 개선하는 것으로 알려진 알고리즘.

에서 자바 코드를 다운로드하는 것을 잊지 마십시오 깃허브 실험. 나는 당신 이이 게시물을 즐기시기 바랍니다! 그렇다면 Facebook과 Twitter에서 기사를 공유하십시오. 🙂