헥스

헥스(Hex)는 1942년에 피에트 하인(, 1905년 12월 16일~1996년 4월 17일)에 의하여 처음 고안되고, 1948년에 존 내시(, 1928년 6월 13일~)에 의해 재고안된 게임이다. 이 게임은 처음에 존() 또는 내시()로 불리다가 1952년, 게임회사 파커 브라더스()에서 상업적으로 판매되면서 헥스라는 이름이 붙게 되었고, 이 이름이 일반적으로 사용되고 있다.

방법 
헥스는 육각형으로 이루어진 마름모 형태의 보드 위에서 두 명의 참가자에 의해 진행된다. 일반적으로 이 게임에는 11×11 크기의 육각형으로 이루어진 보드가 사용된다. 각 참가자는 서로 다른 지정된 색을 사용하여 게임을 진행하는데, 빨간색과 파란색, 혹은 검은색과 흰색 등이 주로 사용된다. 보드에서 서로 마주보고 있는 두 변은 같은 색으로 정해져 있고, 이 두 개의 변이 한 명의 참가자에게 배정되고, 나머지 두 변은 다른 참가자에게 배정된다. 두 참가자는 차례대로 보드의 육각형 위에 자신에게 배정된 색의 칩 등을 이용하여 그 칸을 자신의 것으로 만들 수 있다. 단, 다른 참가자가 먼저 차지한 육각형을 다시 빼앗는것은 불가능하다. 이러한 방법으로 게임을 진행하여 먼저 자신에게 배정된 마주보는 두 변을 자신의 색으로 잇는 참가자가 승리하게 된다.

이론 및 전략 
게임판의 가로와 세로의 육각형의 수가 같은 경우, 두 번째로 하는 참가자에게 그가 반드시 승리하게 되는 '승리전략'이 존재한다고 가정하자. 그렇다면, 첫 번째 참가자는 임의의 어느 한 육각형에 자신의 칩을 두고, 자신이 두 번째 참가자인것처럼 게임을 진행하면 된다. 만약, 첫 번째 참가자가 두 번째 참가자의 '승리전략'을 따르는 과정에서 처음에 자신이 차지한 육각형이 필요한 경우가 생긴다면, 다른 관계없는 육각형에 자신의 칩을 두고 그 전략을 계속 실행할 수 있다. 이러한 방법을 따르면 첫 번째 참가자가 게임에서 승리하게 된다. 이는 두 번째 참가자에게 '승리전략'이 존재한다는 것에 대해 모순이다. 따라서 이 게임은 먼저하는 사람이 일반적으로 더 유리하다.

또한 헥스 게임에서는 무승부가 나올 수 없다. 예를 들어, 어떤 참가자가 왼쪽 변과 오른쪽 변을 파란색으로 이어야 한다고 가정해보자. 이 때, 왼쪽 변과 연결되어있는 모든 파란색 육각형의 집합을 'B'라고 하자. 만약, 'B'에 의해 왼쪽 변과 오른쪽 변이 이어진 길이 있다면, 이 길에 의해서 빨간색의 길은 막히게 되고, 게임은 파란색의 참가자의 승리로 끝이 난다. 만약 왼쪽 변과 오른쪽 변이 연결되지 않았다면, 'B'의 오른쪽에 있는 육각형들은 빨간색이여야만 하고, 이 빨간색의 육각형들은 위쪽 변과 아래쪽 변을 연결하는 길을 만들게 되어, 빨간색의 참가자가 승리하게 된다.

각주 

보드 게임
종이-연필 게임
PSPACE-완전 문제