목 차
1. 들어가며
2. 사전설명
3. 코드설명
4. 전체코드
5. 마치며
1. 들어가며
지난글에서는 틱택톡 만들기 및 pc의 순차적 입력을 통해 대결하는 방법을 알아보았다. pc가 랜덤(random)입력하는 방법이 있겠지만, 필자가 원하는 방법은 아니었다. 이전에 두었던 수(手)를 분석하여 가장 좋은 수(手)를 계산하는 방법을 알아보고자 했는데, 앞의 방법(랜덤입력)은 설계된 코드에 따라 다음 수(手)를 두는게 약간은 부담이었다. 모든 경우의 수를 코드로 짤수도 없을 뿐더러, 설계한 코드가 반드시 승리로 이끌어줄 것 같지는 않다.
이번글에서는 틱택톡에서 MCTS를 활용해 기 입력된 수(手)에 대해 랜덤으로 끝까지 둬보고, 승률이 가장 높은 수(手)를 pc가 두도록 설정하는 코드에 대해 알아본다.
※ 참고로 코드 및 유튜브 영상의 출처는 아래와 같다. 유튜버 Dennis Roof님의 코드가 원본이다.
- 코드 출처 : https://pastebin.com/bUcRrKwF
- 유튜브 출처 : https://www.youtube.com/watch?v=gvlO_-Fdk9w
필자가 설명하기 편하도록 일부 수정은 하였지만, 코드를 크게 수정하지는 않았다.유튜브 강의 내용이 상당히 좋다. 7분 정도의 영상이니 원본 영상을 보는 것을 적극 추천한다. 위 영상을 제작해주신 유튜버 Dennis Roof 님께 감사의 뜻을 남긴다.
2024년 1월은 자동매매는 돌리고 있지 않고, 알고리즘 설계에 대해 고민하고 있다. 기존 차트를 보고 알고리즘을 고민하여 거래하는 것은 한계가 있어보인다. 이 글에서는 MCTS가 돌아가는 원리를 확인해보고자 한다.
상당히 긴 글이 될 것이다. 관심있는 부분을 발췌하여 보면 좋을 것이다.
2. 사전설명
1) MCTS 설명
몬테카를로 트리 서치(Monte Carlo tree search, MCTS)는 검색가능한 공간에서 무작위 추출을 통해 검색트리를 확장한다. 간단히 말하면, 상대방 수(手)에 따라 끝까지 게임을 진행해보고, 가장 승률이 높은 수를 선택한다. MCTS는 2016년 이세돌 9단과 바둑대결을 했던 알파고(Alphago Lee)에서 활용했던 방법이다. (물론 이글에서 2016년의 알파고 코드를 구현하는 것은 아니다)
MCTS를 활용해 사용자와 3x3 틱톡게임을 진행해보면 알 것이다. 생각없이 게임하면, 사용자(you)도 게임에서 질 수있다. 실제 필자도 넋놓고 게임을 하면, 생각보다 게임에서 지는 경우가 종종 있었다.
사실 필자도 MCTS 개념에 대해 정확히 설명하는 것이 어렵다. 실제로 이 코드에서 쓰일 MCTS에 대해 제대로 설명할 수 있을지 걱정된다.
MCTS의 '선택-확장-시뮬레이션-역전달' 내용 등은 인터넷 검색을 통해 알아보는 것이 좋아보인다.
2) 틱택톡 게임 설명
틱택톡은 3x3의 공간에서 가로, 세로, 대각선으로 같은 모양이 있으면 승리하는 게임이다. 인터넷 검색을 통해 알아보면, 3x3 틱택톡 게임을 무한정 진행하면 계속 무승부가 나오게 된다. 즉, 내가 이기지는 못하더라도, 승대가 이길 수 없는 방법은 얼마든지 있기 때문이다.
3x3은 9개 공간에서 승패를 가른다. o플레이어가 먼저 두고, 턴제로 서로 번갈아 두었을때, o플레이어가 마지막(9번째 수)을 두기 때문에 상당히 불공평할 수도 있다. 그래서 5x5 공간(25칸)으로 게임을 진행해보았는데, 시간도 오래 걸리고, 계속 무승부가 나왔기 때문에 3x3 공간으로 코드를 설명한다.
3) 활용할 라이브러리
① random 라이브러리
- random 정의 : 무작위 숫자를 넣어서 시뮬레이션을 돌릴때 활용된다.
- random 활용 : random.randint(1,4) → 1이상 4이하 범위내의 정수 (1,2,3,4)
② ast 라이브러리
- ast 정의 : python 추상 구문 문법의 트리를 처리한다. (여기서 왜 써주는지, 필자도 좀더 공부해봐야겠다)
- ast 활용 : ast.literal_eval(내용)의 형태로, '리스트 혹은 딕셔너리'의 문자형을 리스트 혹은 딕셔너리로 바꾸어준다.
③ sys 라이브러리
- sys 정의 : 응용프로그램이 종료되지 않게 해준다.
- sys 활용 : app=QApplication(sys.argv)를 선언하고, app.exec_() 형태로 실행된 프로그램이 종료되지 않는다.
④ PyQt5.QtWidgets
- PyQt5.QtWidgets 정의 : QApplication는 응용 프로그램을 작동한다.
- PyQt5.QtWidgets 활용 : QApplication(sys.argv)로 활용한다.
3. 코드설명
전체코드는 4번(전체코드)에서 확인할 수 있다. 코드가 상당히 길어보이지만, 인내심을 가지고 천천히 읽어보자. 여기서는 MCTS로 계산되는 부분을 중점적으로 살펴보자. 실행을 해보면 알겠지만, 무승부가 상당히 많이 발생할 정도로 pc가 상당히 잘 둔다. 3 x 3의 공간에서 틱택톡을 실행할 것이다.
※ 원본코드는 https://pastebin.com/bUcRrKwF 에서 확인가능하다. (유튜버 : Dennis Roof님의 코드)
① 코드 순서는 최초 공간(board)을 선언하고, 남은 공간을 확인한다.
② 현재보드 상태에 대한 다음 이동 옵션을 보유한다.(저장)
③ 현재 보드상태를 복사하여 다음 공간에 추가(append)한다.
④ 승리/무승부를 정의한다.
⑤ 다음 플레이어로 반환한다.
⑥ 가장 좋은 다음 동작을 반환한다.
⑦ 파이썬(파이참)에 입력결과를 출력한다.
⑧ 플레이어(you)가 다음 이동을 입력(input)한다.
⑨ 게임의 재시작, 무승부를 정의한다.
⑩ 틱택톡 게임을 시작하고, 승리/무승부를 검사한다.
### The Monte Carlo Search Tree AI
### 1 - It takes the current game state # 현재 게임 상태를 가져온다.
### 2 - It runs multiple random game simulations starting from this game state # 이 게임 상태에서 시작하여 여러 무작위 게임 시뮬레이션을 실행한다.
### 3 - For each simulation, the final state is evaluated by a score (higher score = better outcome) # 각 시뮬레이션에 대해 최종 상태는 점수로 평가된다(점수가 높을수록 더 좋은 결과)
### 4 - It only remembers the next move of each simulation and accumulates the scores for that move # 각 시뮬레이션의 다음 동작만 기억하고 해당 동작(다음동작)에 대한 점수를 누적한다.
### 5 - Finally, it returns the next move with the highest score # 마지막으로 가장 높은 점수를 다음 동작으로 반환한다. (AI의 동작을 말함)
import random # 출처 : https://pastebin.com/bUcRrKwF
import ast
import sys
from PyQt5.QtWidgets import *
1줄~11줄 : 유튜버 Dennis Roof님은 프로그램에 대해 간단하게 설명한다.
3줄 : 현재 게임 상태를 가져온다.
5줄 : 틱택톡 공간을 확인하고 여러 무작위 게임 시뮬레이션을 실행한다.
7줄 : 각 시뮬레이션에서 최종 상태는 점수로 평가된다. (=점수가 높을수록 더 좋은 결과이다)
9줄 : 각 시뮬레이션의 다음 동작만 기억하고, 해당 동작(다음동작)에 대한 점수를 누적한다.
11줄 : 마지막으로 가장 높은 점수를 (받은 동작을) 다음 동작으로 반환한다.(AI가 행동하는 패턴)
13줄~16줄 : 활용될 라이브러리는 위에서 설명하였다.
class Dennis_Roof():
def __init__(self):
self.userPlayer = 'O'
self.boardSize = 3
# self.boardSize = 5
self.numberOfSimulations = 200
if self.boardSize == 3:
self.board = [list('...'),list('...'),list('...')]
elif self.boardSize == 5:
self.board = [list('.....'),list('.....'),list('.....'),list('.....'),list('.....')]
# 현재는 플레이어(you)가 선수를 잡은 경우이다.
self.startingPlayer = 'O' # 'o'로 설정한 경우, 사용자(you)가 1번째(O) 플레이어(1p) - 선수를 잡고 싶으면 31줄 주석해제, 30줄 주석처리
# self.startingPlayer = 'X' # 'x'로 설정한 경우, 2번째 플레이어(2p) - 후수를 잡고 싶으면 30줄 주석해제, 31줄 주석
self.currentPlayer = self.startingPlayer
self.tie_game_list = []
# 시뮬레이션을 위해 보드에 남은 공간이 있는지 확인
def getBoardCopy(self, board):
self.boardCopy = []
for row in board:
self.boardCopy.append(row.copy())
return self.boardCopy
# 현재보드 상태에 대한 다음 이동 옵션을 보유
def hasMovesLeft(self, board):
for y in range(self.boardSize):
for x in range(self.boardSize):
if board[y][x] == '.':
return True
return False
1줄 : Dennis_Roof 클래스를 선언한다.
2줄 : 클래스가 실행될 때, 초기화 함수(__init__)를 정의한다.
3줄 : 사용자(you) 플레이어는 o플레이어이다.
4줄 : 공간은 3으로 설정한다.(3x3 공간)
5줄 : 공간은 5로 설정한다. (여기서는 주석처리한다)
6줄 : 시뮬레이션할 횟수를 정한다. 최초는 200회를 시뮬레이션한다.
8줄~9줄 : 공간이 3일 때, 보드공간 3의 리스트 형태로 선언한다. (3x3)
10줄~11줄 : 공간이 5일 때, 보드공간 5의 리스트 형태로 선언한다. (5x5)
14줄~16줄 : 최초로 선수(first player)를 잡을 플레이어를 선언한다. 현재는 O플레이어(사용자)가 선수를 잡는다.
18줄 : 무승부를 구분하는 리스트를 선언한다.
21줄~27줄 : 시뮬레이션을 돌릴 때, 보드에 남은 공간을 확인한다.
22줄 : '보드 리스트'를 선언한다. (현재 보드에 놓여진 수(手)를 확인한다)
24줄~25줄 : '보드 리스트'에 row를 추가한다.
27줄 : 24줄~25줄에서 추가된 '보드 리스트'를 반환한다.
30줄 : 현재보드 상태에 다음 이동 옵션을 판단한다.
31줄 : self.boardSize(공간 3)에서 x, y축을 확인한다. board[y][x]가 빈칸(dot)이면 true를 반환한다.
# 각 도트(점)에 대한 이동 옵션 (현재 보드상태를 복사)
# - 현재 플레이어의 위치를 표시하고, 이 이동을 다음 이동 목록에 추가하고 다음 이동 목록을 반환
def getNextMoves(self, currentBoard, player):
self.nextMoves = []
for y in range(self.boardSize):
for x in range(self.boardSize):
if currentBoard[y][x] == '.':
self.boardCopy = droof.getBoardCopy(currentBoard) # 함수 실행
self.boardCopy[y][x] = player
self.nextMoves.append(self.boardCopy)
return self.nextMoves
# 승리에 대해 확인(검증)하는 내용
def hasWon(self, currentBoard, player):
# 승리동작은 플레이어에 따라 x 또는 o의 행을 정의
winningSet = [player for _ in range(self.boardSize)]
# 승리 동작에 대해 각 행을 확인한다.
for row in currentBoard:
if row == winningSet:
return True
# 승리 동작에 대해 각 열을 확인한다.
for y in range(len(currentBoard)):
column = [currentBoard[index][y] for index in range(self.boardSize)]
if column == winningSet:
return True
# 보드에서 승리동작이 발견(행,열)되지 않으면, 이 승리동작에 대해 각 대각선을 확인한다.
diagonal1 = []
diagonal2 = []
for index in range(len(currentBoard)):
diagonal1.append(currentBoard[index][index])
diagonal2.append(currentBoard[index][self.boardSize - index - 1])
if diagonal1 == winningSet or diagonal2 == winningSet:
return True
# 위 승리 동작에 해당하지 않으면 False를 반환한다.
return False
# 다음 플레이어를 반환한다.
def getNextPlayer(self, currentPlayer):
if currentPlayer == 'X':
return 'O'
return 'X'
3줄 : 플레이어의 다음 이동 목록을 반환한다.
4줄 : 다음 이동을 판단할 리스트를 선언한다.
6줄~8줄 : 현재 보드의 x, y축이 빈칸(dot)이면,
9줄 : 현재 놓여진 있는 보드상태(self.boardCopy)를 구하기 위해 getBoardCopy 함수를 실행한다.
10줄 : self.boardCopy[y][x]에 플레이어를 넣는다.
11줄 : self.boardCopy에 들어있는 플레이어(O,X)를 4줄의 self.nextMoves를 추가한다.
12줄 : self.nextMoves를 반환한다. (저장한다)
17줄~45줄 : 승리에 대한 내용을 정의한다.
19줄 : 승리동작을 플리이어(o,x)에 따라 정의한다.
22줄~24줄 : 승리 동작에 대해 각 행을 확인한다. (=가로축이 같은 모양일 때 승리)
27줄~31줄 : 승리 동작에 대해 각 열을 확인한다. (=세로축이 같은 모양일 때 승리)
33줄~45줄 : 승리 동작이 행/열에서 발견되지 않으면, 대각선을 확인한다.
48줄~52줄 : 다음 플레이어를 반환한다. (턴제)
# 가장 좋은 다음 동작을 검색한다.
def getBestNextMove(self, currentBoard, currentPlayer):
# evaluations 변수는 각 동작(현재의 보드상태)에 대한 다음 동작을 저장한다.
# 다음 동작들을 딕셔너리 형태인 '키:값' 형태로 저장한다.
# 이때 키에는 보드상태가 들어가고, 값에는 시뮬레이션 점수가 들어간다.
# (예시) self.board = {[list('.x.'),list('.o.'),list('...')] : 24 }
# 위 예시의 딕셔너리 키값에는 리스트형, 값(value)에는 24가 시뮬레이션가 누적되었다.
evaluations = {}
# 시뮬레이션을 실행한다.
for generation in range(self.numberOfSimulations):
# 현재 플레이어 및 현재 보드 상태의 복사본으로 시뮬레이션을 시작한다.
player = currentPlayer
self.boardCopy = droof.getBoardCopy(currentBoard)
# simulationMoves 리스트 변수는 시뮬레이션이 끝날때까지,
# 여기에서 이루어진 모든 동작을 저장한다.
simulationMoves = []
#현재 상태에 대한 다음 이동 옵션을 검색한다.
self.nextMoves = droof.getNextMoves(self.boardCopy, player)
# 가치 점수는 시뮬레이션의 각 이동에 대해 가장 높은 점수에서 시작한다.
# 의역하면, 최초 점수는 9점(3x3)을 선언한다.
# - 향후, 승리하면 +1점을 더하고(firstMoveKey), 승리하지 않으면 -1을 뺀다
# - 즉, 바로 아래의 score는 최초에는 9를 선언해주었다고 생각하면 된다.
score = self.boardSize * self.boardSize
# 더 이상 이동이 남지 않을 때까지 이동한다. (=보드에 빈칸이 없을때, 즉 보드에 9개를 다 두어본다)
while self.nextMoves != []:
# 임의(random)의 이동을 선택한다.
roll = random.randint(1, len(self.nextMoves)) - 1
self.boardCopy = self.nextMoves[roll]
# 임의로 선택한 이동을 시뮬레이션 이동 목록에 추가한다.
simulationMoves.append(self.boardCopy)
# 플레이어가 둔 수(手)가 승리동작(hasWon)에 해당하면(=승리하면), 시뮬레이션 루프를 중단한다.
if droof.hasWon(self.boardCopy, player):
break
# 그렇지 않으면(=승리하지 않으면),
# 점수(score = self.boardsize * self.boardsize)에서 하나를 뺀다.(=점수에서 -1을 한다.)
score -= 1
# 다음 플레이어로 변환하고, 해당 플레이어에 대한 이동 옵션(getNextMoves)를 가져온다.
player = droof.getNextPlayer(player)
self.nextMoves = droof.getNextMoves(self.boardCopy, player)
# 시뮬레이션이 완료되면, 첫번째 동작(firstMove) 및 마지막 동작(lastMove)을 취한다.
firstMove = simulationMoves[0]
lastMove = simulationMoves[-1]
# 첫번째 동작(리스트 태형)을 텍스트로 변환(repr)하여
# evaluations 딕셔너리의 키(keys)에 저장한다.
firstMoveKey = repr(firstMove)
# 사용자가 한번 턴을 하면, 점수가 음수로 표시된다. (=AI가 게임에서 졌다는 의미)
if player == self.userPlayer and droof.hasWon(self.boardCopy, player):
score *= -1
# 평가점수에 대한 동작을 추가한다.
if firstMoveKey in evaluations:
evaluations[firstMoveKey] += score
else:
evaluations[firstMoveKey] = score
self.bestMove = []
self.highestScore = 0
firstRound = True
# 각 동작에 대해 모든 시뮬레이션이 수행되고
# 평가 점수가 가장 높은 동작을 기억한다(=저장한다)
for move, score in evaluations.items():
if firstRound or score > self.highestScore:
self.highestScore = score
# ast 함수를 사용하여 동작을 다시 게임상태로 변환
self.bestMove = ast.literal_eval(move)
firstRound = False
# 모든 평가(evalutions 딕셔너리) 중에서 점수(score)가 가장 좋은 동작을 반환한다.
self.board = self.bestMove
# return self.bestMove
1줄 : 이 글의 핵심이다. 가장 좋은 다음 동작을 검색한다. 여기서부터 천천히 내용을 살펴보자.
2줄 : getBestNextMove 함수는 현재 상태 및 현재 플레이어를 입력받는다.
8줄 : 평가후 담길 딕셔너리를 선언한다. 딕셔너리의 '키:값'의 형태를 활용하고, 값(values)이 가장큰 키(keys)를 선택하여 다음 수를 두는 패턴이다.
11줄 : self.numberOfSimulations는 200으로 선언하였으므로, for문으로 200번을 돌린다.
13줄 : 2줄에서 입력받은 현재 플레이어(currentPlayer)를 player에 넣는다. 여기서 player은 o,x를 말한다.
14줄 : 2줄에서 입력받은 현재 보드상태(currentBoard)를 읽기 위해 getBoardCopy 함수에 넣어 실행하여 현재 보드상태를 최신화한다.
18줄 : 시뮬레이션이 끝날 때까지, 시뮬레이션이 이루어진 모든 동작을 저장한다.
21줄 : 현재 상태에 대한 다음 이동 옵션을 검색하여 self.nextMoves에 담는다.
27줄 : 최초 점수는 9점(3x3)으로 선언한다.
30줄~48줄 : 더 이상 이동공간이 남지 않을 때까지 이동을 시뮬레이션한다. (=보드에 빈칸이 없을 때까지, 보드에 9개를 다 두어본다)
32줄 : 랜덤함수를 이용하여 1~len(self.nextMoves)의 임의의 숫자를 선택하고 1을 뺀다. (1을 뺀 이유는 잘 모르겠다.)
33줄 : 32줄에서 랜덤으로 결정된 숫자가 들어있는 roll을 self.nextMoves에 넣어서, 현재 보드 상태(self.boardCopy)에 넣는다.
36줄 : 33줄에서 임의로 선택한 보드 결과를 시뮬레이션 이동 목록에 추가(append)한다.
39줄 : 플레이어가 둔 수(手)가 승리동작(hasWon)에 해당(승리)하면, 시뮬레이션 루프(for문)을 while를 중단한다.
44줄 : 승리하지 않으면, score(최초 9점)에 -1을 곱한다.
47줄~48줄 : 플레이어를 변환하고, 현재보드상태와 플레이어(o,x)를 getNextMoves 함수에 넣어서, self.nextMoves에 넣는다.
51줄~52줄 : 시뮬레이션이 완료되면, 첫번째 동작(firstMove) 및 마지막 동작(lastMove)을 취한다.
56줄 : 첫번째 동작(=이길 확률이 가장 높은 동작)을 텍스트 변환(repr)하여 evaluation 딕녀너리의 키(keys)에 저장한다.
59줄~60줄 : 시뮬레이션 결과, 게임에서 졌다면 1점을 뺀다.
63줄~64줄 : 8줄에서 선언한 evaluation 리스트 내 firstMoveKey가 있으면 딕셔너리의 values에 스코어를 더해준다.
65줄~66줄 : evaluation 리스트 내 firstMoveKey가 없으면 스코어는 현재 상태(=점수를 더하거나 빼지 않음)이다.
68줄~70줄 : 승률이 가장 높은 동작을 담아주기 위해 self.bestMove 리스트를 선언하고, 가장 높은 점수를 0으로 초기화한다. 시뮬레이션을 돌리므로 firstRound는 True로 선언한다.
74줄~79줄 : 63줄~66줄에서 추가된 evaluation 딕셔너리에서 items를 통해 키:값을 move, score를 추출한다.
75줄 : firstRound 혹은 스코어가 가장높은 스코어(0)보다 크면,
76줄 : self.highestScore에 스코어를 넣어준다.
77줄 : 63줄~66줄에서 추가된 evaluation 딕셔너리의 키값인 move는 문자형('리스트')로 되어 있는데, ast 모듈을 통해 리스트 태형으로 변환하여 self.bestMove에 저장된다.
78줄 : firstRound를 False로 변환한다.
82줄 : 가장 좋은 움직임(결과)를 현재 보드상태인 self.board에 넣어준다.
def game_again(self):
play_again = input("would you like to lpay again? (Y/N)").upper()
self.tie_game_list = []
self.currentPlayer = droof.getNextPlayer(self.currentPlayer)
if play_again == "Y":
if self.boardSize == 3:
print(' 012')
self.board = [list('...'), list('...'), list('...')]
droof.tictactoe_start_game()
elif self.boardSize == 5:
print(' 01234')
self.board = [list('.....'), list('.....'), list('.....'), list('.....'), list('.....')]
droof.tictactoe_start_game()
else:
sys.exit("종료")
def tie_game_restart(self):
# print(self.board)
if self.boardSize == 3:
for a, b, c in self.board:
self.tie_game_list.append(a)
self.tie_game_list.append(b)
self.tie_game_list.append(c)
elif self.boardSize == 5:
for a, b, c,d,e in self.board:
self.tie_game_list.append(a)
self.tie_game_list.append(b)
self.tie_game_list.append(c)
self.tie_game_list.append(d)
self.tie_game_list.append(e)
if self.tie_game_list.count(".") == 0:
print('tie-game!')
droof.game_again()
if self.boardSize == 3:
if self.tie_game_list.count("O")==5 and self.tie_game_list.count("X") == 4:
print('tie-game!')
droof.game_again()
elif self.boardSize == 5:
if self.tie_game_list.count("O")==13 and self.tie_game_list.count("X") == 12:
print('tie-game!')
droof.game_again()
self.tie_game_list = []
1줄~50줄 : 필자가 추가한 코드이다. 코드 원본에는 1판이 끝나면 프로그램이 종료된다. 승리 혹은 무승부인 경우를 판단하여 프로그램을 종료하지 않고, 계속할지 여부를 묻고 Y 혹은 y를 누르면 게임을 재시작한다.
1줄~2줄 : 게임을 다시 할지 여부를 물어본다. upper은 소문자 입력된 내용을 대문자로 변환해준다.
3줄 : 게임을 다시 시작할 때, 재게임을 판단하는 리스트(self.tie_game_list)를 초기화한다. 초기화 안하면, 기존 리스트가 저장되어 계속 tie_game이 선언된다.
4줄 : 게임을 다시 시작할 경우, 선/후를 변경한다. 선수를 둔 사람은 후수를 두게한다. 턴제로 순서를 정한다.
7줄~15줄 : 보드공간을 3x3 혹은 5x5 로 리셋한다.
16줄~17줄 : 2줄에서 N 혹은 n을 누르면 프로그램을 종료한다.
20줄 : 무승부 여부를 검사한다.
23줄~34줄 : 보드공간이 3 혹은 5이면, self.tie_game_list에 각 요소를 담는다.
36줄~38줄 : self.tie_game_list에 빈 공간(dot)이 0개이면, 'tie-game'을 출력하고, 재시작한다.
40줄~48줄 : 보드공간이 3 혹은 5이고, 0 혹은 x가 5개,4개 혹은 13개,12개이면 무승부로 처리하고 게임을 재시작한다.
※ 게임이 무승부되는 것은 모든 수를 두었을 때(=보드에 모든 수를 두었을 때), 승부가 나지 않아, 빈칸이 없거나 모든수를 두었을 때, 무승부가 된다.
50줄 : 무승부를 판단하는 리스트를 초기화 선언한다.
def tictactoe_start_game(self):
# 게임보드를 인쇄한다.
droof.printBoard(self.board)
# 게임보드에 남은 이동이 있는 동안 실행된다.
while droof.hasMovesLeft(self.board):
# 현재 플레이어가 사용자(you)인 경우, 사용자에게 이동(입력)을 요청한다.
if self.currentPlayer == self.userPlayer:
# print("213줄")
# board = droof.getPlayerMove(self.board, self.currentPlayer)
droof.getPlayerMove(self.board, self.currentPlayer)
else:
# 사용자가 AI인 경우, 다음 동작을 요청한다.
# print("216줄")
# board = droof.getBestNextMove(self.board, self.currentPlayer)
droof.getBestNextMove(self.board, self.currentPlayer)
# 플레이어가 '다음동작'을 입력하면, 업데이트된 게임 보드를 파이참에 출력한다.
print('')
droof.printBoard(self.board)
# 게임에서 승리여부를 검사하고, 이긴 플레이어를 출력한다.
if droof.hasWon(self.board, self.currentPlayer):
print('Player ' + self.currentPlayer + ' has won!')
droof.game_again()
# break
# 게임 승리여부가 결정되지 않으면, 다음 플레이어로 전환한다.
self.currentPlayer = droof.getNextPlayer(self.currentPlayer)
if __name__ == "__main__":
app = QApplication(sys.argv)
droof = Dennis_Roof()
droof.tictactoe_start_game()
app.exec_()
1줄~29줄 : 틱택톡 게임을 실행을 정의한다.
3줄 : 현재 보드 상태를 출력한다.
6줄 : 게임보드에 이동할 공간이 있으면 실행된다.(while)
8줄~11줄 : 현재 플레이어가 사용자(you)와 일치하면, 플레이어의 위치를 출력한다.
11줄~16줄 : 현재 플레이어가 사용자(you)가 아니면(=pc이면), getBestMove 함수를 실행한다.
20줄 : 플레이어가 '다음동작'을 입력하면, 업데이트된 보드(게임 상태)를 파이참 결과창에 출력한다.
23줄~25줄 : 게임 승리여부를 검사하고, 이긴 플레이어를 출력한다. 게임 재개 여부를 묻는다.
29줄 : 게임 승리여부가 결정되지 않으면, 다음 플레이어로 전환한다.
31줄~37줄 : 게임 시작 및 프로그램 종료를 방지한다.
32줄 : PyQt5.QtWidgets를 통해 QApplication을 이용하여, 프로그램이 종료되지 않도록 한다.
33줄 : Dennis_Roof 클래스를 droof 변수에 인스턴스한다.(droof에 담는다)
35줄 : 틱택톡 게임을 실행한다.
37줄 : 32줄의 app에 넣은 프로그램을 실행한다. (=종료되지 않게 한다)
4. 전체코드
전체코드는 아래와 같다. 아래 < 접은글 >의 코드의 복사가 한줄로 복사되는등 파이참에 복사가 잘 안되는 경우, 원본 코드를 활용하는 것도 좋다.
### The Monte Carlo Search Tree AI
### 1 - It takes the current game state # 현재 게임 상태를 가져온다.
### 2 - It runs multiple random game simulations starting from this game state # 이 게임 상태에서 시작하여 여러 무작위 게임 시뮬레이션을 실행한다.
### 3 - For each simulation, the final state is evaluated by a score (higher score = better outcome) # 각 시뮬레이션에 대해 최종 상태는 점수로 평가된다(점수가 높을수록 더 좋은 결과)
### 4 - It only remembers the next move of each simulation and accumulates the scores for that move # 각 시뮬레이션의 다음 동작만 기억하고 해당 동작(다음동작)에 대한 점수를 누적한다.
### 5 - Finally, it returns the next move with the highest score # 마지막으로 가장 높은 점수를 다음 동작으로 반환한다. (AI의 동작을 말함)
import random
import ast
import sys
from PyQt5.QtWidgets import *
class Dennis_Roof():
def __init__(self):
self.userPlayer = 'O'
self.boardSize = 3
# self.boardSize = 5
self.numberOfSimulations = 200
if self.boardSize == 3:
self.board = [list('...'),list('...'),list('...')]
elif self.boardSize == 5:
self.board = [list('.....'),list('.....'),list('.....'),list('.....'),list('.....')]
# 현재는 플레이어(you)가 선수를 잡은 경우이다.
self.startingPlayer = 'O' # 'o'로 설정한 경우, 사용자(you)가 1번째(O) 플레이어(1p) - 선수를 잡고 싶으면 31줄 주석해제, 30줄 주석처리
# self.startingPlayer = 'X' # 'x'로 설정한 경우, 2번째 플레이어(2p) - 후수를 잡고 싶으면 30줄 주석해제, 31줄 주석
self.currentPlayer = self.startingPlayer
self.tie_game_list = []
# 시뮬레이션을 위해 보드에 남은 공간이 있는지 확인
def getBoardCopy(self, board):
self.boardCopy = []
for row in board:
self.boardCopy.append(row.copy())
return self.boardCopy
# 현재보드 상태에 대한 다음 이동 옵션을 보유
def hasMovesLeft(self, board):
for y in range(self.boardSize):
for x in range(self.boardSize):
if board[y][x] == '.':
return True
return False
# 각 도트(점)에 대한 이동 옵션 (현재 보드상태를 복사)
# - 현재 플레이어의 위치를 표시하고, 이 이동을 다음 이동 목록에 추가하고 다음 이동 목록을 반환
def getNextMoves(self, currentBoard, player):
self.nextMoves = []
for y in range(self.boardSize):
for x in range(self.boardSize):
if currentBoard[y][x] == '.':
self.boardCopy = droof.getBoardCopy(currentBoard) # 함수 실행
self.boardCopy[y][x] = player
self.nextMoves.append(self.boardCopy)
return self.nextMoves
# 승리에 대해 확인(검증)하는 내용
def hasWon(self, currentBoard, player):
# 승리동작은 플레이어에 따라 x 또는 o의 행을 정의
winningSet = [player for _ in range(self.boardSize)]
# 승리 동작에 대해 각 행을 확인한다.
for row in currentBoard:
if row == winningSet:
return True
# 승리 동작에 대해 각 열을 확인한다.
for y in range(len(currentBoard)):
column = [currentBoard[index][y] for index in range(self.boardSize)]
if column == winningSet:
return True
# 보드에서 승리동작이 발견(행,열)되지 않으면, 이 승리동작에 대해 각 대각선을 확인한다.
diagonal1 = []
diagonal2 = []
for index in range(len(currentBoard)):
diagonal1.append(currentBoard[index][index])
diagonal2.append(currentBoard[index][self.boardSize - index - 1])
if diagonal1 == winningSet or diagonal2 == winningSet:
return True
# 위 승리 동작에 해당하지 않으면 False를 반환한다.
return False
# 다음 플레이어를 반환한다.
def getNextPlayer(self, currentPlayer):
if currentPlayer == 'X':
return 'O'
return 'X'
# 가장 좋은 다음 동작을 검색한다.
def getBestNextMove(self, currentBoard, currentPlayer):
# evaluations 변수는 각 동작(현재의 보드상태)에 대한 다음 동작을 저장한다.
# 다음 동작들을 딕셔너리 형태인 '키:값' 형태로 저장한다.
# 이때 키에는 보드상태가 들어가고, 값에는 시뮬레이션 점수가 들어간다.
# (예시) self.board = {[list('.x.'),list('.o.'),list('...')] : 24 }
# 위 예시의 딕셔너리 키값에는 리스트형, 값(value)에는 24가 시뮬레이션가 누적되었다.
evaluations = {}
# 시뮬레이션을 실행한다.
for generation in range(self.numberOfSimulations):
# 현재 플레이어 및 현재 보드 상태의 복사본으로 시뮬레이션을 시작한다.
player = currentPlayer
self.boardCopy = droof.getBoardCopy(currentBoard)
# simulationMoves 리스트 변수는 시뮬레이션이 끝날때까지,
# 여기에서 이루어진 모든 동작을 저정한다.
simulationMoves = []
#현재 상태에 대한 다음 이동 옵션을 검색한다.
self.nextMoves = droof.getNextMoves(self.boardCopy, player)
# 가치 점수는 시뮬레이션의 각 이동에 대해 가장 높은 점수에서 시작한다.
# 의역하면, 최초 점수는 9점(3x3)을 선언한다.
# - 향후, 승리하면 +1점을 더하고(firstMoveKey), 승리하지 않으면 -1을 뺀다
# - 즉, 바로 아래의 score는 최초에는 9를 선언해주었다고 생각하면 된다.
score = self.boardSize * self.boardSize
# 더 이상 이동이 남지 않을 때까지 이동한다. (=보드에 빈칸이 없을때, 즉 보드에 9개를 다 두어본다)
while self.nextMoves != []:
# 임의(random)의 이동을 선택한다.
roll = random.randint(1, len(self.nextMoves)) - 1
self.boardCopy = self.nextMoves[roll]
# 임의로 선택한 이동을 시뮬레이션 이동 목록에 추가한다.
simulationMoves.append(self.boardCopy)
# 플레이어가 둔 수(手)가 승리동작(hasWon)에 해당하면(=승리하면), 시뮬레이션 루프를 중단한다.
if droof.hasWon(self.boardCopy, player):
break
# 그렇지 않으면(=승리하지 않으면),
# 점수(score = self.boardsize * self.boardsize)에서 하나를 뺀다.(=점수에서 -1을 한다.)
score -= 1
# 다음 플레이어로 변환하고, 해당 플레이어에 대한 이동 옵션(getNextMoves)를 가져온다.
player = droof.getNextPlayer(player)
self.nextMoves = droof.getNextMoves(self.boardCopy, player)
# 시뮬레이션이 완료되면, 첫번째 동작(firstMove) 및 마지막 동작(lastMove)을 취한다.
firstMove = simulationMoves[0]
lastMove = simulationMoves[-1]
# 첫번째 동작(리스트 태형)을 텍스트로 변환(repr)하여
# evaluations 딕셔너리의 키(keys)에 저장한다.
firstMoveKey = repr(firstMove)
# 사용자가 한번 턴을 하면, 점수가 음수로 표시된다. (=AI가 게임에서 졌다는 의미)
if player == self.userPlayer and droof.hasWon(self.boardCopy, player):
score *= -1
# 평가점수에 대한 동작을 추가한다.
if firstMoveKey in evaluations:
evaluations[firstMoveKey] += score
else:
evaluations[firstMoveKey] = score
self.bestMove = []
self.highestScore = 0
firstRound = True
# 각 동작에 대해 모든 시뮬레이션이 수행되고
# 평가 점수가 가장 높은 동작을 기억한다(=저장한다)
for move, score in evaluations.items():
if firstRound or score > self.highestScore:
self.highestScore = score
# ast 함수를 사용하여 동작을 다시 게임상태로 변환
self.bestMove = ast.literal_eval(move)
firstRound = False
# 모든 평가(evalutions 딕셔너리) 중에서 점수(score)가 가장 좋은 동작을 반환한다.
self.board = self.bestMove
# return self.bestMove
# droof.tie_game_restart() # 무승부인지 확인
# 보드를 파이참의 결과창에 출력한다.
def printBoard(self, board):
firstRow = True
for index in range(self.boardSize):
if firstRow:
if self.boardSize == 3:
print(' 012')
elif self.boardSize == 5:
print(' 01234')
firstRow = False
print(str(index) + ' ' + ''.join(board[index]))
droof.tie_game_restart() # 무승부인지 확인
# 플레이어(you)가 다음 이동을 입력(input)하도록 요청한다.
def getPlayerMove(self, board, currentPlayer):
isMoveValid = False
while isMoveValid == False:
print('')
userMove = input('X,Y? ')
userX, userY = map(int, userMove.split(','))
if board[userY][userX] == '.':
isMoveValid = True
board[userY][userX] = currentPlayer
self.board = board
# return self.board
def game_again(self):
play_again = input("would you like to lpay again? (Y/N)").upper()
self.tie_game_list = []
self.currentPlayer = droof.getNextPlayer(self.currentPlayer)
if play_again == "Y":
if self.boardSize == 3:
print(' 012')
self.board = [list('...'), list('...'), list('...')]
droof.tictactoe_start_game()
elif self.boardSize == 5:
print(' 01234')
self.board = [list('.....'), list('.....'), list('.....'), list('.....'), list('.....')]
droof.tictactoe_start_game()
else:
sys.exit("종료")
def tie_game_restart(self):
# print(self.board)
if self.boardSize == 3:
for a, b, c in self.board:
self.tie_game_list.append(a)
self.tie_game_list.append(b)
self.tie_game_list.append(c)
elif self.boardSize == 5:
for a, b, c,d,e in self.board:
self.tie_game_list.append(a)
self.tie_game_list.append(b)
self.tie_game_list.append(c)
self.tie_game_list.append(d)
self.tie_game_list.append(e)
if self.tie_game_list.count(".") == 0:
print('tie-game!')
droof.game_again()
if self.boardSize == 3:
if self.tie_game_list.count("O")==5 and self.tie_game_list.count("X") == 4:
print('tie-game!')
droof.game_again()
elif self.boardSize == 5:
if self.tie_game_list.count("O")==13 and self.tie_game_list.count("X") == 12:
print('tie-game!')
droof.game_again()
self.tie_game_list = []
def tictactoe_start_game(self):
# 게임보드를 인쇄한다.
droof.printBoard(self.board)
# 게임보드에 남은 이동이 있는 동안 실행된다.
while droof.hasMovesLeft(self.board):
# 현재 플레이어가 사용자(you)인 경우, 사용자에게 이동(입력)을 요청한다.
if self.currentPlayer == self.userPlayer:
# print("213줄")
# board = droof.getPlayerMove(self.board, self.currentPlayer)
droof.getPlayerMove(self.board, self.currentPlayer)
else:
# 사용자가 AI인 경우, 다음 동작을 요청한다.
# print("216줄")
# board = droof.getBestNextMove(self.board, self.currentPlayer)
droof.getBestNextMove(self.board, self.currentPlayer)
# 플레이어가 '다음동작'을 입력하면, 업데이트된 게임 보드를 파이참에 출력한다.
print('')
droof.printBoard(self.board)
# 게임에서 승리여부를 검사하고, 이긴 플레이어를 출력한다.
if droof.hasWon(self.board, self.currentPlayer):
print('Player ' + self.currentPlayer + ' has won!')
droof.game_again()
# break
# 게임 승리여부가 결정되지 않으면, 다음 플레이어로 전환한다.
self.currentPlayer = droof.getNextPlayer(self.currentPlayer)
if __name__ == "__main__":
app = QApplication(sys.argv)
droof = Dennis_Roof()
droof.tictactoe_start_game()
app.exec_()
5. 마치며
pc와 틱택톡 게임하는 코드를 알아보았다. 긴글이 되었다. 4번(전체코드)를 파이참에서 실행해보면 생각보다 pc가 상당히 잘 둔다는 것을 알 수 있다.
MCTS의 개념이 추상적이긴 하지만, 그 개념이 대략적으로 머리 속에 들어온 느낌이다. 기존의 알고리즘인 1분봉 데이터 분석을 통해 수익을 내는 것은 어려울 것 같다. 그렇다고 MCTS가 반드시 수익을 보장해 주지도 않을 것 같다. 랜덤으로 끝까지 두어보고, 그 결과값 중 가장 좋은 값으로 진입한다는게 조금은 위험해 보인다.
그래도, 기존의 방법이 막혔다면 새로운 방법을 시도해보는 것도 나쁘지 않아 보인다. 기존의 방법에 매몰되어 정신적 혹은 경제적으로 스트레스 받기보다는, MCTS 개념을 공부하는 등 새로운 방법을 고민해보자.
'2. 해외선물 > 2-2. 해외선물 알고리즘 연구' 카테고리의 다른 글
| (해외선물 자동매매 알고리즘) (2) 역전파(backpropagation) 알고리즘 구현하기 (6) | 2024.02.08 |
|---|---|
| (해외선물 자동매매 알고리즘) (1) 역전파(backpropagation) 구현을 위한 numpy 이해하기 (2) | 2024.02.07 |
| (해외선물 자동매매 알고리즘) (2) 선형회귀분석 설명 (경사하강법) (2) | 2024.01.30 |
| (해외선물 자동매매 알고리즘) (1) 선형회귀분석 설명 (개념설명) (2) | 2024.01.29 |
| (해외선물 자동매매 알고리즘) (2) 틱택톡 만들기 (컴퓨터와 대결) (2) | 2024.01.01 |
| (해외선물 자동매매 알고리즘) (1) 틱택톡 만들기 (2) | 2023.12.31 |
| (해외선물 자동매매 알고리즘) (2) rsi 70이상, 30이하 넓이 구하기 (2) | 2023.12.24 |
| (해외선물 자동매매 알고리즘) (1) rsi 70이상, 30이하 넓이 개념 설명 (0) | 2023.12.23 |