가능한 중복 :
What Algorithm for a Tic-Tac-Toe Game Can I Use To Determine the “Best Move” for the AI?tic tac toe 게임을 구현하는 알고리즘은 무엇입니까?
는 이미 서로에 대한 재생 2 플레이어 즉 위해 박하 사탕 정면 게임을 만들었습니다. 이제는 같은 게임을 구현할 계획이지만 컴퓨터를 상대로 게임을 할 계획입니다. 그래서 누구든지 좋은 알고리즘이나 아이디어를 구현할 것을 제안 할 수 있습니까?
게임이 매우 간단하므로 검색 트리를 만들 수 있습니다. 이것은 "당신의 이동"과 "적의 이동"사이의 대안 인 나무입니다. 적들은 항상 그들에게 가장 좋은 것을 골라 내고 있으며, 당신은 항상 당신에게 가장 좋은 것을 골라냅니다. 최적의 플레이가 각각 승/패/타이가 될 경우 각 보드 위치에 대해 "WINS"/ "LOSE"/ "TIE"로 평가하십시오. 깊이 우선 검색 (또는 모든 검색)을 수행하고 분기를 선택하십시오. 이것은 기본적으로 grandmasters를 이길 수있는 복잡한 체스 프로그램이 (비록 그들이 고도로 최적화되고 우수한 하드웨어에서 병렬로 실행되고 있지만) 작동하는 방법입니다. 이를 minimax algorithm이라고합니다.
또는 최적의 모든 동작을 (보드를 회전하고 뒤집어서 알려진 동작과 비교하는 루틴을 사용하여) 직접 코딩 할 수 있습니다. 단지 500-ish 가능성이 있습니다.
그러나 tic-tac-toe는 해결 된 게임이기 때문에 상당히 지루합니다. 컴퓨터가 최적으로 작동하면 컴퓨터가 항상 연결됩니다. tic-tac-toe는 5 세 아동에게만 도전적이기 때문에 게임의 대상을 고려해야합니다. 컴퓨터가 무작위로 무작위 이동하도록하는 것이 합리적 일 수 있습니다. 그러면 인간 플레이어는 적어도 기회가 있습니다.
ninjagecko가 이미 제안한 것처럼 검색 트리는 코드 작성에 직접적이고 최적 일 것입니다.
그러나 검색 트리를 만드는 것이 모든 최적의 동작을 손으로 코딩하는 것보다 재미 있기 때문에 기계 학습 접근 방식을 시도하는 것이 훨씬 더 재미있을 것이라고 생각합니다.
예를 들어 reinforcement learning을 사용하는 프로그램을 만드는 것이 좋습니다.
중요한 점은 알고리즘이 "if game == global thermonuclear war : exit"어딘가에 있다는 것입니다 –
위키피디아에 최적의 전략이 있습니다 ... – UmNyobe