-
파이썬, 미니맥스 알고리듬, 막대기 게임Python/파이썬 자료구조 알고리듬 2020. 11. 20. 20:18반응형
게임의 룰
단순한 룰의 게임을 하나 만들어 보겠습니다.
어디서 본 게임인데 이름을 모르겠네요.
막대기 게임이라고 해두죠.PS) 검색해 본 결과 이 게임은 NIM 게임 중 하나입니다. ex) 배스킨라빈스31 게임
- 2인용 게임입니다.
- 10개의 빈칸이 있습니다.
- 교대로 빈칸을 채웁니다.
- 한쪽부터 순서대로 차곡차곡 이어서 채워야 합니다. (=stack)
빈칸을 두는 것은 안됩니다. - 한 번에 1에서 3개까지 채울 수 있습니다.
쉬는 것(0개)은 안됩니다. - 마지막 칸을 채우는 사람이 이기는 겁니다.
코딩1 : 랜덤
말보다는 코드가 더 편한 것 같습니다.
알고리듬으로 처리해야 할 부분을
일단은 랜덤으로 두었습니다.from random import randint AI = True HUMAN = False class Game: def __init__(self): self.stick = '' self.choice_min = 1 self.choice_max = 3 self.stick_length = 10 # 간단히 테스트 하기 위해 10개만 def ai_play(self): num = self.find_block_num() print(f'AI가 {num} 칸을 채웠습니다.') self.fill(AI, num) def find_block_num(self): blocks = randint(self.choice_min, self.choice_max) return blocks def human_play(self): num = 0 while not self.choice_min <= num <= self.choice_max: num = int(input(f'{self.choice_min} - {self.choice_max} 사이의 숫자를 입력하세요:')) self.fill(HUMAN, num) def fill(self, player: bool, num): blocks = 'A' * num if player == AI else 'H' * num self.stick += blocks def display(self): print('1234567890') print(self.stick[:self.stick_length]) print() def is_end(self): if len(self.stick) >= self.stick_length: return True return False def ending(self): winner = 'AI' if self.stick[self.stick_length - 1] == 'A' else 'Human' print(f'{winner} win') def main(): g = Game() turn = AI while not g.is_end(): if turn == AI: g.ai_play() else: g.human_play() g.display() turn = not turn g.ending() if __name__ == '__main__': main()AI란 표현은 좀 많이 오버스럽...AI가 1 칸을 채웠습니다. 1234567890 A 1 - 3 사이의 숫자를 입력하세요:3 1234567890 AHHH AI가 1 칸을 채웠습니다. 1234567890 AHHHA 1 - 3 사이의 숫자를 입력하세요:1 1234567890 AHHHAH AI가 1 칸을 채웠습니다. 1234567890 AHHHAHA 1 - 3 사이의 숫자를 입력하세요:2 1234567890 AHHHAHAHH AI가 1 칸을 채웠습니다. 1234567890 AHHHAHAHHA AI win숫자 외의 입력의 경우도 처리해 주면 좋겠습니다
만...귀찮습니다..
try 문을 사용하거나 if 문을 사용하거나 while 문을 사용할 수 있겠죠..def human_play2(self): num = 0 while not self.choice_min <= num <= self.choice_max: try: num = int(input(f'{self.choice_min} - {self.choice_max} 사이의 숫자를 입력하세요:')) except ValueError: pass self.fill(HUMAN, num)파이썬에서 int로 안전하게 문자열을 정수형으로 변환하고 싶다면 isdecimal()을 쓰는 게 좋습니다.
* 파이썬에서 정수 판단 함수의 범위 isnumeric() > isdigit() > isdecimal()def human_play3(self): num = 0 while not self.choice_min <= num <= self.choice_max: input_str = '' while not input_str.isdecimal(): input_str = input(f'{self.choice_min} - {self.choice_max} 사이의 숫자를 입력하세요:') num = int(input_str) self.fill(HUMAN, num)파이썬의 not 연산자는 가독성이 좋은 것 같습니다.
'while not input_str.isdecimal():' 이 구문이
'while input_str is not decimal'로 읽히지 않습니까?
파이썬 재미있습니다. ㅎㅎㅎ경우의 수 확인
일단 틀은 잡았고, 이제 트리와 미니맥스 알고리듬만(?) 코딩하면 됩니다.
코딩을 하기 전에 경우의 수부터 확인해 봅시다.
def make_tree(stick: str, state: bool, count: int): if len(stick) >= 10 - 3: print(count, player[state], stick) return char = 'A' if state else 'H' for i in range(1, 4): temp = char * i make_tree(stick + temp, not state, count + 1) player = {True: 'AI', False: 'Human'} make_tree('', True, 0)총 105회 군요. 가볍게 처리할 수 있을 것 같습니다.
7 Human AHAHAHA 7 Human AHAHAHAA 7 Human AHAHAHAAA 6 AI AHAHAHH 6 AI AHAHAHHH 6 AI AHAHAAH 6 AI AHAHAAHH 6 AI AHAHAAHHH 5 Human AHAHAAA 6 AI AHAHHAH 6 AI AHAHHAHH 6 AI AHAHHAHHH 5 Human AHAHHAA 5 Human AHAHHAAA 5 Human AHAHHHA 5 Human AHAHHHAA 5 Human AHAHHHAAA 6 AI AHAAHAH 6 AI AHAAHAHH 6 AI AHAAHAHHH 5 Human AHAAHAA 5 Human AHAAHAAA 5 Human AHAAHHA 5 Human AHAAHHAA 5 Human AHAAHHAAA 4 AI AHAAHHH 5 Human AHAAAHA 5 Human AHAAAHAA 5 Human AHAAAHAAA 4 AI AHAAAHH 4 AI AHAAAHHH 6 AI AHHAHAH 6 AI AHHAHAHH 6 AI AHHAHAHHH 5 Human AHHAHAA 5 Human AHHAHAAA 5 Human AHHAHHA 5 Human AHHAHHAA 5 Human AHHAHHAAA 4 AI AHHAHHH 5 Human AHHAAHA 5 Human AHHAAHAA 5 Human AHHAAHAAA 4 AI AHHAAHH 4 AI AHHAAHHH 4 AI AHHAAAH 4 AI AHHAAAHH 4 AI AHHAAAHHH 5 Human AHHHAHA 5 Human AHHHAHAA 5 Human AHHHAHAAA 4 AI AHHHAHH 4 AI AHHHAHHH 4 AI AHHHAAH 4 AI AHHHAAHH 4 AI AHHHAAHHH 3 Human AHHHAAA 6 AI AAHAHAH 6 AI AAHAHAHH 6 AI AAHAHAHHH 5 Human AAHAHAA 5 Human AAHAHAAA 5 Human AAHAHHA 5 Human AAHAHHAA 5 Human AAHAHHAAA 4 AI AAHAHHH 5 Human AAHAAHA 5 Human AAHAAHAA 5 Human AAHAAHAAA 4 AI AAHAAHH 4 AI AAHAAHHH 4 AI AAHAAAH 4 AI AAHAAAHH 4 AI AAHAAAHHH 5 Human AAHHAHA 5 Human AAHHAHAA 5 Human AAHHAHAAA 4 AI AAHHAHH 4 AI AAHHAHHH 4 AI AAHHAAH 4 AI AAHHAAHH 4 AI AAHHAAHHH 3 Human AAHHAAA 4 AI AAHHHAH 4 AI AAHHHAHH 4 AI AAHHHAHHH 3 Human AAHHHAA 3 Human AAHHHAAA 5 Human AAAHAHA 5 Human AAAHAHAA 5 Human AAAHAHAAA 4 AI AAAHAHH 4 AI AAAHAHHH 4 AI AAAHAAH 4 AI AAAHAAHH 4 AI AAAHAAHHH 3 Human AAAHAAA 4 AI AAAHHAH 4 AI AAAHHAHH 4 AI AAAHHAHHH 3 Human AAAHHAA 3 Human AAAHHAAA 3 Human AAAHHHA 3 Human AAAHHHAA 3 Human AAAHHHAAA미니맥스 알고리듬
미니맥스 알고리듬으로 코딩합니다.
스틱의 길이는 14개로 늘렸습니다.
(변수의 값만 조절하면 됩니다.)(1~3이 선택 가능할 때 4의 배수 개의 빈칸만 남기면
게임을 마음대로 컨트롤할 수 있습니다.
이걸 게임 다 만들고 테스트하면서 알아버렸습니다. ㅠ,.ㅠ
미니맥스도 필요 없는 건디... )
출처: 위키백과 미니맥스는
마지막(무작정 내려갈 수 없다면 정해진) 노드까지 내려가서
마지막 레벨의 노드들을 평가 함수로 평가를 합니다.위 레벨에서는 아래 노드의 평가값 중 하나를 선택해야 하는데요.
이 때는 각 단계에서 합리적인 선택을 했으리라 가정을 합니다.
즉, min 레벨에서는 가장 낮은 값을 선택하고 max 레벨에서는 가장 높은 값을 선택합니다.만약 상대가 평가 함수에서의 합리적인 선택을 하지 않았다면,
그것은 상대에게 불리하게 작용하기 때문에,
보통 나에게 유리한 경우가 대부분입니다만...
가끔은 알파고와 이세돌의 사례처럼,
합리적이지 않다고 평가된 선택에 대한 준비가 안되었을 경우,
그 선택에 대한 처리가 너무 길어지면 좋지 않은 수가 나올 수도 있습니다..
게임 트리 작성
게임 트리를 만듭니다.
경우의 수가 많지 않기 때문에
승패가 결정되는 끝까지 갑니다.스틱이 다 차면 자식노드의 승패 여부를 평가합니다.
이기는 경우 1 점을 주고 지는 경우는 0점을 줍니다.이 점수를 상위 노드로 전달합니다.
상위 노드는 민, 맥스에 따라 가장 점수가 높거나, 낮은 노드를 선택합니다.
상위 노드는 선택한 하위 노드의 평가 점수를 더 상위의 노드로 전달합니다.
간략하게 스틱 길이 4, 최대 선택 2인 경우의 게임트리를 작성해 보겠습니다.
# 스틱 길이 = 4 # 최대_선택 = 2 ? max |o \x A:1 AA:0 min |o \x |x \o AH:1 AHH:1 AAH:1 AAHH:0 max |x \o |o |o AHA:0 AHAA:1 AHHA:1 AAHA:1 min |o AHAH:0코딩2: 미니맥스
읽기 편하도록 minimax함수에서 스틱 길이를 넘는 선택을 막지 않았습니다. (결과는 같습니다.)
AI = True HUMAN = False class Game: def __init__(self): self.stick = '' self.choice_min = 1 self.choice_max = 3 self.stick_length = 14 self.guide = ''.join([str(x)[-1] for x in range(1, self.stick_length + 1)]) def ai_play(self): num, score = self.minimax(self.stick, True) print(f'AI가 {num} 칸을 채웠습니다. {score}') self.fill(AI, num) def minimax(self, stick, max_player): blocks_num = 0 if len(stick) >= self.stick_length: return (0, 1) if stick[self.stick_length - 1] == 'A' else (0, 0) if max_player == AI: value = float('-inf') for blocks in range(self.choice_min, self.choice_max + 1): _, score = self.minimax(stick + 'A' * blocks, False) if score > value: value = score blocks_num = blocks else: value = float('inf') for blocks in range(self.choice_min, self.choice_max + 1): _, score = self.minimax(stick + 'H' * blocks, True) if score < value: value = score blocks_num = blocks return blocks_num, value def human_play(self): num = 0 while not self.choice_min <= num <= self.choice_max: input_str = '' while not input_str.isdecimal(): input_str = input(f'{self.choice_min} ~ {self.choice_max} 사이의 숫자를 입력하세요:') num = int(input_str) self.fill(HUMAN, num) def fill(self, player: bool, num: int): self.stick += 'A' * num if player == AI else 'H' * num def display(self): print(self.guide) print(self.stick[:self.stick_length]) print() def is_end(self, stick): if len(stick) >= self.stick_length: return True return False def ending(self): winner = 'AI' if self.stick[self.stick_length - 1] == 'A' else 'Human' print(f'{winner} win') def main(): g = Game() turn = AI print(f'막대의 길이는 {g.stick_length}입니다.') if turn == HUMAN: g.display() while not g.is_end(g.stick): if turn == AI: g.ai_play() else: g.human_play() g.display() turn = not turn g.ending() if __name__ == '__main__': main()'4의 배수'개의 빈칸을 남기면 이긴다는 룰을 알려주지도 않았는데 잘 찾아내는군요.. ^^ 흐뭇...
AI가 2 칸을 채웠습니다. 12345678901234 AA 1 - 3 사이의 숫자를 입력하세요:1 12345678901234 AAH AI가 3 칸을 채웠습니다. 12345678901234 AAHAAA 1 - 3 사이의 숫자를 입력하세요:3 12345678901234 AAHAAAHHH AI가 1 칸을 채웠습니다. 12345678901234 AAHAAAHHHA 1 - 3 사이의 숫자를 입력하세요:1 12345678901234 AAHAAAHHHAH AI가 3 칸을 채웠습니다. 12345678901234 AAHAAAHHHAHAAA AI win간단한 가지치기
게임트리 보시면 아셨겠지만..
이 게임에서는 max에서 score == 1, min에서 score == 0을 찾으면,
for문을 계속 진행하지 않아도 결과는 같습니다.def minimax(self, stick, max_player): blocks_num = 0 if len(stick) >= self.stick_length: return (0, 1) if stick[self.stick_length - 1] == 'A' else (0, 0) if max_player == AI: value = float('-inf') for blocks in range(self.choice_min, self.choice_max + 1): _, score = self.minimax(stick + 'A' * blocks, False) if score > value: value = score blocks_num = blocks if score == 1: # break # else: value = float('inf') for blocks in range(self.choice_min, self.choice_max + 1): _, score = self.minimax(stick + 'H' * blocks, True) if score < value: value = score blocks_num = blocks if score == 0: # break # return blocks_num, value반응형