[stfds] Noughts and crosses (Tic-tac-toe/빙고)

 

첫 학기에는 4개 과목을 배우는데

그중 제일 많은 시간을 할애하고 과제도 제일 많은

software technology for data science, 줄여서 stfds라고 함.

주로 python을 이용해서 닥치는 대로 과제를 하고 있다.

일주일에 하나씩 과제가 나와서

6주차까지는 첫 주 제외하고 매주 과제만 했던 것 같고

 

7주 차부터 11주 차까지는

과제 하나와 미니 프로젝트가 주어졌다.

이번 금요일 저녁 8시까지 미니 프로젝트를 제출해야 하는데

내일이면 아마 끝낼 수 있을 것 같아서 내일부터는 시험 준비를 해야지ㅜ

 

우선, 첫 번째로 했던 과제는

한국어로는 빙고라고 하는 것 같은데

Noughts and crosses라는 심플 AI를 구현하는 것이다.

Minimax background

우선 minimax 알고리즘은 게임이론 중 하나인데,

다른 사람과 경쟁할 때 어떻게 행동하는지 정형화하는 것이다.

기본적인 버전은 두 플레이어가 번갈아가면서 게임을 진행할 때,

제로섬 게임에서 가장 적합한 움직임을 찾는 것이다.

그중 deterministic and observable이라는 특징이 있는데

deterministic: 정확하게 어떤 행동의 결과를 알 수 있다는 것이고

observable: 두 플레이어가 모든 것을 알고 있다는 것이다.

 

우선 게임을 위해 판을 짜 보자.

print_state() 함수를 이용해서 nested loop를 이용해보았다.

여기서, input값으로 입력되는 state란,

3x3으로 구성된 튜플이다.

즉, 첫 번째 그림의 input은

((' ',' ',' '),(' ',' ',' '),(' ',' ',' '))

:아무것도 입력되지 않았기 때문.

 

두 번째, 결과를 미리 예측해서 계산하기

이길 것이라고 예상되는 플레이를 진행해서 미리 점수를 할당한다.

이 파트는 좀 더 최적화를 시키고

효율적으로 코드를 작성하고 싶었는데

31 줄이나 나왔다..

하드 코딩하는 것보다야 낫긴 하지만 아쉬움이 많이 남는 파트ㅜ

 

세 번째, 게임 실행하기(play function)

만약,

move1 = play(start, 1, 1, 'x') 이런 식으로 함수를 호출한다면,

이렇게 (1,1) 위치에 있는 x를 보여주어야 한다.

즉, 컴퓨터가 말해주는 위치에 장기짝을 놓는 격.

 

네 번째, 가능한 움직임 찾기(moves function)

주어진 상황에 맞게 그중 가장 적합한 위치를 보여주는 함수이다.

input: 주어진 state

output: (row, column)으로 이루어진 list in tuple이다.

 

enumerate 함수를 사용해서 인덱스와 값을 동시에 이용했다.

지금 보니까 왜 굳이 저렇게 여러 번 map과 tuple을 이용했다가

다시 list로 변환했는지 이유를 모르겠다. 하핳

그래서 결과를 찍어보면 tuple들로 구성된 list가 출력되는 것을 알 수 있다.

 

다섯 번째, minimax

그동안 만들었던 함수를 이용해서 예상 점수를 출력하기!

첫 player가 어떻게 시작하느냐에 따라서

결과가 달라지고 네 번째 가능한 움직임 중에서 맨 처음 값을 이용하여

예측할 수 있다.

 

마지막, perfect game

tic-tac-toe 혹은 빙고의 마지막!

자동으로 판을 입력하면 게임을 이용해서

누가 이길지 보여주기.

 

 

첫 과제다 보니 튜플, 리스트 등을 이용하고

for, if를 주로 이용하여 구현하는 것을 했었다.

 

minimax를 구현하는 게 처음에는 헷갈렸는데

원리를 알면 나쁘지 않은 듯!

처음에 다들 minimax로 연습하는 이유를 알 것 같았다.