개별 프로젝트로 Java에서 Gomoku (연속 5 개) 게임을 코딩하려고합니다. AI의 경우 Alpha-Beta Pruning과 Minimax 함수를 함께 사용하는 것이 좋은 방법이라는 것을 알고 있습니다. 그러나, 나는 이것이 어떻게 효과가 있을지 상상하는 데 약간의 어려움을 겪고 있습니다.고모 쿠 (Gomoku)에서 좋은 Minimax 표현이 가능한가요?
내 질문은 다음과 같습니다. 미니 맥스 트리의 노드를 나타내는 것은 무엇입니까?
내 평가 기능이 보드의 모든 빈 공간에 "무게를 가할"것이라고 생각합니다. 그런 다음이 보드에서 minmax 결정 트리의 노드로 최상의 가치를 취합니다. 나는 올바른 방향으로 나아가고 있는가?
그리고 다른 도움말도 환영합니다! 미리 감사드립니다.
상태 공간 검색은 보드의 여러 상태를 통해 이루어집니다. 비어있는 곳에 돌을 놓을 수 있기 때문에 많은 움직임이 있습니다. 각 상태는 예를 들어, 흰색, 검은 색 또는 비어있는 3 가지 값이있는 9x9 매트릭스. 따라서 9x9 보드의 경우 3^81 개의 보드 상태가 가능합니다.
보드 상태에서 이동 수는 비어있는 정점 수입니다. 이 꼭지점 중 하나에 돌을 배치 할 수 있습니다. 자신 만의 색을 재생할 수 있습니다. 따라서, 최대 81 회의 이동이 가능합니다. 첫 번째 이동의 경우 81, 두 번째 이동의 경우 80 등이 있습니다. 따라서 깊이 5로 합리적으로 검색 할 수 있습니다.
올바른 표현은 위에서 언급 한 것처럼 2D 매트릭스입니다.이 값은 int 값의 2D 배열 일 수 있습니다. 비어있는 경우 0, 흰색 일 경우 1, 검정이면 2. ... int [9,9].
평가 기능이 좋지 않습니다. 대신, 나는 다음과 같은 점을 줄 것입니다 :
- 행이 5 개를 얻습니다. 기본적으로이 점에 대해 최대 점수를 부여합니다. 이기기 때문에 - 2 개가 열린 행에 4 개가 있습니다. 또한 최대 점수는 상대방이 당신을 막을 수 없기 때문입니다. - 1 개의 오픈 엔드가있는 연속 4 명 - 여전히 위협적인 위치입니다. 상대방은 을 차단해야합니다. - 2 개의 열린 끝이있는 연속 3 개 - 매우 높은 점수 --- 닫힌 끝이 모두 0 인 4, 3, 2, 1 - 행을 5 개 만들 수 없으므로 0입니다.
등등.
표준 미니 맥스 알고리즘 즉 알파 베타 프 루닝을 적용하면 체스와 완전히 동일하지만 상태 공간 생성기와 평가 기능이 다릅니다.
다음과 같은 형태의 평가 함수를 고려해보십시오. 예를 들어 한 줄에 6 개의 위치를 고려하십시오. (19x19 보드에는 각 라인을 따라 14 개가 있고 각각의 대각선을 따라 0에서 14까지 다양한 수를 가지고 있는데 전체 보드에서이 중 742 개가된다고 생각합니다.) 산수가 틀릴 수도 있습니다. 각 세트에 대해 729 개의 가능한 배열이 있습니다 검은 색, 흰색 및 빈 공간. 또는 종단 간 대칭을 고려하면 378 개입니다. 아니면, 음, 음, 그보다 적지 만, 흑인/백인 대칭을 고려해 보면 얼마나 적을 지 알아 내려고합니다.
이제 평가 함수는 378 개 또는 여러 개의 요소가있는 테이블 (또는 두 개는 수평 및 수직 선, 하나는 하나)에 6 개의 돌 블록마다 테이블 조회로 구성됩니다. 대각선의 경우). 결과를 추가하면 위치에 대한 평가가됩니다.
실제로 더 큰 테이블 (더 긴 위치 행에서 파생 됨)이 더 효과적 일 수 있습니다.
하지만 테이블에 무엇이 들어 있습니까? 귀하의 프로그램이 그것을 작동하게하십시오. 표에서 임의의 값으로 시작하십시오 (예 : eval (line) = #black (line) - # white (line) 등). 알파 베타 검색을 사용하여 프로그램 자체를 재생하십시오. 이제 어떤 일이 일어나는지에 따라 테이블 항목을 업데이트하십시오. 이 작업에는 여러 가지 방법이 있습니다. 여기에 (스케치로 설명 된) 소수가 있습니다.
은 (체스에 적용하지만, 같은 아이디어는 고모 쿠에 잘 작동 것), http://cs.anu.edu.au/~Lex.Weaver/pub_sem/publications/knightcap.pdf를보십시오.
이러한 평가 기능 중 일부는 검색 조정으로 더 잘 구현 될 수 있습니다. 어쨌든 모든 위치에서 "열린 끝이 하나 인 행 4"를 찾고 있다면 다음과 같이 말할 수 있습니다. 이러한 위치를 볼 때마다 그 열린 끝에서 이동하고 검색 깊이를 늘릴 수도 있습니다 (컴퓨터 체스에서 비슷한 기술이 사용됩니다.) –
검색해야하는 상태 수는 9^(n + 1)이 아니라 81^n입니다. 반면에 이동 순서가 양호한 경우 알파 베타는 결국 대략 9^n까지 대략 제곱근이됩니다. –
정말 도움이됩니다. 고마워요. 9x9 참조 프레임은보다 효율적인 의사 결정 트리를 허용합니다. 그리고 위의 의견에, 나는 그것이^^ 81이 아닌 3^81 개의 보드 스테이트라고 생각합니다. 81 개의 독립적 인 셀, 3 개의 가능한 상태를 가진 각각 – jyt