매우 큰 Tic-Tac-Toe 게임을 해결하기 위해 어떤 알고리즘을 사용 하시겠습니까?
https://stackoverflow.com/questions/1545158
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
작은 (3x3, 4x4) tic-tac-toe는 모든 경우를 고려하여 쉽게 해결할 수 있습니다. 그러나 예를 들어, 30x30 tic-tac-toe가 있습니다. 이 경우 다음으로 가장 좋은 움직임을 결정하기 위해 어떤 알고리즘을 사용 하시겠습니까?
미니 맥스 + 알파 베타 가지 치기 내가 아는 한 가지 방법입니다.
더 효율적이거나 효율적이지만 더 시원한 다른 방법이 있습니까?
나는 그것이 매우 흥미로운 게임이 아니라는 것을 알고 있습니다. 30x30은 완벽한 솔루션을 위해 고려해야 할 케이스 수가 매우 높아서 실현 가능하지 않은 이러한 종류의 게임에서 가장 잘 작동하는 알고리즘이 가장 잘 작동하는 IE를 묻기 위해 30x30이라고 말했습니다.
해결책
나는 이것이 아마도 매우 유익한 문제라고 생각하지 않습니다. 이유 :
당신이이기는 데 필요한 줄의 마크 수가 높으면, 게임은 어떤 수준의 적절한 수준에서 얻을 수 있습니다. 왜냐하면 자신의 승리를 막는 것보다 가능한 승리를 막는 것이 훨씬 쉽기 때문입니다. 예를 들어, 30x30 보드에서 승리하기 위해 20 인칭이 필요한 경우, 승리를 방지 해야하는 모든 것은 각 행의 자국과 보드 중간 근처에있는 열에 표시되며 각각의 중간 근처에 표시됩니다. 긴 대각선.
이기고 있어야하는 줄의 마크 수가 낮 으면, 보드의 여분의 공간이 전략에 크게 차이가 없다고 생각하며, 두 번째 플레이어가 방어하는 유일한 현명한 전략은 상대 근처에서 놀고 있습니다. 결과적으로 어떤 종류의 알파 베타 방법은 괜찮습니다.
다른 팁
GO의 게임을 위해 컴퓨터가 어렵습니다 30x30 tic-tac-toe에 대해 당신을 괴롭히는 것과 같은 이유로 (30x30 tic-tac-toe가 이동만큼 어렵고 더 직접적인 기술이 적용되지 않는다는 말은 아닙니다), 몬테 카를로 트리 검색 최근에 좋은 결과를 얻었습니다.
보세요 고모쿠 또는 연속 5 명. 웹에는 여러 가지 일반적인 전략이 있습니다. Wikipedia 기사에는 Gomoku와의 위협 기반 검색에 대한 좋은 논문이 있습니다.
마지막 움직임의 인접한 공간을 검색하고 인접한 상대편이있는 빈 공간에 블록을 내려 놓으려고하는 탐욕스러운 알고리즘을 사용하는 것이 좋지 않습니까? 플레이어가 이길 수없는 한, 당신은 승리합니다.
알파 베타는 당신이 사용할 수있는 가장 좋은 것입니다. 알파 베타의 중요성은 평가 기능에 있습니다. 1/0/-1 (승리/아무것도 잃어버린) (한 플레이어 관점에서) 만 반환하지는 않지만 자격이 있습니다.
이 기사를 확인하십시오 (그는 tic-tac-toe를 사용하지만 대부분 체스를 예제 게임으로 사용합니다)http://www.fierz.ch/strategy1.htm
3 열 3 열에 첫 번째 토큰을 놓습니다. 상대방이 3 행에 토큰을 놓는 경우, 다음 토큰을 행 2, 열 3, 그렇지 않으면 3 열, 열 2에 놓습니다. 다음을 파악할 수 있어야합니다 (승리 ) 이동하다.
상대가 시작되면 빈 4x4 블록을 선택하고 위의 설명과 같이 중간에서 시작하십시오. 상대방이 당신 앞에 트리플을 완료하면 잃어 버립니다.
나는 이것이 4x4 보드 이상의 최적의 전략이라고 감히 말할 것입니다.
