극대 극소 알고리즘 기반 Tic-Tac-Toe

본고에서 나는 minimax 알고리즘을 사용하는tic-tac-toe 구해기의 실현을 보여주고 싶다.이것은 상태가 상대적으로 적은 간단한 게임이기 때문에tic-tac-toe는 편리한 기계 학습과 인공지능 실험의 사례 연구가 될 것이라고 생각합니다.여기서 나는 미니맥스라는 간단한 알고리즘을 실현했다.
극대 극소 배후의 기본 사상은 우리가 상대방이 가능한 한 가장 좋은 동작을 할 것이라고 가정할 때, 우리는 어떻게 공을 치는지 알고 싶다는 것이다.예를 들어, X 차례가 되면 X가 특정 이동을 수행합니다.이 행동의 가치는 무엇입니까?가령 O는 두 가지 방식 중 하나로 반응할 수 있다. 첫 번째 상황에서 O는 다음 단계에서 승리한다.O의 또 다른 동작은 X가 다음 동작에서 승리하게 한다.O가 이길 수 있기 때문에, 우리는 X의 최초의 행동이 잘못된 것이라고 생각한다. 그것은 실패를 초래했다.우리는 만약 O가 잘못을 저질렀다면 X가 이길 수 있다는 사실을 소홀히 했다.우리는 값이 1이면 X가 이기고, 1이면 O가 이기고, 0이면 무승부라고 정의할 것이다.위의 장면에서 O는 다음 단계에서 승리할 수 있기 때문에 X의 원시 이동은 하나의 값-1로 분배된다.
극대 극소 알고리즘은 모든 포지셔닝에서 이 정책을 적용합니다. - 우리는 주어진 시작 위치에서 게임을 탐색하고 가능한 모든 게임이 끝날 때까지 합니다.우리는 그것을 나무로 표시할 수 있다. 나무의 각 층은 플레이어에게 라운드할 수 있는 바둑판 위치를 표시한다.우리가 게임 종료 상태에 도달했을 때 선택이 없기 때문에 값은 게임 결과이다. 즉, X가 이기면 1, O가 이기면 1, 무승부면 0이다.X 차례가 최종판 상태가 아닌 경우 트리에서 다음 이동할 수 있는 최대값을 선택합니다.이것은 X의 가장 좋은 선택을 나타낸다. 만약 O의 차례가 된다면, 우리는 이 값 중의 가장 작은 값을 선택한다. 이것은 O의 가장 좋은 선택이다. 우리는 루트 위치까지, 최대 값과 최소 값 사이를 교체할 때까지 위치 값을 계속 위로 전파한다. - 이것은 당연히 미니맥스 알고리즘의 이름이다.
다음 그림은 보드 위치에 적용되는 최소 최대치의 예를 보여 줍니다.

만약 이 위치가 게임 종료 상태라면, 이 위치의 값은 이 게임의 결과입니다. - 이것은 귀속 호출의 종료 조건입니다.일단 우리가 게임이 끝난 위치에 도착하면, 우리는 뿌리로 돌아가려고 노력할 수 있다.트리의 최대 레벨의 위치 (이제 X 차례) 에 대해 가능한 연속에서 최대 값을 가진 이동을 선택합니다.트리의 최소 계층 내의 위치 (이제 O 차례) 에 대해 최소값을 지정합니다.모든 상황에서 우리는 현재 유저의 다음 행동을 위해 가능한 최상의 결과를 찾고 있다.보시다시피 그림에서 X가 할 수 있는 가장 좋은 일 (O가 실수를 하지 않았다면) 은 바둑판의 오른쪽 상단에서 비겼다.

It's worth emphasizing that minimax works fine for a toy scenario like tic-tac-toe: There are few distinct game positions - 765 if we take rotation and reflection symmetry into account. For more complex scenarios, including games like chess and go, minimax would, at the very least, have to be combined with other techniques. I haven't implemented it here, but alpha-beta pruning can be used to reduce the number of positions that need to be visited. The overall idea is that if we know that exploring a subtree won't produce a better result than what we've already got, then we don't need to bother with it. There are additional heuristics as well. We can limit the depth of search, and once we hit that limit, we can use a heuristic to estimate the likely value of the position. This idea has been used extensively in chess engines like Stockfish. MCTS is another technique that can be applied to simplify scenarios where minimax would result in too many combinations to keep track of. These days, for games like chess and go, deep learning has proven remarkably effective. In fact, it's far more effective than any other known technique.

미니맥스를 실현하는 데 필요한 코드를 간단명료하게 봅시다.이 코드를 작성하는 것은 최고 효율을 실현하기 위한 것이 아니라 기본 개념을 설명하기 위한 것이므로 주의하십시오.이 항목은 github 에서 얻을 수 있습니다.이 코드는 minimax.py 파일에서 온 것입니다.

def play_minimax_move(board):
    move_value_pairs = get_move_value_pairs(board)
    move = filter_best_move(board, move_value_pairs)

    return play_move(board, move)

play_minimax_move 주어진 바둑판의 위치에서 이동할 것을 확정한다.우선, 이것은 이동할 수 있는 모든 값을 얻은 다음, X 차례가 되면 최대값으로 이동을 재생하거나, O 차례가 되면 최소값으로 이동을 재생합니다.get_move_value_pairs 현재 보드 위치에서 시작된 각 후속 이동의 값을 가져옵니다.

def get_move_value_pairs(board):
    valid_move_indexes = get_valid_move_indexes(board)

    assert not_empty(valid_move_indexes), "never call with an end-position"

    move_value_pairs = [(m, get_position_value(play_move(board, m)))
                        for m in valid_move_indexes]

    return move_value_pairs

get_position_value 캐시에서 현재 위치의 값을 얻거나 게임 트리를 탐색하여 직접 계산합니다.캐시가 없으면, 내 컴퓨터에서 게임을 하는 데 약 1.5분이 걸린다.캐시를 0.3초 정도로 단축합니다!전체 검색에서 동일한 위치가 여러 번 나타납니다.캐시는 우리가 이 과정을 크게 가속화시킬 수 있도록 한다. 만약에 우리가 이전에 한 위치를 보았다면, 우리는 게임 트리의 이 부분을 다시 탐색할 필요가 없다.

def get_position_value(board):
    cached_position_value, found = get_position_value_from_cache(board)
    if found:
        return cached_position_value

    position_value = calculate_position_value(board)

    put_position_value_in_cache(board, position_value)

    return position_value

calculate_position_value 주어진 회로 기판이 캐시에 없을 때 그 값을 찾습니다.만약 우리가 게임이 끝날 때, 우리는 게임 결과를 위치값으로 되돌려준다.그렇지 않으면, 우리는 호출 get_position_value 과 모든 유효한 이동 가능성을 귀속한다.그리고 우리는 이 모든 값의 최소치를 얻거나 최대치를 얻는다. 이것은 누구의 차례가 되느냐에 달려 있다.

def calculate_position_value(board):
    if is_gameover(board):
        return get_game_result(board)

    valid_move_indexes = get_valid_move_indexes(board)

    values = [get_position_value(play_move(board, m))
              for m in valid_move_indexes]

    min_or_max = choose_min_or_max_for_comparison(board)
    position_value = min_or_max(values)

    return position_value

아래에서 볼 수 있듯이 choose_min_or_max_for_comparison O의 경우 반환 min 함수, X의 경우 반환 max:

def choose_min_or_max_for_comparison(board):
    turn = get_turn(board)
    return min if turn == CELL_O else max

캐시로 돌아가서 캐시 코드는 등가의 위치를 고려했다.회전 및 수평 및 수직 반사를 포함합니다.회전할 때 0 °, 90 °, 180 °, 270 ° 등 4개의 등효 위치가 있다.그리고 4개의 반사: 수평과 수직으로 원시 위치를 뒤집거나 90°를 먼저 회전한 다음 수평과 수직으로 뒤집을 수 있다.나머지 회전을 뒤집는 것은 불필요한 것이다. 180도 회전을 뒤집으면 원래 위치와 같은 위치가 생긴다.270° 회전을 뒤집으면 90° 회전과 같은 위치가 됩니다.회전과 반사를 고려하지 않는 상황에서 내 컴퓨터의 게임은 대략 0.8초가 걸린다. 그에 비해 캐시도 회전과 반사를 사용할 때 0.3초가 걸린다.get_symmetrical_board_orientations 캐시에서 찾을 수 있도록 동일한 보드 위치를 모두 가져옵니다.

def get_symmetrical_board_orientations(board_2d):
    orientations = [board_2d]

    current_board_2d = board_2d
    for i in range(3):
        current_board_2d = np.rot90(current_board_2d)
        orientations.append(current_board_2d)

    orientations.append(np.flipud(board_2d))
    orientations.append(np.fliplr(board_2d))

    orientations.append(np.flipud(np.rot90(board_2d)))
    orientations.append(np.fliplr(np.rot90(board_2d)))

    return orientations

자세한 내용을 보려면 github repo와 이 프로젝트의 모든 코드를 다음 사이트에서 얻을 수 있습니다.

Nested 소프트웨어 / tictac회사

서로 다른 기교를 시험하여 우물 글자 놀이를 하다

프로젝트의 다른 방법을 시범하여 우물 글자 놀이를 하다.
코드는python 3,numpy,pytest가 필요합니다.
pipenv를 사용하여 설치:

pipenv shell

pipenv install --dev

PYTHONPATH 를 주 프로젝트 디렉토리로 설정해야 합니다.

윈도우즈에서 실행path.bat

bashrunsource path.sh에서

테스트 및 프레젠테이션 실행:

운영 테스트: pytest

프레젠테이션 실행: python -m tictac.main

다음은 최신 프레젠테이션 결과입니다.현재의 qtable 에이전트는 자신, 극소극대, 무작위로 완벽한 바둑에 가깝다.X 플레이어의 경우 좋은 결과를 얻는 것은 매우 간단하지만, O의 경우 초변수에 대해 상당히 많은 수정이 필요하다.
최신 결과:

C:\Dev\python\tictac>python -m tictac.main
Playing random vs random
-------------------------
x wins: 60.10%
o wins: 28.90%
draw  : 11.00%
Playing minimax not random vs minimax random
---------------------------------------------
x wins: 0.00%
o wins: 0.00%
draw  : 100.00%

Playing minimax random vs minimax not random:
---------------------------------------------
x wins: 0.00%
o wins: 0.00%
draw  : 100.00%

…
View on GitHub
다음은 최대 극소와 랜덤 유저의 서로 다른 조합의 승리 비율로 그룹당 1000게임을 진행합니다.

두 선수 모두 잘 싸우면 무승부만 가능하지만 두 선수가 무작위로 경기하면 X가 이길 가능성이 더 높다는 것을 알 수 있다.

관련했어