石取りゲームってなーに

石取りゲームとは一般的には

「２人のプレイヤーが場にある石を順番にとりあっていく。この際一度にとれる石の数は決まっている。最後の石を取った方の勝ち（あるいは負け）」

というルールのゲームを指します。（以下、この記事では最後の石を取ったほうを勝ちとします。） このようなゲーム1度はやったことがあるって人も多いのではないでしょうか？

一般的な石取りゲームの勝者判定方法

このルールの場合、プレイヤーが最適に動いた場合、先手が勝つのか後手が勝つのかを判定することができます。はじめに場にある石の数をN個、一回でとれる石の数をK個とした場合Nを（K+1）で割った余りが０なら後手の勝ちで、そうでないなら先手が勝ちます。詳説は省きますが、1周期分の操作で相手がどう動こうと（K+1）個の石が取れるためこの判定ができます。

競技プログラミング関連でよく見かける

競技プログラミングにおいては

「場にN個の石の山があります。それぞれの山の石の数は$A_{i}$($1<=i<=N$)個です。プレイヤーは自分の番に好きな石の山を1つ選び、その石の山から好きなだけ石を取ります。石が1つも取れなくなった方のプレイヤーの負け。」

といった、ルールの石取りゲームが有名（？）です。 この場合においても、プレイヤーが最適に動いた場合にどちらが勝利するかを判定できるのでしょうか？なんと、この場合にも判定できてしまうのです。

この場合の石取りゲームの勝者判定方法

このルールの場合も判定方法はそこまで難しくなく、$A_{i}$($1<=i<=N$)の排他的論理和（xor)が０の場合は後手が勝ち、そうでない場合は先手が勝ちます。 どうしてそうなるのかについては今は時間がない（私事ですみません！）ので省きます。

最後に

どうでしたか、どうしてこのような判定ができるのかが気になった人は「Grundy数」で検索をかけるか、後日、僕が記事を投稿するのを待っていてください。 競技プログラミングではこのようなゲームの問題も出るので、興味のある人は「ランダムに入って」競技プログラミングをはじめて見るのはどうでしょうか。 この記事を最後まで読んでいただきありがとうございました。