第７７章 ３５７ゲーム　その２

さて、もしこのゲームに必勝法があるとします。対戦する二人が二人とも この必勝法を知っているとします。二人のうちどちらかは必ず負けます。 と、いうことは必勝法は存在しないということになります。(屁理屈です。)

ま、必勝法に近い方法はあります。筆者が経験的に考えたもので、これを知らない人はほぼ １００パーセント筆者に負けます(本当です)。

では、どうすれば勝つことができるのでしょうか。

それは、あるパターンに持ち込むことです。

一番簡単なパターンは３つの山のうち１つが０で他の２つの山が同数になるにすることです。 ただし、1-0-1のように０以外の山が１ではいけません。

自分が石を取って3-3-0になったとします。相手が取って2-3-0になったら、真ん中から１取って 2-2-0にします。そして相手が取って1-2-0になったら真ん中からすべてを取ると勝ちます。

仮に相手が取った後、2-0-0となったら、最初の山から１を取れば勝ちます。

簡単のためにこのパターンを0-x-xパターンと名付けます。もちろん石の順番はどうでもよく 実際にはx-0-x, x-x-0などとなってもかまいません。

序盤ではなかなか、0-x-xパターンに持っていくのが難しいものです。 そのときは何とか2-4-6パターンに持って行きます。 これが出来ると必ず勝ちます。 相手が取った後、どれかの山が０となった場合は0-x-xパターンに持っていけます。 あるいは、次に示すいずれかのパターンに必ず持っていけます。

次に1-4-5パターンをねらいます。 もし、2-4-6から相手が取って、2-4-5となった場合は1-4-5パターンに持ち込めます。

次が1-2-3パターンです。

そして、1-1-1パターンも勝ちです。

2-4-6パターンが出来ると、必ず上記のいずれかのパターンに持っていけます。 最終的には1-1-1または、0-x-xパターンとなり勝つことが出来ます。

これを、プログラム化するのはかなり面倒くさいです。

最初の石山が3-5-7とすると、2-4-6は必ずこの順でしか起こりません。(各山の石の数は 減ることはあっても増えることはない)

しかし、1-4-5パターンはどうでしょうか。実際には1-5-4となるかもしれません。 1-2-3パターンに至ってはいろいろな並びが考えられますね。

試行錯誤でプログラムを書いていくと、ifのなかにifが出来て、その中にさらにifができるなど だんだん訳がわからなくなってしまいます。

今回は、なるべく人間の考え方に近く、かつifの階層が深くならないようにするため、 goto文を多用したプログラムになりました。Cではgotoはなるべく使わないというのが 鉄則ですが、たまにはいいかもしれません。

では、実際のプログラムを見てみましょう。

// stone35702.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

int comptake(int *);
int judge(int *);
int takestone(int *);
int showno(int *);
int no_of_0(int *);

// sente:人が先手 1,後手 0,    order:現在先手の番 1, 後手の番 0
int sente, order;

int main()
{
    // mt[x] 石山の数
    int mt[3], ret;
    char ans[8];

    mt[0] = 3;
    mt[1] = 5;
    mt[2] = 7;

    showno(mt);

    printf("あなたが先手になりますか(Y/N)---");
    gets(ans);
    if (strcmp(ans, "y") == 0 || strcmp(ans, "Y") == 0) {
        sente = 1;
    } else {
        sente = 0;
    }

    order = 1;

    while (1) {
        ret = takestone(mt);
        if (ret == 1)
            break;
    }
    
    return 0;
}

int comptake(int *mtno)
{
    int mtorder, stone, jump = 0, i;


    srand((unsigned)time(NULL));
    
    if (no_of_0(mtno) == 0) { //どの山も０ではない
        //2-4-6パターンにする
        if (mtno[0] == 3 && mtno[1] == 4 && mtno[2] == 6) {
            mtorder = 0;
            stone = 1;
            mtno[0] = 2;
            goto end;
        }
        if (mtno[1] == 5 && mtno[0] == 2 && mtno[2] == 6) {
            mtorder = 1;
            stone = 1;
            mtno[1] = 4;
            goto end;
        }
        if (mtno[2] == 7 && mtno[0] == 2 && mtno[1] == 4) {
            mtorder = 2;
            stone = 1;
            mtno[2] = 6;
            goto end;
        }
        //1-4-5パターンにする
        if (mtno[0] > 1 && mtno[1] + mtno[2] == 9 && mtno[1] * mtno[2] == 20) {
            mtorder = 0;
            stone = mtno[0] - 1;
            mtno[0] = 1;
            goto end;
        }
        if (mtno[1] > 4 && mtno[0] == 1 && mtno[2] == 5) {
            mtorder = 1;
            stone = mtno[1] - 4;
            mtno[1] = 4;
            goto end;
        }
        if (mtno[2] > 4 && mtno[0] == 1 && mtno[1] == 5) {
            mtorder = 2;
            stone = mtno[2] - 4;
            mtno[2] = 4;
            goto end;
        }
        if (mtno[2] > 5 && mtno[0] == 1 && mtno[1] == 4) {
            mtorder = 2;
            stone = mtno[2] - 4;
            mtno[2] = 4;
            goto end;
        }
        //1-2-3パターンにする
        if (mtno[0] > 1 && mtno[1] + mtno[2] == 5 && mtno[1] * mtno[2] == 6) {
            mtorder = 0;
            stone = mtno[0] - 1;
            mtno[0] = 1;
            goto end;
        }
        if (mtno[0] > 2 && mtno[1] + mtno[2] == 4 && mtno[1] * mtno[2] == 3) {
            mtorder = 0;
            stone = mtno[0] - 2;
            mtno[0] = 2;
            goto end;
        }
        if (mtno[0] == 3 && mtno[1] + mtno[2] == 3 && mtno[1] * mtno[2] == 2) {
            mtorder = 0;
            stone = mtno[0] - 3;
            mtno[0] = 3;
            goto end;
        }
        if (mtno[1] > 1 && mtno[0] + mtno[2] == 5 && mtno[0] * mtno[2] == 6) {
            mtorder = 1;
            stone = mtno[1] - 1;
            mtno[1] = 1;
            goto end;
        }
        if (mtno[1] > 2 && mtno[0] + mtno[2] == 4 && mtno[0] * mtno[2] == 3) {
            mtorder = 1;
            stone = mtno[1] - 2;
            mtno[1] = 2;
            goto end;
        }
        if (mtno[1] > 3 && mtno[0] + mtno[2] == 3 && mtno[0] * mtno[2] == 2) {
            mtorder = 1;
            stone = mtno[1] - 3;
            mtno[1] = 3;
            goto end;
        }
        if (mtno[2] > 1 && mtno[0] + mtno[1] == 5 && mtno[0] * mtno[1] == 6) {
            mtorder = 2;
            stone = mtno[2] - 1;
            mtno[2] = 1;
            goto end;
        }
        if (mtno[2] > 2 && mtno[0] + mtno[1] == 4 && mtno[0] * mtno[1] == 3) {
            mtorder = 2;
            stone = mtno[2] - 2;
            mtno[2] = 2;
            goto end;
        }
        if (mtno[2] > 3 && mtno[0] + mtno[1] == 3 && mtno[0] * mtno[1] == 2) {
            mtorder = 2;
            stone = mtno[2] - 3;
            mtno[2] = 3;
            goto end;
        }
        //1-1-1パターンにする
        if (mtno[0] == mtno[1] && mtno[0] == 1 && mtno[2] > 1) {
            mtorder = 2;
            stone = mtno[2] - 1;
            mtno[2] = 1;
            goto end;
        }
        if (mtno[1] == mtno[2] && mtno[1] == 1 && mtno[0] > 1) {
            mtorder = 0;
            stone = mtno[0] - 1;
            mtno[0] = 1;
            goto end;
        }
        if (mtno[0] == mtno[2] && mtno[0] == 1 && mtno[1] > 1) {
            mtorder = 1;
            stone = mtno[1] - 1;
            mtno[1] = 1;
            goto end;
        }
        if (mtno[0] == mtno[1]) {
            mtorder = 2;
            stone = mtno[2];
            mtno[mtorder] = 0;
            goto end;;
        }
        if (mtno[1] == mtno[2]) {
            mtorder = 0;
            stone = mtno[0];
            mtno[mtorder] = 0;
            goto end;;
        }
        if (mtno[2] == mtno[0]) {
            mtorder = 1;
            stone = mtno[1];
            mtno[mtorder] = 0;
            goto end;;
        }
    }

    //０の山が１つだけである
    if (no_of_0(mtno) == 1) {
        if (mtno[0] == 0) {
            if (mtno[1] == 1) {
                mtorder = 2;
                stone = mtno[2];
                mtno[2] = 0;
                goto end;
            }
            if (mtno[2] == 1) {
                mtorder = 1;
                stone = mtno[1];
                mtno[1] = 0;
                goto end;
            }

            if (mtno[1] > mtno[2]) {
                mtorder = 1;
                stone = mtno[1] - mtno[2];
                mtno[mtorder] -= stone;
                goto end;
            }
            if (mtno[2] > mtno[1]) {
                mtorder = 2;
                stone = mtno[2] - mtno[1];
                mtno[mtorder] -= stone;
                goto end;
            } 
            if (mtno[2] == mtno[1]){
                mtorder = 1;
                stone = 1;
                mtno[mtorder] -= stone;
                goto end;
            }
        }
        if (mtno[1] == 0) {
            if (mtno[0] == 1) {
                mtorder = 2;
                stone = mtno[2];
                mtno[2] = 0;
                goto end;
            }
            if (mtno[2] == 1) {
                mtorder = 0;
                stone = mtno[0];
                mtno[0] = 0;
                goto end;
            }
            if (mtno[0] > mtno[2]) {
                mtorder = 0;
                stone = mtno[0] - mtno[2];
                mtno[mtorder] -= stone;
                goto end;
            }
            if (mtno[2] > mtno[0]) {
                mtorder = 2;
                stone = mtno[2] - mtno[0];
                mtno[mtorder] -= stone;
                goto end;
            }
            if (mtno[0] == mtno[2]) {
                mtorder = 2;
                stone = 1;
                mtno[mtorder] -= stone;
                goto end;
            }
        }
        if (mtno[2] == 0) {
            if (mtno[1] == 1) {
                mtorder = 0;
                stone = mtno[0];
                mtno[0] = 0;
                goto end;
            }
            if (mtno[0] == 1) {
                mtorder = 1;
                stone = mtno[1];
                mtno[1] = 0;
                goto end;
            }
            if (mtno[0] > mtno[1]) {
                mtorder = 0;
                stone = mtno[0] - mtno[1];
                mtno[mtorder] -= stone;
                goto end;
            }
            if (mtno[1] > mtno[0]) {
                mtorder = 1;
                stone = mtno[1] - mtno[0];
                mtno[mtorder] -= stone;
                goto end;
            }
            if (mtno[1] == mtno[0]) {
                mtorder = 0;
                stone = 1;
                mtno[mtorder] -= 1;
                goto end;
            }
        }
    }

    if (no_of_0(mtno) == 2) {
        for (i = 0; i < 3; i++) {
            if (mtno[i] != 0) {
                stone = mtno[i] - 1;
                mtorder = i;
                mtno[i] = 1;
                goto end;
            }
        }
    }
    while (1) {
        mtorder = rand() % 3;
        if (mtno[mtorder] == 0)
            continue;
        else
            break;
    }
    while (1) {
        stone = 1;
        mtno[mtorder] -= stone;
        if (mtno[0] + mtno[1] + mtno[2] == 0) {
            mtno[mtorder] += stone;
            continue;
        } else {
            break;
        }
    }
end:
    printf("コンピュータは%cから%d個取りました\n", mtorder + 'A', stone);
    showno(mtno);
    return 0;
}

０の山が無いとき、まず2-4-6パターンにならないか検討します。 自分が取って2-4-6になるわけですから、現在x-4-6, 2-x-6, 1-4-xのいずれかに なっていなくてはいけません。この時xは最初の場合は3しかありません。 次の場合はxは5しかありません。最後の場合はxは7しかありません。 これら３つの場合の時のみ2-4-6パターンに持ち込めます。

次に1-4-5パターンに持ち込めるかどうかを考えます。
(1-1)最初の山が１より大で次の山が４,最後の山が５の場合。
(1-2)最初の山が１より大で次の山が５,最後の山が４の場合

これは、最初の山が１より大、その他の山の和が９，積が２０というようにまとめることができます。

(2)第２の山が４より大で、最初の山が１，最後の山が５の場合
(3)最後の山が４より大で、最初の山が１, 第２の山が５の場合
(4)最後の山が５より大で、最初の山が１, 第２の山が４の場合

この４通りが考えられます。

次に1-2-3パターンに持ち込めないかどうか調べます。このパターンに持ち込めるのは どういう場合かソースを読んで考えてみてください。

次に1-1-1パターンにならないか検討します。これは簡単ですね。

そして、２つの山が同数でないか調べます。同数であれば0-x-xパターンに持ち込めますね。

次に０の山が１つだけ存在する場合を考えます。
０の山以外に１の山が存在すれば、残りの山を全部取ってしまえば勝ちですね。

１の山が存在しないときは、多い方の山からその差を取って0-x-xパターンにします。

最後に０の山が２つある場合、これは残りの山から１だけ残して取ってしまえば勝ちです。

いずれにも該当しない場合は、取る山を乱数で決めて、そこから１だけ取ります。 取る数を最小にして相手のミスを待つわけです。

検討する項目はこの順序で行います。順番を間違えるとおかしなことになります。 該当するところがあれば、goto文で最後に飛びます。

int takestone(int *mt)
{
    char ans[8];
    int stone, mtorder;

    if (sente != order) {
        comptake(mt);
        if (judge(mt) == 0) {
            printf("コンピュータの勝ちです\n");
            return 1;
        }
        if (order == 1)
            order = 0;
        else
            order = 1;
        return 0;
    }
    while (1) {
        printf("どの山からとりますか(A,B,C)---");
        gets(ans);
        if (strcmp(ans, "A") != 0 && strcmp(ans, "B") != 0 && strcmp(ans, "C") != 0 &&
            strcmp(ans, "a") != 0 && strcmp(ans, "b") != 0 && strcmp(ans, "c") != 0) {
            printf("山の指定が正しくありません\n");
            continue;
        } else {
            ans[0] = toupper(ans[0]);
            mtorder = ans[0] - 'A';
            if (mt[mtorder] == 0) {
                printf("その山にはもう石はありません\n");
                continue;
            }
            break;
        }
    }
    
    while (1) {
        printf("いくつとりますか---");
        gets(ans);
        stone = atoi(ans);
        mt[mtorder] -= stone;
        if (mt[0] + mt[1] + mt[2] == 0) {
            printf("その取り方では山の石が全部０になります\n");
            mt[mtorder] += stone;
            continue;
        }
        mt[mtorder] += stone;
        if (mt[mtorder] - stone < 0 || stone <= 0) {
            printf("取る石の数が不正です\n");
            continue;
        } else {
            break;
        }
    }
    mt[mtorder] -= stone;
    showno(mt);
    if (judge(mt) == 0) {
        printf("あなたの勝ちです\n");
        return 1;
    }
        
    if (order == 1)
        order = 0;
    else
        order = 1;

    return 0;
}

int judge(int *mt)
{
    if (mt[0] + mt[1] + mt[2] == 1)
        return 0;
    else
        return 1;
}

int showno(int *mt)
{
    printf("[A] = %d, [B] = %d, [C] = %d\n", mt[0], mt[1], mt[2]);

    return 0;
}

int no_of_0(int *mt)
{
    int no, i;

    no = 0;
    for (i = 0; i < 3; i++) {
        if (mt[i] == 0)
            no++;
    }
    return no;
}

プログラムを作ったら、必勝法もどきを知らない人と対戦させてみてください。 ほとんど無敵状態です。