tic-tac-toe 게임에 어떤 알고리즘을 사용하여 AI에 대한 "최고의 움직임"을 결정할 수 있습니까?

tic-tac-toe 게임에 어떤 알고리즘을 사용하여 AI에 대한 "최고의 움직임"을 결정할 수 있습니까?

---

tic-tac-toe 구현에서 어려운 부분은 기계가 수행 할 최상의 동작을 결정하는 것입니다.

추구 할 수있는 알고리즘은 무엇입니까? 단순한 것에서 복잡한 것까지 구현을 찾고 있습니다. 문제의이 부분을 어떻게 해결해야합니까?

---

완벽한 게임을하기위한 Wikipedia의 전략 (매번이기거나 무승부)은 단순한 의사 코드처럼 보입니다.

Wikipedia의 인용문 (Tic Tac Toe # Strategy)

플레이어는 Newell과 Simon의 1972 년 tic-tac-toe에서 사용 된대로 매 턴마다 다음 목록에서 사용 가능한 첫 번째 이동을 선택하면 Tic-tac-toe (승리 또는 적어도 무승부) 게임을 할 수 있습니다. 프로그램. [6]

1. 승리 : 연속 2 개가있는 경우 3 개를 플레이하여 연속 3 개를 얻습니다.

2. 블록 : 상대방이 연속으로 두 개를 가지고 있다면 세 번째를 플레이하여 그들을 막습니다.

3. 포크 : 두 가지 방법으로 이길 수있는 기회를 만듭니다.

4. 상대방의 포크 차단 :

   옵션 1 : 포크를 만들거나 승리하지 않는 한, 상대가 방어하도록 강제하기 위해 두 개를 연속으로 만듭니다. 예를 들어 "X"에 코너가 있고 "O"에 중앙이 있고 "X"에도 반대 코너가있는 경우 "O"가 코너킥을해서는 안됩니다. (이 시나리오에서 코너를 플레이하면 "X"가 이길 수있는 포크가 생성됩니다.)

   옵션 2 : 상대가 포크 할 수있는 구성이있는 경우 해당 포크를 차단합니다.

5. 중앙 : 중앙을 연주합니다.

6. 반대 코너 : 상대가 코너에 있으면 반대 코너를 플레이합니다.

7. 빈 코너 : 빈 코너를 재생합니다.

8. 빈면 : 빈면을 재생합니다.

"포크"상황이 어떻게 보이는지 인식하는 것은 제안 된대로 무차별 대입 방식으로 수행 될 수 있습니다.

참고 : "완벽한"상대는 좋은 운동이지만 궁극적으로 상대 할 가치가 없습니다. 그러나 위의 우선 순위를 변경하여 상대 성격에 특징적인 약점을 부여 할 수 있습니다.

---

필요한 것은 (tic-tac-toe 또는 Chess와 같은 훨씬 더 어려운 게임) minimax 알고리즘 또는 약간 더 복잡한 변형 인 alpha-beta pruning 입니다. 하지만 일반적인 순진한 미니 맥스는 tic-tac-toe와 같은 작은 검색 공간을 가진 게임에 적합합니다.

요컨대, 당신이 원하는 것은 당신에게 가능한 최상의 결과를 가진 움직임을 찾는 것이 아니라 가능한 한 최악의 결과가 좋은 움직임을 찾는 것입니다. 상대가 최적으로 플레이하고 있다고 가정한다면, 그들이 당신에게 최악의 움직임을 취할 것이라고 가정해야합니다. 따라서 당신은 그들의 최대 이득을 최소화하는 움직임을 취해야합니다.

---

가능한 모든 보드를 생성하고 나중에 트리에서 더 아래로 생성하는 보드를 기반으로 점수를 매기는 무차별 대입 방법은 많은 메모리를 필요로하지 않습니다. 특히 90도 보드 회전이 중복된다는 것을 인식하면 수직에 대한 뒤집기처럼, 수평 및 대각선 축.

그 지점에 도달하면 결과를 설명하는 트리 그래프에 1k 미만의 데이터가 있으므로 컴퓨터에 가장 적합한 이동이 있습니다.

-아담

---

tic-tac-toe에 대한 일반적인 알고리즘은 다음과 같습니다.

Board : 보드를 나타내는 9 개 요소 벡터입니다. 2 (공백 표시), 3 (X 표시) 또는 5 (O 표시)를 저장합니다. Turn : 플레이 할 게임의 움직임을 나타내는 정수입니다. 첫 번째 이동은 1로, 마지막으로 9로 표시됩니다.

알고리즘

주요 알고리즘은 세 가지 기능을 사용합니다.

Make2 : 보드의 중앙 사각형이 비어 있으면 5를 반환합니다 board[5]=2. 그렇지 않으면이 함수는 모서리가 아닌 사각형을 반환합니다 (2, 4, 6 or 8).

Posswin(p): 플레이어 p가 다음 행마에서 이길 수 없으면 0을 반환합니다 . 그렇지 않으면이기는 이동을 구성하는 사각형의 번호를 반환합니다. 이 기능은 프로그램이 이기고 상대방의 승리를 막을 수 있도록합니다. 이 기능은 각 행, 열, 대각선을 확인하여 작동합니다. 전체 행 (또는 열 또는 대각선)에 대해 각 사각형의 값을 곱하면 승리 가능성을 확인할 수 있습니다. 제품이 18( 3 x 3 x 2)이면 X이길 수 있습니다. 제품이 50( 5 x 5 x 2)이면 O가 이길 수 있습니다. 이기는 행 (열 또는 대각선)이 발견되면 그 안에있는 빈 사각형을 확인할 수 있으며 해당 사각형의 수는이 함수에 의해 반환됩니다.

Go (n): n 제곱으로 이동합니다. 이 절차는 [n]턴이 홀수이면 보드 를 3으로, 턴이 짝수이면 5로 설정합니다. 또한 1 턴씩 증가합니다.

알고리즘에는 각 이동에 대한 기본 제공 전략이 있습니다. 플레이 X하면 홀수 이동을하고 O를 플레이하면 짝수 이동을합니다.

Turn = 1    Go(1)   (upper left corner).
Turn = 2    If Board[5] is blank, Go(5), else Go(1).
Turn = 3    If Board[9] is blank, Go(9), else Go(3).
Turn = 4    If Posswin(X) is not 0, then Go(Posswin(X)) i.e. [ block opponent’s win], else Go(Make2).
Turn = 5    if Posswin(X) is not 0 then Go(Posswin(X)) [i.e. win], else if Posswin(O) is not 0, then Go(Posswin(O)) [i.e. block win], else if Board[7] is blank, then Go(7), else Go(3). [to explore other possibility if there be any ].
Turn = 6    If Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else Go(Make2).
Turn = 7    If Posswin(X) is not 0 then Go(Posswin(X)), else if Posswin(X) is not 0, then Go(Posswin(O)) else go anywhere that is blank.
Turn = 8    if Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else go anywhere that is blank.
Turn = 9    Same as Turn=7.

나는 그것을 사용했습니다. 여러분의 기분을 알려주세요.

---

가능한 위치의 3x3 매트릭스 만 다루기 때문에 컴퓨팅 성능에 부담을주지 않고 모든 가능성을 통해 검색을 작성하는 것은 매우 쉽습니다. 각 열린 공간에 대해 해당 공간을 표시 한 후 가능한 모든 결과를 계산 한 다음 (재귀 적으로 말하고 싶습니다) 승리 가능성이 가장 높은 움직임을 사용하십시오.

이를 최적화하는 것은 실제로 노력 낭비입니다. 쉬운 것은 다음과 같습니다.

• 먼저 다른 팀의 승리 가능성을 확인하고, 찾은 첫 번째 팀을 차단하십시오 (어쨌든 게임이 2 개 이상인 경우).
• 열려있는 경우 항상 센터를 선택하십시오 (이전 규칙에는 후보자가 없음).
• (이전 규칙이 비어있는 경우)

---

AI가 학습 할 일부 샘플 게임에서 자체적으로 플레이하도록 할 수 있습니다. 지도 학습 알고리즘을 사용하여 도움을 받으세요.

---

플레이 필드를 사용하지 않는 시도.

1. 이기려면 (당신의 더블)
2. 그렇지 않다면 잃지 않기 위해 (상대는 이중)
3. 그렇지 않다면 이미 포크가 있습니까 (더블 더블이 있습니다)
4. 그렇지 않다면 상대가 포크를 가지고 있다면
   
   1. 차단 지점에서 가능한 더블 및 포크 검색 (궁극의 승리)
   2. 블로킹 포인트에서 포크를 검색하지 않는 경우 (상대에게 가장 많은 패배 가능성을 제공함)
   3. 블로킹 포인트가 아니라면 (잃지 않을 것)
5. 더블과 포크를 검색하지 않으면 (궁극의 승리)
6. 상대방에게 가장 많은 패배 가능성을주는 포크 만 검색하지 않는다면
7. 더블 만 검색하지 않으면
8. 막 다른 골목이 아니라면 넥타이, 무작위.
9. 그렇지 않은 경우 (첫 번째 이동을 의미)
   
   1. 게임의 첫 번째 움직임이라면;
      
      1. 상대에게 가장 많은 패배 가능성을줍니다 (알고리즘은 상대에게 7 점의 패배 가능성을주는 코너만을 만듭니다)
      2. 또는 지루함을 깨기 위해 무작위로.
   2. 게임의 두 번째 움직임이라면;
      
      1. 잃지 않는 포인트 만 찾기 (조금 더 많은 옵션을 제공합니다)
      2. 또는이 목록에서 가장 좋은 승률을 가진 점수를 찾으십시오 (모든 모서리 또는 인접한 모서리 또는 중앙 만 나오기 때문에 지루할 수 있음)

참고 : 더블과 포크가있을 때 더블이 상대에게 더블을 주 었는지 확인하고, 더블이 주면 새로운 필수 포인트가 포크 목록에 포함되어 있는지 확인하십시오.

---

숫자 점수로 각 사각형의 순위를 매 깁니다. 사각형이 선택되면 다음 선택 항목으로 이동합니다 (순위에 따라 내림차순으로 정렬 됨). 당신은 전략을 선택해야 할 것입니다 (첫 번째로가는 두 가지 주요 전략과 두 번째로 세 가지 (내 생각에)가 있습니다). 기술적으로는 모든 전략을 프로그래밍 한 다음 무작위로 하나를 선택할 수 있습니다. 그것은 덜 예측 가능한 상대를 만들 것입니다.

---

이 답변은 P1에 대한 완벽한 알고리즘을 구현하는 것을 이해하고 다른 사람보다 더 자주 실수를하는 일반 인간 플레이어를 상대로 조건에서 승리를 달성하는 방법에 대해 설명합니다.

물론 두 선수가 최적으로 플레이한다면 게임은 무승부로 끝나야합니다. 인간 수준에서 P1은 코너에서 뛰는 것이 훨씬 더 자주 승리합니다. 심리적 인 이유가 무엇이든 P2는 중앙에서 플레이하는 것이 그다지 중요하지 않다고 생각하게되는데, 이는 P1의 승리 게임을 만들지 않는 유일한 반응이기 때문에 그들에게는 불행한 일입니다.

P2 가 중앙에서 올바르게 막히면 P1은 반대쪽 코너에서 플레이해야합니다. 다시 말하지만 심리적 이유가 무엇이든 P2는 코너를 플레이하는 대칭을 선호하여 다시 패배 한 보드를 생성하기 때문입니다.

P1이 시작 이동을 위해 만들 수있는 이동에 대해 두 플레이어가 그 후 최적으로 플레이하면 P1에 대한 승리를 생성하는 이동 P2가 있습니다. 그런 의미에서 P1은 어디에서나 플레이 할 수 있습니다. 엣지 무브는이 무브에 대한 가능한 응답의 가장 큰 부분이 무승부를 생성한다는 점에서 가장 약하지만 P1에 대한 승리를 만들 응답이 여전히 있습니다.

경험적으로 (더 정확하게는 일화 적으로) 최고의 P1 시작 동작은 첫 번째 코너, 두 번째 중앙 및 마지막 가장자리 인 것처럼 보입니다.

직접 또는 GUI를 통해 추가 할 수있는 다음 과제는 보드를 표시하지 않는 것입니다. 인간은 모든 상태를 확실히 기억할 수 있지만 추가 된 도전은 기억하는 데 적은 노력이 드는 대칭 보드를 선호하게하여 첫 번째 분기에서 설명한 실수로 이어집니다.

나는 파티에서 많은 재미를 알고 있습니다.

---

최소 최대 알고리즘에 대한 Tic-tac-toe 적응

let gameBoard: [
    [null, null, null],
    [null, null, null],
    [null, null, null]
]

const SYMBOLS = {
    X:'X',
    O:'O'
}

const RESULT = {
    INCOMPLETE: "incomplete",
    PLAYER_X_WON: SYMBOLS.x,
    PLAYER_O_WON: SYMBOLS.o,
    tie: "tie"
}

결과를 확인할 수있는 함수가 필요합니다. 이 함수는 연속 된 문자를 확인합니다. 보드의 상태가 무엇이든 결과는 네 가지 옵션 중 하나입니다 : 불완전, 플레이어 X 승리, 플레이어 O 승리 또는 무승부.

function checkSuccession (line){
    if (line === SYMBOLS.X.repeat(3)) return SYMBOLS.X
    if (line === SYMBOLS.O.repeat(3)) return SYMBOLS.O
    return false 
}

function getResult(board){

    let result = RESULT.incomplete
    if (moveCount(board)<5){
        return result
    }

    let lines

    //first we check row, then column, then diagonal
    for (var i = 0 ; i<3 ; i++){
        lines.push(board[i].join(''))
    }

    for (var j=0 ; j<3; j++){
        const column = [board[0][j],board[1][j],board[2][j]]
        lines.push(column.join(''))
    }

    const diag1 = [board[0][0],board[1][1],board[2][2]]
    lines.push(diag1.join(''))
    const diag2 = [board[0][2],board[1][1],board[2][0]]
    lines.push(diag2.join(''))
    
    for (i=0 ; i<lines.length ; i++){
        const succession = checkSuccesion(lines[i])
        if(succession){
            return succession
        }
    }

    //Check for tie
    if (moveCount(board)==9){
        return RESULT.tie
    }

    return result
}

Our getBestMove function will receive the state of the board, and the symbol of the player for which we want to determine the best possible move. Our function will check all possible moves with the getResult function. If it is a win it will give it a score of 1. if it's a loose it will get a score of -1, a tie will get a score of 0. If it is undetermined we will call the getBestMove function with the new state of the board and the opposite symbol. Since the next move is of the oponent, his victory is the lose of the current player, and the score will be negated. At the end possible move receives a score of either 1,0 or -1, we can sort the moves, and return the move with the highest score.

const copyBoard = (board) => board.map( 
    row => row.map( square => square  ) 
)

function getAvailableMoves (board) {
  let availableMoves = []
  for (let row = 0 ; row<3 ; row++){
    for (let column = 0 ; column<3 ; column++){
      if (board[row][column]===null){
        availableMoves.push({row, column})
      }
    }
  }
  return availableMoves
}

function applyMove(board,move, symbol) {
  board[move.row][move.column]= symbol
  return board
}
 
function getBestMove (board, symbol){

    let availableMoves = getAvailableMoves(board)

    let availableMovesAndScores = []

    for (var i=0 ; i<availableMoves.length ; i++){
      let move = availableMoves[i]
      let newBoard = copyBoard(board)
      newBoard = applyMove(newBoard,move, symbol)
      result = getResult(newBoard,symbol).result
      let score
      if (result == RESULT.tie) {score = 0}
      else if (result == symbol) {
        score = 1
      }
      else {
        let otherSymbol = (symbol==SYMBOLS.x)? SYMBOLS.o : SYMBOLS.x
        nextMove = getBestMove(newBoard, otherSymbol)
        score = - (nextMove.score)
      }
      if(score === 1)  // Performance optimization
        return {move, score}
      availableMovesAndScores.push({move, score})
    }

    availableMovesAndScores.sort((moveA, moveB )=>{
        return moveB.score - moveA.score
      })
    return availableMovesAndScores[0]
  }

Algorithm in action, Github, Explaining the process in more details

참고URL : https://stackoverflow.com/questions/125557/what-algorithm-for-a-tic-tac-toe-game-can-i-use-to-determine-the-best-move-for