algorithm - 木の上のゲーム、枝を切る

Question

根の張った木の森があります。2 人のプレーヤーが、次のルールに従って交互に移動します。1 つの移動は、頂点とそのすべての子をカットすることです。最後の移動 (頂点が残っていない) を行うプレイヤーが勝ちます。

ゲーム内の位置の Grundy 関数をどのように計算できますか?

木があり、現在の位置が勝っているか負けているかを言う必要があるとします。

Answer 1

これがハッケンブッシュゲームです。この記事を強くお勧めします。この記事では、Grundy の数字を非常に明確に説明し、ハッケンブッシュについて最後まで徹底的に説明しています。