/*

    ○×ゲーム

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


           |   |         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] を二通りに使うところが少々ややこしい。）

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

000|000|000  111|111|111  引き分け

となるので、先手が最初にどこに○を書いても、双方が最善をつくせば、ゲームは
引き分けに終わることがわかる。どこに書くかは本質的には三通りだが、

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

であることから、先手が第一手を打つ場所ごとに、後手が×を打つべき位置がわかる。
それらを図示すれば以下のようになる。

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

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

000|001|021  222|220|200  ○の勝ち

のように表示される。）

コンピュータと対戦するときは、コンピュータは、最善の結果にいたる手のうちから
ランダムに選んで打ってくる。どの手が、人間にとって最善の手を返すのが一番難しい
か、などは考えていない。（コンピュータが先手の場合、第一手のみは例外で、中央に
打ってくる確率をほかのマスの４倍にしてある。それは、隅や辺は４箇所ずつあり、
その４箇所のどこに打っても本質的には同じことなので、「隅に打ってくる確率」「辺
に打ってくる確率」「中央に打ってくる確率」を等しくしたかったからである。）

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

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

付）あり得ない局面とされなかった局面を考えてみよう。書かれている○の数は高々
５個、×の数は高々４個なので、縦・横・斜めに三本以上並ぶことはあり得ない。それ
は、二本並ぶのに少なくとも５個を要するからである。二本並んだ場合、それは○で
あり、その二本の共通部分のマスに最後に○を打ったと考えれば、その局面が実際に
起こり得ることがわかる。121|212|121 などがその例である。
*/

#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--) {
        /* m > n とすると、b[m] は -10, 0, 10, -123 のどれかであることに注意 */
        b[n] = f(n);
        if (b[n] == 10 || b[n] == 0 || b[n] == -10 || b[n] == -123) {
            ;   /* 終わっているとき、ありえないときは何もしない */
        } else if (b[n] == 1) {     /* ○の手番のとき */
            b[n] = -10; /* 最悪の場合、すなわち×の勝ち、としてみる */
            a[n] = 0;   /* 注)次の for ループ通過後は b[n] は -10 か 0 か 10 */
            for (pow = 1; pow < N; pow = pow * 3) {
                /* 空いているマスを探し、試しに○を置いて、よくなるか調べる */
                if ((n / pow) % 3 == 0) {   /* マスが空いていたら */
                    if (b[n] == b[n + pow]) {   /* 置いてみて等しければ */
                        a[n] = a[n] + pow;      /* そのケタも 1 にする */
                    } else if (b[n] < b[n + pow]) { /* 置いてみてよくなれば */
                        a[n] = pow; b[n] = b[n + pow];  /* そこだけ 1 にする */
                    }
                }
            }
        } else if (b[n] == -1) {    /* ×の手番のとき */
            b[n] = 10;  /* 最悪の場合、すなわち○の勝ち、としてみる*/
            a[n] = 0;   /* 注)次の for ループ通過後は b[n] は 10 か 0 か -10 */
            for (pow = 1; pow < N; pow = pow * 3) {
                /* 空いているマスを探し、試しに×を置いて、よくなるか調べる */
                if ((n / pow) % 3 == 0) {   /* マスが空いていたら */
                    if (b[n] == b[n + 2*pow]) { /* 置いてみて等しければ */
                        a[n] = a[n] + 2*pow;    /* そのケタも 2 にする */
                    } else if (b[n] > b[n + 2*pow]) {   /* 置いてよくなれば */
                        a[n] = 2*pow; b[n] = b[n + 2*pow];  /* そこだけ 2 に */
                    }
                }
            }           /*（b[n + 2*pow] == -123 はありえないことに注意）*/
        }
    }

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

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


/*
整数 n に対応する局面の○と×の配置を見て、次の数を返す。
    10 ... ○の勝ち（ゲームは終了している）。
     1 ... 勝敗はついておらず、次は○の手番。
     0 ... 引き分け（ゲームは終了している）。
    -1 ... 勝敗はついておらず、次は×の手番。
   -10 ... ×の勝ち（ゲームは終了している）。
  -123 ... ありえない局面。-123 という数に特別の意味はない。
*/
int f(int n) {
    int i, counto, countx, owin, xwin;
    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 -123;    /* ○と×の数が合わないので、ありえない場合 */
    }

    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) {   /* 両方が勝つことはありえない。片方 */
        return -123;                    /* が勝った時点でゲーム終了だから。 */
    }
    if (owin == YES) {              /* ○が勝ちの局面 */
        return 10;
    }
    if (xwin == YES) {              /* ×が勝ちの局面 */
        return -10;
    }
    if (counto + countx == 9) {     /* 盤がいっぱいになっている。引き分け。*/
        return 0;
    }
    if (counto == countx) {         /* ○×同数なら次は○の手番 */
        return 1;
    } else {                        /* そうでなければ×の手番 */
        return -1;
    }
}


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

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

このとき a[n] は 001|001|000 と出力され、その右に「○の勝ち」と表示されるが、
これは、次に 6 か 3 のマスに○を書けば、また、その場合のみ、以下双方が最善を
つくしても○（先攻）の勝ち、という意味である。つまり、これが必勝法（引き分けに
持ち込むのがベストの局面では“必・引き分け法”）を示している。
*/
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("  ");               /* 以下、a[n] を三進で上のケタから表示 */
        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] == 10) {
            printf("  ○の勝ち\n");
        } else if (b[n] == -10) {
            printf("  ×の勝ち\n");
        } else if (b[n] == 0) {
            printf("  引き分け\n");
        } else if (b[n] == -123) {
            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) == 1 || f(n) == -1;    ) { /* 決着がついていない限り */
        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) == 1 || f(n) == -1) {  /* 決着がついていない場合 */
            /* 以下、コンピュータの打つ手を考える */
            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;
                /* ユーザが先攻なら pow を、後攻なら 2*pow を n に加える */
            n = n + pow * (3 - i);
        }
    }
        /* 決着がついてループを抜けるとここへくる */
    show(n);                                                /* 画面表示 */
    if (i == 1 && f(n) == -10 || i == 2 && f(n) == 10) {
        printf("私の勝ちです.\n");
    } else if (f(n) == 0) {
        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 ");
    }
}