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

#define     BOARD_SIZE      3       // 盤の大きさ
#define     SQUARE_COUNT    9       // すべてのマスの数

/**************************************************
* 盤のマス等、白、黒、その他を表す
**************************************************/
typedef enum _HP_DEFS
{
    NONE,       // 盤外、未定を表す
    BLACK,      // 黒を表す
    WHITE,      // 白を表す
    EMPTY       // 空き
}HP_DEFS;

/**************************************************
* Booleanな感じを定義する
**************************************************/
typedef enum _HP_BOOL
{
    HP_FALSE = 0,
    HP_TRUE = 1
}HP_BOOL;

/**************************************************
* 盤のマスを示す構造体
**************************************************/
typedef struct
{
    int file;   // 左を0とした横方向
    int rank;   // 下を0とした縦方向
} HP_POINT;

/**************************************************
* 盤の状態を表す構造体
**************************************************/
typedef struct
{
    HP_DEFS     squares[BOARD_SIZE][BOARD_SIZE];    // 盤のマス
    HP_POINT    from;       // 駒の移動元
    HP_POINT    to;         // 駒の移動先
} HP_BOARD;


///////////////////////////////////////////////////
// file, rank からHP_POINT構造体を作成する
//
// file：横方向の位置
// rank：縦方向の位置
// return：HP_POINT構造体
///////////////////////////////////////////////////
HP_POINT Point(int file, int rank)
{
    HP_POINT pt;

    pt.file = file;
    pt.rank = rank;

    return pt;
}

///////////////////////////////////////////////////
// 盤の指定されたマスの状態を取得する
//
// board：取得する BOARDへのポインタ
// pt：マスの位置
// return：マスの状態
///////////////////////////////////////////////////
HP_DEFS GetSquare(HP_BOARD board, HP_POINT pt)
{
    if (0 <= pt.file && pt.file < BOARD_SIZE
        && 0 <= pt.rank && pt.rank < BOARD_SIZE)
    {
        return board.squares[pt.file][pt.rank];
    }
    else{
        return NONE;
    }
}

///////////////////////////////////////////////////
// 盤の指定されたマスの状態を設定する
//
// pboard：設定する BOARDへのポインタ
// pt：マスの位置
// pawn：設定する状態
///////////////////////////////////////////////////
void SetSquare(HP_BOARD* pboard, HP_POINT pt, HP_DEFS pawn)
{
    if (0 <= pt.file && pt.file < BOARD_SIZE
        && 0 <= pt.rank && pt.rank < BOARD_SIZE)
    {
        pboard->squares[pt.file][pt.rank] = pawn;
    }
}

///////////////////////////////////////////////////
// 盤を初期状態にする
//
// pboard：初期状態にする BOARDへのポインタ
///////////////////////////////////////////////////
void InitializeBoard(HP_BOARD* pboard)
{
    int file;

    for (file = 0; file < BOARD_SIZE; file++)
    {
        SetSquare(pboard, Point(file, 2), BLACK);   // 黒のポーン
        SetSquare(pboard, Point(file, 1), EMPTY);   // 空き
        SetSquare(pboard, Point(file, 0), WHITE);   // 白のポーン
    }
}

///////////////////////////////////////////////////
// すべてのマスの位置を取得する
//
// apt：HP_POINTの配列（要素数はSQUARE_COUNT）
///////////////////////////////////////////////////
void GetAllPoints(HP_POINT apt[])
{
    int file, rank;
    int n = 0;

    for (rank = 0; rank < BOARD_SIZE; rank++)
    {
        for (file = 0; file < BOARD_SIZE; file++)
            apt[n++] = Point(file, rank);
    }
}
///////////////////////////////////////////////////
//  HP_BOARDを比較する
//
// bd1：比較するHP_BOARD構造体
// bd2：比較するHP_BOARD構造体
// return：HP_TRUE 同じ、HP_FALSE 異なる
///////////////////////////////////////////////////
HP_BOOL CompareBoard(HP_BOARD bd1, HP_BOARD bd2)
{
    HP_POINT all[SQUARE_COUNT];
    int i;

    GetAllPoints(all);

    for (i = 0; i < SQUARE_COUNT; i++)
    {
        if (GetSquare(bd1, all[i]) != GetSquare(bd2, all[i]))
            return HP_FALSE;
    }

    if (bd1.from.file != bd2.from.file || bd1.from.rank != bd2.from.rank
        || bd1.to.file != bd2.to.file || bd1.to.rank != bd2.to.rank)
        return HP_FALSE;

    return HP_TRUE;
}

///////////////////////////////////////////////////
// 盤の状態を表示する
//
// bd：表示するHP_BOARD構造体
///////////////////////////////////////////////////
void ShowBoard(HP_BOARD bd)
{
    int rank, file;

    printf("\n");

    for (rank = BOARD_SIZE-1; rank >= 0 ; rank--)
    {
        printf("\n   +---+---+---+");
        printf("\n %d |", rank + 1);

        for (file = 0; file < BOARD_SIZE; file++)
        {
            if (GetSquare(bd, Point(file, rank)) == BLACK)
                printf(" ○|");
            else if (GetSquare(bd, Point(file, rank)) == WHITE)
                printf(" ●|");
            else if ((rank % 2) == (file % 2))
                printf(":::|");
            else
                printf("   |");
        }

        if (rank == 2)
            printf("      7  8  9");
        else if (rank == 1)
            printf("      4  5  6");
        else if (rank == 0)
            printf("      1  2  3");
    }

    printf("\n   +---+---+---+");
    printf("\n     a   b   c\n");
}

///////////////////////////////////////////////////
//  指定された位置のポーンが動けるかどうか
//
// bd：盤の状態
// pt：調べるマス
// return：HP_TRUE 動ける、HP_FALSE 動けない
///////////////////////////////////////////////////
HP_BOOL IsMoveablePawn(HP_BOARD bd, HP_POINT pt)
{
    int dir;    // 進む方向
    int opp;    // 対戦相手の駒

    if (GetSquare(bd, pt) == WHITE)
    {
        dir = 1;
        opp = BLACK;
    }
    else if (GetSquare(bd, pt) == BLACK)
    {
        dir = -1;
        opp = WHITE;

    }
    else{
        return HP_FALSE;
    }

    if (GetSquare(bd, Point(pt.file, pt.rank + dir)) == EMPTY)
        return HP_TRUE;     // １マス前が空
    else if (GetSquare(bd, Point(pt.file - 1, pt.rank + dir)) == opp)
        return HP_TRUE;     // 斜め前に相手の駒がある
    else if (GetSquare(bd, Point(pt.file + 1, pt.rank + dir)) == opp)
        return HP_TRUE;     // 反対の斜め前に相手の駒がある
    else
        return HP_FALSE;
}

///////////////////////////////////////////////////
// 駒の移動が有効であるかどうかを調べる
//
// bd：盤の状態
// return：HP_TRUE 有効、HP_FALSE 無効
///////////////////////////////////////////////////
HP_BOOL IsValidMove(HP_BOARD bd)
{
    int     df = bd.to.file - bd.from.file;
    int     dr = bd.to.rank - bd.from.rank;

    if (GetSquare(bd, bd.from) == WHITE)
    {
        // 動かす駒が白

        if (GetSquare(bd, bd.to) == EMPTY && df == 0 && dr == 1)
            return HP_TRUE;    // １マス前に動ける
        else if (GetSquare(bd, bd.to) == BLACK && (df == 1 || df == -1) && dr == 1)
            return HP_TRUE;    // 斜め前に動ける
    }
    else if (GetSquare(bd, bd.from) == BLACK)
    {
        // 動かす駒が黒

        if (GetSquare(bd, bd.to) == EMPTY && df == 0 && dr == -1)
            return HP_TRUE;    // １マス前に動ける
        else if (GetSquare(bd, bd.to) == WHITE && (df == 1 || df == -1) && dr == -1)
            return HP_TRUE;    // 斜め前に動ける
    }

    return HP_FALSE;
}

///////////////////////////////////////////////////
// HP_POINTを文字列にする
//
// pText：文字列へのポインタ
// pt：HP_POINT構造体
///////////////////////////////////////////////////
void ToFileRankText(char* pText, HP_POINT pt)
{
    pText[0] = pt.file + 'a';   // 左から a,b,c
    pText[1] = pt.rank + '1';   // 下から 1,2,3
    pText[2] = 0;
}

///////////////////////////////////////////////////
// HP_POINTを左右対称の位置に変換する
//
// pt：HP_POINT構造体
// return：変換したHP_POINT構造体
///////////////////////////////////////////////////
HP_POINT ConvertMirror(HP_POINT pt)
{
    if (pt.file == 0)
        pt.file = 2;
    else if (pt.file == 2)
        pt.file = 0;

    return pt;
}

void DumpMem(HP_BOARD mem)
{
    int i, j;
    char    from[10];
    char    to[10];

    printf("\n");
    for (i = BOARD_SIZE - 1; i >= 0; i--){
        for (j = 0; j < BOARD_SIZE; j++)
        {
            printf("%c", GetSquare(mem, Point(j, i)));
        }

        printf(" ");
    }

    ToFileRankText(from, mem.from);
    ToFileRankText(to, mem.to);

    printf("   %s → %s", from, to);
}

///////////////////////////////////////////////////
// 負けの状態を検索する（左右対称も含んで）
//
// bd：検索するHP_BOARD構造体
// aDefeat：負けの手の配列
// cntDefeat：配列の要素数
// return：HP_TRUE 見つかった HP_FALSE 見つからない
///////////////////////////////////////////////////
HP_BOOL FindDefeat(HP_BOARD bd, HP_BOARD aDefeat[], int cntDefeat)
{
    HP_POINT all[SQUARE_COUNT];
    HP_BOARD    mirror;
    int     i;

    // 左右反対の盤の状態を作成する ///////////////
    GetAllPoints(all);

    mirror.from = ConvertMirror(bd.from);
    mirror.to = ConvertMirror(bd.to);

    for (i = 0; i < SQUARE_COUNT; i++)
        SetSquare(&mirror, all[i], GetSquare(bd, ConvertMirror(all[i])));

    // 負けの手から探す ///////////////////////////
    for (i = 0; i < cntDefeat; i++)
    {
        if (CompareBoard(bd, aDefeat[i]))
            return HP_TRUE;

        if (CompareBoard(mirror, aDefeat[i]))
            return HP_TRUE;
    }

    return HP_FALSE;
}

///////////////////////////////////////////////////
// マッチ箱の手を決定する
//
// bd：現在の盤の状態
// HP_SQUARE borw：白番か黒番か
// aDefaet：負けの手の配列
// cntDefeat：配列の要素数
// return：HP_TRUE 打った！ HP_FALSE 手が無い（リザイン）
///////////////////////////////////////////////////
HP_BOOL MatchBoxTurn(HP_BOARD* pbd, HP_DEFS borw, HP_BOARD aDef[], int cntDef)
{
    HP_POINT allsq[SQUARE_COUNT];
    int     i, j;

    // すべてのマスの位置を取得する
    GetAllPoints(allsq);

    // ランダムに打つよう、配列の順番を変更する
    for (i = 0; i < 20; i++)
    {
        // 任意の２つのマスの配列内の順番を入れ替える
        int     p = rand() % SQUARE_COUNT;
        int     q = rand() % SQUARE_COUNT;

        if (p != q)
        {
            HP_POINT    t = allsq[p];
            allsq[p] = allsq[q];
            allsq[q] = t;
        }
    }

    // 有効な手を探索する
    for (i = 0; i < SQUARE_COUNT; i++)
    {
        if (GetSquare(*pbd, allsq[i]) != borw)
            continue;   // 手番の駒が無ければ次へ

        for (j = 0; j < SQUARE_COUNT; j++)
        {
            pbd->from = allsq[i];    // 移動元
            pbd->to = allsq[j];      // 移動先

            // 有効な手であり、負けの手に含まれていなければOK!
            if (IsValidMove(*pbd) && !FindDefeat(*pbd, aDef, cntDef))
            {
                char    szFrom[10];
                char    szTo[10];

                ToFileRankText(szFrom, pbd->from);
                ToFileRankText(szTo, pbd->to);

                printf("\nマッチ箱： %s を %s へ", szFrom, szTo);

                return HP_TRUE;
            }
        }
    }

    printf("\nリザインします。");

    return HP_FALSE;    // リザイン
}
///////////////////////////////////////////////////
// 入力された文字から駒の位置に変換する
//
// ch：入力された文字（'1'～'9'）
// return：HP_POINT構造体
///////////////////////////////////////////////////
HP_POINT InputSquarePoint( char* szGuide)
{
    for (;;)
    {
        int     ch;

        printf(szGuide);

        ch = _getche();

        switch (ch)
        {
        case '7':
            return Point(0, 2);
        case '8':
            return Point(1, 2);
        case '9':
            return Point(2, 2);
        case '4':
            return Point(0, 1);
        case '5':
            return Point(1, 1);
        case '6':
            return Point(2, 1);
        case '1':
            return Point(0, 0);
        case '2':
            return Point(1, 0);
        case '3':
            return Point(2, 0);
        }
    }

    return Point(-1, -1);
}

///////////////////////////////////////////////////
// プレイヤーの手を入力する
//
// pbd：HP_BOARD構造体へのポインタ
// borw：白番か、黒番か
///////////////////////////////////////////////////
void PlayerTurn(HP_BOARD* pbd, HP_DEFS borw)
{
    for (;;)
    {
        pbd->from = InputSquarePoint("\n駒を選んでください(1～9)：");

        if (borw == GetSquare(*pbd, pbd->from) && IsMoveablePawn(*pbd, pbd->from))
            break;
        else
            printf("\n動かせる駒がありません");
    }

    for (;;)
    {
        pbd->to = InputSquarePoint("\nどこに動かしますか？(1～9)：");

        if (IsValidMove(*pbd))
            break;
        else
            printf("\nそこには動かせません");
    }
}
///////////////////////////////////////////////////
// 勝敗を確認する
//
// bd：HP_BOARD構造体
// next：次が白番か、黒番か
///////////////////////////////////////////////////
HP_DEFS CheckFinish(HP_BOARD bd, HP_DEFS next)
{
    HP_POINT all[SQUARE_COUNT];
    int file, sq;
    int cntWhite = 0;
    int cntBlack = 0;

    // ３列目に駒があるか /////////////////////////
    for (file = 0; file < BOARD_SIZE; file++)
    {
        if (GetSquare(bd, Point(file, BOARD_SIZE - 1)) == WHITE)
            return WHITE;
        else if (GetSquare(bd, Point(file, 0)) == BLACK)
            return BLACK;
    }

    // 動ける駒の数 ///////////////////////////////

    GetAllPoints(all);

    for (sq = 0; sq < SQUARE_COUNT; sq++)
    {
        if (IsMoveablePawn(bd, all[sq]))
        {
            if (WHITE == GetSquare(bd, all[sq]))
                cntWhite++;
            else if (BLACK == GetSquare(bd, all[sq]))
                cntBlack++;
        }
    }

    if (next == WHITE && cntWhite == 0)
        return BLACK;   // 次が白番で動かせる駒が無い
    else if (next == BLACK && cntBlack == 0)
        return WHITE;   // 次が黒番で動かせる駒が無い

    return EMPTY;   // 勝敗未定
}

///////////////////////////////////////////////////////////////////////
//  main関数
///////////////////////////////////////////////////////////////////////
void main(void)
{
    HP_BOARD    aDefeat[30];        // 負けの手を保持する配列
    int         cntDefeat = 0;      // 配列の要素数
    HP_DEFS     player = WHITE;     // プレイヤーの色
    HP_DEFS     matchbox = BLACK;   // マッチ箱の色
    int reply;                      // ユーザー入力を受け取る変数

    srand((unsigned int)time(0));   // 乱数の初期化

    do
    {
        HP_BOARD    board;                  // 現在の盤の状態
        HP_BOARD    lastMatchBoxMove;       // マッチ箱の最後の手
        int         cntMatchBoxMove = 0;    // マッチ箱の手数
        HP_DEFS     winner = NONE;
        HP_DEFS     turn = WHITE;

        InitializeBoard(&board);

        ShowBoard(board);

        while (winner != WHITE && winner != BLACK)
        {
            if (turn == player)
            {
                // プレイヤーのターン

                PlayerTurn(&board, player);
            }
            else
            {
                // マッチ箱のターン

                if (MatchBoxTurn(&board, matchbox, aDefeat, cntDefeat))
                {
                    lastMatchBoxMove = board;
                    cntMatchBoxMove++;
                }
                else
                {
                    // リザインした場合
                    winner = player;
                    break;
                }
            }

            // 駒を移動
            SetSquare(&board, board.to, GetSquare(board, board.from));
            SetSquare(&board, board.from, EMPTY);

            // 盤面を表示
            ShowBoard(board);

            // 次のターンへ
            if (turn == BLACK)
                turn = WHITE;
            else
                turn = BLACK;

            // 勝敗の確認
            winner = CheckFinish(board, turn);
        }

        if (winner == WHITE)
            printf("\n白の勝ちです。\n");
        else if (winner == BLACK)
            printf("\n黒の勝ちです。\n");

        if (winner != matchbox && cntMatchBoxMove > 0)
            aDefeat[cntDefeat++] = lastMatchBoxMove;

        printf("終了する場合は'Q'、続ける場合は他のキーを押してください");
        reply = _getche();
    } while (!(reply == 'q' || reply == 'Q'));
}