TTT를위한 minimax 알고리즘을 구현했습니다. 인공 지능 플레이어가 첫 번째 이동을하게되면 가능한 이동의 모든 미니 맥스 값을 0으로 평가합니다. 즉, 첫 번째 이동으로 그리드의 모든 사각형을 선택할 수 있습니다. 그러나 어떤 Tic Tac Toe 가이드는 첫 번째 이동을 할 때 코너 또는 센터 스퀘어를 선택하는 것이 더 높은 선택의 기회이기 때문에 더 나은 선택이라고 말합니다.Minimax 및 tic tac toe - 내 알고리즘이 맞습니까?
왜 알고리즘에이를 반영하지 않는 이유가 무엇입니까?
편집 : 명확히하기 위해 내가 물어 보려는 것은 미니 맥 알고리즘의 한계입니까, 아니면 구현이 잘못 되었습니까?
알고리즘이이를 반영 할 필요는 없습니다. 모든 시작 위치를 시도해 보면 모퉁이와 센터가 다른 셀보다 더 많은 경로를 얻을 수 있습니다.
tic-tac-toe의 복잡성이 없기 때문에 미니 맥스는 게임이 끝날 때까지 맨 처음 이동하여 볼 수 있습니다. 게임을 진행하면서 사용 가능한 이동 수가 빠르게 줄어들므로 전체 검색이 매우 빠르게 완료됩니다.
더 복잡한 게임 (오셀로, 체커, 체스)에서는 소위 "오프닝 서적"이 더욱 중요 해지고 있습니다. 게임 시작시 사용할 수있는 이동 횟수는 엄청납니다. 따라서 전통적인 접근 방법은 첫 번째 3 회에서 6 회의 플레이를 위해 미리 계산 된 "책 이동"을 유지하면서 오프닝의 "책"에서 이동을 선택하는 것입니다. 책 밖에서의 이동은 고려되지 않으므로 본질적으로 동일하게 남아있는 이동에 많은 CPU를 절약 할 수 있습니다.
'모든 출발 위치를 시험해 보면 코너와 센터가 다른 셀보다 더 많은 승리의 길을 찾을 수 있습니다. 미니 맥스가 이것을 알아 내려 했습니까? 아니면이기는 경로의 수를 고려하지 않아도됩니까? – Lanaru
minimax 알고리즘은 완벽한 플레이어 (항상 최선의 이동을 선택하는 플레이어)에 대해 최상의 이동을 찾기 위해 설계되었습니다. 그러한 선수에 대해서, 어떤 출발 위치가 선택 되더라도 무승부로 게임이 끝나기 때문에 시작 위치는 다른 것보다 좋거나 나쁘지 않습니다. –
@Lanaru 미니 맥스가 처음부터 끝까지 게임을 할 수 있고 우승 전략이 없다면, 모든 움직임이 똑같아 보입니다. 승리 또는 패하는 위치는 없습니다. 미니 맥스가 게임을 중간 정도의 위치에서만 플레이하고 휴리스틱을 사용하여 평가하도록 강요한다면, 일부 시작은 다른 위치보다 더 잘 판단 될 것입니다. – dasblinkenlight
구현을 보지 못해서 말하기가 어렵지만 제대로 작동하지 않는 것 같습니다. – DPM
나는 편집에서 나의 질문을 명확히했다. – Lanaru
minimax의 요점은 단기 점수를 기반으로 할 수없는 솔루션을 제거하기 위해 솔루션 트리를 정리할 수 있다는 것입니다. 단지 20,000 건의 가능성 (3^9)과 9,000 건의 유효한 게임 상태가있을 때 _Zero_ 가지 치기가 필요합니다. 미니 맥스를 배우기 위해 TTT를 사용하고 있다면 괜찮습니다. 이상적인 유스 케이스는 아닙니다. – paxdiablo