TicTacToe AI가 잘못된 결정을 내림

Question

약간의 배경지식:C++에서 다중 노드 트리를 학습하는 방법으로 가능한 모든 TicTacToe 보드를 생성하여 노드에서 시작하는 분기가 해당 노드에서 따를 수 있는 모든 보드가 되고 노드의 하위 보드가 보드가 되도록 트리에 저장하기로 결정했습니다. 한 번의 움직임으로 이어지는 것입니다.그 후, 그 트리를 의사결정 트리로 사용하여 TicTacToe를 플레이하는 AI를 작성하면 재미있겠다는 생각이 들었습니다.

TTT는 완벽한 플레이어가 절대 지지 않는 해결 가능한 문제이기 때문에 AI를 처음 시도하는 저로서는 코딩하기 쉬운 AI인 것 같았습니다.

이제 AI를 처음 구현했을 때 생성 시 각 노드에 두 개의 필드를 추가했습니다.해당 노드 아래의 모든 자식에서 X가 승리할 횟수와 O가 승리할 횟수입니다.나는 가장 좋은 해결책은 단순히 각 움직임에 대해 내 AI가 가장 많은 승리를 거둔 하위 트리를 선택하고 내려가도록 하는 것이라고 생각했습니다.그런 다음 나는 그것이 대부분의 경우 완벽하게 재생되지만 그것을 이길 수 있는 방법을 찾았다는 것을 발견했습니다.내 코드에 문제가 있는 것이 아니라 AI가 경로를 선택하는 방식에 문제가 있는 것뿐입니다.

그런 다음 컴퓨터의 최대 승리 또는 인간의 최대 손실 중 더 많은 트리를 선택하도록 결정했습니다.이로 인해 성능이 향상되었지만 여전히 완벽하지는 않습니다.나는 아직도 그것을 이길 수 있었다.

그래서 저는 두 가지 아이디어를 가지고 있으며 어느 것이 더 나은지에 대한 의견을 기대하고 있습니다.

1) 승패를 최대화하는 대신 승리에 1, 무승부에 0, 패배에 -1의 값을 할당할 수 있습니다.그런 다음 가장 높은 값을 가진 트리를 선택하는 것이 최선의 이동이 될 것입니다. 왜냐하면 다음 노드는 손실을 초래하는 이동이 될 수 없기 때문입니다.보드 생성 시 변경이 쉽지만 검색 공간과 메모리 사용량은 동일하게 유지됩니다.또는...

2) 보드 생성 중에 다음 수에서 X 또는 O 중 하나가 승리할 보드가 있는 경우 해당 승리를 방해하는 자식만 생성됩니다.다른 하위 노드는 고려되지 않으며 그 이후에는 정상적으로 생성이 진행됩니다.트리 크기가 줄어들지만 한 번의 승리가 있는지 확인하는 알고리즘을 구현해야 하며 이는 선형 시간에서만 수행될 수 있다고 생각합니다(보드 생성이 훨씬 느려지나요?).

어느 것이 더 낫습니까, 아니면 더 나은 해결책이 있습니까?

Answer 1

의사 결정 트리를 기반으로 AI를 구현하는 올바른 방법은 사용하는 것입니다.미니 맥스"알고리즘 :

1. 각 잎 노드 할당 A 점수를 지정합니다 (+1 = 플레이어 승리, -1 = 플레이어 손실, 0 = 타이)

2. 각 노드에 다음 규칙을 적용하여 트리 위로 올라가십시오.

   • 심지어 깊이 (플레이어가 움직일 때), 점수가 가장 높은 아이를 선택하고 그 점수를 노드에 복사하십시오.
   • 홀수 깊이의 경우 (컴퓨터가 움직일 때) 점수가 가장 낮은 아이를 선택하고 그 점수를 노드에 복사하십시오.

물론, 당신이 결정한 사람에 따라 먼저 가고 이상하고 홀수를 취해야 할 수도 있습니다.

다음에서 더 읽을 수 있습니다.

• http://ai-depot.com/articles/minimax-emplained/
• http://en.wikipedia.org/wiki/minimax

Answer 2

한 가지를 잊어 버린 것을 제외하고는 기존 알고리즘이 좋습니다. 다른 플레이어의 움직임으로 인해 적어도 묶을 수없는 경로를 선택하지 마십시오.

따라서 기본적으로 플레이어가 다음 움직임이 필요하지 않은 상황을 버린 다음 기존 알고리즘을 실행할 수있는 지점을 폐기하십시오. 이로 인해 패배 가능성을 제거하면서 피할 수없는 상대와의 경기에서 승리 할 가능성이 가장 높습니다.

Answer 3

Tic-Tac-Toe는 다음을 사용하여 풀 수 있습니다. 그리디 알고리즘 실제로 의사 결정 트리가 필요하지 않습니다.

현재 알고리즘을 계속 사용하려면 patros가 제안하는 대로 수행하고 각 결정에서 손실 가능성을 최소화하십시오.

더 간단한 접근 방식을 원한다면 AI가 매 턴마다 다음을 수행하도록 하십시오.

1. 가능하다면 승리하는 Tic-Tac-Toe를 완료하세요.
2. 가능하다면 반대측 Tic-Tac-Toe를 차단하세요.

3. 각 사각형의 바람직함을 평가하고, AI가 한 선에서 정사각형을 취한 서로에 대해 해당 사각형에 대한 만족도 1점을 추가합니다.상대방이 차지한 각 사각형에 대해 바람직도 1점을 제거합니다.

   예를 들어, 보드가 현재 다음과 같은 경우:

   _|O|X
   _|X|_
   O| |
   

   왼쪽 위 모서리의 바람직성은 0입니다(같은 행의 X에 대해서는 1, 대각선에 있는 X에 대해서는 1, 각 Os에 대해서는 -1).

4. 가장 바람직한 광장에서 플레이하세요.임의로 관계를 끊습니다.

   위의 예에서 AI는 바람직도가 2이고 다음 턴에 승리할 수 있는 오른쪽 중앙 사각형을 선택합니다.

5. 게임이 막 시작했다면 중앙 광장을 플레이하고, 중앙 광장을 차지했다면 무작위로 코너를 선택하세요.

6. 승리(또는 무승부).

이것은 내 10학년 Visual Basic 학기 프로젝트였습니다.결정 트리를 저장하는 것보다 이기는 것이 불가능하고 훨씬 적은 메모리가 필요합니다.

Answer 4

이 작업을 수행하는 "순진한"방법 (두 선수가 교대로 이동하는 임의의 게임의 경우)은 한 사람이 승자 인 보드로 끝날 때까지 가능한 각 가능한 움직임을 재귀 적으로 시도한 다음 나무에서 위로 뒤로 트랙하는 것입니다. 노드를 "O wins", "x wins"또는 "draw"로 표시합니다.

당신이 올라갈 때마다 (그러한 단계 중 하나는 일반적으로 플라이라고 함), 누가 움직이는 지에 따라 플레이어가 자신에게 가장 적합한 움직임을 선택한다고 가정합니다. 잎에서 위쪽으로 움직이고 있기 때문에 항상 각 어린이 노드에 대한 최적의 결과를 알 수 있습니다.

계산할 때 숫자 하위 트리에서 승리 또는 손실 보드의 가능성에 대해, 당신은 본질적으로 각 플레이어가 항상 무작위로 움직일 것이라고 가정합니다. 당신이 언급했듯이, 당신이 스마트 플레이어와 경기를하면 이것은 그다지 효과적이지 않을 것입니다. 위에서 설명한 계획은 대신 상대방이 항상 완벽한 움직임을 보이고이기려고한다고 가정합니다.