Cマガ電脳クラブ(第021回) 31ゲーム

問題

今回は、ふたりで遊ぶ31ゲームを紹介しよう。
2から6までの数を書いた駒それぞれ4個ずつを、Fig.1のように左右にだけスライドできるような盤の上に並べ、
すべての駒を左側に寄せてゲームを始める。ふたりが交互に、駒をひとつずつ右に移動する。

移動するごとに右側の数の合計を唱え、これがちょうど31になるようにした者が勝ちだ。
でなかったら、31にならなくても相手を32以上にしてしまってもよい。
もちろん、「パス」は許されない。

Fig.2は、あるゲームの終了の図で、ちょうど31ができている。

こんなこともある。Aが24を作ってBの番になった。見ると2の駒はすべて移動済みだ。
そこでBは6を動かして30にした。すると次の手でAは32以上しか作れない。そこでBの勝ちとなる。

実はこのゲーム、先手に必勝法がある。
そこで問題。1手目をコンピュータとし、人と対戦する必勝プログラムを作ってほしい。
対戦の表示方法はご自由にどうぞ。

          

ソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static List<int> LeftValList = new List<int>();
    static int RightValSum = 0;

    static bool HasSyouhai = false;

    static void Main()
    {
        for (int I = 1; I <= 6; I++) LeftValList.AddRange(Enumerable.Repeat(I, 4));
        BanHyouji();

        while (true) {
            ExecComItte();
            if (HasSyouhai) return;
            InputHitoItte(false);
            if (HasSyouhai) return;
        }
    }

    //人の1手を入力
    static void InputHitoItte(bool IsRetry)
    {
        if (IsRetry == false) Console.Write("動かす数字を入力して下さい ");
        string wkStr = Console.ReadLine();
        int wkInt;
        if (int.TryParse(wkStr, out wkInt) == false) {
            Console.Write("入力エラーです。再入力して下さい ");
            InputHitoItte(true); return;
        }
        if (LeftValList.Contains(wkInt) == false) {
            Console.Write("存在しない数字です。再入力して下さい ");
            InputHitoItte(true); return;
        }
        ExecItte(wkInt);
    }

    //手を指して、メッセージ表示
    static void ExecItte(int pVal)
    {
        LeftValList.Remove(pVal); RightValSum += pVal;

        Console.WriteLine("{0}を動かしました", pVal);
        Console.WriteLine();

        SyouhaiHantei();
        if (HasSyouhai == false) BanHyouji();
    }

    //COMが手を指す
    static void ExecComItte()
    {
        //優先順位1 合計を31にする手がある場合
        int NeedVal = 31 - RightValSum;
        if (LeftValList.Contains(NeedVal)) {
            ExecItte(NeedVal);
            return;
        }

        //優先順位2 定跡DBにマッチしている場合
        if (IsMatchJyouseki()) return;

        //優先順位3 合計を10,17,24にする手を指す
        if (RightValSum < 10) NeedVal = 10 - RightValSum;
        else if (RightValSum < 17) NeedVal = 17 - RightValSum;
        else if (RightValSum < 24) NeedVal = 24 - RightValSum;
        ExecItte(NeedVal);
    }

    //定跡DBにマッチしているかを判定し、マッチしたら1手指す
    static bool IsMatchJyouseki()
    {
        var JyousekiBanList = new List<int>();
        for (int I = 1; I <= 6; I++) JyousekiBanList.AddRange(Enumerable.Repeat(I, 4));

        var OrderedLeftValList = LeftValList.OrderBy(X => X);

        //定跡その1 初手は5を動かす
        if (JyousekiBanList.OrderBy(X => X).SequenceEqual(OrderedLeftValList)) {
            ExecItte(5); return true;
        }

        //定跡その2 55なら2を動かす
        JyousekiBanList.Remove(5); JyousekiBanList.Remove(5);
        if (JyousekiBanList.OrderBy(X => X).SequenceEqual(OrderedLeftValList)) {
            ExecItte(2); return true;
        }

        //定跡その3 5525なら2を動かす
        JyousekiBanList.Remove(2); JyousekiBanList.Remove(5);
        if (JyousekiBanList.OrderBy(X => X).SequenceEqual(OrderedLeftValList)) {
            ExecItte(2); return true;
        }

        //定跡その4 552525なら2を動かす
        JyousekiBanList.Remove(2); JyousekiBanList.Remove(5);
        if (JyousekiBanList.OrderBy(X => X).SequenceEqual(OrderedLeftValList)) {
            ExecItte(2); return true;
        }

        return false;
    }

    //盤を表示
    static void BanHyouji()
    {
        var sb = new System.Text.StringBuilder();
        if (LeftValList.Count % 2 == 0) {
            sb.AppendLine("□□□□□□□□□□□□□□□□□□□□□□□□□");
        }
        else {
            sb.AppendLine("■■■■■■■■■■■■■■■■■■■■■■■■■");
        }

        sb.AppendFormat("現在の手数={0}。", 4 * 6 - LeftValList.Count);
        sb.AppendFormat("現在の合計値={0,2}。", RightValSum);
        sb.Append((LeftValList.Count % 2 == 0) ? "コンピュータの手番。" : "人の手番。");
        sb.AppendLine();

        for (int I = 1; I <= 6; I++) {
            int Cnt = LeftValList.Count(X => X == I);
            for (int J = 1; J <= Cnt; J++) sb.Append(I);

            sb.Append("***");

            for (int J = 1; J <= 4 - Cnt; J++) sb.Append(I);
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }

    //勝敗が決定しているかを判定
    static void SyouhaiHantei()
    {
        //場合1 コンピュータが31を取った場合
        if (RightValSum == 31 && LeftValList.Count % 2 == 1) {
            Console.WriteLine("コンピュータが合計値31を取ったので、コンピュータの勝ちです。");
            HasSyouhai = true;
            return;
        }

        //場合2 人が32以上をとった場合
        if (RightValSum >= 32 && LeftValList.Count % 2 == 0) {
            Console.WriteLine("人が32以上の合計値を取ったので、コンピュータの勝ちです。");
            HasSyouhai = true;
        }
    }
}

実行結果

省略

■■■■■■■■■■■■■■■■■■■■■■■■■
現在の手数=7。現在の合計値=26。人の手番。
1111***
2***222
3333***
4444***
***5555
6666***
動かす数字を入力して下さい 3
3を動かしました

□□□□□□□□□□□□□□□□□□□□□□□□□
現在の手数=8。現在の合計値=29。コンピュータの手番。
1111***
2***222
333***3
4444***
***5555
6666***
2を動かしました

コンピュータが合計値31を取ったので、コンピュータの勝ちです。

解説

もし、使用出来る数字に制限がないならば、
最初に先手が3を移動させる。
後手が何か移動させる。先手は(7-後手が移動させた数)を繰り返すと、
3+7*4 = 31 なため、先手必勝です。

しかし、使用出来る数字に制限があるため、
最初に5を取り、
コンピュータが10,17,24,31を狙う戦術を定跡として実装してます。
10,17,24,31を取れれば取り、
取れなかったら2を取って、再度10,17,24,31を狙います。

■コマネチ大学数学科110講：「31」: ガスコン研究所