connect4게임의 AI를 만들어보자

Posted by 이창권 on May 01, 2019

2019 1학기 김현철 교수님의 인공지능 수업을 듣게 되었습니다. AI에 사용하는 여러가지 인공지능 기법을 배우게 되었고 그 중 min-max algorithm을 실제로 구현해 보기로 하였습니당.

간단한 게임을 선택해야할 것 같아서 connect4를 선정하게 되었습니다. 구글에 참고할 만한 자료가 많이 있는 것도 선정한 이유였습니다. 게임 룰은 column을 선택해서 해당 column의 맨 위에 자신의 돌을 놓을 수 있습니다. 대각선이나 가로, 세로로 4개를 연속해서 채우면 이기게 됩니다.

image

min-max algorithm은 기본적으로 hueristic을 1개 선정합니다. heuristic을 이용해 나의 차례에는 내 점수가 최대가 되게 상대의 차례에는 내 점수가 최소가 되게 한다는 가정을 하고 Tree를 만들어 정해놓은 depth만큼 탐색을 해 나의 점수가 최대가 되는 노드로 돌을 두게 합니다.

작동 방식은 아래와 이미지를 보면 이해가 더 명확합니다.

image

image

만든 AI가 depth를 5를 넘기면 시간이 너무 많이 걸리게 됩니다. 이때 alpha-beta pruning을 이용해서 탐색 필요가 없는 노드들은 가지치기를 해서 시간을 줄여줍니다. 가지치기를 적용하니 depth 10까지도 1분 안에 해결됩니다.

image

만든 connect4_ai의 github 주소는 다음과 같습니다.

https://github.com/changgunyee/connect4