//************************************************
// 　ロミオゲーム/ミニマックス法
//************************************************
#include <stdio.h>
#include <stdlib.h>

#define  SIZE  11 // ボードサイズ

#define  SPACE  0
#define  WHITE  1
#define  BLACK  2

int  BOARD[SIZE+2];
char *PIECE[3] = {"  ","○","●"};

//************************************
// 手を戻す(反した駒も戻す)          
//************************************
void Get(int me, int pos, int *left, int *right)
{
    int  you, i;

    you = (me % 2) + 1;

    BOARD[pos] = 0;
    if (*right <= SIZE)
        for (i=pos+1; i<*right; i++) BOARD[i] = you;
    if (*left > 0)
        for (i=*left+1; i<pos; i++) BOARD[i] = you;
}
//************************************
// 手を打つ(相手の駒を反せるなら反す)
//************************************
void Put(int me, int pos, int *left, int *right)
{
    int  you, i;

    you = (me % 2) + 1;

    BOARD[pos] = me;

    for (*left=pos-1; *left > 0; (*left)--)
        if (BOARD[*left] != you) break;
    if (BOARD[*left] != me) *left = 0;
    else for (i = *left + 1; i<pos; i++) BOARD[i] = me;

    for (*right=pos+1; *right <= SIZE; (*right)++)
        if (BOARD[*right] != you) break;
    if (BOARD[*right] != me) *right = SIZE + 1;
    else for (i=pos+1; i < *right; i++) BOARD[i] = me;
}
//************************************
// 局面を表示してから人の手を入力する
//************************************
int Human(int com)
{
    int  i, man;
    char buff[4];

    do {
        if (com) printf("com(○)=%2d ",com);
        else     printf("           ");
        for (i=1; i<=SIZE; i++)
            printf("|%s",PIECE[BOARD[i]]);
        printf("| man(●)=");
        gets(buff);
        man = atoi(buff);
    } while (man<1 || man>SIZE || BOARD[man]);

    return man;
}
//****************************************
// 再帰呼出しを使って次の手を選択する
//****************************************
int MinMax(int you, int tesu)
{
    int  me, n, left, right, me_cnt, you_cnt, retc;

    // 自分＝相手の反対
    me = (you == WHITE)? BLACK: WHITE;

    // ゲームが終了している
    if (tesu == SIZE) {
        me_cnt = you_cnt = 0;
        for (n=1; n<=SIZE; n++)
            if (BOARD[n] == me) me_cnt++; else you_cnt++;
        if (me_cnt < you_cnt) return 0; // 自分の勝ち
    } else {
        // 空きマスに駒を置いてみる
        for (n=1; n<=SIZE; n++) {
            if (!BOARD[n]) {
                Put(me, n, &left, &right); // 手を打つ
                retc = MinMax(me, tesu+1); // 相手に再帰で渡す
                Get(me, n, &left, &right); // 手を戻す

                // 相手が負けと答えたらこの手で勝てる
                if (retc < 0) return n;
            }
        }
    }
    return -1; // 自分の負け
}
//************************************
// ゲーム進行                        
//************************************
int main(void)
{
    int  i, pos, tesu, com_cnt, man_cnt, dummy1, dummy2;
    char buff[4];

    do {
        // 初期化する
        printf("\n           ");
        for (i=1; i<=SIZE; i++) {
            BOARD[i] = 0;
            printf("|%2d",i);
        }
        printf("|\n");

        // ゲーム進行
        tesu = pos = 0;
        for (;;) {
            // 人の手番
            pos = Human(pos);
            Put(BLACK, pos, &dummy1, &dummy2);
            if (++tesu == SIZE) break;

            // コンピュータの手番
            pos = MinMax(BLACK, tesu);
            if (pos == -1) { printf("\n未対応\n"); exit(0); }
            Put(WHITE, pos, &dummy1, &dummy2);
            ++tesu;
        }

        // 結果の表示
        com_cnt = man_cnt = 0;
        for (i=1; i<=SIZE; i++)
            if (BOARD[i] == WHITE) com_cnt++; else man_cnt++;
        printf("[ %2d ] win!",com_cnt);
        for (i=1; i<=SIZE; i++)
            printf("|%s",PIECE[BOARD[i]]);
        printf("| [ %2d ] lost\n",man_cnt);

        // 再プレーの確認
        printf("\nTry Again?(y/n) = ");
        gets(buff);
    } while (buff[0] == 'y');

    return 0;
}