研究集会
第８回日本組合せゲーム理論研究集会（2024年8月23日・24日）
第８回日本組合せゲーム理論研究集会を2024年8月23日・24日に名古屋大学情報学研究科棟第一講義室で実施しました。
（※8月20日追記：参加申込いただいた皆様にメールで諸連絡をお送りしました。）
（※8月21日追記：セッション５の時間を修正しました。これに伴い、以降のスケジュールが10分早まりました。議論セッション２の終了時間が確定しました。会場案内のリンクを貼りました）
日時：2024年8月23日（金），24日（土）
共催：名古屋大学大学院情報学研究科
場所：名古屋大学情報学研究科棟第一講義室（地図はこちら）
参加費：不要
参加申込：締め切りました
（※ 発表申込締切：8月13日 参加申込締切：8月19日）
現地参加できない方のために、聴講のみ可能なオンライン配信を計画しています。
事情によりオンラインでの発表を希望される場合は参加申込フォームにてご連絡ください。
＜プログラム＞
8月23日（金）
10:00 開場
10:20 開会
10:30－11:50 セッション１ 20分ー30分ー30分
望月悠人「マンカラの超弱解決とその可視化」
佐藤優「不偏ゲーム化したマンカラについて」
安福智明「伴課ゲームの理論を用いた連続フック引き抜きゲームの変種の解析」
13:00－14:20 セッション２ 20分ー30分ー30分
前山和喜「一松信と組合せゲーム理論研究 -日本組合せゲーム理論研究の起源を辿る-」
森脇悠斗「無限制限ニムについてmory数列を用いた考察」スライド
山下貴央「Wythoff Nimの変種とその逆形」スライド
14:35－15:55 セッション３ 30分ー20分ー30分
荻沼弘実「Link Stonesの導入と基本的性質」スライド
篠田正人「一般グラフ上のLinkStones」スライド
橋本健吾「整数とスターのsequential compound」
15:55ー 議論セッション１（最大19時くらいまで）
8月24日（土）
10:00 開場
10:20－11:50 セッション４ 30分ー30分ー30分
今村翔吾「複数パスグラフにおけるハッピーセットゲームの解析」
石垣尚斗「完全グラフ・パス・サイクルにおけるTronのゲーム値」
吉渡叶「様々な非不偏しりとりとその全象性」
13:00－14:10 セッション５ 30分ー20分ー20分
末續鴻輝「Maxニムとヨセフス問題の対応関係の様々な例」
村上蒼「A restricted amalgamation nim」
菊地遼「Amalgamation nimとSteiner Loop」
14:25－15:40 セッション６ 30分ー45分
木村俊一「両プレイヤーの着手が同じpartizan subtraction nimについて」スライド
稲津大貴「両プレイヤーの着手が同じpartizan subtraction nimのpartizan quotientについて」
15:40 中締め
15:50ー 議論セッション２（最大19時くらいまで：出口が18時30分ごろに閉まるため、夜間出口の方をご利用いただきますようお願いいたします ）
※組合せゲーム理論の基本事項を共有するチュートリアルセッションをこれまで設けてきましたが、本理論の理解が広がっていることや、新しい本の出版状況などを鑑み、今回はチュートリアルセッションを設定しないことになりました。上記の内容にご不安がある参加者の方がいらっしゃいましたら、２年前に開催されました第６回日本組合せゲーム理論研究集会のチュートリアルセッションで用いたスライドが残っておりますので、こちらをぜひご参照いただければと思います。
・不偏ゲームについてはこちら
・非不偏ゲームについてはこちら
また、共立出版より販売中の「組合せゲーム理論の世界 －数学で解き明かす必勝法－」第１章から第５章にも上記の内容は詳しく解説されておりますので、よろしければご参照ください。
各ご発表者の皆様におかれましては組合せゲーム理論の基本的な知識（グランディ数、ゲームの値、など）を聴講者にご理解いただけているものとして、ご発表を組み立てていただければと思います。
＜発表詳細＞
１．マンカラの超弱解決とその可視化
発表者：望月悠人
共著者：佐藤優，矢島雄河，前山和喜，田中輝雄，藤井昭宏
キーワード：非不偏ゲーム, マンカラ, 超弱解決, コンピュータ実験, 可視化
概要：本研究では，ボード上の穴に配置された複数の石を動かし，得点を競う古典的な２人用ボードゲームであるマンカラの超弱解決を試みた．マンカラは世界各地で遊ばれており，地域によってルールセットが多様である．そのため，ポケットとストアの個数や配置，石の個数，４種類の特殊ルールをパラメータとして設定することで，多様なルールセットを実現した．その複雑な構造をしたゲームの局面の遷移を直感的に理解できるように，ゲーム木を用いて局面の可視化した．その上で，大規模なコンピュータシミュレーションによって，マンカラの超弱解決を実現した．
２． 不偏ゲーム化したマンカラについて
発表者： 佐藤優
共著者：望月悠人，矢島雄河，前山和喜，藤井昭宏，田中輝雄
キーワード：不偏ゲーム, マンカラ, グランディ数, HPC, ゲーム木
概要：本研究では，非不偏ゲームであるマンカラのルールを一部変更することで不偏ゲーム化し，そのゲームのグランディ数の解析した．多様な盤面について扱うため，ポケットとストアの個数や配置，石の個数をパラメータとして，盤面を変化させて解析を行った．盤面のパラメータによっては，計算時間や使用メモリ量が膨大になってしまう．それらを削減するために，計算済みの部分をメモ化する，盤面の情報をbit列で保持するなどの対策を取った．
解析の結果，ポケットが2個以下，ストアが複数個の盤面のグランディ数を求めることができた．また最も小さいケースとして，ポケットが1個，ストアが複数個の盤面のグランディ数を直接求める式を導出できた．
３． 伴課ゲームの理論を用いた連続フック引き抜きゲームの変種の解析
発表者： 安福智明
共著者：末續 鴻輝，多田 将人
キーワード：伴課ゲーム，連続フック引き抜きゲーム
概要：本研究では，連続フック引き抜きゲームの変種である強制的連続フック引き抜きゲームと連鎖的連続フック引き抜きゲームについて，伴課ゲームの理論を用いて解析を行った．従来の不偏ゲームにおけるSprague-Grundy数（グランディ数）の理論を用いた解析よりも見通しの良いものとなったため，その研究成果について報告する．
４． 一松信と組合せゲーム理論研究 -日本組合せゲーム理論研究の起源を辿る-
発表者： 前山和喜
共著者：
キーワード：日本組合せゲーム理論研究史，応用数学史，コンピュータ数学
概要：日本における応用数学の大家である一松信氏は，1960年代に石取りゲームなどの組合せゲーム理論研究を扱い，本分野の名著である『石とりゲームの数理』（1968）を出版した．本発表では，一松信氏の書庫の整理を通じて得られた当時のノートや原稿について紹介し，日本におけるゲーム理論研究の嚆矢としての一松の数学的視座を検討する．
５． 無限制限ニムについてmory数列を用いた考察
発表者： 森脇 悠斗
共著者：木村俊一
キーワード：制限ニム グランディー数 周期性 加法的周期性
概要：昨年8月の「第7回日本組合せゲーム理論研究集会」および今年3月の「広島・岡山代数学セミナー」で``制限ニムから発見された数列''として紹介した、(有限の)除去可能数集合に対する制限ニムのG数列の周期を除去可能数に追加していくということを繰り返して各周期を並べた数列をこの度『mory sequence』と名付けた。これは初期の除去可能数集合によって明快なパターンが見えるものとカオスとも呼べるものとに二極化していることが数値実験により確かめられており、現在検証が進行中である。
さて、追加していく各周期は必ず相異なるため、数列の全ての項を除去可能数に追加すると(可算)無限集合となる。
除去可能数集合が有限集合の場合、G数列は必ず周期的となるのはよく知られており、mory数列の定義においても根幹となる性質である。
それに対し、除去可能数集合が無限集合の場合のG数列については、周期性や加法的周期性を持たないものも知られているし、逆にそれらを拡張した準加法的周期性という規則性を持つことが確認された例もある。
本発表では、mory数列から上のようにして得られる(と予想される)無限除去可能数集合に対する制限ニムのG数列を紹介する。
また、上で触れた準加法的周期性について木村先生と共に提唱している「除去可能数集合が周期的ならば制限ニムのG数列は準加法的周期的となる」という予想を、実例を交えて紹介する。
６． Wythoff Nimの変種とその逆形
発表者： 山下 貴央
共著者：木村 俊一
キーワード：不偏ゲーム，Nim，Wythoff Nim，必勝法
概要：Wythoff Nimとその変種について以下のトピックについて説明を行います。
(i) 先行研究として、通常のWythoff Nimにおいて、通常のNimに両方から石の差がc個(cは非負整数)以下なら両方から取って良い着手 (c-Wythoff Twist) を加えた「c-Wythoff Nim」について、特にcが1以上の時にグランディ数が1の集合と逆形のP-positionが一致する。
(ii)「1つの山からa個以上石を取り、もう一方の山に石をb個以上戻すが、石の総数は着手ごとに減らさなければならない」(a,b)-Triangular Nimのc-Wythoff Twist(本発表ではこのゲームを(a,b,c)-Nimと呼ぶ)の逆形のP-positionも、c≥1ならグランディ数が1の局面集合が逆形のP-positionと一致する。
(iii)その他、(a,b)-Yama Nimのc-Wythoff Twistで面白い現象を発見したので、紹介する。
７． Link Stonesの導入と基本的性質
発表者： 荻沼 弘実
共著者：
キーワード：不偏ゲーム，ゲームの選択和，ゲームの弱解決
概要：２人のプレイヤーが長方形の盤面上に石を置くゲームの導入を行う。各手番でプレイヤーは、既に石のあるマスの隣接マスをいくつか選んで、石を置く。最後のマスに石を置いたプレイヤーが勝ちとなる、正規形ゲームである。今回は、盤面が３×Ｎサイズまでの場合について、先手後手の勝敗を考察した。
８． 一般グラフ上のLinkStones
発表者： 篠田 正人
共著者：
キーワード：不偏ゲーム、グラフ理論、ゲームの選択和
概要：盤面に２人のプレイヤーが石を置いていくゲームとして新たに提案するLinkStonesを、さらに有限グラフ上のゲームとして一般化し、初歩的ないくつかの性質を紹介する。
９． 整数とスターのsequential compound
発表者： 橋本 健吾
共著者：
キーワード：Sequential Compound，ゲームの値，整数，スター
概要：（短い）ゲームG, Hのsequential compound G→Hは，プレイヤーがGに選択肢を持つ場合はGに着手し，そうでない場合はHに着手してGを切り捨てるという規則でプレイされるゲームである．有限個のゲームのsequential compound G_1 → G_2 → ... → G_nについて，各G_iが整数またはスターである場合のゲームの値を示す．
１０． 複数パスグラフにおけるハッピーセットゲームの解析
発表者： 今村翔吾
共著者：江藤宏, 宮野英次, 小野廣隆, 木谷裕紀, 斉藤寿樹
キーワード：グラフ理論, グラフクラス, グラフゲーム
概要：複数の独立したパスグラフにおけるハッピーセットゲームの先手後手の戦略を考える.
１１． 完全グラフ・パス・サイクルにおけるTronのゲーム値
発表者： 石垣尚斗
共著者：吉渡叶，小野廣隆
キーワード：Tron，ゲーム値，完全グラフ，パス，サイクル
概要：Tronは無向グラフ上で行われる組合せゲームである．初期局面では青トークン(先手番)と赤トークン(後手番)がそれぞれ異なる頂点上にあらかじめ配置されており，手番のプレイヤは自分の色のトークンを隣接する頂点へと移動させる．一度トークンが置かれたことのある頂点にはトークンを置くことができず，自分の手番でトークンを動かせなくなったプレイヤの負けである．このゲームは一般にはNP困難かつco-NP困難であること，有向グラフ版はPSPACE完全であることが知られている．また初期局面が木グラフである場合はO(n)時間の必勝判定アルゴリズムが提案されている．
本研究では，完全グラフ・パス・サイクルにおけるTronのゲーム値の特徴付けを与える．
１２． 様々な非不偏しりとりとその全象性
発表者： 吉渡叶
共著者：小野廣隆
キーワード：全象，一般化しりとり
概要：全象なルールセットとは，任意のゲーム値を表現できるルールセットである．現在知られている全象なルールセットは全てPSPACE完全であり，全象性とPSPACE完全性の関係について注目されている．
本研究では，非不偏しりとりとして分類される9つのルールセットについて，その全象性を示した．特にそのうち8つのルールセットは木に限定しても全象であり，これらは必勝判定が多項式時間で可能な初の全象なルールセットである．残る一つは点彩色型トロンという古くから知られるグラフゲームの一般化である．他のトークン移動型ゲームの全象性の証明が両プレイヤーがどのトークンも自由に動かせることを利用しているのに対し，点彩色型トロンは各プレイヤーは自分の色のトークンしか動かせないという制約のため新たな証明のフレームワークが必要となる．本研究では，2種のトークンを活用した証明を与えるとともに，全象性における色付き点・色なし点の影響についても議論する．
１３．Maxニムとヨセフス問題の対応関係の様々な例
発表者： 末續鴻輝
共著者：眞部光，宮寺良平，高橋祥英
キーワード：Maxニム，ヨセフス問題，グランディ数
概要：Maxニムは取ってよい石の個数が，全体の石の総数に応じて変わるニムであり，ヨセフス問題は円形に並んだ人を，一定の規則で順番に消していって，最後に誰が残るかを考える問題である．あるMaxニムのグランディ数を見ることで，特定のヨセフス問題において誰がいつまで生き残るかを知ることができるということがこれまで知られていたが，我々はその結果をさらに拡張し，任意の取り順のヨセフス問題とそれに対応するMaxニムの関係を見出した．本発表では，この成果によりどのようなMaxニムとヨセフス問題の関係が見えるのかを紹介する．
１４． A Restricted Amalgamation Nim
発表者： 村上蒼
共著者：眞部光, 宮寺良平
キーワード：Amalgamation Nim, restricted Nim
概要：Amalgamation Nimとは、古典的なn山の石取りゲームにおいて、一つの山を選んでそこから石を取るという通常のルール以外に、２つの山を選んでそれを合併させるというルールを追加したものである。これまでの先行研究によると、山の個数がn=2の場合は、amalgamation NimのP-positionは、伝統的な（山の合併がない）NimのP-positionと同じであるが、山の個数nが3以上になるとP-positionを表す公式は発見されていない。私たちは、１つの山から石を取るとき、取れる個数は、その山の石の個数の半分以下という条件をつけた２つ山のrestricted Nimと、そのrestricted Nimに石の山の合併(amalgamation)を追加した、 restricted amalgamation Nimを比べてみた。結果としてわかったことは、山の個数n=2の場合、restricted amalgamation NimのP-positionの集合は式で表すことができるが、restricted NimのP-positionとrestricted amalgamation Nimはかなり違っており、しかもn=2のrestricted amalgamation NimのP-positionを求めるためには、３変数の指数を含んだ不定方程式を解くという操作が必要になり、組合せ的な整数論的な面白さがあることがわかった。
１５． AMALGAMATION NIM と Steiner Loop
発表者： 菊地 遼
共著者：
キーワード：AMALGAMATION NIM, Steiner Loop
概要：AMALGAMATION NIMの3山のP局面(x,y,z)についてz = x◦yとすると，この演算はSteiner Loopとなる．これは自然数全体に対する基本的に非結合的な代数構造だが, (F_2)^3の群構造が点在することを見つけたので紹介する．
１６． 両プレイヤーの着手が同じPartizan Subtraction Nim について
発表者： 木村俊一
共著者：井上博裕、門脇慎之介、川上滉太 、稲津大貴
キーワード：Partizan Subtraction Nim、逆形商、Parity Partizan Quotient、ケイレス
概要：両プレイヤーが同じ着手ができるが、終了局面が何通りかあって、どこで終わるかによって勝敗を決めるタイプの Partizan Subtraction Nim について紹介する。主に、除去可能数集合Sが２以上の自然数のみからなり、最後に残った石の個数が偶数個ならLが、奇数個ならRが勝ちとするルールを扱う。
（１）例えばSが２を含む１山ニムの場合、最後が０で終わればLが、１で終わればRが勝ちになるので、LとRのどちらが特に有利ということはなさそうに思えるが、実際には L-position が極めて多く、Sの元を増やしていくと８割以上のSにおいて、ある番号から先が全てL局面になる、という現象が観察される。その理由の一つとして、あるSに対して石の個数n個の初期局面がR局面であれば、n+1個およびn-1個の初期局面がともにL局面となることが証明され、Lの方が圧倒的に多い理由のひとつとしてあげられる。
（２）石の山を複数個にしても残った石の個数の偶奇で勝敗が決められるので、逆形商のアナロジーとして Parity Partizan Quotient を定義することができる。簡単なケースについて計算を紹介する。これは Partizan ゲームでの逆形商のモデルケースとしても使えると期待される。より複雑な例については、稲津大貴氏が詳しく紹介する予定である。
１７． 両プレイヤーの着手が同じ partizan subtraction Nim の partizan quotient について
発表者： 稲津大貴
共著者：渡辺 業
キーワード：非不偏 octal game、逆形商、グレブナー基底
概要：非不偏 octal game とは両プレイヤーが同じ octal code に従って着手し、終了局面によって非不偏に勝敗判定を与えるゲームである。
本研究では 4.0...01 ( 1 は k 桁目、k は 3 以上の奇数) で最後に残った石の個数が偶数なら L の勝ち、奇数なら R の勝ちという場合を調べた。
逆形商を一般化した partizan quotient がうまく定義でき必勝法を与えることに成功した。
＜組織運営委員＞
小野廣隆
末續鴻輝
安福智明
木谷裕紀
吉渡叶
Alda Carvalho先生&Carlos Santos先生来日記念 日本組合せゲーム理論研究集会（2024年3月6日・7日）(Japan Combinatorial Game Theory Workshops with Alda Carvalho and Carlos Santos)
本研究集会は既に開催されました．
This workshop has already been held.
・組合せゲーム理論の著名な研究者であるAlda Carvalho先生とCarlos Santos先生が来日されます．そのため，お二方をお招きして研究集会を開くことを企画しています．皆様のご参加をお待ちしています．
Professor Alda Carvalho and Professor Carlos Santos, great researchers of combinatorial game theory, will be visiting Japan. Therefore, we are planning a workshop with Professor Carvalho and Professor Santos. We look forward to your participation.
・研究発表や議論は原則として英語で行うようお願いいたします
Please make presentations and discussions in English.
研究集会(Workshop)：3月6日（水）―3月7日（木）(6th Mar.-7th Mar.)
※国立情報学研究所 1512会議室（6日）、1208会議室（7日）とオンラインのハイブリッド開催をします。日によって部屋が異なりますのでご注意ください。場所はこちら
情報処理学会ゲーム情報学研究集会との連続開催になっています
また、3月7日には書泉グランデにて「組合せゲーム理論の世界」出版記念イベントが開かれます
The workshop will be held at National Institute of Informatics, Room No. 1512(6th), and 1208(7th). (This is a hybrid event including online participation.) Note that the room varies depending on the day. The map is here.
A workshop of Information Processing Society of Japan, Game Informatics Research Group will held at the same place the day after our conference. Also, at 7th Mar., an event to celebrate the publication of the book on CGT written by Abuku, Sakai and Suetsugu will be held at the bookstore Shosen Grande, close to NII.
発表申し込みは2月27日までにお願いいたします。
Please submit your presentation application by 27th Feb.
<Program (tentative)>
6th, March
10:15 opening
10:20-11:20 Session 1 (Chair: Hironori Kiya)
Hikaru Manabe (Keimei Gakuin High School), Restricted Nim
Shoei Takahashi (Keimei Gakuin High School), Maximum Nim with Two Types of Stones
11:20-13:00 Lunch
13:00-13:30 Invited talk 1 (Chair: Koki Suetsugu)
Alda Carvalho (DCeT-Universidade Aberta & CEMAPRE/REM-University of Lisbon), Universality of Konane
13:45-14:45 Session 2 (Chair: Diptarama Hendrian)
Ryo Kikuchi (Shibaura Institute of Technology), The partizan Sato-Welter game
Koki Suetsugu (National Institute of Informatics), New universal dicotic partisan ruleset
14:45-18:00 Working & Discussion session
7th March
10:20-11:20 Session 3 (Chair: Hikaru Manabe)
Tomoaki Abuku (National Institute of Informatics), Variants of Multiple Hook Removing Game
Masaru Sato (Kogakuin University), Analysis of the Grundy Number by Image Processing of the NIM Game
11:20-13:00 Lunch
13:00-14:00 Invited talk 2 (Chair: Tomoaki Abuku)
Carlos Pereira dos Santos (Center for Mathematics and Applications (NovaMath), FCT-NOVA University of Lisbon), Combinatorial Game Theory monoids: an overview
14:15-15:15 Session 4 (Chair: Ko Sakai)
Haruki Wada (Hiroshima University), Subtraction games with symmetric sets of removable numbers
Takahiro Yamashita (Hiroshima University), Some game values of Yama Nim and Triangular Nim
15:15-17:30 Closing, Working & Discussion session
<Invited talks>
Invited Talk 1
Alda Carvalho, DCeT-Universidade Aberta & CEMAPRE/REM-University of Lisbon
Title: Universality of Konane
Abstract: The traditional Hawaiian Konane is the first ruleset whose universality has been proved. This means that there is a Konane position for each equivalence class of short normal play games (acyclic games with finite ranks and outdegrees). One can think of this as a CGT analogy of a universal Turing machine: one ruleset encodes it all. In this presentation, the fundamental steps within the proof will be intuitively shown. During the talk, whenever relevant, insights into some fundamental ideas of Combinatorial Game Theory will be discussed.
Invited Talk 2
Carlos Pereira dos Santos, Center for Mathematics and Applications (NovaMath), FCT-NOVA University of Lisbon
Title: Combinatorial Game Theory monoids: an overview
Abstract: The classic order relation employed in Combinatorial Game Theory asserts that a game form is greater than or equal to another when Left can exchange the second for the first in all disjunctive sums, regardless of the other components, without incurring any disadvantage. In the early developments of Combinatorial Game Theory, ``other components'' encompassed all possible game forms. Recently, much research has been made by restricting the range of that to a subclass of forms. In the case of the misère play convention, it is possible to obtain monoids with more structure by adding restrictions. The same is true in scoring play. Furthermore, Absolute Combinatorial Game Theory has been recently developed as a unifying tool for options-only game comparison, providing some general results applicable to any parental restriction. This talk aims to provide a concise overview of current advancements in the study of these structures.
<Talks>
Hikaru Manabe, Keimei Gakuin High School (Co-author: Keita Mizugaki, Shoei Takahashi )
Title: Restricted Nim
Abstract: We study two types of one-pile Nim. (1) In this game, players can remove f(k) stones at most in the k-th turn of the game, where f is a function whose values are natural numbers. We study the formulas for the previous player's winning positions in this game. (2) In this game there are stones {a_0, a_1, a_2, …a_n, …}, where the weight of the stone a_i is 2^i. Two players take turns to remove stones from one of the piles. The total weight of the stones to be removed should be equal to or less than a third of the total weight of the stones in the pile. We study Grundy numbers of this game.
Shoei Takahashi, Keimei Gakuin junior high school (Co-author: Hikaru Manabe , Ryohei Miyadera )
Title: Maximum Nim with Two Types of Stones
Abstract: (1) We consider one-pile Nim with stones with a weight of 1 and stones with a weight of 2. In each turn, the total number of stones to be removed is less than or equal to half of the number of stones in the pile. We study the formulas for the previous player's winning positions in this game. (2) We propose a variant of two-pile Nim. In the first pile, we have stones with a weight of 1, and in the second pile, we have stones with a weight of -2. Two players take turns to remove stones from one of the piles. The total weight of the stones to be removed should be equal to or less than half of the total weight of the stones in the pile. The authors discovered that when (n,m) is the winning position of the previous player, 2m+1 is the last remaining number in the Josephus problem, where there are n+1 numbers, and every second number is to be removed. For any natural number s, there are similar relationships between the position at which the Grundy number is s and the (n+1-s)-th removed number in the Josephus problem with n+1 numbers.
Ryo Kikuchi, Shibaura Institute of Technology
Title: The partizan Sato-Welter game
Abstract: In combinatorial game theory, we often consider impartial game versions of partizan games. In this presentation , conversely, we propose a partizan game version of the impartial game, the Sato-Welter game, and describe how we found a method to obtain its value somewhat easily.
Koki Suetsugu, National Institute of Informatics
Title: New universal dicotic partisan ruleset
Abstract: A dicotic ruleset is a ruleset such that in every position, one can move if and only if the other can move. It has been open to find a universal dicotic partisan ruleset, that is, a dicotic rule set which has every dicotic value. In this talk, we consider dicotic version of beyond the door, and prove the ruleset is a universal partisan dicotic ruleset.
Tomoaki Abuku, National Institute of Informatics (Co-author: Masato Tada )
Title: Variants of Multiple Hook Removing Game
Abstract: The Multiple Hook Removing Game is a combinatorial game played using a rectangular Young diagram. In this study, we investigate the properties of variants of the Multiple Hook Removing Game, namely the Forced Multiple Hook Removing Game and the Sequential Multiple Hook Removing Game. These variants are combinatorial games that modify some of the rules regarding the continuous removal of hooks in the Multiple Hook Removing Game. In this talk, we will explain the analysis of these games and report the results obtained.
Masaru Sato, Kogakuin University (Co-author: Yuga Yajima, Kazuki Maeyama )
Title: Analysis of the Grundy Number by Image Processing of the NIM Game
Abstract: In this study, we consider a NIM with two mountains in which the players are allowed to start taking stones from both mountains at the same time. Even if the number of possible moves is strictly limited, the behavior of the Grundy number is very different, and it is very difficult to find the Grundy number as a general problem for now. Therefore, in this study, we attempt to capture the trend and characteristics of the Grundy numbers by creating an image of a two-dimensional table of the Grundy numbers of the two mountains and treating it as a clustering problem using machine learning as a data set.
Haruki Wada, Hiroshima University
Title: Subtraction games with symmetric sets of removable numbers
Abstract: Let S be a finite set of positive integers. We consider a one pile subtraction NIM with S as the set of removable numbers. It is known that the grundy numbers are periodic, but the period remains mysterious in general. In this talk, we assume that S is symmetric, namely there exists a positive integer N such that s is in S if and only if N-s is in S. We prove that under this assumption, the grundy numbers are purely periodic (namely the period starts from 0), with N as a period.
Takahiro Yamashita, Hiroshima University
Title: Some game values of Yama Nim and Triangular Nim
Abstract: Yama Nim is a two heaps Nim game introduced in my Master Thesis, where the player takes at least 2 tokens from one heap, and return 1 token to the other heap. Triangular Nim is a generalization, where the player takes at least 2 tokens from one heap, and return at least one token to the other heap, so that the total number of tokens in the heaps decrease strictly. In my recent work, the set of P-positions of normal play of Yama Nim and Triangular Nim are same but the Grundy numbers it was proved that are different. In addition to the Grundy numbers, other game values are known, such as the remoteness numbers and the suspense numbers will be discussed. I found an interesting result about some game values of Yama Nim and Triangular Nim, so in this talk I will report them.
※本研究集会は学術変革領域(A) 社会変革の源泉となる革新的アルゴリズム基盤の創出と体系化 新しい概念に基づいたアルゴリズム・最適化の問題創出とその効率的求解方法の研究（課題番号：20H05962）の後援を受け開催しています。
This workshop is supported by JSPS KAKENHI Grant Number 20H05962.
第7回日本組合せゲーム理論研究集会（2023年8月20日・21日）
第7回日本組合せゲーム理論研究集会を開催します。国立情報学研究所とZoomを用いたオンラインでのハイブリッド開催を予定しています。皆様のご参加をお待ちしております。
日時：2023年8月20日（日），21日（月）
場所：国立情報学研究所1208室* および オンライン
*8月20日は日曜日のため正面入り口は閉鎖されています。横に夜間休日用の入り口があるためそちらからお入りください。なるべく運営委員が建物前にいるようにするか、目印を立てるようにいたします。
※東京は連日猛暑日が続き、年間の猛暑日日数記録を更新しています。また、新型コロナウイルス感染症の定点医療機関当たり患者報告数も二カ月ほど上昇傾向が続いております。お体に気をつけてお越しください。体調がすぐれない場合や急な予定変更がある場合は、オンラインミーティングリンクをご利用ください。4年ぶりとなる本研究集会の対面開催が円滑・安全に進みますよう、皆様のご協力をお願いいたします。
参加費：不要
参加申込：締め切りました
（発表申込は8月10日23時59分、参加申込は8月16日23時59分までにお済ませください）
＜スケジュール＞
*1 チュートリアルセッションは、組合せゲーム理論で共通して用いられる用語や概念を紹介し、本理論に不慣れな方が以降の発表を理解しやすくするためのセッションです。組合せゲーム理論の初学者や、準備をしておきたいと言う方はぜひチュートリアルセッションからご参加ください。
8月20日（日）
＜チュートリアルセッション*＞
10:15-11:00 末續鴻輝「非不偏ゲームについて」スライド
11:00-11:30 安福智明「不偏ゲームについて」スライド
13:05-13:10 開会 スライド
＜セッション１＞
13:10-13:40 篠田正人「円形ニムのある変種：収縮円形ニム」スライド
13:40-14:10 森脇悠斗「制限ニムから発見された数列について」スライド
＜セッション２＞
14:25-14:55 草刈圭一朗「二部グラフ上の屋島ゲームにおける局面値の特定」
14:55-15:15 末續鴻輝「いくつかのゲームの値について」スライド
＜セッション３＞
15:30-16:00 木谷裕紀「一般化しりとり問題の計算量」
16:00-16:20 稲津大貴「グラフゲームのNP困難性」
16:20-16:50 塚村善弘「N対N+1」
＜ワーキングセッション＞
16:50-19:00頃
8月21日（月）
＜セッション４＞
10:00-10:30 山下貴央「Yama Nim とその一般化」
10:30-11:30 木村俊一「On variations of Yama Nim ~What happens if you return stones in Nim games?~」
＜セッション５＞
13:00-13:20 山下貴央「Comply/constrain operator of conbinatorial games について」
13:20-13:50 小田原亜久里「制限ニムの複数の和に関する comply/constrain operators」
13:50-14:20 木村俊一「Comply/Constrain games のグランディー数について」
＜セッション６＞
14:35-15:05 洞龍弥「圏論から見た組合せゲーム理論」スライド
15:05-15:25 渡辺業「Collatz予想のパズルやゲームへの応用可能性について」
＜セッション７＞
15:40-16:10 眞部光「チョコレート問題」
16:10-16:40 佐藤優「二山NIMの画像処理によるグランディ数の解析について」
16:40-17:10 木村俊一「逆形の不偏ゲームと正規形でのグランディー数について」
＜閉会・ワーキングセッション＞
閉会 スライド
17:10-19:00頃
＜発表ごとの詳細＞
１．「円形ニムのある変種：収縮円形ニム」
発表者*と共著者：篠田正人*
発表概要：円形ニム（Circular Nim）のある変種型ゲームとして収縮変形ニム（Shrinking Circular Nim）を考える。このゲームでは円形ニムと異なり、円周上にある山の石数が0個になるとその山が消えて円が縮むものとする。ゲーム開始時の石の山数が5以下の場合について、局面の勝敗条件を報告する。
キーワード：ニム，円形ニム，不偏ゲーム
２．「制限ニムから発見された数列について」
発表者*と共著者：森脇悠斗*
発表概要：自然数からなる集合Sに対し、次のような制限ニムG(S)を考える: 1つの山からいくつか石をとる、ただしとる個数はSの元に限られる。 Sの元を除去可能数と言うが、除去可能数が有限個の場合グランディ数(ここではG数と呼ぶ)の列は周期的となる。また、その(最小の)周期pは除去可能数の約数とはならない、とくにSの元でないので、G(S∪{p})のG数列の周期はpとは異なる。同様にして周期を拾っていって得られる数列をいくつかのSに対して計算し、以下の作業仮説を目標として研究を進めた。 (i) 狭義単調増加となる。 (ii) 加法的周期的となる。 その後の検証による仮説の行方や、ある場合に不思議な場合分けが生じることについて紹介する。
キーワード：組合せゲーム，ニム，制限ニム，グランディ数，周期列
３．「二部グラフ上の屋島ゲームにおける局面値の特定」
発表者*と共著者：草刈圭一朗*，横井雅也
発表概要：屋島ゲームとはグラフ上の組合せゲームである． 屋島ゲームではグラフの節点上に二人の対局者が駒を1つずつ置きゲームを開始する． 各対局者は自駒を枝に沿って隣接節点に移動し，その際に使用した枝を消去し， 先に移動できなくなったほうが負けとなる． 本発表では二部グラフ上の屋島ゲームにおける局面値が 全て {m|n} (m と n は整数)という非常に単純な形になることを紹介する．
キーワード：屋島ゲーム，局面値
４．「いくつかのゲームの値について」
発表者*と共著者：末續鴻輝*
発表概要：正の実数a, bに対しては必ずある整数nが存在してna > bとなる（アルキメデスの原理）．これに対し，正のゲームG, Hではアルキメデスの原理は成り立たず，例えば↑>0と1>0について，任意の整数nに対してn・↑<1である．一方で，何倍しても↑より大きくならないような正の値の系列も知られている．また，*，*2，…は任意の正の数より小さく，負の数より大きいが，0とは比較不能である．このように，いくつかの値や値の系列についてはそれらの大小関係の性質が知られている．本発表ではそのような大小関係について簡単にサーベイするとともに，代数的な特徴を共有する値の系列について考える
キーワード：非不偏ゲーム，ゲームの値，ゲームの大小関係
５．「一般化しりとり問題の計算量」
発表者*と共著者：木谷裕紀*，江藤宏，土中哲秀，小野廣隆
発表概要：しりとりをグラフ一般化したゲームである一般化しりとりは1970年代に提案されたゲームである．
このゲームはそのグラフの対象として，無向グラフ，有向グラフのどちらで行うか?また，辺，頂点のどちらの削除を行うかによって，いくつかの亜種が存在する．
その亜種の一つである一般化無向頂点しりとりに対しては，Kyleらによってそのゲームが勝敗を求めることは多項式時間でできるにも関わらず，その各局面のgrundy数を求めることの計算がPSPACE困難であるゲームであることが2021年に示された．
本発表ではこれらの一般化しりとりの種々の亜種の結果を紹介し，閾値グラフ上の一般化無向辺しりとりに対する勝敗判定を行う．
キーワード：一般化しりとり，グラフ理論，グラフクラス，不偏ゲーム
６．「グラフゲームのNP困難性」
発表者*と共著者：稲津大貴*
発表概要：FOX AND GEESE は特定のグラフゲームとみなすことができる. 本講演では Set Covering という NP 完全問題も同じタイプのグラフゲームの必勝者判定問題として実現することで, このようなゲームが少なくとも NP 困難であることを証明する.
キーワード：グラフゲーム, NP完全
７．「N対N+1」
発表者*と共著者：塚村善弘*
発表概要：完全互角の7人が東軍３人と西軍４人に分かれて総当たり１２戦を行う。勝率１位の者が賞を取る。どちらの所属が確率的に有利か。
キーワード：確率１/２対戦
８．「Yama Nim とその一般化」
発表者*と共著者：山下貴央*
発表概要：発表者は修士論文で「⽯の⼭が２つあり、プレイヤーはどちらかの⼭から2個以上⽯を取り、もう⼀⽅の⼭に⽯を1 個戻す」ルールである Yama Nim を考案し、正規形と逆形のルールの必勝法とグランディ数の解析に成功した。また、Urban先生との研究ディスカッションや自身の研究の進捗でここ数ヶ月で一般化したルールの必勝法とグランディ数について解析ができたものについて説明を行う。最後に、修士論文ではYama Nim の正規形でも逆形でもないルールの必勝法とグランディ数についても解析しており、そこについてもその後に出てきた新たな結果も含めて説明できればと思っている。
キーワード：不偏ゲーム，Nim，必勝法，グランディ数
９．「On variations of Yama Nim ~What happens if you return stones in Nim games?~」
発表者*と共著者：木村俊一*，山下貴央
発表概要：Yama Nim およびTriangular Nim とその拡張について、いくつかのトピックをお話しします。(i) Triangular Nim では グランディー数の記述に数列があらわれること、(ii) Wythoff variations で、三角数、平方数、五角数、..、n 角数がP-positions の記述にあらわれ、さらにグランディー数についても完全記述できること、(iii) さらに、２ベキ、３ベキがあらわれる一般化の紹介 (iv) ３次元以上への Triangular Nim の一般化、(v) 無限個の石がある場合のTriangular Nim の話
キーワード：Yama Nim, Triangular Nim, Wythoff Variations, Transfinite Nim
１０．「Comply/constrain operator of conbinatorial games について」
発表者*と共著者：山下貴央*，安福智明，木村俊一，木谷裕紀，Larsson Urban，Saha Indrajit，末續 鴻輝
発表概要：同じ局面集合に着手ルールが2つあり、どのルールで着手するのかを相手が決めるという設定での組合せゲームをComply/constrain operator of conbinatorial gamesと呼ぶ。このゲームは、一見複雑なルールでも、正規形のルールの下である条件を満たせば、必勝法が分かることが共同研究で分かった。本発表では、その条件について具体例を交えながら説明する。また、その条件から分かる性質や逆形のComply/constrainの面白い例について紹介する。
キーワード：Comply/constrain，不偏ゲーム，必勝法
１１．「制限ニムの複数の和に関する comply/constrain operators」
発表者*と共著者：小田原亜久里*
発表概要：制限ニムの相異なる和(Disjunctive Sum、Continued Conjunctive Sum、Diminished Disjunctive Sum、Conjunctive Sum)について、comply/constrainで組合わせたP-positionを調べた結果、面白い例が見つかったので報告する。
キーワード：制限ニム，comply/constrain operator，様々な和
１２．「Comply/Constrain games のグランディー数について」
発表者*と共著者：木村俊一*，安福智明，木谷裕紀，Larsson Urban，Saha Indrajit，末續鴻輝，山下貴央
発表概要：Comply/Constrain 不偏ゲームについて、グランディー数が定義できることを紹介します。また、A dominates B dominates C dominates A ならばA, B, CがSimilar であることの証明を行います。時間があれば、Strong dominiate についても話します。
キーワード：Comply/Constrain games，グランディー数
１３．「圏論から見た組合せゲーム理論」
発表者*と共著者：洞龍弥*
発表概要：組合せゲームの圏はそれ自体魅力に溢れているが，モノイダル圏論という枠組みを通して，特に計算機科学，論理学，圏論の融合的な分野で理論的に重要な役割も果たしている．本発表の目的は，圏論の立場から見た組合せゲームの魅力と威力を概説することである．
キーワード：圏，モノイダル圏，計算機科学
１４．「Collatz予想のパズルやゲームへの応用可能性について」
発表者*と共著者：渡辺 業*
発表概要：有名な未解決問題であるCollatz予想に関連して,ある奇数p(≧3)と奇数の集合R_pを決め,nが奇数ならば,奇数rをR_pから自由に選んで(pn+r)/2を対応させる非決定的関数に従って数字をうつすパズルやゲームを考える. 本講演では,それらの中でも特に重要な「一般に与えられた2つの数字の間のルートが存在するか？」という問題について考察する.特に,任意の奇数p(≧3)について奇数の集合R_pを適当にとれば,一般に自然数n,mをとったときnからmへのルートが存在することを証明した.
キーワード：Collatz予想，非決定的，Collatzパズル，Collatzゲーム，グラフゲーム
１５．「チョコレート問題」
発表者*と共著者：眞部光*，宮寺良平
発表概要：チョコレートゲームというのは、石取りゲームの一般化の1つである。正方形のピースをいくつも並べたチョコレートを考え、チョコレートの一部に苦いところがあって、そこを食べることはできない。二人のプレイヤーが交互に、線に沿ってチョコレートを2つにカットし、苦い部分がない方を食べる。これを繰り返していき、自分の番で苦い部分だけを残したプレイヤーが勝つ。苦い部分は食べることはできないので、最後にプレーした人が勝つことになり、正規形のゲームである。
苦い部分が長方形の隅にある場合は、チョコレート問題は2つ山の石取りゲームと数学的に同値になる。苦い部分が長方形の底面になっている場合は、3つ山の石取りゲームになる。従って、これらの場合は、Grundy数は苦い部分から数えて0,1,2,...と座標をつけた場合に、座標の排他的論理和に等しくなる。 すると、次のことが問題になる。
問 チョコレートの形状を変えた場合に、どのような形であれば、Grundy数が排他的論理和に一致するのか。
この問に対して、平面のチョコレートに関してはIntegers Volume 20, 2020.\# G1に論文を掲載したが、そこで扱ったチョコレートは、座標軸で考えると、原点の位置に苦い部分があり、チョコレートは第一象限に限定されていて、垂直にカットするとx軸方向の長さが減ると同時に、y軸方向の高さが減る可能性があるというものだった。
今回は第一象限と第四象限のチョコレートがあり、垂直にカットするとx軸方向の長さが減ると同時に、y軸の正の方向の高さとy軸の歩の方向の深さとが減る可能性がある。この場合を扱うためにはIntegers Volume 20, 2020.\# G1で使った証明方法をかなり変えないとできない。
また、 Grundy数が排他的論理和に等しくなる条件を緩めて、Grundy数が0となるのは、排他的論理和0の時とすると、チョコレートの形状を特定するのは極めて難しく、今回はいくつかの十分条件を与える。３次元のチョコレートの場合には、Integers Vol.21B, 2021 $\#$ A19で論文を出したが、この3次元の場合でも、1つのカットで減る座標が3つになる可能性を考えることができる。
最後に、この問題のPartizan化を考えており、今の時点で得られていることを簡単に紹介する。
キーワード：チョコレートゲーム，グランディー数，P-position
１６．「二山NIMの画像処理によるグランディ数の解析について」
発表者*と共著者：佐藤優*，矢島雄河，前山和喜
発表概要：本研究では，二山のNIMにおいて，二山から同時に石を取る着手を許したNIMについて考える．選択可能な手を厳しく制限を与えたとしてもグランディ数の振る舞いが大きく異なるため，現状では一般問題としてグランディ数を求めることはとても難しい．そこで本研究では二山のグランディ数を２次元の表にしたものを画像化し，それをデータセットとして機械学習を用いてクラスタリング（分類）問題として扱うことで，グランディ数の傾向や特徴を捉えることを試みる．
キーワード：二山NIM，グランディ数，画像処理，機械学習
１７．「逆形の不偏ゲームと正規形でのグランディー数について」
発表者*と共著者：木村俊一*
発表概要：逆形の不偏ゲームの必勝手順について、正規形でのグランディー数だけから分析できるケースがあるので、それを紹介します。
キーワード：Misere games
＜組織運営委員＞
末續鴻輝（代表）
安福智明
木谷裕紀
前山和喜
洞龍弥
Urban Larsson先生来日記念 日本組合せゲーム理論ミニ研究集会（2023年5月）(Japan Combinatorial Game Theory Mini-Workshops with Urban Larsson)
※参加に際し何かお困りの際はsuetsugu.koki[AT]gmail.comまでご連絡ください
If you encounter any issues in participating, please contact suetsugu.koki[AT]gmail.com.
組合せゲーム理論の有名な研究者であるUrban Larsson先生が来日されます．そのため，Larsson先生をお招きして三つの（ミニ）ワークショップを企画しています．また，それ以外の日につきましても多くの日について議論にご参加いただくことが可能になっております．皆様のご参加をお待ちしています．（ミニ）ワークショップの日には各自の研究発表を中心に行い，それ以外の日（セミナー）には研究議論を中心に行う予定です．
一連の期間を三部に分け，それぞれの期間にテーマを設定していますが，組合せゲーム理論に関するものであれば、期間のテーマ以外のものもお気軽にお持ち寄りください．
Professor Urban Larsson, a great researcher of combinatorial game theory, will be visiting Japan. Therefore, we are planning three (mini)workshops with Professor Larsson and many other days are open for discussion. We look forward to your participation.
We are dividing the period into three parts, each with its own topic, but please feel free to bring anything related to combinatorial game theory other than the topic of the period.
＜全期間共通 (Common things for every part)＞
申し込み…終了しました．
研究発表や議論は原則として英語で行うようお願いいたします．
詳細については決まり次第順次本Webサイトを更新していきます．
Registration...The registration form is closed.
Please make presentations and discussions in English.
Details will be updated on this website as soon as they are finalized.
＜第一部・国立情報学研究所（東京）(First part; at National Institute of Informatics, Tokyo)＞
セミナー(Seminar)：5月10日（水）及び5月11日（木）10時より (10th May and 11th May 10:00~)
※国立情報学研究所 神田サテライトラボで開催します 神田駅前ですのでご注意ください 場所はこちら
*The seminar will be held at Tokyo Kanda AFSA Laboratory, National Institute of Informatics. The nearest station is JR Kanda station. The map is here.
ミニワークショップ(Mini-workshop)：5月12日（金）13時～ (12th May 1:00 p.m. ~)
※国立情報学研究所 1208会議室で開催します セミナーとミニワークショップで開催場所が異なるのでご注意ください 場所はこちら
*The workshop will be held at National Institute of Informatics, Room No. 1208, different place from the seminar. The map is here.
発表申し込みはなるべく10日までにお願いいたします。
Please submit your presentation application by the 10th.
トピック(Topic)：Guaranteed scoring games
Program:
<Session 1>
13:00-13:30 Ryo Kikuchi, "Partisan fill-in-the-blank game on finite partially ordered sets "
13:30-14:00 Kazuki Maeyama, "Research of Combinatorial Game Theory to the Beginner in Informatics Students"
<Session 2>
14:15-15:15 Ryuya Hora, "Grundy numbers and Categories "
<Invited talk>
15:30-16:15 Urban Larsson, "Guaranteed scoring games"
<Working session>
16:30-18:30
Ryo Kikuchi, Shibaura institute of technology
Title: Partisan fill-in-the-blank game on finite partially ordered sets
Abstract: We propose a fill-in-the-blank game as a variation of Hackenbush. The original game was played on a half-line, but we extend it to a finite partially ordered set. In this presentation, we will discuss the rules and strategies of the game and explore its mathematical properties.
Kazuki Maeyama, SOKENDAI, the Graduate University for Advanced Studies
Title: Research of Combinatorial Game Theory to the Beginner in Informatics Students
Abstract: A case study will be presented on the approach of a beginning informatics student to the research of combinatorial game theory as a non-specialist in mathematics and algorithmic theory. In particular, I will talk about how we are creating tools for analysis and visualization, and what educational perspectives in informatics we are including.
Ryuya Hora, The university of Tokyo
Title: Grundy numbers and Categories
Abstract:
Grundy numbers and their nim-sums play a central role in combinatorial game theory. However, where do they come from, and why do they work so well? Is a conceptual understanding possible? Category theory is a possible approach to give mathematical answers to such naive and ambiguous questions! Combinatorial games and category theory are closely related. André Joyal defined the category "Games" of combinatorial games and strategies, and further proved that this category has a remarkable structure (Compact Closed Category). This categorical structure appears everywhere in pure mathematics and is also attracting attention in applied category theory, such as in quantum computing and natural language processing. Combinatorial game theory might be connected to those areas via categories. In this presentation, I will outline my research aimed at categorically deriving Grundy numbers and their nim-sums. In doing so, we will define the category of impartial games using a different method (Monoidal category of recursive coalgebras) from Joyal's and explore the categorical origin of Grundy numbers. If time permits, I will discuss the direction of future research and some dreams.
<Invited talk>
Urban Larsson, IEOR, IITB
Title: Guaranteed scoring games
Abstract: Recent research adorns scores to terminal nodes, scores that depend on whose turn it is; that is, we combine the last-move and scoring-play conventions. Stewart 2017 studies the full scoring universe and indicates that so-called “hot-empty” games are problematic; they ruin most structure. A “hot-empty” game rewards a player without options. The breakthrough came about in recent work via the monoid of guaranteed scoring-play (Larsson, Nowakowski and Santos 2016, 2018), where such “hot-empty” games are excluded, and indeed, many rulesets have natural interpretations in terms of guaranteed scoring-play. This monoid has a rich structure, and in particular, normal-play is order embedded in guaranteed scoring-play. This theory has even broader theoretical interest. In more recent work, the authors utilise the ideas to achieve constructive game comparison on a higher abstract level, dubbed Absolute CGT (Larsson, Nowakowski and Santos 2017); the work encompasses normal-, misère-, scoring-play and more. This is joint work with Nowakowski and Santos.
＜第二部・京都大学（京都）(Second part; at Kyoto University)＞
セミナー(Seminar)：5月16日（火）12時30分～(16th May 12:30~) 場所は個別にご案内します We will tell the room in person.
ミニワークショップ(Mini-workshop)：5月17日（水）13時～ (17th May 1:00 p.m. ~)
場所：京都大学 総人棟1401(以下の地図の84番の建物、4階です)
（The workshop will be held the room 1401 of the building 84 in the following map.）
京都大学吉田南構内マップ
トピック(Topic)：Bidding çombinatorial games
Program:
<Invited talk>
13:00-13:45 Urban Larsson, Bidding combinatorial games
<Session 1>
14:00-14:20 Koki Suetsugu, Outcomes of Bidding CGT with real number bidding
<Working session>
14:30-18:30
<Invited talk>
Urban Larsson, IEOR, IITB
Title: Bidding combinatorial games
Abstract: Recent research generalises alternating normal play to bidding play. A given total budget, a nonnegative integer, is split between the two players. At each stage of a game, they bid for the privilege to play. The player who wins the bid hands over the winning bid to the other player. A marker differentiates between ties. Zugzwangs are possible, and indeed the 0-total budget corresponds to alternating normal-play. The outcomes are vectors that indicate who wins in perfect play, given any split of the total budget. We describe the feasible outcomes and prove that they all appear as game forms. We have managed to obtain a constructive comparison test for any given total budget. By using this test, we prove various structure results. In particular, for any total budget, numbers, integers, and dyadic rationals are subgroups of the larger monoid. This is joint work with Kant, Larsson, Rai and Upasany.
<Session 1>
Koki Suetsugu, National Institute of Informatics
Title: Outcomes of Bidding CGT with real number bidding
Abstract: In Bidding CGT, the player bids an integer. In this talk, we consider similar convention to Bidding CGT, but each player can bid any real number. We investigate some outcomes of this convention.
発表申し込みはなるべく15日までにお願いいたします。
Please submit your presentation application by the 15th.
＜第三部・九州大学（福岡）(Third part; at Kyushu University, Fukuoka)＞
セミナー(Seminar)：5月22日（月），23日（火），25日（木），26日（金），29日（月）10時～(22nd, 23rd, 25th, 26th and 29th May 10:00 a.m.~)場所は個別にご案内します We will tell the room in person.
ミニワークショップ(Mini-workshop)：5月24日（水） 15:00~(24th May 3:00 p.m.~)
場所：九州大学伊都キャンパスウエスト２号館 310 シス情 第2講義室
http://qu-concrete.com/access/west2/
トピック(Topic)：Entailing combinatorial games
Program:
<Session 1>
15:00-15:30 Tomoaki Abuku, Generalized Variant Delete Nim
15:30-16:00 Koki Suetsugu, Two-dimensional subtraction games as a combination of one-dimensional subtraction games and cyclic nimhoff
<Invited talk>
16:30-17:15 Urban Larsson, Entailing combinatorial games
<Working session>
17:15-19:00
<Session 1>
Tomoaki Abuku*, National Institute of Informatics
Title: Generalized Variant Delete Nim
Abstract: Nim is a well-known combinatorial game with several variants, e.g., Delete Nim and Variant Delete Nim. In Variant Delete Nim, the player deletes one of the two heaps of stones and splits the other heap on his/her turn. In this talk, we discuss generalized Variant Delete Nim, which generalizes the number of stone heaps to three or more, All-but-one-delete Nim, Half-delete Nim, No-more-than-half-delete Nim, and Single-delete Nim. We study the win-loss conditions for each of these games.
*This is joint work with Ko Sakai, Masato Shinoda, and Koki Suetsugu.
Koki Suetsugu, National Institute of Informatics
Title: Two-dimensional subtraction games as a combination of one-dimensional subtraction games and cyclic nimhoff
Abstract: In general, finding a closed formula for G-values or P-posigions of two-dimensional subtraction games is difficult. On the other hand, with some restrictions, we can find formulas for G-values or P-positions. As an example, in this talk, we introduce some cases in which we can obtain closed formulas for G-values by using the result obtained in a paper "On a Combination of the Cyclic Nimhoff and Subtraction Games".
<Invited talk>
Urban Larsson, IEOR, IITB
Title: Entailing combinatorial games
Abstract: There are rulesets with entailing moves that break the alternating play axiom and/or restrict the other player's options within the disjunctive sum components. Although some examples have been analyzed in the classical work Winning Ways, such rulesets usually fall outside the scope of the established normal play mathematical theory. At the first Combinatorial Games Workshop at MSRI, John H. Conway proposed that an effort should be made to devise some nontrivial ruleset with entailing moves that had a complete analysis. Recently (2022), Larsson, Nowakowski, and Santos proposed a more general theory, dubbed affine impartial, which facilitates the mathematical analysis of impartial rulesets with entailing moves. Here, by using this theory, we present a complete solution for a nontrivial ruleset with entailing moves. This is joint work with Nowakowski and Santos.
※このほか，セミナーではsubtraction games in more than one dimension についても議論が行われる予定です
*In addition, "subtraction games in more than one dimension" will also be discussed during the seminars.
発表申し込みはなるべく22日までにお願いいたします。
Please submit your presentation application by the 22nd.
＜Urban Larsson先生 ご経歴 (Biography of Professor Urban Larsson)＞
Urban Larsson is an Associate Professor at IEOR, IITB. Before that he had research fellow positions at the National University of Singapore, the Technion Israel, and Dalhousie University, Canada. Before that he was a lecturer in mathematics and Ph.D. student at Chalmers & University of Goteborg, Sweden. He was awarded Killam and Aly Kaufman fellowships. His main research areas are Game Theory, Number Theory, Discrete Mathematics, Computer Science and Algorithms. He publishes regularly (with 19 peer reviewed published papers in international journals in 2018-2023). His main contributions find bridges between combinatorial games and neighbouring disciplines. Urban has presented his research at more than 100 international conferences and seminars, he is an Associate Editor for International Journal of Game Theory, and he is the Editor of two Games of No Chance volumes (MSRI, CUP). He has co-organised several workshops in Combinatorial Game Theory: Games at Dal, with Prof. R. J. Nowakowski; Games at Carmel; at Ohio State University, with Dr. E. R. Roa; at IEOR, IITB, with Prof. M. Rao. And he is a member of the program committee for CGTC I, II and III, IV (Azores 2023), organised by Dr. C. P. dos Santos University of Lisbon.
組合せゲーム理論ミニワークショップ（2023年4月29日）
2023年1月に開かれた組合せゲーム理論の国際研究集会Combinatorial Game Theory Colloquium IVで得られた情報の共有、および希望者の研究テーマの紹介と、それらの情報を元にした議論を行うためのワークショップを開催します。
※（5月2日追記）組合せゲーム理論ミニワークショップは無事開催されました。ご参加いただいた皆様ありがとうございました。メーリングリストへの招待をお送りしましたので、引き続き組合せゲーム理論研究集会の情報を得たい方は是非ともご登録よろしくお願いいたします。
日時：2023年4月29日（土・祝）
場所：京都大学 総人棟1401(以下の地図の84番の建物、4階です)
※対面開催のみを予定していますが、状況により変更をする可能性があります。
9:30〜
開場
10:00～11:30
安福智明、木谷裕紀、末續鴻輝
「Combinatorial Game Theory Colloquium IV 参加報告（詳細版）」
11:30〜13:00
昼休憩
13:00～16:00
未解決問題情報共有＆議論セッション
どうぞよろしくお願いいたします。
第6回日本組合せゲーム理論研究集会（2022年8月20日・21日）
（2022/8/21追記）第6回日本組合せゲーム理論は無事開催されました。皆様ご参加ご発表ありがとうございました。
第6回日本組合せゲーム理論研究集会を開催します。Zoomを用いた完全オンラインでの開催を予定しています。皆様のご参加をお待ちしております。
※8月17日、参加申込者にZoom URLを記載したメールをお送りしました。
届いていない方は、suetsugu.kokiあっとまーくgmail.comまでご連絡ください。
日時：2022年8月20日（土），21日（日）
場所：国立情報学研究所 および オンライン（新型コロナウイルスの感染状況等を鑑み、完全オンラインでの開催となりました。ご理解のほどよろしくお願いいたします）
参加費：不要
参加申込：参加申込は終了しました
（発表申込は8月10日23時59分、参加申込は8月16日23時59分までにお済ませください）
＜スケジュール＞
8月20日（土）
10:00 開会
10:05-10:45 チュートリアルセッション 不偏ゲームについて（安福智明）
11:00-11:30 公約数ニムの Grundy 数 （野萩遼太郎）
11:30-12:00 穴埋めゲームとその一般化 （菊地遼）
14:00-14:30 ４山削除分割ニムの勝敗判定条件とその証明 （篠田正人）
14:30-15:00 削除ニムの拡張 （安福智明）
15:15-15:45 不偏ゲーム化したLights Outの解析について （佐藤優 ）
15:45-16:15 コンピュータを用いた不偏ゲーム化Gobbletの解析 （根木颯也 ）
16:15-16:45 パス付きの石取りゲームについて（宮寺良平・眞部光 ）
16:45- 議論（ブレークアウトルームを開放予定）
8月21日（日）
10:00-10:45 チュートリアルセッション 非不偏ゲームについて（末續鴻輝）
11:00-11:30 色付き辺ケイレスの必勝判定 （吉渡叶）
11:30-12:00 全象ゲームに関する研究のここまでの概要（末續鴻輝）
14:00-14:30 石とりゲームが単なる遊戯ではなくなったとき （前山和喜）
14:30-15:00 入札組合せゲームの紹介と単貧民への応用 （木谷裕紀）
15:00-15:30 打ち切り優先正規系非不偏ゲームに関する研究 （木谷裕紀）
15:30 閉会
15:30- 議論（ブレークアウトルームを開放予定）
＜発表内容＞
タイトル：公約数ニムの Grundy 数
発表者：野萩遼太郎
キーワード：公約数, Grundy 数, 2進付値
概要：制限 n 山ニムについて, 各局面に対する除去可能数を, 各山の石の個数の公約数とした. これを公約数ニムと名付け, n = 1,2 の場合については Grundy 数を求められた. n が 3 以上の場合は Grundy 数の予想を紹介する.
タイトル：穴埋めゲームとその一般化
発表者：菊地遼
キーワード：グランディ数、不偏ゲーム
概要：卒業研究として取り組んでいるオリジナルのゲームについて、グランディ数解析の途中成果を発表する。
タイトル：４山削除分割ニムの勝敗判定条件とその証明
発表者：篠田正人
キーワード：石取りゲーム、ゲームの解法
概要：４つの石の山の１つを削除し、残った３山のうちの１つを２分割する石取りゲームにおける勝敗判定条件について考察した研究報告「Delete Nimの一般化と勝敗判定」 http://id.nii.ac.jp/1001/00217400/ の証明のポイントを詳述する。
タイトル：削除ニムの拡張
発表者：安福智明
共著者：坂井公，篠田正人，末續鴻輝
キーワード：組合せゲーム，不偏ゲーム，ニム，削除ニム
概要：削除ニムと呼ばれる不偏ゲームがある．そのゲームの様々な拡張について紹介する．
タイトル：不偏ゲーム化したLights Outの解析について
発表者：佐藤優
共著者：前山和喜
キーワード：LightsOut，グランディ数，コンピュータ実験，可視化
概要：1人用パズルであるLights Outを各手番に着手可能な手が同じになるように制限を加え，不偏ゲーム化したものをコンピュータを用いて完全解析した結果について論じる．さらに，解析結果からグランディ数を求め色付けなどを行なうことで，ゲームの構造の可視化を試みる．
タイトル：コンピュータを用いた不偏ゲーム化Gobbletの解析
発表者：根木颯也
共著者：前山和喜，矢島雄河
キーワード：Gobblet，グランディ数，コンピュータ実験
概要： 2人で行うボードゲームGobbletを各手番の着手可能な手が同じになるように制限を加え，2人用の不偏ゲーム化したものをコンピュータで完全解析した結果について論じる．また，不偏ゲーム化する際の制限の細かな違いによってグランディ数がどのように変化したか考察する．
タイトル：パス付きの石取りゲームについて
発表者：宮寺良平，眞部光
キーワード：石取りゲーム パス P-position 組合せゲーム
概要：3山崩しの石取りゲームで、2人のプレイヤーで合わせて一回だけパスを使うことを許す。ただし、石が0個になってからはパスは使えない。このような条件でP-position（後手必勝位置）を表す公式はまだ見つかっていない。3山崩しの石の取り方に制限をつけると、P-positionはわかりやすい式になり、またパスを使えない状態を変えても、P-positionがわかりやすい式になることを見つけた。もし時間が残れば、遺伝アルゴリズムでこの問題を研究している状況についても話したい。
タイトル：色付き辺ケイレスの必勝判定
発表者：吉渡叶
キーワード：辺ケイレス，必勝判定アルゴリズム
共著者：木谷裕紀，土中哲秀，小野廣隆
概要：辺ケイレスは，ケイレスを計算論的観点から一般化する形で1978 年 Schaefer により定義された単純無向グラフ上で行われる2人ゲームである．辺ケイレスでは各プレイヤは自分の手番においてグラフ上の辺を1つ選択する．このとき選択された辺とその両端点，さらにその両端点に接続していた全ての辺は削除される．これを2人のプレイヤで交互に繰り返し，先に自分の手番で選択できる辺が無くなった方が負けである．このゲームはケイレスのほかクラムの一般化にもなっており，削除できる辺をプレイヤごとに限定した色付き辺ケイレスではドミニアリング(ドミニーリング)の一般化にもなっている．本研究では辺ケイレスと色付き辺ケイレスに対するO∗(2^n) 時間必勝判定アルゴリズムとグラフの構造に着目したFPTアルゴリズムを提案する． さらに色付き辺ケイレスの必勝判定がNP困難であることを証明する．
タイトル：全象ゲームに関する研究のここまでの概要
発表者：末續鴻輝
キーワード：全象ゲーム、タイル返し、計算複雑性
概要： 全象ゲームは、ある枠組みの中のすべての値を取るルールセットのことであり、特に非不偏正規形ゲームにおける全象ゲームがよく議論される。本発表では、これまで行われてきた全象ゲームについて、発表者の研究の最新の知見を交えて紹介する。
タイトル：石とりゲームが単なる遊戯ではなくなったとき
発表者：前山和喜
キーワード：組合せゲーム理論研究史 遊戯数学史 計算機利用
概要：三山崩しに代表される「石とりゲーム」は，日本においては少なくともWW2の戦前までは遊戯の対象としてのみ見られていた．本発表では，戦後の”デジタル”な計算機の導入期に遊戯以外の目的で石とりゲームが扱われた事例を紹介し，それらの意義に考察していく．
タイトル：入札組合せゲームの紹介と単貧民への応用
発表者：木谷裕紀
キーワード：入札組合せゲーム，単貧民
概要：入札組合せゲーム(Bidding combinatorial game)では，手番に関して入札を行い，入札額がより大きいプレイヤが次の手番プレイヤとなり，手番プレイヤとして着手後，再び入札を行いゲームが進行する．本発表ではKantらの結果https://arxiv.org/abs/2207.08073を紹介した後，単貧民への適用を行う．
タイトル：打ち切り優先正規系非不偏ゲームに関する研究
発表者：木谷裕紀
キーワード：正規系，非不偏，死局面
共著者：末續鴻輝
概要：打ち切り優先正規系非不偏ゲーム(仮名)に関して本研究では扱う．打ち切り優先正規系ゲームは，基本的には正規系，つまり最後に着手したプレイヤが勝ち(着手できなくなったプレイヤが負け)であるゲームだが，着手できなくなった局面の後続局面が着手できなくなったプレイヤにとって全て死局面だった場合，そのプレイヤの勝ちとする．本研究では高々両プレイヤの選択肢の和が1(つまりどちらかのプレイヤのみが着手可能)であるこのゲームに対して，ある種のゲームの値を定義し，その直和的性質を紹介する．
第5回日本組合せゲーム理論研究集会（2021年8月20日）
第5回日本組合せゲーム理論研究集会を開催します。新型コロナウイルス感染症の流行を踏まえ、今年もオンラインで開催することとなりました。使用ツールはZoomを予定しております。皆様のご参加をお待ちしております。
※研究集会は無事開催されました。たくさんのご参加いただきありがとうございました。
日時：2021年8月20日（金）
場所：オンライン
参加費：不要
参加申し込み：終了しました
（発表申込は8月9日23時59分8月16日23時59分、参加申込は8月19日23時59分までにお済ませください）
＜スケジュール＞※下線は発表者を示す
13:00 開会
13:05 チュートリアル１ 末續鴻輝「非不偏ゲームについて」
13:35 チュートリアル２ 安福智明「不偏ゲームについて」
14:15 前山和喜「組合せゲームにおける電子計算機の意義」
14:30 矢島雄河 ・前山和喜「二山NIMにおけるP-positionに関する実験と分析」
14:45 末續鴻輝「保証された得点付きゲームについて」
15:30 多田将人・安福智明「連続フック引き抜きゲームのGrundy数」
16:00 入江佑樹「p 進法における Sprague-Grundy 型の定理」
16:30 閉会
16:35 ワーキングセッション（希望者でグループに分かれたディスカッション）-18:00
＜発表内容＞
チュートリアル１：非不偏ゲームについて（末續鴻輝）
チュートリアル２：不偏ゲームについて（安福智明）
組合せゲーム理論の初学者や、あまりなじみのない参加者向けに、組合せゲーム理論の基礎的事項を紹介する。
タイトル：組合せゲームにおける電子計算機の意義（前山和喜）
概要：本発表では、組合せゲーム(理論研究)において、紙と鉛筆に代わる新たな道具として電子計算機が使われるようになった意義について考察を行なう。パズル本や数・数学（特に遊戯数学）に関する書籍や、RIMSで行なわれた研究集会の発表資料を対象として、その語られ方を分析した。
キーワード：組合せゲーム理論研究史 遊戯数学史 計算機利用
タイトル：二山NIMにおけるP-positionに関する実験と分析（矢島雄河 ・前山和喜）
概要：二山NIMのP-positionについて，コンピュータ実験と分析結果を発表する．実験ではランダムに決めたP-positionの局面集合から，新たなゲームの可能着手集合を生成し，それを使ってさらにゲームを実行することで，グランディ数を求めた．本発表では，この実験を通じて得られたP-positionの性質について論じる．
キーワード：二山NIM Grundy Number コンピュータ実験
タイトル：保証された得点付きゲームについて（末續鴻輝）
概要：組合せゲーム理論においてこれまでよく論じられてきた正規形／逆形という分類は、それぞれ最後の手を打った着手者を勝者／敗者とするものである。これに対し、得点付きゲームは、最後の手を打った着手者ではなく、盤上に生じる得点を勝敗の結果に用いる。本講演では、近年研究されている『保証された得点付きゲーム』について先行研究を紹介し、最後に『保証された得点付きゲーム』に属する新しいルールセットを提案する。
キーワード：得点付きゲーム 保証された得点付きゲーム カラードミナリング
タイトル：連続フック引き抜きゲームのGrundy数（多田将人・安福智明）
概要：長方形型Young図形に「山状番号付け」と呼ばれる番号付けを与え、この番号の情報をもとにフック引き抜きゲームの変種である組合せゲーム「連続フック引き抜きゲーム」を考案した。本発表では、連続フック引き抜きゲームにおいてフックの引き抜きが持つ性質について紹介する。また、開始局面がそれぞれ1×n，2×n，n×n，n×(n+1)の長方形型Young図形である場合を中心に、局面のGrundy数の解析結果について紹介する。
キーワード：組合せゲーム フック引き抜きゲーム Grundy数 Young図形 Weyl群
タイトル：Sprague-Grundy の定理の p-進法における類似物: マヤゲームの和と一般化対称群の表（入江佑樹）
概要：組合せゲーム理論では 2-進法が重要な役割を果たす. 特に Sprague-Grundy の定理から (不偏) ゲームの和の Sprague-Grundy 関数は, 各ゲームの Sprague-Grundy 関数のニム和と一致する. それでは p-進法が活躍するようなゲームはあるのだろうか？本講演では, Sprague-Grundy の定理の p-進法における類似物を紹介する. 具体的には, p-calm subtraction ゲームを導入し, p-calm subtraction ゲームの和の p-飽和の Sprague-Grundy 関数は, 各ゲームの p-飽和の Sprague-Grundy 関数の p-ニム和と一致することを紹介する (p-ニム和とは p-進法での繰り上がりのない和であり, ゲームの p-飽和とは元のゲームにいくつかの手 (グラフの言葉でいうと辺) を増やして得られるゲームである. また p-calm subtraction ゲームの例としてはニムやマヤゲームがある). この結果の応用として, マヤゲームと対称群の表現のある関係を, マヤゲームの和と一般化対称群の表現の関係に拡張できる.
キーワード：Sprague-Grundy 関数 p-ニム和 p-calm 性
第4回日本組合せゲーム理論研究集会（2020年8月30日, 31日 ）
第4回日本組合せゲーム理論研究集会を開催します。新型コロナウイルス感染症の流行を踏まえ、今年はオンラインで開催することとなりました。使用ツールはZoomを予定しております。皆様のご参加をお待ちしております。
日時：2020年8月30日-8月31日
場所：オンライン
参加費：不要
参加申し込み：こちらからお願いいたします。
（発表申込は8月29日11時59分、参加申込は8月29日23時59分までにお済ませください）
＜スケジュール＞
8月30日（日）
13時10分～13時15分 開会
13時15分～14時00分 チュートリアルセッション「不偏ゲームについて」
14時15分～15時15分 セッション１
入江佑樹「ゲームとデザイン」
安福智明・茂木祐紀・多田将人「2人Numbers Game」
15時30分～16時30分 セッション２
篠田正人「数当てゲームの最適戦略」
宮寺良平「同時に２つの山から石を取ることができるタイプの石取りゲームにおいて、Grundy数が排他的論理和に一致する例について」*
小林靖明「ピッチャーを空にできるか？」*
8月31日（月）
13時00分～13時45分 チュートリアルセッション「非不偏ゲームについて」
14時00分～15時00分 セッション３
木谷裕紀・末續鴻輝「組合せゲーム理論を用いたパス七並べの解析」
大渡勝己「二人単貧民の定理をCoqで証明する試み」
15時15分～16時30分 セッション４
林大翔・宮寺良平「裏表パズルについて」*
末續鴻輝「3日目までに生まれたゲームの観察」
前山和喜「計算機を用いたパズルとゲームの研究史―1970年代を中心に―」
16時30分～16時35分 閉会
*印のついた発表は15分、それ以外は30分です。
スケジュール等、随時更新していきます。
＜概要＞
入江佑樹「ゲームとデザイン」
＜キーワード＞ 不偏ゲーム 必勝局面 Steiner system
良い「配置」について研究する組合せデザイン理論は、もとは統計学において実験計画法という名で研究が進められてきた分野である。デザインから特別な代数構造が得られる場合があり、デザインは代数的にも重要な研究対象である。デザインの特別な族に Steiner system と呼ばれるものがある。Conway と Ryba は 必勝局面集合がある Steiner system になる、hexad ゲームというゲームを研究した。しかし、hexad ゲームのように Steiner system と関係するゲームの例は、これまでほとんど知られていなかった。本講演では、任意の Steiner system D に対して、必勝局面集合が D となる（不偏）ゲームの構成法をあたえる。そして、構成したゲームを使って、projective Steiner triple system と呼ばれる族が特徴付けられることを紹介する。
安福智明・茂木祐紀・多田将人「2人Numbers Game」
＜キーワード＞組合せゲーム アフィン・リー代数
Numbers Gameと呼ばれる円形のグラフ上の一人遊びのゲームについて、その2人ゲーム版を考察する。このゲームの操作はアフィン・ワイル群の作用にも対応している。我々は、このゲームについて、3頂点の場合のゲームの長さとGrundy数について、得られた結果を紹介する。
篠田正人「数当てゲームの最適戦略」
＜キーワード＞ 数当てゲーム 期待値最小化戦略
AB Game と呼ばれる数当てゲームで、正解するまでの回答数の期待値を最小化する戦略について考察する。このAB Game は MOO またはBulls and Cows という名でも呼ばれており、10種の数字を4つ並べる4×10 Gameが一般的であるが、本発表ではN種の数字を3つ並べる3×N Gameの回答数の期待値を最小化する戦略について、発表者の研究結果（情報処理学会誌Vol.53 No.6）を中心に紹介する。
宮寺良平「同時に２つの山から石を取ることができるタイプの石取りゲームにおいて、Grundy数が排他的論理和に一致する例について」
木谷裕紀・末續鴻輝「組合せゲーム理論を用いたパス七並べの解析」
＜キーワード＞ 七並べ 組合せゲーム理論
本研究では二人で行う札の枚数を一般化した七並べについて先にパスをしたプレイヤが負けという亜種のゲームを定義し，組合せゲーム理論を用いてその解析を行う． まず，その必勝戦略保持者が札の総枚数の線形時間で得られることを示す．また，オールマイティ札と呼ばれる特殊札を含めても線形時間で必勝戦略保持者を計算することができることを示す．
大渡勝己「二人単貧民の定理をCoqで証明する試み」
＜キーワード＞ 大富豪 単貧民 グラフ理論
定理証明支援系Coqによって、組合せゲームの一つである二人単貧民の勝敗に関する定理の証明を試みる。
林大翔・宮寺良平「裏表パズルについて」
＜キーワード＞ 裏表パズル ルービックキューブ
裏表パズルの先行研究の発表と、裏表パズルをiOSアプリとし実装したので、その紹介を行う。
末續鴻輝「3日目までに生まれたゲームの観察」
＜キーワード＞ 非不偏ゲーム n日目までに生まれたゲーム
n日目までに生まれたゲーム全体の集合がどのような性質を持つのかは非不偏ゲームの研究における重要な未解決問題である。本研究ではこれまでに知られている2日目までに生まれたゲームや3日目までに生まれたゲームを、CGSuiteなどを利用しながら注意深く観察することで得られた新たな結果について紹介する。
前山和喜「計算機を用いたパズルとゲームの研究史―1970年代を中心に―」
＜キーワード＞ ゲーム史 パズル史 コンピューティング史 計算機利用
1970年代に京都大学数理解析研究所で行われたコンピュータ（計算機）によるパズルとゲームに関する研究会での議論の記録を題材とし，主に数学者らによって計算機が利用された意義について析出する．
組合せゲーム理論ミニワークショップ （2020年2月21日 , 3月19日）
海外の研究者が来てくださる，組合せゲーム理論のミニワークショップを開催いたします．
第一回(Carlos Santos先生) 2月21日（金）13:00- 国立情報学研究所 神田ラボ
※予定通りに開催されました。多くのご参加ありがとうございました。
第二回(Richard Nowakowski先生) 3月19日（木） 津田塾大学 千駄ヶ谷キャンパス
13:00-14:45
招待講演[TBA]:(Richard Nowakowski,Dalhousie University)
15:00-16:30
"Square and Rectangular Nim":(片山真一, 徳島大学)
"A new universal ruleset":(末續鴻輝, 国立情報学研究所)
"Vertex Nim on Cayley Graph":(安福智明, 筑波大学)
※新型コロナウイルスの感染拡大に伴い，Nowakowski先生の来日およびミニワークショップの開催は中止されました．
第3回日本組合せゲーム理論研究集会（2019年8月27日, 28日 ）
日程：8月27日～8月30日(前半：研究集会，後半：セミナー合宿. )
開催地：基山町民会館(佐賀県三養基郡基山町)(一階会議室)
アクセス：JR基山駅（博多駅から鹿児島本線下り快速を利用で約30分）から徒歩10-15分程度.
*基山駅よりコミュニティバスも利用可能です. 降車バス停は基山町民役場が便利です.
宿泊地候補：基山合宿所(開催地と隣接しています. 夜まで議論したい方はおすすめです．
（発表の有無の変更は8月21日まで、発表タイトル変更は8月25日までにお願いします)
参加費：500円
組織運営委員会
木谷裕紀
末續鴻輝
安福智明
坂井公
簡易スケジュール（8月28日9時10分更新）
※研究集会は発表の数に関わらず2日間開催します。
※特別警報発令に伴い8月28日の開始時刻を14時に変更しました。
８月27日（火）
12:50-13:10 受付
13:15-18:00 研究集会
8月28日（水）
14:00-18:00 研究集会
18:00- 解散（合宿参加者はそのまま残ります）
29日，30日の日程につきましてはセミナー合宿ページをご覧ください．
詳細プログラム(発表者敬称略)
8/27(基山町民会館1階会議室))(13時開場)
13:15-14:15(チュートリアルトーク1)
1.不偏ゲームと未解決問題(末續)
14:40-16:20(不偏ゲーム1)
2.組合せゲームとＷeyl群 (安福)
3.まるけし研究のその後(木谷)
4. 一般化対称群の表現とWelterゲームの和(入江)
16:40-(working session)
8/28(基山町民会館視聴覚室)
14:00-14:30(チュートリアルトーク2)
5.非不偏ゲームについて(安福)
14:40-15:45(非不偏ゲーム)
6. 複数系列で行う単貧民(木谷)
7. 逆型ゲームを用いた囲碁の攻合いの定式化(中村)
15:55-17:00(不偏ゲーム2)
8. 要素数4のFES集合で行うAll-but Nim(末續)
9. 超限実数について(坂井)
17:00-Working session
第2回日本組合せゲーム理論研究集会（2018年8月17日, 18日）
場所：筑波大学（アクセス）
（電車をご利用の場合）
秋葉原駅→つくばエクスプレス「つくば駅」A3出口→バス6番乗り場「筑波大学中央」「筑波大学循環（右回り）」→「第一エリア前」下車→徒歩約1分→総合研究棟B（19日のみ自然学系棟D）
（高速バスをご利用の場合）
東京駅八重洲南口→「大学会館前」下車→徒歩約5分→総合研究棟B（19日のみ自然学系棟D）
日程：2018年8月17日～8月20日
(前半：研究集会，後半：セミナー合宿）
参加費：無料（食費＆宿泊費別途）
宿泊所：筑波大学の宿泊所が工事中であるため，一般の宿泊施設をご利用ください．
宿泊施設候補：
・筑波研修センター（安くてオススメです）
セミナー教室：筑波大学総合研究棟B0110＆B0108（19日と20日は自然学系棟D509）
集合場所：同上
組織運営委員会
安福智明
末續鴻輝
入江佑樹
木谷裕紀
前山和喜
坂井公
≪予定≫
８月17日（金）
12:30-13:00 受付
13:00-18:00 研究集会
8月18日（土）
9:30-12:00 研究集会
11:20-13:30 昼休憩
13:30-18:00 研究集会
18:00- 解散（合宿参加者はそのまま残ります）
8月19日（日）
9:30-12:00 研究会
12:00-13:30 昼休憩
13:30-18:00 研究会
18:00- 夕食
8月20日（月）
9:30-12:00 研究会
12:00-13:30 昼休憩
13:30-16:00 研究会
16:00- 解散
プログラム：
タイトルと発表概要：
１日目（8月17日）
『組み合わせゲーム理論の囲碁への応用』瀧澤武信
キーワード：数理碁
囲碁への応用の概要．研究者の紹介
『トランプゲームと組合せゲーム』木谷裕紀
キーワード：組合せゲーム 単貧民
不完全情報ゲームであるいくつかのトランプゲームは完全情報化することによって組合せゲームの非不偏ゲームとして考えることができる.それらのゲームの戦略に関して考察する.
『Conwayの標数 2 の体 On_2 について』坂井公
順序数の全体は，ニム和とニム積を基本演算とすることにより GF(2)={0,1} の拡大体として標数 2 の代数的閉体 On_2 となる。演算の定義，性質，計算法，代数方程式の求解など On_2 にかかわるいくつかの問題について話をする。
2日目（8月18日）
『n手詰ルーラー』新田佳菜, 橋本梨菜, 貞廣泰造
キーワード：コイン裏返しゲーム, 正規表現
ターニング・タートルズなどの一部のコイン裏返しゲームの局面を0,1列で表現すると、ルールを正規表現で記述でき、局面遷移行列がある種の自己相似性を持つことがわかる。この事実の応用例を報告する。
『直前手番によるニムとマンカラニムのグランディ数の分析』前山和喜, 坂井創一
キーワード：Nim，Grundy Number，フィボナッチニム，直前手番によるニム，マンカラニム，可視化
フィボナッチニム（直前の２倍の個数まで石を取れるニム）に代表される直前手番により行動の制限を受けるニムと，手番後に取った石をマンカラのように他の山に分配するニムのグランディ数の基礎的な解析の結果を報告する．また，これらのゲームのグランディ数の分析には多次元のテーブルを作る必要があるため，この可視化の手法も合わせて紹介する．
『Edge geographyなどの様々な不偏ゲームの解析』安福智明, 小林靖明
キーワード：Impartial game, Grundy value, graph
グラフ上の不偏ゲームについて紹介する．特に二部グラフにおいては，隣接行列のrankにより必勝判定ができることが知られている．また，その他の不偏ゲームについても言及する．
『グラフ上のニムについて』小林靖明, 安福智明
キーワード：グラフ，ニム，計算量理論
ニムの一般化のひとつとして，グラフ上のニムが知られている．グラフ上のニムでは頂点や辺に山があるニムを考え，どの山から石が取れるかはそのグラフの構造によって制約される．本発表では，グラフ上のニムには様々な定義があることを紹介し，既存の研究結果や未解決問題を中心に紹介する．
『Grundy_Loopとn進表記』末續鴻輝
キーワード：竜王NIM、Wythoff、Loop(代数構造)、n進表記
竜王NIMやWythoffなどのGrundy数の表を、二次元の演算表とみなしたとき、そこにはLoopと呼ばれる代数構造が観測できる。本研究では、その構造を利用して、NIMに関係する2進表記だけでなく、n進表記と関連するゲームを構成することについて紹介する。
『ゲームと表現のつながり』入江佑樹
キーワード：群の表現，Sprague-Grundy関数
ゲームと表現の間の一つのつながりを紹介する．1970年代頃，佐藤幹夫は「マヤゲームのSprague-Grundy関数の明示公式」と「対称群のフック公式」の形が似ていることなどから，両者には見かけ以上の関連があることを予想した．本講演では対称群の既約表現の次数に関する定理を与え，これを使い p 飽和マヤゲームのSprague-Grundy関数の明示公式が得られることを紹介する．
第1回日本組合せゲーム理論研究集会（2017年10月1日）
2017年10月1日(日)に、京都大学にて第1回日本組合せゲーム理論研究集会(JCGTW)を開催いたします。
組合せゲーム理論(CGT)に関することなら何でもありの研究集会です。
午前中に基礎知識を共有するセッションを設けますので、組合せゲーム理論に興味があるけれど予備知識がなくて……という方もどうぞお気軽にご参加ください。
参加申し込みはこのページの下にある申し込みフォームよりどうぞ。
皆様のご参加をお待ちしております。
日程:10月1日 10:00-18:00
場所:京都大学 総人棟1401(以下の地図の84番の建物、4階です)
タイムテーブル:
10月1日
9:30-10:00
受付
10:00-10:10
開会宣言
10:10-11:30
チュートリアルセッション;組合せゲーム理論の基礎
11:30-13:00
昼食休憩
13:00-13:15
前山和喜;"約数ニムについて"
13:15-13:45
高野凌史;"多次元Mayaゲームと多次元Silver Dollarにおける必勝法の解明"
13:45-14:15
安福智明;"3次元竜王ニムと新しいゲームについて"
14:15-14:45
末續鴻輝;"いくつかの興味深いGrundy数導出式を持ったゲーム"
14:45-15:00
休憩
15:00-15:15
福井昌則;"組合せゲーム理論の教育利用の可能性について"
15:15-15:45
小林靖明;"Node Kaylesとその一般化について ～アルゴリズム的組合せゲーム理論の観点から～"
15:45-16:15
中村貞吾;"組合せゲーム理論を用いた囲碁局面の解析"
16:15-16:45
山崎洋平;"古典的ゲームのルールをウォッチングする"
16:45-18:00
議論・閉会宣言
組織運営委員会
末續鴻輝
安福智明
福井昌則
織田祐輔
坂井公
立木秀樹
宮寺良平
タイトルと概要
1.約数ニムについて:前山和喜，落合竜也，牧野潔夫
キーワード:ニム，グランディ数 「取ることが出来る石の個数は，山の石の個数の真の約数個」という制限をつけたニムについて，そのゲームの解析とグランディ数について報告する．
2.多次元Mayaゲームと多次元Silver Dollarにおける必勝法の解明:高野凌史,廣川快,水田和成,坂本悠輔,宮寺良平,末續鴻輝
キーワード:Corner the Queen, Sato-Welter game,The Sliver Dollar Game
NIM(石取りゲーム)の変種である Corner the Queen (Wythoff’s Game) の条件を変えて,複数のRookの場合を考えた。他の駒を飛び越えることができるとすると、多次元Mayaゲームとなり、飛び越えれないと 多次元Silver Dollarとなる。２次元MayaゲームでRook２つの場合は、 P-position (後手必勝手)をニム和(排他的論理和)で表した。 2次元Silver Dollarにおいては,Rook２つの場合、いくつかの状況において,P-positionの判定法を見つけた. ２次元MayaゲームでRook3つの場合は、Grundy数よりも計算速度の速い関数を見つけた。
3.3次元竜王二ムと新しいゲームについて:安福智明，末續鴻輝，福井昌則
キーワード:Nim, Impartial game, Wythoff
ワイトホフ二ムの変種である竜王二ムを3次元へと拡張し，その後手必勝形について発表する．また，ナイトツアーの変種である新しいゲームのルールと周期性について発表する．
4.いくつかの興味深いGrundy数導出式を持ったゲーム:末續鴻輝
キーワード:不偏ゲーム, Grundy Number, それは俺の魚だ！
不偏ゲームのGrundy Numberを導出する公式はそのゲームによって異なり、公式が見つかっていないゲームも存在するが、一方でNIM和やNIM積のような美しい導出法も研究されてきた。本研究では、ボードゲーム”それは俺の魚だ！”を元にした不偏ゲームの盤面を一次元に限定した場合、駒の左右にあるマスの数を2進展開し、”両方ともに0になる最も低い桁”に着目することで、Grundy Numberを求めることができることを示す。さらに、それ以外にも興味深いGrundy Number導出公式を持つゲームについて議論する。
5.組合せゲーム理論の教育利用の可能性について:福井昌則
キーワード:創造性，数学教育，創造的問題解決
従来から現在に至るまで，教育において創造性が重要であると随所で述べられてきた．しかし，その創造性の定義や育成方法に至る内容は，未確定であったり多義的であったりするのが現状である．そこで，創造性の定義について概観し，新事実の発見も視野に入れた創造的問題解決が可能である組合せゲーム理論の今後の教育利用およびその可能性について検討を行う．
6.Node Kaylesとその一般化について ～アルゴリズム的組合せゲーム理論の観点から～:小林靖明
キーワード: Node Kayles,計算複雑性
Node KaylesはKayles(ボーリングに似た不偏ゲーム)をグラフ上に拡張したゲームであり，Schaefer(1978)によってPSPACE完全性が証明されたこの問題は別の組合せゲームの困難性を議論するときに良く用いられ，またアルゴリズムの研究も良く行われている．本発表では，Node Kaylesとそれに対するアルゴリズム的な結果のキーとなるアイデアを紹介し，Node Kaylesが(ある意味で)効率良く解けるケースについて紹介する．また，Node Kaylesやその一般化の問題に対する未解決問題をいくつか紹介する．
7.組合せゲーム理論を用いた囲碁局面の解析:中村貞吾
キーワード:囲碁，ヨセ，コウ，眼形，攻合い
組合せゲーム理論の囲碁への適用として，これまでに，ヨセの解析，コウの解析，眼形の解析，攻合い解析などが行なわれてきている．本発表では，その内容を概説する．
8.古典的ゲームのルールをウォッチングする:山崎洋平
キーワード:ゲームのルール
長年にわたって多くの人に支持されてきたゲームにはそれなりの長所がある。ルールに関しては簡素であるほどよい。一方で競技するという観点からは単純には解明しがたい深遠さが要求される。また引き分けになりにくいこと、そして両競技者に対する公平感が望まれる。このトークではこういった競技実践上の欲求がルールに対して（人知れず）及ぼす軋みについて論じる。
