장기의 게임이론 분류

보통 장기류의 게임은 컴퓨터가 생각 이상의 실력을 발휘합니다. 특히 비슷해보이는 바둑과 비교하면 더욱 그런데, 바둑 프로그램은 아마츄어 중수 수준도 어려운데 반해 장기계통의 게임에서 컴퓨터의 실력은 게임의 종류에 따라서는 인간을 넘어서는 수준에 도달한 것도 있습니다.

그 이유는 장기는 2인-제로섬-유한-확정-완전정보 게임으로 분류되어 오래전부터 인공지능의 연구대상에 적합한 것으로 인정되어 연구되었기 때문이기도 합니다. 같은 종류는, 체스나 장기, 쇼기 같은 차트랑가 류의 게임, 오델로, 오목 ^[각주:1], 위쌍성, 3목 ^[각주:2], Checkrer ^[각주:3]  등등이 있는데 이들은 이론적으로는 완전한 예측이 가능하고, 쌍방이 최선의 수를 사용한다면 반드시 선수필승, 후수필승, 무승부 등이 시작부터 정해진다는 것이 특징이고 모든 패턴이 파악되면 인간이 컴퓨터를 절대 이길 수 없는 경우까지 있죠.

2인-제로섬-유한-확정-완전정보 라는 말의 의미를 설명하자면,

"2인" - 플레이어가 2명인 게임으로, 게임이론에서 플레이어란 의사결정의 주체를 의미하는 말입니다. 예를 들어서 2:2 스타 게임이 있다면 그건 플레이어가 4명이며 고스톱은 3명이 되겠죠. 만약 2명 이상의 사람이 토의를 거쳐서 의사를 최종 결정하는 식의 구조라면 그건 한명으로 계산하게 됩니다.

만약 플레이어가 3명 이상이 되는 경우라면, 플레이어를 Pa, Pb, Pc로 나누었을 때, Pa의 1수가 Pa에게는 유리하더라도 다른 플레이어 Pb에게는 이익이 되고 Pc에게는 불이익이 되는 상황에서 Pc는 잠재적인 동맹자가 될 경우에 이것은 최선의 수가 되지 않습니다. 따라서 상관관계 때문에 최선의 수를 계산하는 데에 직접적인 이해이외의 것이 포함되기 때문에 자신의 대응수단이 복잡해지게 되죠.(예를 들어서 2:2 스타게임에서 자기만 살겠다고 방어하는 것이 안좋게 되는 것과 같습니다.)

"제로섬" - 플레이 중인 전원의 이익 합계가 항상 제로가 되거나 이익 합계가 일정한 수치가 되는 게임으로, 장기등의 제로섬 게임에서는 각각의 수 편성에 있어서 평가를 해서 이익표를 작성할때, 이익을 +1, 무승부를 0, 손해를 -1로 잡을 경우 계산하면 상대방의 손해가 곧 자신의 이익이 되므로 합계는 항상 0이 됩니다. 룰렛과 같은 게임에서는 플레이어 이득의 합계가 항상 0이 된다고 할 수 없기 때문에(두배 내기 등이 있으므로) 제로섬 게임은 아니죠. ^[각주:4]

어느 한쪽이 승리했을 경우에는 +1, 패한 쪽은 -1, 무승부라면 0가 되는 경우에도 게임의 득실표는 항상 0입니다. ^[각주:5] 죄수의 딜레머^[각주:6] 처럼 균형점이 최적점이 아니거나 치킨게임 ^[각주:7] 처럼 비겼을 경우가 양쪽 승리지만 파멸이 되어 최적점은 있으나 상대방 행동에 의존하는 등의 게임은 제로섬 게임이 아니고 이런 경우에는 예측이 훨씬 어렵겠죠.

"유한" - 게임에 있어서 각 플레이어의 가능한 수 편성 합계가 유한한 게임으로, 일반적으로 각종 보드게임과 카드게임은 상태의 변화가 이론상 유한하기 때문에 어떤 상태에서 다른 상태로 변했다가 다시 원 상태로 돌아오는 반복이 무한히 행해지지 않는한 유한게임이 됩니다. 한편 바둑의 경우에는 일본에서는 규정상 시간 제한등이 있지만 대국자가 합의하지 않으면 승부는 무한하게 계속될 수 있습니다. ^[각주:8]

유한하지 않은 경우에는 전략을 끝까지 예측할 수 없기 때문에 완전예측이 불가능합니다.

"확정" - 플레이어의 수 이외에 게임에 영향을 주는 우연한 요소가 없는 게임으로, 포커나 고스톱, 마작 등에서 처럼 랜덤으로 쌓여있는 패에서 뽑아오거나 다이스 류의 주사위 게임으로 랜덤이 들어가는 게임들은 불확정 게임으로 분류하게 된다. 각각 선후수를 결정할때에는 불확정성이 포함되어 있지만 근본적으로 바둑이나 장기 등은 확정게임으로 분류된다. ^[각주:9]

"완전정보" - 각 플레이어가 자신의 수차례에 지금까지의 모든 선택을 알고 있는 게임으로, 장기, 바둑, 체스 등의 보드게임에서는 각 플레이어가 다른 플레이어의 상황을 항상 완전히 파악할 수 있지만

1. 카드 게임 등에서는 일반적으로 상대방의 패를 자신이 볼 수 없고(또는 상대방의 패를 본다면 자신의 패를 볼 수 없고)

2. 가위바위보에서는 상대방과 동시에 의사표시를 하게 되므로, 상대측의 수를 보고 난 다음에 의사표시를 할 수 없으며

3. 해전 게임 등에서는 우연의 요소는 없으나 상대방의 수를 불완전하게 밖에는 파악할 수 없으므로 불완전 정보 게임으로 분류 됩니다. ^[각주:10]

완전정보 게임에서는 종료시의 상황에서 그 상태가 되는 1수 전의 상황을 비교함으로써 계속 유추를 해나가 유, 불리의 예측과 개선을 해나갈 수 있지만 불완전 정보 게임에서는 이러한 추론이 불가능합니다.

http://ja.wikipedia.org/wiki/%E4%BA%8C%E4%BA%BA%E9%9B%B6%E5%92%8C%E6%9C%89%E9%99%90%E7%A2%BA%E5%AE%9A%E5%AE%8C%E5%85%A8%E6%83%85%E5%A0%B1%E3%82%B2%E3%83%BC%E3%83%A0

1. 1899년에 쿠로이와 루이코에 의하여 종전의 규칙으로는 선수 필승이라는 것이 증명되었다. 이 이후 3-3 금지 규칙이 제정되었다. [본문으로]
2. 무승부가 된다. http://ja.wikipedia.org/wiki/%E4%B8%89%E7%9B%AE%E4%B8%A6%E3%81%B9 참고 [본문으로]
3. 1994년 컴퓨터가 세계챔피언에게 승리한 이후에 연구가 계속 진행되어 정석적인 조합에 대해서는 모든 분석이 끝났다. 2007년, 앨버트 대 연구팀에 의하여 무승부가 됨이 증명. 참조：Project - Chinook - World Man-Machine Checkers Champion (동연구팀의 사이트) 및 Checkers Is Solved - Schaeffer et al. 317 (5844): 1518  Science지 [본문으로]
4. 특히 잭팟이 있을 경우가 그렇다. [본문으로]
5. 가능한 조편성의 총수가 유한하지 않은 경우, 단순하게 0의 가산을 계속한다고 합계를 0이라고 판단할 수 없는 경우도 있지만, 일반적으로는 0이라고 생각할 수 있다. [본문으로]
6. http://ko.wikipedia.org/wiki/%EC%A3%84%EC%88%98%EC%9D%98_%EB%94%9C%EB%A0%88%EB%A7%88 [본문으로]
7. http://100.naver.com/100.nhn?docid=776526 [본문으로]
8. 중국이나 유럽의 바둑에서는 반복금지 규칙이 있으므로, 승부는 유한하다고 볼 수 있지만 무승부의 경우에는 재시합을 벌이기도 하기 때문에 무한하게 될 가능성도 있지만 일단은 유한하다고 할 수 있다. [본문으로]
9. 4인제 체트랑가에서는 다이스가 포함되어 있다. [본문으로]
10. 이런 분류로는 스타크래프트도 기본적으로는 불완전한 정보가 된다. 하지만 맵이 모두 밝혀져 잇는 상황이라면 제한적으로 완전정보 게임 [본문으로]