qjatn0120

Minimax algorithm 게임의 진행 상태를 트리에서 정의할 수 있다. 현재 상태를 트리의 루트로 정의하자. 그리고 현재 상태에서 가능한 모든 행동을 해당 노드의 자식 노드로 정의할 수 있다. 만약 게임이 끝난다면 자식 노드는 존재하지 않는다. 아래는 틱택토 게임에서 3수 앞을 트리로 표현한 것이다. 내 말은 O, 상대의 말은 X이고, 내가 행동할 차례면 검은색 원으로, 상대가 행동할 차례면 회색 원으로 표시하였다. 위 트리에서 각 상태의 가치를 평가할 수 있다. 먼저 게임이 끝난 경우에는 가치를 쉽게 판단할 수 있다. 내가 이겼으면 1, 상대가 이겼으면 -1, 비겼으면 0으로 평가할 수 있다. 또한 행동할 수 있는 경우가 하나밖에 없다면, 다음 상태와 현재 상태의 가치는 똑같다고 할 수 있다. ..

게임이란? 에이전트를 구현하기 전에 먼저 게임을 어떻게 정의하고 구성하는지 알아둘 필요가 있다. 먼저 게임이 존재하기 위해서는 게임을 수행하기 위한 환경과 게임을 수행하는 주체가 있어야 한다. 마리오 게임으로 비교하자면, 마리오 게임 프로그램이 환경, 게임을 하는 사람이 주체에 해당한다. 주체는 본인의 행동을 환경에 전달한다. 행동은 마리오 게임이서 이동, 달리기 및 점프에 해당한다. 그러면 환경은 주체에게 행동 후의 상태와 행동으로 얻은 보상을 전달한다. 상태는 마리오 게임에서 현재 스테이지와 위치, 맵 모양 등에 해당하고, 점수는 행동으로 얻은 점수에 해당한다. 이때, 보상은 게임 시작부터 지금까지 얻은 총점수가 아니라 이 행동 하나만으로 얻은 점수로 정의한다. 또한 게임에서 가장 중요한 건 내 행동..

AI 게임 선정 포카전을 준비하기 위해 포스텍 알고리즘 동아리인 POSCAT의 인공지능 세미나를 진행하게 되었다. 이번 포카전에서 진행되는 게임으로 세미나를 진행하기에는 게임이 복잡할 것 같아 간단한 게임으로 세미나를 진행할 예정이다. 따라서 세미나에서 어떤 게임을 이용하여 연습할지를 정해야 했다. 포카전처럼 2인 대전 게임 형식이되 크게 복잡하지 않은 4목 게임(Connect 4)으로 선정하였다. State가 복잡하지 않고, action의 종류도 7가지로 적은 편이며 규칙도 간단하기 때문에 4목 게임으로 선정하였다. 4목 게임은 가로 7칸, 세로 6칸 크기의 판에서 진행되는 게임이다. 이 게임의 특징은 말을 놓을 '열'만 정할 수 있다는 점이다. 열을 정하고 나면, 해당 열의 빈칸 중 가장 아래에 있는..