신경 네트워크 기반 Tic-Tac-Toe 알고리즘

작년에 우리는 강화 학습을 이용하여tic-tac-toe 에이전트를 개발했다.우리는 하나의 표를 사용하여 포지셔닝에서 시작하는 모든 이동에 대해 Q 값을 지정합니다.훈련 게임은 이러한 Q 값을 점점 더 좋은 결과를 만드는 방향으로 밀어붙이는 데 사용된다. 좋은 결과는 이러한 결과를 초래하는 동작의 Q 값을 높이고, 나쁜 결과는 그것들을 낮춘다.본고에서 우리는 학습을 강화하는 동일한 사상을 표를 사용하지 않고 신경 네트워크에 응용할 것이다.

함수로서의 신경 네트워크

우리는 Q표를 다변수 함수로 볼 수 있다. 입력은 주어진tic-tac-toe 위치이고 출력은 이 위치가 이동할 때마다 대응하는 Q값 목록이다.우리는 이 함수와 비슷한 신경 네트워크를 가르치기 위해 노력할 것이다.
네트워크의 입력에 대해 우리는 회로판의 위치를 9개의 값으로 평평하게 할 것이다. 1은 X를 나타내고, -1은 O를 나타내고, 0은 빈 단원을 나타낸다.출력층은 9개의 값의 수조로 이동할 수 있는 모든 Q값을 대표할 것이다. 0에 가까운 낮은 값은 좋지 않고 1에 가까운 높은 값은 좋다.훈련 후 네트워크는 이 모델에서 최고 출력값에 대응하는 이동을 선택한다.
다음 그림은 훈련 후 주어진 위치의 입력과 출력 (최초의 모든 값이 0.5 정도를 맴돌았다) 을 보여 줍니다.

보시다시피 X, A2의 승리 이동은 가장 높은 Q치, 0.998을 가지고 있으며, 불법 이동은 매우 낮은 Q치를 가지고 있습니다.기타 합법적인 이동의 Q 값은 불법 이동보다 크지만 승리 이동보다 작다.이것이 바로 우리가 원하는 것이다.

모델

네트워크(Pytork 사용)에는 다음과 같은 구조가 있습니다.

class TicTacNet(nn.Module):
    def __init__(self):
        super().__init__()
        self.dl1 = nn.Linear(9, 36)
        self.dl2 = nn.Linear(36, 36)
        self.output_layer = nn.Linear(36, 9)

    def forward(self, x):
        x = self.dl1(x)
        x = torch.relu(x)

        x = self.dl2(x)
        x = torch.relu(x)

        x = self.output_layer(x)
        x = torch.sigmoid(x)
        return x

현재 회로기판의 위치를 나타내는 9개의 입력 값은 두 개의 밀집된 숨겨진 층을 통해 각 숨겨진 층은 36개의 신경원으로 구성된 다음에 출력 층으로 전달되고 출력 층은 9개의 값으로 구성되며 각 값은 정해진 이동된 Q 값에 대응한다

훈련하다

이 대리의 대다수 훈련 논리는 본 시리즈에서 논의한 Q표와 같다.그러나 실시 과정에서 우리는 불법 행위를 방지했다.신경 네트워크에 대해 나는 주어진 위치에 더 현실적인 출력 값을 만들기 위해 불법적인 동작을 하지 말라고 가르치기로 결정했다.
다음 코드는 qneural.py 에서 왔으며 단일 트레이닝 게임에 대한 네트워크 매개 변수를 업데이트하는 방법을 보여 줍니다.

def update_training_gameover(net_context, move_history, q_learning_player,
                             final_board, discount_factor):
    game_result_reward = get_game_result_value(q_learning_player, final_board)

    # move history is in reverse-chronological order - last to first
    next_position, move_index = move_history[0]

    backpropagate(net_context, next_position, move_index, game_result_reward)

    for (position, move_index) in list(move_history)[1:]:
        next_q_values = get_q_values(next_position, net_context.target_net)
        qv = torch.max(next_q_values).item()

        backpropagate(net_context, position, move_index, discount_factor * qv)

        next_position = position

    net_context.target_net.load_state_dict(net_context.policy_net.state_dict())


def backpropagate(net_context, position, move_index, target_value):
    net_context.optimizer.zero_grad()
    output = net_context.policy_net(convert_to_tensor(position))

    target = output.clone().detach()
    target[move_index] = target_value
    illegal_move_indexes = position.get_illegal_move_indexes()
    for mi in illegal_move_indexes:
        target[mi] = LOSS_VALUE

    loss = net_context.loss_function(output, target)
    loss.backward()
    net_context.optimizer.step()

우리는 두 개의 네트워크, 정책 네트워크(policy_net와 목표 네트워크(target_net를 유지한다.우리는 정책 네트워크에서 역방향 전파를 실행하지만, 목표 네트워크에서 다음 상태의 최대 Q값을 얻는다.이렇게 하면 단일 게임의 훈련 과정에서 목표 네트워크에서 얻은 Q값은 변하지 않는다.게임 훈련을 마친 후, 우리는 전략 네트워크의 매개 변수(load_state_dict로 목표 네트워크를 업데이트한다.move_history 매번 Q-learning 에이전트가 단일 훈련 게임에서의 이동을 포함한다.Q-learning 대리가 하는 마지막 동작에 대해 우리는 이 게임의 보상치를 사용하여 선택한 동작-0은 실패를 표시하고, 1은 승리 또는 무승부를 표시합니다.그리고 우리는 사진 반대 시간 순서로 게임 역사에서 남은 동작을 훑어보았다.우리는 다음 상태(다음 상태는 현재 상태에서 취한 동작이 발생한 상태)에서 최대 Q 값 방향을 따라 이동하는 Q 값을 끌어냅니다.
이것은 표 Q-학습 방법에서 사용하는 지수 이동 평균과 유사하다. 이 두 가지 상황에서 우리는 현재 값을 다음 상태에서 사용할 수 있는 최대 Q 값의 방향으로 당긴다.주어진 게임 위치에서 오는 어떠한 불법 이동에 대해서도 우리는 이 이동의 부정적인 피드백을 제공하여 역방향 전파의 일부분으로 삼는다.이렇게 하면 우리 인터넷은 불법 행위를 하지 않는 것을 배울 수 있을 것이다.

결과

결과는 표 Q 학습 대리와 비슷하다.다음 표(각 상황에 따라 1000경기)는 전형적인 훈련 운행 후 얻은 결과를 나타낸다.

이 결과는 한 모델에서 얻은 것으로 X와 O당 200만 개의 트레이닝 게임에서 배웠다(무작위 이동을 위한 에이전트).내 컴퓨터에서 이 모형을 훈련시키는 데 한 시간이 넘게 걸린다. 이것은 훈련표 대리에 필요한 게임 수량보다 훨씬 많다.
나는 이것이 대량의 고품질 데이터가 깊이 있는 학습에 얼마나 중요한지를 나타낸다고 생각한다. 특히 우리가 이런 장난감 예시에서 현실 세계 문제로 넘어갈 때.물론 신경 네트워크의 장점은 범용할 수 있다는 것이다. 즉, 훈련 기간에 보지 못한 입력을 처리할 수 있다는 것이다.
표법을 사용할 때 삽입값이 없습니다. 만약 우리가 이전에 보지 못했던 위치를 만나게 된다면, 우리가 할 수 있는 가장 좋은 일은 계발식을 응용하는 것입니다.바둑과 체스 같은 게임에서 위치의 수가 이렇게 많아서 우리는 심지어 그것들을 저장하기 시작할 수 없다.우리는 보급할 수 있는 방법이 필요하다. 이것이 바로 신경 네트워크가 이전의 기술에 비해 진정으로 역할을 발휘할 수 있는 곳이다.
우리의 네트워크는 승리와 무승부를 위해 같은 보상을 제공한다.나는 무승부에 대한 보상이 이긴 경기의 보상보다 작지만 무승부의 가치를 0.95 정도로 낮추어도 네트워크의 안정성을 떨어뜨릴 것 같다.특히 X를 할 때 인터넷은 결국 무작위 극대 극소 대리에게 대량의 게임에 질 수 있다.승리와 무승부의 보상을 똑같이 하면 이 문제를 해결할 수 있을 것 같다.
설령 우리가 승리와 무승부에 대해 같은 보상을 준다 하더라도 매니저는 경기를 이기는 데 있어서 매우 잘하는 것 같다.나는 이것이 이기는 경기가 통상적으로 앞당겨 끝나기 때문이라고 생각한다. 바둑판의 모든 9개의 칸이 채워지기 전에.이것은 게임 역사의 모든 단계에서 보상의 희석 정도가 낮아진다는 것을 의미한다.한편, 무승부는 (정의에 따라) 모든 9개의 동작을 필요로 한다. 이것은 우리가 한 동작에서 Q-learning 대리가 한 이전 동작까지 할 때 무승부가 주어진 게임에서의 동작 보상이 더욱 희석된다는 것을 의미한다.따라서 주어진 이동이 시종 더 빨리 승리를 가져올 수 있다면, 그것은 결국 무승부를 초래하는 이동보다 우세하다.

네트워크 토폴로지 및 하이퍼패라메트릭

앞에서 말한 바와 같이 이 모델은 두 개의 숨겨진 치밀층이 있는데 각 층은 36개의 신경원으로 구성되어 있다.MSELoss 손실 함수로 사용되며 학습률은 0.1이다.relu 숨겨진 레이어의 활성화 함수로 사용됩니다.sigmoid 결과를 0에서 1 사이의 범위로 압축하기 위해 출력층의 활성화로 사용됩니다.
인터넷의 단순성을 감안하면 이런 디자인은 말하지 않아도 알 것 같다.그러나 이 간단한 사례 연구에도 이 네트워크를 조정하는 데는 상당한 시간이 걸린다.처음에 나는 tanh(쌍곡정절)을 출력층-설정-1을 손실값으로 하고 1을 승리값으로 하는 것이 나에게 의미가 있었다.그러나 나는 이 활성화 함수로 안정적인 결과를 얻을 수 없다.마지막으로 다른 몇 가지 생각을 시도한 후에 나는 sigmoid로 그것을 바꾸었고 이것은 더욱 좋은 결과를 얻었다.이와 유사하게 숨겨진 층의 다른 내용으로 대체relu하면 결과가 더욱 나빠진다.
나는 또 몇 가지 다른 네트워크 토폴로지를 시도했는데 하나, 둘 또는 세 개의 숨겨진 층의 조합이 있고 각 숨겨진 층은 9, 18, 27과 36개의 신경원의 조합을 사용한다.마지막으로 나는 훈련 게임의 수를 100000에서 시작하여 점차적으로 2000000으로 늘렸는데 이것이 가장 안정적인 결과를 낳은 것 같다.

DQN 회사

이 구현은 DeepMind의 DQN 아키텍처에서 영감을 얻었습니다(참조 Human-level control through deep reinforcement learning. 그러나 완전히 같지는 않습니다.DeepMind는 볼륨 네트워크를 사용하여 직접 화면 이미지를 가져옵니다.여기서 저는 목표가 인터넷tic-tac-toe의 핵심 논리를 가르치는 것이라고 생각하기 때문에 표현을 간소화하는 것이 의미가 있다고 생각합니다.입력을 이미지로 처리할 필요가 없다는 것은 더 적은 층(회로판의 시각적 특징을 식별할 층이 없음)이 필요하다는 것을 의미하며 훈련 속도를 높인다.
DeepMind의 실현은 체험 재방송도 사용했는데 훈련 기간에 체험의 무작위 부분을 인터넷 입력으로 한다.이런 상황에서 새로운 랜덤 게임을 만드는 것이 더 간단하다는 느낌이 든다.
우리는 이런tic-tac-toe를'깊이'학습이라고 할 수 있습니까?나는 이 용어가 통상적으로 적어도 세 개의 숨겨진 네트워크에 쓰인다고 생각하기 때문에 아마 그렇지 않을 것이다.나는 층수를 늘리는 것이 권적 네트워크에 더욱 가치가 있다고 생각한다. 권적 네트워크에서 우리는 이를 하나의 과정으로 이해할 수 있다. 그 중에서 각 층은 전 층에서 식별된 특징을 추상화하고 밀집층에 비해 파라미터의 수량이 감소한다.어떤 상황에서도 더 좋은 결과가 나올 때만 우리는 층을 추가해야 한다.

비밀번호

전체 코드는 github qneural.py 및 main_qneural.py 에서 사용할 수 있습니다.

Nested 소프트웨어 / tictac회사

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

프로젝트의 다른 방법을 시범하여 우물 글자 놀이를 하다.
코드는python 3,numpy,pytest가 필요합니다.신경 네트워크/dqn 구현(qneural.py)에 대해Pytork가 필요합니다.
pipenv를 사용하여 가상 환경 만들기:

pipenv --site-packages

pipenv를 사용하여 설치:

pipenv shell

pipenv install --dev

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

윈도우즈에서 실행path.bat

bashrunsource path.sh에서

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

운영 테스트: pytest

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

신경 네트워크 데모 실행: python -m tictac.main_qneural

최신 결과:

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%

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

Playing minimax random vs minimax random:

…
View on GitHub

관련했어

공구서류

Human-level control through deep reinforcement learning