一山の石から交互に取り、最後に石を取った方が負けとなるゲーム。
ルールは以下のとおり。
  • N個の石から交互に石を取る
  • 一回に取れる石はM個( M < N )である
  • 最後に石を取ったほうが負け
  • パスはできない

石取りゲームのアルゴリズムは以下の通りである。 1回に取れる石数を3個とした時、相手が1, 2, 3個の石を取った時、自分は3, 2, 1個の石を取ることにする。そうすれば、石は毎回4個減ることになる。よって、残りの石数を (4k+1) 個にできれば、相手に最後の1個を残すことができる。

一般に、1回に取れる石数がM個であれば、残りの石数を k×(M+1)+1個(kは任意の整数)にできれば、上記方法で勝つことができる。もし残りの石数が k×(M+1)+1個 でなければ、ランダムな個数をとって相手の敗着を待つ。

#prompt
Dim n As Integer
Dim m As Integer
Dim x As Integer
Dim my_turn As Integer

Input "石の数 "; n
Input "1回に取れる石数 "; m
If n < 1 Or m < 1 Then
Print "石数が足りません"
End
End If

Randomize
my_turn = Int(Rnd() * 2)
While n <> 0
my_turn = my_turn Xor 1
If my_turn Then
x = (n - 1) Mod (m + 1)
If x = 0 Then
Do
x = Int(Rnd() * m) + 1
Loop While x > n
End If
Print "コンピューターは"; x; "個の石を取ります"
Else
Do
Input "何個の石を取りますか "; x
Loop While x < 1 Or x > n Or x > m
End If
n = n - x
Print "残りの石数は"; n; " 個です"
Wend

If my_turn Then
Print "あなたの勝ちです"
Else
Print "コンピューターの勝ちです"
End If