【C言語】まるばつゲーム（三目並べ）を作ってみた

C言語で「まるばつゲーム（三目並べ）」を作ってみました。

コンピューター相手に対戦できる簡単なAIも実装してあります。

出来る限りわかりやすく書いたつもりです。400行程度の簡単なコードになります。

この記事では簡単な解説を行いたいと思います。

質問等がありましたらコメント欄にて受け付けます！
（出来る限りお答えさせていただく予定です）

ソースコードについて

GitHubに公開させていただきました → kazumasa-kusaba/TicTacToe

余談ですが、英語圏では、まるばつゲーム（三目並べ）は、TicTacToeと呼ばれているようです。

遊び方

GitHubのREADME.mdに書いてあることの繰り返しになってしまいますが。

まずはコードをビルドしてください。ルートディレクトリで”make”と入力してエンターキーを押せば完了です。

TicTacToe % make
gcc -Wall -o src/board.o -c src/board.c
gcc -Wall -o src/main.o -c src/main.c
gcc -Wall -o src/strategy.o -c src/strategy.c
gcc -Wall -o TicTacToe src/board.o src/main.o src/strategy.o

そのままルートディレクトリで実行ファイルを実行すれば、ゲーム開始です。

表示された内容に従って、任意の数字を入力していけば、ゲームを進行できます。

TicTacToe % ./TicTacToe 
TicTacToe version 1.00
https: //github.com/kazumasa-kusaba/TicTacToe

Which do you play? (0: first, 1: second)
Input: 0
You are first, computer is second.
  012
 |---|
0|...|
1|...|
2|...|
 |---|
Where do you place?
Input Row: 0
Input Column: 0
  012
 |---|
0|O..|
1|...|
2|...|
 |---|
Computer ROW: 1, COLUMN: 1.
  012
 |---|
0|O..|
1|.X.|
2|...|
 |---|
Where do you place?
Input Row: 
~~ omitted ~~
  012
 |---|
0|OXO|
1|XXO|
2|OOX|
 |---|
Draw

ソースコードの簡単な解説

各ファイルについて

ソースコードはsrc以下に置かれています。

大きく分けて3種類のファイルがあります。

main.c

main関数だけ抜粋して簡単に解説します。

int main(void)
{
  PrintSoftwareInfo();

  BoardInfo bi;
  BoardInitialize(&bi);

  PlayerTurn human_turn = PLAYER_TURN_FIRST;
  PlayerTurn computer_turn = PLAYER_TURN_SECOND;
  InputTurn(&human_turn, &computer_turn);
  
  BoardMark human_mark = human_turn == PLAYER_TURN_FIRST ? BOARD_MARK_O : BOARD_MARK_X;
  BoardMark computer_mark = human_mark == BOARD_MARK_O ? BOARD_MARK_X : BOARD_MARK_O;
  BoardPrint(&bi);

  ConductGame(&bi, human_turn, human_mark, computer_turn, computer_mark);

  PrintResult(&bi, human_turn);

  return 0;
}

PrintSoftwareInfo関数で、本ソフトの情報を表示します。

BoardInitialize関数で、定義されたBoardInfo型の変数を初期化します。BoardInfoは、盤面を管理するための構造体です。（後述あり）

InputTurn関数で、プレイヤーがどちらの手番で遊ぶかを入力させます。

BoardPrint関数で、現在の盤面の情報を表示します。

ConductGame関数で、ゲームを行います（終了するまで継続）

PrintResult関数で、結果を表示します。

board.h / board.c

board.h

#define BOARD_SIZE   3

盤面の大きさを決定するマクロです。伝統的な「まるばつゲーム」は3 x 3なので、3で設定しています。

※3より大きい値を設定しても正常に機能しますが、コンピューター（AI）の計算にものすごく時間がかかります（詳細は後述します）

typedef enum {
  BOARD_ERROR_OK = 0,
  BOARD_ERROR_FATAL,
} BoardError;

board関連の関数の戻り値の定義です。

typedef enum {
  BOARD_MARK_NONE = 0,
  BOARD_MARK_O,
  BOARD_MARK_X,
} BoardMark;

マークの種類です。

盤面のマスに、何も置かれていないときはNONEを使用します。

typedef enum {
  BOARD_RESULT_MARK_O_WON = 0,
  BOARD_RESULT_MARK_X_WON,
  BOARD_RESULT_DRAW,
  BOARD_RESULT_NOT_DECIDED,
} BoardResult;

typedef struct {
  unsigned int row;
  unsigned int col;
} BoardPoint;

typedef struct {
  int rows[BOARD_SIZE];
  int cols[BOARD_SIZE];
  int diagonal;
  int anti_diagonal;
} BoardLines;

typedef struct {
  BoardMark board[BOARD_SIZE][BOARD_SIZE];
  BoardLines lines;
  unsigned int left_spaces;
  BoardResult result;
} BoardInfo;

この辺りはまとめて説明。

BoardResultは、勝敗を示すenumです。

BoardPointは、盤面上のマスの場所を示す構造体です。左上から右下に向かって正方向とします。

BoardLinesは、勝敗決定を効率化するための管理用の構造体です。これを使うことで、勝敗の決定の判断を効率化できます。（詳細は後述します。）

BoardInfoは、盤面を管理するための構造体です。実態は、main関数の中で定義されていたと思います。left_spacesメンバは、盤面上に残っている空きマスの数を示します。

board.c

難しいのは、BoardPlaceMarkのみだと思いますので、そこだけ解説します。

BoardError BoardPlaceMark(BoardInfo *bi, const BoardPoint *point, BoardMark mark)
{
  BoardError ret = BOARD_ERROR_OK;

  ret = CheckIfMarkIsValid(bi->board, point, mark);
  if (ret != BOARD_ERROR_OK) {
    return ret;
  }

  bi->board[point->row][point->col] = mark;

  bi->left_spaces -= 1;
  UpdateBoardLines(bi, point, mark);
  UpdateBoardResult(bi, point, mark);

  return ret;
}

BoardPlaceMark関数は、盤面にマークをつけるための関数です。main関数の中で使用されています。

第一引数に盤面の管理構造体、第二引数にマスの場所、第三引数にマークの種類を渡します。

CheckIfMarkIsValid関数で、引数で指定されたマスに指定されたマークを付けられるのかをチェックします。（具体的には、盤面の範囲内なのか、何も置いてないマスであるかどうかを確認）

指定された場所にマークをつけられることが確認できたら

bi->board[point->row][point->col] = mark;

でマスにマークを付けます。

bi->left_spaces -= 1;
UpdateBoardLines(bi, point, mark);
UpdateBoardResult(bi, point, mark);

管理構造体の盤面の情報を更新します。

マスにマークが置かれることで、１つマスが減るわけですから、left_spacesを-1します。

UpdateBoardLines関数とUpdateBoardResult関数が、このプログラムのポイントになります。まるばつゲームの勝敗の判定を効率化するための仕組みのようなものです。

static void UpdateBoardLines(BoardInfo *bi, const BoardPoint *point, BoardMark mark)
{
  bi->lines.rows[point->row] += GetMarkValue(mark);
  bi->lines.cols[point->col] += GetMarkValue(mark);
  if (point->row == point->col) {
    bi->lines.diagonal += GetMarkValue(mark);
  }
  if (point->row == (BOARD_SIZE - point->col - 1)) {
    bi->lines.anti_diagonal += GetMarkValue(mark);
  }
}

UpdateBoardLines関数内で、マークを付けられた場所に相当するlinesのrowsとcolsの値を -1 or +1 加算します。（値はマークによって決定される。）

また対角線を示すdiagonalとanti_diagonalも加算します。

static void UpdateBoardResult(BoardInfo *bi, const BoardPoint *point, BoardMark mark)
{
  if (abs(bi->lines.rows[point->row]) == BOARD_SIZE ||
      abs(bi->lines.cols[point->col]) == BOARD_SIZE ||
      abs(bi->lines.diagonal)         == BOARD_SIZE ||
      abs(bi->lines.anti_diagonal)    == BOARD_SIZE) {
    bi->result = GetBoardResult(mark);
  } else if (bi->left_spaces == 0) {
    bi->result = BOARD_RESULT_DRAW;
  }
}

最後に、UpdateBoardResult関数内で勝敗を判定します。

rows, cols, diagonal, anti_diagonalの絶対値のどれかが、盤面の大きさと一致していれば、勝敗は決着しています。

勝敗は、BoardInfoのresultメンバに設定します。

この勝敗判定を使えば、計算量を減らすことができます。計算量はO(1)です。

他のやり方としては、マークを付けた行と列と対角線を全てチェックする方法が考えられますが、このやり方だと盤面のサイズNに依存するので、計算量はO(N)となります。

strategy.c / strategy.c

冒頭で「AI」と呼びましたが、実態はただのミニマックス法による探索です…
(大げさな表現を使ってすみません。。)

ミニマックス法については、こちらのサイトがわかりやすかったです。
（この記事では、ミニマックス法について詳細な解説は行いません。質問はコメント欄にて受け付けております。）

3 x 3 の まるばつゲームは、手数が少ないので、ミニマックス法法で最後まで計算する作りにしてあります。
（全てのマスが埋まった場合 9! = 362880通り。実際は全てのマスが埋まらずに終局するケースも多いので、実際はもっと少ないと思われる。）

StrategyError StrategyPlaceMark(const BoardInfo *bi, BoardMark mark, BoardPoint *point)
{
  return StrategyMinMax(bi, mark, point);
}

static StrategyError StrategyMinMax(const BoardInfo *bi, BoardMark computer_mark, BoardPoint *next_point)
{
  MinMax(*bi, computer_mark, computer_mark, next_point);
  return STRATEGY_ERROR_OK;
}

StrategyPlaceMark関数で、(AIによる)最適なマスの場所を計算します。第三引数は最適な場所を返す出力用の引数として使用します。

その関数の中で、StrategyMinMax関数を呼び出します。これは、名前の通り、MiniMax法を使用して最適手を求める関数です。

static int MinMax(BoardInfo bi, BoardMark computer_mark, BoardMark mark, BoardPoint *point)
{
  if (bi.result != BOARD_RESULT_NOT_DECIDED) {
    return CalculateScore(&bi, computer_mark);
  }

  int ret = computer_mark == mark ? -SCORE_VALUE_MAX : SCORE_VALUE_MAX;

  for (int row = 0; row < BOARD_SIZE; row++) {
    for (int col = 0; col < BOARD_SIZE; col++) {
      BoardPoint next_point = {row, col};
      BoardInfo next_board = bi;
      if (BoardPlaceMark(&next_board, &next_point, mark) != BOARD_ERROR_OK) {
        continue;
      }
      BoardMark next_mark = mark == BOARD_MARK_O ? BOARD_MARK_X : BOARD_MARK_O;
      int score = MinMax(next_board, computer_mark, next_mark, &next_point);
      UpdateResult(computer_mark, mark, score, &next_point, &ret, point);
    }
  }

  return ret;
}

再帰を利用しています。（MinMax関数の中でMinMax関数を呼んでいる。）

3行目のif文で、ゲームが終局しているかどうかを確認します。終局していれば、CalculateScore関数で点数を求めます。勝ちは+1点、負けは-1点、引き分けは0点です。

2重のfor文の中で、可能な場所にマークを付け、手番を入れ替え、更にMinMax関数を呼び出し、点数を計算しようとしています。

UpdateResult関数の中で、点数を比較し最適な手かどうかを判断します。最適であれば、点数と最適手（マークをつける場所）を更新します。

以上が簡単な説明でした！

何か質問等がありましたら、コメント欄にください！

考察

AIには絶対に勝てません

実際にコードをビルドして遊んだ人は既にわかっていると思いますが。

このAIには絶対に勝てません。

実は、3 x 3 のまるばつゲームでは、互いのプレイヤーが最善手を打てば、絶対に引き分けになることがわかっています。

AIは常に最善手を打つので、勝てません。。

探索アルゴリズムについて

簡単なゲームなので、ミニマックス法を利用しましたが、AlphaBeta法の方が探索効率が良いです。

前者の探索アルゴリズムは、仕組み上、無駄な探索を行っています。それを省いて探索を行えるアルゴリズムが、AlphaBeta法です。

興味のある人は、本プログラムを書き換えてみてください。GitHubでのプルリクエストをお待ちしております。。

マクロ BOARD_SIZE について

盤面の大きさは、board.hの中で3で定義されています。

#define BOARD_SIZE   3

この値を変更して盤面を大きくしても遊べるのかどうかという質問についてです。

結論を書くと、難しいです。。

盤面が大きくなることで、手数が多くなるため、AIで終局まで読みきれなくなってしまいます。その場合は、途中の盤面の状況判断できる評価関数の導入が必要かと思います。

今回はそこまで行いません。。

以上です！

何か質問等がありましたら、コメント欄にお願いいたします！