研究集会

ダウンロード
第4回組合せゲーム理論研究集会 チュートリアルセッション 非不偏ゲームについて
チュートリアル2020.pdf
PDFファイル 1.2 MB

第4回日本組合せゲーム理論研究集会について

 

第4回日本組合せゲーム理論研究集会を開催します。新型コロナウイルス感染症の流行を踏まえ、今年はオンラインで開催することとなりました。使用ツールはZoomを予定しております。皆様のご参加をお待ちしております。

 

※本研究集会は無事に開催されました。たくさんのご参加・ご発表いただき誠にありがとうございました。

 

日時:2020年8月30日-8月31日

場所:オンライン

参加費:不要

参加申し込み:申込受付は終了しました

 

<組織運営委員>

 末續鴻輝

 安福智明

 Diptarama

 木谷裕紀

 前山和喜

 

 

<スケジュール>

8月30日(日)

13時10分~13時15分 開会

13時15分~14時00分 チュートリアルセッション「不偏ゲームについて」

14時15分~15時15分 セッション1

 

入江佑樹「ゲームとデザイン」

安福智明・茂木祐紀・多田将人「2人Numbers Game」

 

15時30分~16時30分 セッション2

 

篠田正人「数当てゲームの最適戦略」

宮寺良平「同時に2つの山から石を取ることができるタイプの石取りゲームにおいて、Grundy数が排他的論理和に一致する例について」*

小林靖明「ピッチャーを空にできるか?」*

 

8月31日(月)

13時00分~13時45分 チュートリアルセッション「非不偏ゲームについて」

14時00分~15時00分 セッション3

 

木谷裕紀・末續鴻輝「組合せゲーム理論を用いたパス七並べの解析」

大渡勝己「二人単貧民の定理をCoqで証明する試み」

 

15時15分~16時30分 セッション4

 

林大翔・宮寺良平「裏表パズルについて」*

末續鴻輝「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)を中心に紹介する。

 

宮寺良平「同時に2つの山から石を取ることができるタイプの石取りゲームにおいて、Grundy数が排他的論理和に一致する例について」

 

小林靖明「ピッチャーを空にできるか?」

 映画「ダイ・ハード3」では次のような場面がある.ジョン・マクレーン刑事のもとに「サイモン」と名乗る爆弾テロの犯人から次のような電話がある.「噴水のところに3ガロンと5ガロンの容器がある.爆弾を解除したければ,5分以内にちょうど4ガロン計って計測器に乗せろ.さもないと爆発するぞ.」 さて,ここに3つの容器があり,それぞれに水が入っている.発表時間以内に空にできるかな?さもないと・・・,というのはもちろん冗談で,興味深いパズルを紹介します.

 

木谷裕紀・末續鴻輝「組合せゲーム理論を用いたパス七並べの解析」

<キーワード> 七並べ 組合せゲーム理論

 本研究では二人で行う札の枚数を一般化した七並べについて先にパスをしたプレイヤが負けという亜種のゲームを定義し,組合せゲーム理論を用いてその解析を行う. まず,その必勝戦略保持者が札の総枚数の線形時間で得られることを示す.また,オールマイティ札と呼ばれる特殊札を含めても線形時間で必勝戦略保持者を計算することができることを示す.

 

大渡勝己「二人単貧民の定理を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先生の来日およびミニワークショップの開催は中止されました. 

 

 

 

第3回日本組合せゲーム理論研究集会(JCGTW)は無事開催されました. 

日程:8月27日~8月30日(前半:研究集会,後半:セミナー合宿. )

開催地:基山町民会館(佐賀県三養基郡基山町)(一階会議室)

アクセス:JR基山駅(博多駅から鹿児島本線下り快速を利用で約30分)から徒歩10-15分程度. 

*基山駅よりコミュニティバスも利用可能です. 降車バス停は基山町民役場が便利です. 

宿泊地候補:基山合宿所(開催地と隣接しています. 夜まで議論したい方はおすすめです.

(発表の有無の変更は8月21日まで、発表タイトル変更は8月25日までにお願いします)

参加費:500円

 

組織運営委員会       

         木谷裕紀

  末續鴻輝

         安福智明

  坂井公 

簡易スケジュール(8月28日9時10分更新)

※研究集会は発表の数に関わらず2日間開催します。

※特別警報発令に伴い8月28日の開始時刻を14時に変更しました。

8月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.組合せゲームとWeyl群 (安福)

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回日本組合せゲーム理論研究集会(JCGTW)は、無事開催されました

 

 2018年8月17日-8月18日、第2回日本組合せゲーム理論研究集会を筑波大学にて開催いたしました。

 多く方にご参加,発表をいただき、盛況のうちに幕を閉じました。

 参加者、発表者の皆様には厚く御礼申し上げます。

 

 今後も開催を続けていく予定です。詳細は決まり次第こちらのWebページで告知いたします。

 

<研究集会の様子>

第2回組合せゲーム理論研究集会と第3回組合せゲーム理論セミナー合宿を同時開催します.

 

場所:筑波大学(アクセス

(電車をご利用の場合)

秋葉原駅→つくばエクスプレス「つくば駅」A3出口→バス6番乗り場「筑波大学中央」「筑波大学循環(右回り)」→「第一エリア前」下車→徒歩約1分→総合研究棟B(19日のみ自然学系棟D

(高速バスをご利用の場合)

東京駅八重洲南口→「大学会館前」下車→徒歩約5分→総合研究棟B(19日のみ自然学系棟D

日程:2018年8月17日~8月20日

(前半:研究集会,後半:セミナー合宿)

参加費:無料(食費&宿泊費別途)

宿泊所:筑波大学の宿泊所が工事中であるため,一般の宿泊施設をご利用ください.

 

宿泊施設候補:

筑波研修センター(安くてオススメです)

ダイワロイネットホテルつくば

オークラフロンティアホテルつくば

ホテルつくばヒルズ

 

セミナー教室:筑波大学総合研究棟B0110&B0108(19日と20日は自然学系棟D509

集合場所:同上

 

組織運営委員会

 

  安福智明

  末續鴻輝

         入江佑樹

  木谷裕紀

  前山和喜

  坂井公

  

≪予定≫

8月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-  解散

 

プログラム:


タイトルと発表概要:
 
1日目(8月17日)
『組み合わせゲーム理論の囲碁への応用』瀧澤武信 
キーワード:数理碁
囲碁への応用の概要.研究者の紹介

 
『トランプゲームと組合せゲーム』木谷裕紀
キーワード:組合せゲーム 単貧民
不完全情報ゲームであるいくつかのトランプゲームは完全情報化することによって組合せゲームの非不偏ゲームとして考えることができる.それらのゲームの戦略に関して考察する.


『Conwayの標数 2 の体 On_2 について』坂井公
順序数の全体は,ニム和とニム積を基本演算とすることにより GF(2)={0,1} の拡大体として標数 2 の代数的閉体 On_2 となる。演算の定義,性質,計算法,代数方程式の求解など On_2 にかかわるいくつかの問題について話をする。


2日目(8月18日)
『n手詰ルーラー』新田佳菜,  橋本梨菜, 貞廣泰造
キーワード:コイン裏返しゲーム, 正規表現
ターニング・タートルズなどの一部のコイン裏返しゲームの局面を0,1列で表現すると、ルールを正規表現で記述でき、局面遷移行列がある種の自己相似性を持つことがわかる。この事実の応用例を報告する。


『直前手番によるニムとマンカラニムのグランディ数の分析』前山和喜,  坂井創一
キーワード:Nim,Grundy Number,フィボナッチニム,直前手番によるニム,マンカラニム,可視化
フィボナッチニム(直前の2倍の個数まで石を取れるニム)に代表される直前手番により行動の制限を受けるニムと,手番後に取った石をマンカラのように他の山に分配するニムのグランディ数の基礎的な解析の結果を報告する.また,これらのゲームのグランディ数の分析には多次元のテーブルを作る必要があるため,この可視化の手法も合わせて紹介する.


『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関数の明示公式が得られることを紹介する.