研究集会

※参加に際し何かお困りの際は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年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
未解決問題情報共有＆議論セッション

どうぞよろしくお願いいたします。

（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回日本組合せゲーム理論研究集会を開催します。新型コロナウイルス感染症の流行を踏まえ、今年もオンラインで開催することとなりました。使用ツールは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回日本組合せゲーム理論研究集会を開催します。新型コロナウイルス感染症の流行を踏まえ、今年はオンラインで開催することとなりました。使用ツールは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年代に京都大学数理解析研究所で行われたコンピュータ（計算機）によるパズルとゲームに関する研究会での議論の記録を題材とし，主に数学者らによって計算機が利用された意義について析出する．

海外の研究者が来てくださる，組合せゲーム理論のミニワークショップを開催いたします．

第一回(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先生の来日およびミニワークショップの開催は中止されました． 

日程：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

場所：筑波大学（アクセス）

（電車をご利用の場合）

秋葉原駅→つくばエクスプレス「つくば駅」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関数の明示公式が得られることを紹介する．

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.古典的ゲームのルールをウォッチングする:山崎洋平

　キーワード:ゲームのルール

　長年にわたって多くの人に支持されてきたゲームにはそれなりの長所がある。ルールに関しては簡素であるほどよい。一方で競技するという観点からは単純には解明しがたい深遠さが要求される。また引き分けになりにくいこと、そして両競技者に対する公平感が望まれる。このトークではこういった競技実践上の欲求がルールに対して（人知れず）及ぼす軋みについて論じる。