알파 - 베타 가지 치기가있는 양자 택틱 발가락 - 상태를 가장 잘 나타냅니다.

Question

AI 클래스의 경우 알파 베타 제거 기능을 사용하여 quantum tic-tac-toe 게임을 만들어야합니다.

보드의 상태를 표현하는 가장 좋은 방법을 생각하고 있습니다. 첫 번째 직관은 일종의 이웃 행렬, 즉 9x9 행렬을 사용하는 것이며, M[i,j]은 이동을 나타내는 정수입니다. (tic-tac-toe) 사각형 i 및 j이 표시됩니다 (이러한 연결이없는 경우 - M[i,j]이 0 임). M[i,i]은 사각형 i이 접 히면 0이 아닙니다. 그런 다음, 그런 매트릭스의 게임 트리를 만들고 alpha-beta pruning과 함께 고전적인 미니 맥을 사용합니다.

그러나이 방법은 비용이 많이들 것입니다. 비교적 큰 분기 요소와 모든 노드에 대한 기본적인 작업이있을 것입니다. 사이클을 확인하고 9x9 매트릭스의 모든 동등한 상태를 찾는 것이 좋습니다.

나는 더 똑똑한 해결책이 있어야한다는 느낌이 들었습니다. 양자 게임을 고전적인 tic-tac-toe 게임 세트로보고 일반화 된 minimax 검색을 사용하는 것처럼 어쩌면 선상에서 뭔가를 느낄 수 있습니다. 모든 것은 고전적인 tic-tac-toe 문제의 (작은) 세트로 회귀 하는가? 정확히 어떻게 작동하는지 나는 볼 수 없다.

이 문제 (또는 이와 유사한 문제)에 경험이있는 사람이 누구이며 올바른 방향으로 나를 가리킬 수 있습니까?

Answer 1

문제는 단지 틱택 토 인 경우, 당신은 당신의 보드에게 길을 대표 할 수있는 것보다 내이 프로그램은 http://pastie.org/1715115

그것은 원계 기반의 숫자 행렬 않습니다. 보드는 9 자리 숫자이며 각 숫자는 3 개의 가능한 값 중 하나를가집니다. 0은 공백, 1은 x, 0은 2입니다.

이 접근 방식은 보드가 단일 정수로 설정 될 수 있기 때문에 미니 맥스에 탁월합니다! 숫자들의 각 쌍은 (a)의 현재 위치에 대응하고, (b) 다음의 더 좋은 위치가 미리 계산하여 최소 최대 여기서

int suc[TOTAL][2]={ { 0, 10000}, { 1, 20001}, { 10, 20010}, { 12, 1012}, { 21, 1021}, 
    { 100, 20100}, { 102, 100102}, ... 

다음 행렬의 형태를 갖는다. 따라서 보드가 비어 있다면 (suc [0] [0] == 0) 다음으로 더 좋은 위치는 'x'를 위치 5에 놓는 것, 즉 중심 (suc [0] [1] == 000010000)

실제로이 프로그램을 사용하면이 프로그램이 이미 임시 매트릭스에서 가능한 모든 대답을 계산 했으므로 미니 맥스를 만들 필요가 없습니다.

/* find and return the next board after the given board terno */ 
int move(int terno) 
{ 
    int i; 

    for (i=0; i<TOTAL; i++) 
     if (suc[i][0]==terno) 
      return suc[i][1]; 
    return 0; 
} 

그것은 양자 알고리즘 (임베디드 시스템)를위한 좋은 방법입니다 : 다음 이동을 선택하는 가장 중요한 기능은, 행렬 SUC (후계자)에보고 간단하게 이루어집니다. 나는 이것이 당신을 돕기를 바랍니다.

는 4520` TOTAL