Conway's Game of life. 직역하면 인생게임. 영국의 수학자 존 호튼 콘웨이가 고안한 Cellular automaton 게임이다. Cellular automaton에 대해 궁금하다면 아래의 이전 포스팅 링크를 참조하자. 격자(grid)의 사각형 하나당 하나의 세포를 의미하고, 각각의 세포는 정해진 규칙에 따라 삶과 죽음이 결정된다. Game이지만, 우리가 흔히 생각하는 즐기는(?) 게임은 아니다. 초기 그림을 그려놓고 관찰만 하면 된다. 아래 사이트에서 플레이해볼 수 있다. bitstorm.org/gameoflife/ Play John Conway’s Game of LifePlay John Conway’s Game of Life in your browser.playgameoflife.com..
수학에서는 '존재성(Existence)' 과 '유일성(Uniqueness)'를 증명하는 것이 중요하다 말한다. 그도 생각해보면 당연한 것이, 엄청난 시간을 들여 어떤 문제를 풀고자 노력했는데, 알고보니 답이 없는 문제였던 것 만큼 비극적인 결말이 있을까. 혹은 열심히 해서 답을 얻었더니 답이 무수히 많은 문제였다면..? 물론 그 과정 속에서도 배움은 있었겠지만, 피하고 싶은 상황임에는 틀림없을 것이다. 시험이었다면 가차없이 점수를 빼앗기고 말겠지 그렇기에 수학에서 어떤 문제를 풀거나 증명하는 과정 전에는 존재성과 유일성을 증명하는 것이 중요하고, 당연한 과정인 것이 당연하다. 그 중에서, 이번에는 존재성을 증명하는 두가지 큰 갈래에 대하여 포스팅하려고 한다. 1. Constructive Existence..
Discrete Mathematics 수업 때 접하게 된 Game of Chomp. 처음에 rule을 몰랐을 때는 그냥 31게임의 외국 버전인가?라고 생각했는데, 닮아있는 듯 약간의 차이가 있다. Game of Chomp의 rule을 아래 그림과 함께 살펴보자. Rule 1. 두 명의 플레이어가 한 번씩 번갈아가며 플레이한다. 2. 각 플레이어는 자신의 차례가 오면 하나의 버섯을 선택하고, 그 버섯을 기준으로 오른쪽과 아래쪽 사각형 바운드 내의 버섯을 모두 가져간다. (그림 1 참조) 3. 가장 왼쪽 위의 버섯은 독버섯이고, 이를 먹는 자는 게임에 패배한다. 패배의 결말은 죽음 nim game이나 tic-tac-toe 처럼 한판이 엄청나게 짧다. 그냥 가볍게 생각 없이 하기 괜찮은 게임인 듯하다. 이런 ..
Strategy Stealing argument : 전략 훔치기 논증(?) 한국어로 번역된 용어를 찾기가 힘들어 직역할 수 밖에 없었다. 전략 훔치기 논증이라니,그 이름만큼이나 내용도 흥미롭다. 바로 알아보자 Definition> "Strategy stealing" argument 만약 게임에서 두 번째 플레이어(이하 후공자)에게 "항상 이기는 전략" 이 있다고 가정하면, 첫번째 플레이어(이하 선공자)는 이를 아래와 같은 방법으로 "훔칠 수" 있다. 선공자는 자신의 첫번째 턴에 의미없는 랜덤한 수를 둔다. 그 다음, 후공자의 첫번째 턴의 수를 토대로, "항상 이기는 전략"을 실행한다. 조금 더 쉽게 풀어서 이야기해보자. 일단 기본적인 가정은 >> 후공자에게 "항상 이기는 전략" 이 있다면 ..! 이 말인..
오토마타의 Special Case로, 폰 노이만이 제시한 개념이다. 일정한 규칙을 가진, 복잡한 물리적 과정을 모형화한 모델이라고 생각하면 되겠다. #1 Cellular Automaton은 격자에서 정의된다. Cellular Automaton은 규칙적인 격자 형태를 가지고 있는 공간에서 각 Cell(공간 혹은 격자 속 하나의 요소)에서 '유한한' '상태'를 가질 수 있다. Cellular automaton의 대표적 예시인 Conway's Game of Life에서는 삶(1)/죽음(0)이 '상태'에 해당되는 것이다. #2 이웃과의 상호작용 혹은 관계에 따라 '상태' 가 변화한다. 이웃이라 함은, 각 방향으로 한 칸 씩 떨어진 곳을 의미한다. 지뢰 찾기를 예시로 들자면, 각 사각형의 숫자는 '이웃' 사각형 ..
Combinatorial Game이란, perfect information 조건에서의 Sequential Game을 뜻한다. perfect information : 직역하면 '완전한 정보' 이다. 플레이어들이 자신의 턴에서 한 행동이 오픈되어 다음 플레이어가 그 정보를 숙지한 채 자신의 플레이를 이어나갈 수 있다. 고전 '게임이론' 하면 떠오르는 것이 아마 "죄수의 딜레마" 일텐데, 이는 대표적인 inperfect information 게임의 예시인 것이다. 다른 플레이어의 선택을 알 수 없기 때문에, 결국 전체적인 최선의 결과가 아닌 자신의 좁은 판단경계 안에서 의사결정을 하게 되는 딜레마가 발생하게 되는 것이다. 하지만, Combinatorial Game은 완전히 서로의 플레이정보를 알 수 있기 때문..
