大会名称
2010年 情報科学技術フォーラム(FIT)
大会コ－ド
F
開催年
2010
発行日
2010/8/20
セッション番号
14
セッション名
組合せパズルの数理とコンピュテーション
講演日
2010/9/9
講演場所(会議室等)
第3イベント会場
講演番号
14-2
タイトル
ハラリィの一般化三並べの世界
著者名
伊藤　大雄, 
キーワード
抄録
三並べという二人ゲームは、「三目並べ」や「まるばつ」等、地方によって呼び名は色々かもしれないが、誰しも一度は見たことがあるだろうし、子供のころに遊んだ記憶がある方も多いと思う。20世紀後半に活躍した数学者フランク・ハラリィはこれを一般化して、数学的にたいへん面白い問題を作り上げた。正方形のセルを辺と辺、頂点と頂点が合わさるようにいくつか繋げてできた図形（ポリオミノ）を「動物」と呼ぶ。先手と後手とが交互に碁盤目状の盤面のセルを一つずつ選んでいき、自分の選んだセルによって、事前に指定されている動物（ただし回転と裏返しも認める）を先に作った方を勝ちとするゲームである。両者が最前を尽くしたときに先手が勝つ様な動物のことを「勝ち型」、そうでないものを「負け型」と呼ぶ。本講演では、この問題に関する既存研究や未解決問題を紹介する。