MMSS 12일차 (8/3 Thu)

• Hackenbush Game: 그래프 위에서 진행되는 게임 중 아마 가장 복잡하면서도 연구가 많이 진행되어 있는 하켄부시 게임이라는 것에 대해 배우고, 그런디 수와 비슷하게 하켄부시 게임에서의 position을 수로 나타낼 수 있는지 알아보았다.
  • 하켄부시라는 주제의 존재에 대해서는 잘 알고 있었는데, 하켄부시 게임이 아무래도 수학 분야에서도 크게 유명하지 않고(그래프와 게임 이론을 모두 알아야 접할 수 있는 분야이기 떄문) 정보과학 쪽에서도 관련 문제가 출제되는 일이 매우 적다 보니(국내 문제는 딱 하나 있는 것으로 알고 있음) 적어도 우리나라 안에서는 하켄부시에 대한 자료가 사실상 없고 그렇다 보니 배우고 싶어도 배울 수 없는 주제 중 하나였다.
  • 때문에 이번에 처음 하켄부시를 배웠는데, 뭔가 엄밀헤게 모든 게임의 상태를 정의하는 것에 대해 배우지는 못했지만 그래도 하켄부시 게임의 position이나 게임의 승리 방법에 대해 배우니 매우 흥미롭게 수업을 들을 수 있었다.
• Cops and robber game on a graph: 마찬가지로 그래프 위에서 진행할 수 있는 흥미로운 게임 중 하나인 cops and robber 게임에 대해 배웠다.
  • 이 게임은 실제 게임(보드게임으로 나와 있는 것도 해본 적이 있고, 플레이스토어에 모바일 게임으로 등록되어 있는 것으로 알고 있다)으로도 나와있을 정도로 유명한 게임이다.
  • 그런데 의외로 최적으로 문제를 해결할 수 있는 알고리즘이 있지는 않다고 한다. 특정 그래프의 cop-number를 다항 시간에 구하는 것도 잘 없고, 뭔가 많은 연구가 진행되어 있지 않거나 매우 어려운 풀이를 사용해야 문제를 해결할 수 있는 것 같다.
  • Homework로 이런저런 문제를 풀면서 몇몇 작은 그래프 위에서 하켄부시와 cops and robber 게임을 하고 각 게임의 position을 확인하는 등 게임을 분석해보았다.
• 마지막 수업이라 수업을 들은 친구들끼리 이야기도 나누고 수료증도 받고 재미있는 시간을 보냈다.

이 정도면 마지막 수업까지 정말 알차게 수업을 들은 것 같다. 그래프 이론에 대해 이미 알고 있는 것, 새로운 것, 순수수학에 더 가까운 것들과 문제 해결 프로그래밍 등에서 응용하기 좋은 이런저런 아이디어나 성질들, 게임 이론이나 조합론적인 응용, 여러 가지 특수한 그래프와 그런 그래프들이 가지는 성질, 보다 일반적인 그래프가 가지는 특성과 각 특성 간의 - 어떨 때는 직관적이고, 가끔은 말도 안 되는 - 관계들 등 8일간 수많은 것들을 배웠다. 특히, 오늘 배운 하켄부시 게임의 경우 평소에 배우고 싶었지만 알려주는 곳이 없어서 잘 모르고 있던 개념이었다. 대충 주변 친구들에게 하켄부시가 수업 내용에 있다고 하면 부러워하는 친구들이 있을 정도이다. 그 정도로 정말 흥미로은 것을 많이 배우고 갈 수 있었던 것 같다. 앞으로 순수수학적인 그래프 이론을 접할 길이 다시 있을 지는 모르겠지만, 적어도 문제 해결 프로그래밍을 하면서는 그래프를 수도 없이 볼 것이라 생각한다. 이번에 들을 수업이 나중에 문제 푸는 등의 여러 가지 일에 큰 도움이 될 수 있을 것이라 생각한다.