/*

    ○×ゲーム（特別ルール版）

        必勝法（または“必・引き分け法”）の出力、およびコンピュータとの対戦


           |   |         8 | 7 | 6 
        ---+---+---     ---+---+---
           |   |         5 | 4 | 3 
        ---+---+---     ---+---+---
           |   |         2 | 1 | 0 

左の図のように、３×３のマス目を書く。二人のプレイヤーが、交互に、先攻は○を、
後攻は×を、マスの中に書いてゆく。いったん○または×が書かれたマスにはもう何も
書くことはできない。これを、空いたマスがなくなるまで続け、縦・横・斜めのいずれ
かに、自分の記号を三つ並べた者が勝ちである。

ただし、両者ともに並べることに成功した場合は、最後に並べた者の勝ちとする、と
いうのが、このバージョンの特別ルールである。○と×がそれぞれ三つ並んだ状態と
は、両者とも縦、または両者とも横に並んだ状態である。このとき、残りの三つのマス
に○二つ、×一つをどのようにおいても、他の場所に○または×が三つ並ぶことは
ない。よって、このルールに従うなら、一方が三つ並べたあと、相手が三つ並べたら、
その時点で後者の勝ちとしてよいことがわかる。そのため、そこでゲームを打ち切る
ようにした。

（ゲームの画面では、○は O で、×は X で表現される。以下の説明の中の、ゲームの
画面の図でも同様である。）

右の図のようにマスに番号を振る。考えられるおのおのの局面に、「三進表記をした際
に 9 ケタ以下となる非負整数で、下から k ケタめ（一の位を 0 ケタめと数える）が
『k が振られたマスに○が書かれていれば 1, ×が書かれていれば 2, 何も書かれて
いなければ 0』であるもの」を対応させる。

次に、三進表記で 0 から 222222222（2 が九つ、十進では 19682）までの整数 n を
考える。これらの数のそれぞれが、上の対応でこのゲームのある局面に対応するかどう
か、するとしたらどちらかが勝ってゲームが終わっているか、ゲームの途中なら次は
どちらの手番か、などを判別して返す関数が f() である。

ただし、○と×の両方が三つ並んでいる場合、勝負はついているはずだが、どちらが
勝っているかはわからない。この場合は不明とする。

それが返した値をいったん b[n] に代入する。

ゲームの途中で、○か×が一つ書き込まれ、ある局面からある局面へと変わると、上の
対応で対応する整数は必ず増加することに注意する。

n が三進表記の 222222222 から始めて 0 まで、1 ずつ戻りながら、その局面から一手
で移りうる局面すべてを考え、○の手番なら○が、×の手番なら×が最も有利になる
行き先にゆくために○あるいは×を書いてよいマスの番号すべてを考える。

たとえば○の手番でそれが 8, 6, 2 だったとすると、三進表記で下から 8 ケタめ、
6 ケタめ、2 ケタめだけが 1 でほかは 0 である整数、すなわち 101000100 を a[n] に
代入する。×の手番でそれが 8, 7, 2 だったとすると、三進表記で下から 8 ケタめ、
7 ケタめ、2 ケタめだけが 2 でほかは 0 である整数、すなわち 220000200 を a[n] に
代入する。また、b[n] は、最終的に○が勝つか、×が勝つか、引き分けるか、それとも
あり得ない局面であるか、のいずれか、および、どちらの手番か、を合わせた情報で
置き換える。ただし、終わっている局面については、何もしない。

（このように、b[n] を二通りに使うところが少々ややこしい。また、どちらの手番か
は、別の配列を用意してそれに格納するほうがプログラムは簡単になるが、DOS 上の
コンパイラでは大域変数が多すぎてコンパイルできなくなるので、このようにした。）

また、○の手番で、すでに×は三つ並べているが○は三つ並べていないとき、次に○が
どこかに打つことで○も三つ並ぶ場合は、それを選択するのが必勝法であるから、そう
する。また、いずれそのようにして勝てる方法がある場合、それを選択する。

こうしてゆくと、局面 n に対する必勝法が得られる。main() の終わり近くの print()
で、それらを表にして出力する。その冒頭は

000|000|000  000|010|000  ○の勝ち

となるので、先手は、最初に中央のマスに○を書くのが必勝法である。それ以外の場所
は、本質的に二通りである。

000|000|001  200|020|000  引き分け
000|000|010  000|020|000  引き分け

から、それ以外の場所に打った場合、×は最善を尽くすことで引き分けに持ち込むこと
ができる。

○が中央に打った場合、×の打ちかたは本質的に二通りである。

000|010|002  011|101|110  ○の勝ち
000|010|020  111|101|000  ○の勝ち

から、○が次に打つべき位置がわかる。

   | O | O    O | O | O 
---+---+---  ---+---+---
 O | O | O    O | O | O 
---+---+---  ---+---+---
 O | O | X      | X |       （中央の「O」は最初に打った O である。）

（その局面になったら自分の負けしかない、という局面もある。それは、それ以前に
まずい手を打ってしまった場合である。その局面に対しては「空いているマスのどこに
打っても負け」ということで

000|001|201  222|220|020  ○の勝ち

のように表示される。）

コンピュータと対戦するときは、コンピュータは、最善の結果にいたる手のうちから
ランダムに選んで打ってくる。どの手が、人間にとって最善の手を返すのが一番難しい
か、などは考えていない。

コンピュータが先手の場合、第一手のみは例外で、最善の手は中央のマスに打つことと
わかっているが、ほかのマスにも打ってくる。なお、第一手で中央のマスに打ってくる
確率を、ほかのマスの４倍にしてある。それは、隅や辺は４箇所ずつあり、その４箇所
のどこに打っても本質的には同じことなので、「隅に打ってくる確率」「辺に打って
くる確率」「中央に打ってくる確率」を等しくしたかったからである。）

付）3 のベキ乗を計算する関数や、三進表記の i ケタめを返す関数を書いて利用しては
みたが、素朴に、毎回計算するように戻してしまった。特に理由はない。

付）必勝法は 19683 行にわたって出力されるが、そのうち「あり得ない局面」とされる
ものが 13637 行あり、残りは 6046 行である。

付）あり得ない局面とは、○と×の数が合わない局面のみである。それ以外は、すべて
起こり得る。○と×の両方が三つ並んでいる場合、どちらかが最後に置いた○か×で
三つ並んだと考えればよい。両方が三つ並んでいない場合、もしかしたら並ぶかも
知れないと考え、ゲームはそこまで続いてくるから、起こり得る。

付）ttt.c, ttt2.c と比べると、main() が複雑になった。それは、○と×の両方が
三つ並んだ局面では、どちらの勝ちか判定できないためである。

注）以下のプログラム内のコメントでは、三つ並べることを「上がり」と表現した。
*/

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

#define N ((3*3*3)*(3*3*3)*(3*3*3))     /* 19683 に等しい */

#define YES 1
#define NO  0

#define O 1     /* ○ */
#define X 2     /* × */

int f(int n);
void print(void);
void play(void);
void show(int n);
void show2(int i);

int a[N];   /* どこへゆくべきか、がはいる */
int b[N];   /* 結論がはいる。メモリが不足するときは signed char 型にしても可 */

main() {
    int n;      /* 局面に対応する非負整数 */
    int pow;    /* 3 のベキ乗に値をとる */

    for (n = N-1; n >= 0; n--) {
        a[n] = 0;       /* 0 は行き先がないことを示す印 */
        b[n] = f(n);
        if (b[n] % 5 == 0 || b[n] / 5 == 6 || b[n] == -1) {
            ;   /* 空きマスなし・両者上がり・ありえない、は何もしない */
        } else if (b[n] == 21) {    /* ○番で×はすでに上がりのとき */
            for (pow = 1; pow < N; pow = pow * 3) {
                /* 空いているマスを探し、試しに○を置いて、上がれるか調べる */
                if (n / pow % 3 == 0) {     /* マスが空いていたら */
                    /* ↓自分も上がれるか、いまに上がれるなら勝ち */
                    if (b[n + pow] / 5 == 6 || b[n + pow] == 12) {
                        a[n] = a[n] + pow; b[n] = 11;
                    }
                }
            } 
            if (b[n] != 11) {   /* どうしても上がれないとき */
                for (pow = 1; pow < N; pow = pow * 3) {
                    if (n / pow % 3 == 0) { /* マスが空いていたら */
                        a[n] = a[n] + pow;
                    }
                }
            }
        } else if (b[n] % 5 == 1) {     /* ○の手番で×は上がっていないとき */
            b[n] = 21;  /* 最悪の場合、すなわち×の勝ち、としてみる */
            for (pow = 1; pow < N; pow = pow * 3) {
                /* 空いているマスを探し、試しに○を置いて、よくなるか調べる */
                if (n / pow % 3 == 0) { /* マスが空いていたら */
                    if (b[n] / 5 == b[n + pow] / 5) {   /* 置いて等しければ */
                        a[n] = a[n] + pow;          /* そのケタも 1 にする */
                    } else if (b[n] > b[n + pow]) {     /* 置いてよくなれば */
                        a[n] = pow;                 /* そこだけ 1 にする */
                        b[n] = b[n + pow] / 5 * 5 + 1;  /* それで置き換える */
                    }
                }
            }
        } else if (b[n] == 12) {    /* ×番で○はすでに上がりのとき */
            for (pow = 1; pow < N; pow = pow * 3) {
                /* 空いているマスを探し、試しに×を置いて、上がれるか調べる */
                if (n / pow % 3 == 0) {     /* マスが空いていたら */
                    /* ↓自分も上がれるか、いまに上がれるなら勝ち */
                    if (b[n + 2*pow] / 5 == 6 || b[n + 2*pow] == 21) {
                        a[n] = a[n] + 2*pow; b[n] = 22;
                    }
                }
            }
            if (b[n] != 22) {   /* どうしても上がれないとき */
                for (pow = 1; pow < N; pow = pow * 3) {
                    if (n / pow % 3 == 0) { /* マスが空いていたら */
                        a[n] = a[n] + 2*pow;
                    }
                }
            }
        } else if (b[n] % 5 == 2) {     /* ×の手番で○は上がっていないとき */
            b[n] = 12;  /* 最悪の場合、すなわち○の勝ち、としてみる*/
            for (pow = 1; pow < N; pow = pow * 3) {
                /* 空いているマスを探し、試しに×を置いて、よくなるか調べる */
                if ((n / pow) % 3 == 0) {   /* マスが空いていたら */
                    if (b[n] / 5 == b[n + 2*pow] / 5) { /* 置いて等しければ */
                        a[n] = a[n] + 2*pow;        /* そのケタも 2 にする */
                    } else if (b[n] < b[n + 2*pow]) {   /* 置いてよくなれば */
                        a[n] = 2*pow;               /* そこだけ 2 にする */
                        b[n] = b[n + 2*pow] / 5 * 5 + 2;    /* それに換える */
                    }
                }
            }
        }
    }

    printf("このままでは、このプログラムはこの文章以外何も出力しません. ");
    printf("プログラムの、main() の終わり近くにある、この文章を出力する箇所");
    printf("の次の二行のどちらか（あるいは両方）のコメントをはずし、この文章");
    printf("を出力する部分はコメントにして、再度コンパイルしてください.\n");

/*  print();    /* 必勝法の出力 */
/*  play();     /* ゲームで遊ぶ */
}


/*
整数 n に対応する局面の○と×の配置を見て、次の数を返す。
    case 1. 「0 ... 盤がいっぱいである、1 ... ○の手番、2 ... ×の手番」のどれ
            かと「10 ... ○のみ上がり、15 ... どちらも上がりでない、20 ... ×
            のみ上がり、30 ... 両方上がり」のどれかの和。
    case 2. -1 ... ありえない局面。
*/
int f(int n) {
    int i, counto, countx, owin, xwin, ret;
    int c[9];

    for (i = 0; i < 9; i++) {   /* 三進表記の各ケタを求める */
        c[i] = n % 3;           /* c[0] が一の位            */
        n = n / 3;
    }

    counto = 0;                 /* ○の数を数える */
    for (i = 0; i < 9; i++) {
        if (c[i] == O) {
            counto++;
        }
    }

    countx = 0;                 /* ×の数を数える */
    for (i = 0; i < 9; i++) {
        if (c[i] == X) {
            countx++;
        }
    }

    if (counto != countx && counto != countx + 1) {
        return -1;      /* ○と×の数が合わないので、ありえない場合 */
    }

    if (c[0] == O && c[1] == O && c[2] == O) {  /* ○が上がりのケースを網羅 */
        owin = YES;
    } else if (c[3] == O && c[4] == O && c[5] == O) {
        owin = YES;
    } else if (c[6] == O && c[7] == O && c[8] == O) {
        owin = YES;
    } else if (c[0] == O && c[3] == O && c[6] == O) {
        owin = YES;
    } else if (c[1] == O && c[4] == O && c[7] == O) {
        owin = YES;
    } else if (c[2] == O && c[5] == O && c[8] == O) {
        owin = YES;
    } else if (c[0] == O && c[4] == O && c[8] == O) {
        owin = YES;
    } else if (c[2] == O && c[4] == O && c[6] == O) {
        owin = YES;
    } else {
        owin = NO;
    }
    if (c[0] == X && c[1] == X && c[2] == X) {  /* ×が上がりのケースを網羅 */
        xwin = YES;
    } else if (c[3] == X && c[4] == X && c[5] == X) {
        xwin = YES;
    } else if (c[6] == X && c[7] == X && c[8] == X) {
        xwin = YES;
    } else if (c[0] == X && c[3] == X && c[6] == X) {
        xwin = YES;
    } else if (c[1] == X && c[4] == X && c[7] == X) {
        xwin = YES;
    } else if (c[2] == X && c[5] == X && c[8] == X) {
        xwin = YES;
    } else if (c[0] == X && c[4] == X && c[8] == X) {
        xwin = YES;
    } else if (c[2] == X && c[4] == X && c[6] == X) {
        xwin = YES;
    } else {
        xwin = NO;
    }

    if (owin == YES && xwin == YES) {   /* 両方が上がり */
        ret = 30;
    } else if (owin == YES) {
        ret = 10;          /* ○のみ上がりの局面 */
    } else if (xwin == YES) {
        ret = 20;          /* ×のみ上がりの局面 */
    } else {
        ret = 15;          /* どちらも上がりでない */
    }
    if (counto + countx == 9) {     /* 盤がいっぱいになっている */
        return ret;
    } else {                        /* 盤がいっぱいになっていない */
        if (counto == countx) {     /* ○×同数なら次は○の手番 */
            return ret + 1;
        } else {                    /* そうでなければ×の手番 */
            return ret + 2;
        }
    }
}


/*
必勝法の出力。三進で n と a[n] を表記し、結論をことばで書く。1 が○に、2 が×に
対応する。0 はどちらも置かれていないところ。三ケタずつ区切って表示する。n が
010|012|020 は下の局面にあたる。

   | O |   
---+---+---
   | O | X 
---+---+---
   | X |   

このとき a[n] は 100|000|100 と出力され、その右に「○の勝ち」と表示されるが、
これは、次に 7 か 1 のマスに○を書けば、また、その場合のみ、以下双方が最善を
つくしても○（先攻）の勝ち、という意味である。つまり、これが必勝法（引き分けに
持ち込むのがベストの局面では“必・引き分け法”）を示している。
*/
void print(void) {
    int n, pow;

    for (n = 0; n < N; n++) {
                                    /* 以下、n を三進で上のケタから表示 */
        for (pow = (3*3*3)*(3*3*3)*(3*3); pow > 0; pow = pow / 3) {
            printf("%d", n / pow % 3);
            if (pow == (3*3*3)*(3*3*3) || pow == (3*3*3)) {
                printf("|");
            }
        }
        printf("  ");
        if (a[n] == 0) {            /* 以下、a[n] を三進で上のケタから表示 */
            printf("   |   |   ");
        } else {
            for (pow = (3*3*3)*(3*3*3)*(3*3); pow > 0; pow = pow / 3) {
                printf("%d", a[n] / pow % 3);
                if (pow == (3*3*3)*(3*3*3) || pow == (3*3*3)) {
                    printf("|");
                }
            }
        }
        if (b[n] / 5 == 2) {            /* 10, 11, 12 のとき */
            printf("  ○の勝ち\n");
        } else if (b[n] / 5 == 4) {     /* 20, 21, 22 のとき */
            printf("  ×の勝ち\n");
        } else if (b[n] / 5 == 3) {     /* 15, 16, 17 のとき */
            printf("  引き分け\n");
        } else if (b[n] / 5 == 6) {     /* 30, 31, 32 のとき */
            printf("  不明\n");
        } else if (b[n] == -1) {
            printf("  あり得ない局面\n");
        } else {    /* 以上のどれかになるはずだが、念のため次の行も用意した。*/
            printf("  何かが変です!\a\n");  /* \a は警告音を鳴らす働きをする */
        }
    }
}


/*
ゲームで遊ぶ。ここではマスの番号が冒頭のコメントと異なるが、表示も変えてあるの
で大丈夫。（必勝法の表を見るときは、番号の違いは気にせずに見ればよい。）
*/
void play(void) {
    int i;      /* （人間が）先攻のとき 1, 後攻のとき 2 */
    int n;      /* 局面の番号 */
    int j, k;   /* さまざまに使う変数 */
    int x;      /* ユーザ入力に使う */
    int pow;    /* 3 のベキ乗に値をとる */

    {    /* この中カッコの中はわからなくてもよい */
        unsigned seed;
        seed = (unsigned)time(NULL);    /* 現在時刻を種にして */
        srand(seed);                    /* 乱数を初期化 */
    }

    printf("マスの番号を覚えてください.  （テンキーと同じです. ）\n\n");

    printf(" 7 | 8 | 9 \n");
    printf("---+---+---\n");
    printf(" 4 | 5 | 6 \n");
    printf("---+---+---\n");
    printf(" 1 | 2 | 3 \n\n");

    for (i = 0; i == 0;    ) {
        printf("先攻 O にしますか？  後攻 X にしますか？  ");
        printf("先攻 ... 1, 後攻 ... 2 ＞");
        scanf("%d", &i);
        if (i != 1 && i != 2) {
            i = 0;                  /* これで入力し直しになる */
        }
    }
    if (i == 1) {   /* 人間が先攻なら */
        n = 0;      /* 何もないところから打たせる */
    } else {        /* 人間が後攻なら */
        j = rand() % (9 + 3);       /* 乱数を使って初手を決めるのだが、j が */
        if (j >= 9) {               /* 4 となる（＝まん中に打つ）確率がほか */
            j = 4;                  /* のマスの 4 倍になるよう細工してある  */
        }
        for (n = 1; j > 0; j--) {
            n = 3 * n;
        }
    }
    for (     ; f(n) % 5 != 0 && f(n) / 5 != 6;    ) {  /* ゲームが続く限り */
        show(n);                                /* 盤面を表示 */
        for (x = 0; x == 0;    ) {
            if (i == 1) {
                printf("あなたは O です.  ");   /* これ、意外と忘れるので */
            } else {
                printf("あなたは X です.  ");   /* 毎回出力するようにした */
            }
            printf("どこに打ちますか？  ");
            scanf("%d", &x);                    /* ユーザが打つ場所を入力 */
            if (x < 1 || x > 9) {           /* 範囲外の値を入力したとき */
                x = 0;                      /* これで入力し直しになる */
            } else {
                pow = 1;
                for (j = 0; j < x - 1; j++) {
                    pow = pow * 3;
                }
                if (n / pow % 3 != 0) { /* そこに O か X が書いてあったら */
                    x = 0;              /* これで入力し直しになる */
                }
            }
        }
        n = n + i * pow;    /* ユーザの入力に従い局面を変える */
        show(n);            /* 盤面を表示 */
        if (f(n) % 5 != 0 && f(n) / 5 != 6) {   /* ゲームが続く場合 */
            /* 以下、コンピュータの打つ手を考える */
            k = 0;  /* 以下、a[n] の三進表記で 0 でないものの数を k に入れる */
            for (pow = 1; pow < N; pow = pow * 3) {
                if (a[n] / pow % 3 != 0) {
                    k++;
                }
            }
                /* 以下、乱数を使って、その中から一つ（下から j 番め）を選ぶ */
            j = rand() % k;
            for (pow = 1; j >= 0; pow = pow * 3) {
                if (a[n] / pow % 3 != 0) {
                    j--;
                }
            }
            pow = pow / 3;
            /* ユーザが先攻なら 2*pow を、後攻なら pow を n に加える */
            n = n + pow * (3 - i);
        }
    }
        /* 決着がついてループを抜けるとここへくる */
    show(n);                                                /* 画面表示 */
    if (i == 1 && f(n) / 5 == 4 || i == 2 && f(n) / 5 == 2) {
        printf("私の勝ちです.\n");          /* 普通のルールで勝った場合 */
    } else if (i == 1 && f(n) == 31 || i == 2 && f(n) == 32) {
        printf("私の勝ちです.\n");          /* 特別ルールで勝った場合 */
    } else if (i == 1 && f(n) == 30) {
        printf("私の勝ちです.\n");          /* 同上、その残り */
    } else if (f(n) / 5 == 3) {
        printf("引き分けです.\n");
    } else {
        printf("私の負けです.\n");
    }
}


/* ゲーム用に、局面を画面表示 */
void show(int n) {
    printf("\n");
    show2(n / ((3*3*3)*(3*3*3)) % 3);           /* 6 ケタめを表示 */
    printf("|");
    show2(n / ((3*3*3)*(3*3*3)*(3)) % 3);       /* 7 ケタめを表示 */
    printf("|");
    show2(n / ((3*3*3)*(3*3*3)*(3*3)) % 3);     /* 8 ケタめを表示 */
    printf("\n");
    printf("---+---+---\n");
    show2(n / (3*3*3) % 3);                     /* 3 ケタめを表示 */
    printf("|");
    show2(n / ((3*3*3)*(3)) % 3);               /* 4 ケタめを表示 */
    printf("|");
    show2(n / ((3*3*3)*(3*3)) % 3);             /* 5 ケタめを表示 */
    printf("\n");
    printf("---+---+---\n");
    show2(n % 3);                               /* 0 ケタめを表示 */
    printf("|");
    show2(n / 3 % 3);                           /* 1 ケタめを表示 */
    printf("|");
    show2(n / (3*3) % 3);                       /* 2 ケタめを表示 */
    printf("\n\n");
}


/* x に応じて、空白、O, X を出力 */
void show2(int x) {
    if (x == 0) {
        printf("   ");
    } else if (x == 1) {
        printf(" O ");
    } else {
        printf(" X ");
    }
}