eポートフォリオ(ePortfolio)

Accept済(出版準備中) Will be appeared

Acceped : September 13th, 2024 Published(Online) : December 20th, 2024 Published(Paper) : December, 2024 Acceped : September 13th, 2024 Published(Online) : December 20th, 2024 Published(Paper) : December, 2024

中学・高校生向けに組合せゲーム理論の中でも不偏石取りゲームに絞って、基礎から現在活発に行われている研究対象のゲームの理論まで解説した。

修士論文の内容について口頭発表した。

Yama Nim は発表者が修⼠論⽂で報告したゲームであり、 ⼀⽅の⼭から 2 個以上の⽯を取り、もう⼀⽅の⼭に 1 個戻す、という着⼿の 2 ⼭の⽯取りゲームである。TriangularNim は、Yama Nim の⾃然な拡張で、⼀⽅の⼭から 2 個以上の⽯を取り、全体として⽯が減るようにもう⼀⽅の⼭に少なくとも 1 個以上戻す、という着⼿の 2 ⼭の⽯取りゲームである。両者のゲームの必勝法は、2 つの⽯の個数の差が 1 個以下の時に良形になる。 本発表では、 まず Triangular Nim の Wythoff バリエーションの正規形の必勝法について説明を⾏う。このゲームは、 Triangular Nim の着⼿に加え、 𝑖と𝑗の制限の下で、プレイヤーが両⽅の⼭から⽯を取ることが許される、例えば 𝑖個の⽯を⼀⽅の⼭から、𝑗個の⽯をもう⼀⽅の⼭から取ることができる。𝑖 = 𝑗 > 0 としたとき、このゲームの局⾯(𝑥, 𝑦) の良形は、 𝑥 ≤ 𝑦 として、(𝑥, 𝑦) ∈ {(0, 0), (0, 1), (1, 3), (3, 6), (6, 10), (10, 15), . . . } すなわち、連続した三⾓数である。⼀般化したとき、(つまり、𝑖, 𝑗 > 0かつ|𝑖 = 𝑗| ≤ 𝑐 のとき、) 必勝局⾯が連続した(c+3)⾓数で記述できることも分かった。 その後、逆形のルールについても𝑐 = 0と𝑐 ≥ 1で異なる記述が得られたので、それについても報告する。 その他、 Triangular Nim を⼀般化したゲーム((𝑎, 𝑏)- Triangular Nim)の Wythoff バリエーションについて⾯⽩い結果が得られたので、それについても報告する。

査読有の国際研究集会

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で面白い現象を発見したので、紹介する。

奈良女子大学の篠田正人先生の招待で、Yama Nimとその一般化について研究紹介をしました。 また、それぞれの研究に関する交流も行いました。

査読有の国内研究集会

発表者は木村俊一氏

発表者は木村俊一氏

発表者は修士論文で「⽯の⼭が２つあり、プレイヤーはどちらかの⼭から2個以上⽯を取り、もう⼀⽅の⼭に⽯を1 個戻す」ルールである Yama Nim を考案し、正規形と逆形のルールの必勝法とグランディ数の解析に成功した。また、Urban先生との研究ディスカッションや自身の研究の進捗でここ数ヶ月で一般化したルールの必勝法とグランディ数について解析ができたものについて説明を行う。最後に、修士論文ではYama Nim の正規形でも逆形でもないルールの必勝法とグランディ数についても解析しており、そこについてもその後に出てきた新たな結果も含めて説明できればと思っている。

同じ局面集合に着手ルールが2つあり、どのルールで着手するのかを相手が決めるという設定での組合せゲームをComply/constrain operator of conbinatorial gamesと呼ぶ。このゲームは、一見複雑なルールでも、正規形のルールの下である条件を満たせば、必勝法が分かることが共同研究で分かった。本発表では、その条件について具体例を交えながら説明する。また、その条件から分かる性質や逆形のComply/constrainの面白い例について紹介する。

Yama Nimは2山の不偏石取りゲームであり，プレイヤーは，一度の着手で片方の山から石を2個以上取り，もう片方の山に石を1個加える．Digraph Yama NimはYama Nimの一般化であり，有向グラフの各頂点に石が乗っていて，プレイヤーはある頂点を選び，そこからその頂点の出自数+1個以上の石を取り，その頂点からの各有向辺の先にある頂点それぞれに1個ずつ石を加える，というゲームである．本研究では，いくつかの特徴的な有向グラフ上でのDigraph Yama Nimについて，局面がP局面（後手番のプレイヤーに必勝戦略がある局面）となるための必要十分条件を求めたので，それを報告する．

石取りゲーム（ニム）は，1900年代初頭のBoutonによる業績を始めとし，これまでそれ自身や数多くの変種においてその勝敗判定に関する研究が行われてきた．それらの変種の中にはある山の石の個数を減らすとともに他の山の石の個数を増加させるルールもあるが，それらは石の総数が真に減少するもののみを合法手とすることによって，ゲームが有限回の着手で終わることを保証している．本研究では石の総数が減ることを保証しないが有限回の着手で終わることを保証する，有向グラフを用いた新たな石取りゲーム「増殖ニム」を提案する．

有向グラフ上の石取りゲームを考える．本稿で扱うゲームでは，各頂点にそれぞれ石がいくつか置かれていて，プレイヤーは有向辺を1つ選び，その始点から1個以上何個でも石を取る．それで着手を終えてもよいし，あるいは，取った石のいくつかを終点の頂点に戻してもよい．ただし，取った石全てを戻してはならない．3頂点A,B,Cと3辺A→B,B→C,C→Aを持つグラフ上でこのゲームの後手必勝局面を調べたところ，その記述に黄金比が現れたので，そのメカニズムを報告する．

Yama Nim は、2 人目の筆者の修士論文で初めて紹介された 2 山 Nim の一種で、一方の山から2 個以上の石を取り、もう一方の山に 1 個の石を戻すゲームである。 Triangular Nim はその一般化であり、一方の山から 2 個以上の石を取り、全体として石が減るようにもう一方の山に少なくとも 1 つ以上戻してよいと拡張した石取りゲームである。 本論文では、これらのゲームの必勝戦略、グランディ数、及び Wythoff バリエーションについて報告する。 特に興味深いのは Triangular Nim の Wythoff バリエーションであり、Triangular Nim の着手に加え、i と j の制限の下で、プレイヤーが両方の山から石を取ることが許される、例えば i 個の石を一方の山から、j 個の石をもう一方の山から取ることができる。 例えば、Triangular Nim で i = j > 0 としたとき、局面 (x, y) の必勝局面は、x ≥ y として、(x, y) ∈ {(0, 0), (1, 1), (3, 6), (6, 10), (10, 15), ...} すなわち、連続した三角数である。他のバリエーションでは、四角数、五角数、べき乗数、メルセンヌ数で記述できる例も見つかった。 Yama Nim is a two heaps Nim game introduced in the second author’s Master Thesis, where the player takes more than 2 tokens from one heap, and return 1 token to the other heap. Triangular Nim is a generalization, where the player takes several tokens from one heap, and return some tokens (at least one token) to the other heap, so that the total number of the tokens in the heaps decrease strictly. In this paper, we investigate their winning strategies, Grundy numbers, and Wythoff variations. Particularly interesting is the Wythoff variations, where in addition to the Triangular Nim moves, the player is allowed to take tokens from both heaps, say i tokens from the first heap and j tokens from the other, under some restrictions for i and j. For example when we force i = j > 0 for the Triangular Nim, then (x, y) ∈ Z≥0 with x ≤ y is in the P-position if and only if (x, y) ∈ {(0, 0), (0, 1), (1, 3), (3, 6), (6, 10), (10, 15), ...}, namely the winning strategy is described by triangular numbers. In other rulesets, we also found examples where the square numbers, pentagonal numbers, geometric progressions, Mersenne numbers, and so on.

We introduce Yama Nim, a variation of Nim played on a two-dimensional semi-infinite game board, with terminal positions in the upper left corner. The player can move two or more up steps and one right step, or two or more left steps and one down step. If a player cannot move, they lose. We find the solution to this game. We also consider a comply/constrain operator on impartial rulesets. Applied to the rulesets A and B, on each turn the opponent proposes one of the rulesets and the current player complies, by playing a move in that ruleset. If the outcome table of the comply/constrain variation of A and B is the same as the outcome table of A, then we say that B is dominated by A. We show necessary and sufficient conditions of “A dominates B”. Yama Nim is a good example that dominates classical rulesets such as Nim and Wythoff Nim.