four in a row, min max 알고리즘, Alpha beta pruning 에 대하여
안녕하십니까. 제 개인 컴퓨터에 있는 자료를 정리하다 보니, 학부 3학년때 제출 하였던 인공지능 과제를 찾게 되어서 블로그 포스팅 합니다. 코드 링크 : https://github.com/Myeongjoon/examples/blob/master/artificial%20intelligence/four_in_a_row.html (사실 코드는 대부분 짜지 않았다는 점..) 해당 인공지능 수업을 할 당시는 구글에서 알파고를 발표하였던 그시기였기 때문에 인공지능 수업이 핫하였고, 그중 게임 이론이 중심이었습니다. 인공지능에서 쉽게 다룰 수 있는 내용이 트리 구조를 통한 게임 인공지능 알고리즘이었고 자연스럽게 텀 프로젝트는 four-in-a-row를 통한 리포트가 되었습니다. Four In A Row four in a row 라는 게임은 간단한 게임입니다. 테트리스 처럼 위에서 아래로 돌이 떨어지는 게임이고, 상대방과 내가 번갈아서 한번씩 돌을 사용 합니다. 위로 4줄, 옆으로 4줄, 대각선으로 4줄 어떤식이든 4개로 이루어진 줄을 하나를 만들면 게임에서 이기게 됩니다. 위의 사진에서 보면 파란색 돌 기준으로 대각선 하나가 4개의 돌로 되어 있고, 따라서 파란색 돌의 승리 입니다. Min Max 알고리즘 위의 게임의 인공지능을 구현하는데에 있어서 여러 방법이 있겠지만 수업시간에서는 민맥스 알고리즘을 중심으로 진행하였습니다. 민맥스 알고리즘은 최대 n번째 이후까지의 수를 예측을 합니다. 이는 두 플레이어가 최선의 수를 두는 것을 가정을 하며, 결국 누군가가 이기려면 그사람은 이길 경우가 가장 높은 수를 두고, 반대로 상대의 수를 예측을 하면 상대가 이길 경우가 가장 낮은 수를 예측을 해야합니다. 아래 사진은 Geekforgeeks 라는 사이트에서 가져왔습니다. 아래는 3개의 수까지 예측을 하는 경우 이며, 마지막 노드의 숫자들은 해당 경우의 수에서의 점수 입니다. 점수를 매기고 난 후에는 차례로 내차례에는 최대...
