트위스트

Question

나는를 사용하여 ticTacToe 프로그램하지만 아닌 전통를 사용하여 ticTacToe 모든 보드의

먼저 4 × 4가 승리하는 방법을 쓰고 있어요에 상대의 가지 3과 1을 얻는 것입니다 행, 열 또는 대각선. 내가 패배 할 수 없다 "하드"모드 프로그램을 제공하기 위해 최소 최대 알고리즘을 구현하기 위해 노력하고있어

O|_|X|_ 
O|X|_|_ 
O| |_|_ 
X|_|_|_ 

: 그래서 다음은 첫 번째 열을 통해 "O"에 대한 승리가 될 것입니다.

내 문제는 모든 가능한 게임 상태를 가진 트리를 만들 수 없기 때문에 내가 생성 할 수있는 게임 상태를 평가하는 일종의 기능을 생각해 내야한다는 것입니다.

제 질문은 어떻게 그런 기능을 생각해 낼 수 있을까요?

Answer 1

이 게임은 무차별 적으로 충분히 작습니다.

모든 상태를 열거 할 수 있습니다. 각 사각형에는 3 개의 가능한 값 (X, O 또는 비어 있음)이있는 16 개의 사각형이 있습니다.

3^16 = 43046721, 약 4300 만.

이것은 각 상태의 winnability를 설명하는 1 바이트가있는 테이블이 43 메가 바이트 밖에되지 않는다는 것을 의미합니다.

저는 각 상태를 1에서 4300 만 사이의 색인으로 매핑하는 기능을 만들었습니다 (가능한 상태의 주문 만 가능함). 기본적으로 3을 기준으로 숫자로 나타내며 인덱스에서 상태를 만들 수 있습니다.

각 상태가 취할 수있는 4 개의 winnability 값 - O는 Winnable, X는 Winnable, Winnable은 아니며 unknown을 선택할 수 있습니다.

각 게임 상태의 승패를 저장하기 위해 길이 43046721의 버퍼를 할당하십시오.

모든 인덱스 번호를 반복하여 원 상태를 표시합니다. 그런 다음 모든 국가의 승률을 반복적으로 기입하십시오 (모든 승계 국가를 확인하십시오. 누가 승자인지에 따라 결정됩니다). 이것은 인덱스 집합에 대해 최대 16 번의 반복을 필요로하기 때문에 무차별 대입이 여기에서 작동하지 않는다는 어떤 이유도 보이지 않습니다.

n 개의 조각이있는 모든 상태가 n + 1 개의 조각이있는 상태로 이어지는 등의 이점을 활용하여 대칭을 활용하는 것과 같은 최적화가 있지만 처음에는 필요하지 않다고 생각합니다.

Answer 2

게임용 휴리스틱 기능은 주어진 게임 상태를 평가하는 기능입니다. 여기에서 - 주정부는 기본적으로 두 부분으로 구성됩니다. (1) 보드 자체. (2) 누구의 차례인가.

유발할 수 휴리스틱 함수 :

대각선/컬럼 (평가 된 플레이어에 따라 또는 O의) X의의
1. 최대/
한 누락 이적로만 제한 "거의 경력"의
2. 번호 () -이기는 가능성의 수를 극대화하기 위해 정서적 일 수 있습니다.

나는 더 많은 추론을 생각할 수 있다고 가정합니다.다음과 같이
당신은 하나의 "큰"휴리스틱 기능으로 다른 추론을 결합 할 수 있습니다 :

a_1 * h_1(state) + a_2 * h_2(state) + ... + a_n * h_n(state) 

까다로운 부분이 A_1, ..., a_n에 대한 점수를 배울 수있을 것입니다 -이 다양한 방법으로 수행 할 수 있습니다 - 그 중 하나는 monte carlo learning입니다. 기본적으로 : 다양한 a_1,..,a_n 값을 가진 다양한 에이전트를 만들고, 토너먼트가 실행되고, 토너먼트가 끝나면 - 승자에 따라 가중치를 조정하고, 아직 시간이있을 때 프로세스를 반복하십시오 (그것은 anytime algorithm입니다).
작업이 끝나면 최종 상담원을 위해 학습 된 가중치를 사용하십시오.

P. 가능한 게임 수는 ~ 16입니다! (선택한 사각형의 순서를 결정할 필요가 있습니다. 게임의 나머지 부분이 어떻게 끝날지 선택합니다.) 제약 조건 내에서 개발할 수있을 정도로 작을 지 물어보십시오. 그렇지 않으면 너무 많은 것이므로 경험적 솔루션이 실제로 필요합니다. .