Weighted Tic-Tac-Toeとは？
Weighted Tic-Tac-Toeは AtCoder Beginner Contest 349 で出題された問題です。問題の内容は以下のようなものです。
3 × 3 のマス目があります。上から i 行目、左から j 列目 のマスをマス (i,j) と表します。マス (i,j) には整数 A[i, j] が書かれています。ここですべてのマスに書かれている数の総和は奇数であることが保証されます。また、すべてのマスははじめ白で塗られています。
高橋君と青木君が、このマス目を使ってゲームを行います。ゲームでは、高橋君を先手として、二人が交互に三目のゲームをします。またプレイヤーがまだ選択されていないマスを選ぶとマスに書かれている点数を得ることができます。両者がすべてのマスを選択したにもかかわらず勝負がつかない場合は点数が多いほうが勝ちです。マスに書かれている数の総和は奇数なので引き分けにはなりません。
両者が勝ちを目指して最適に行動するとき、どちらが勝つか判定してください。
高橋君が勝つならば Takahashi を、青木君が勝つならば Aoki を出力せよ。
入力されるデータ
A[1,1] A[1,2] A[1,3]
A[2,1] A[2,2] A[2,3]
A[3,1] A[3,2] A[3,3]
（ただし、-10^9 ≦ A[i,j] ≦ 10^9 ）
で、鳩君、君はこの問題できたの？ ゴメンナサイ、できませんでした。
どうやって解けばよいのか？
以下、解説を要約すると以下のようになります。
ゲームの各時点における盤面は 3×3 の2次元配列 C で表すことができます。そして C である状態からゲームを続けたとき，最終的に勝つプレイヤーを f(C) とします。
では f(C) をどうやって計算するかを考えでみまましょう。
現在の手番のプレイヤーを x，もう一方のプレイヤーを y とします、
もし C がすでに終了状態にあるとき、すなわちすべてのマスがどちらかのプレイヤーによって選択されているか、どちらかのプレイヤーが選択したマスが縦横斜めのどれかで3つ並んでいる場合は勝敗を判定することができます。
C が終了状態でない場合は、手番があるプレイヤーがマスを一つ選ぶことで別の盤面に遷移します。このとき次が成り立ちます。
（1）C から 1 回の操作で遷移できる盤面 C′のうち f(C′) = x となるようなものがあれば、 C から C′に遷移することで x が勝つことができる。
（2）逆に C から 1 回の操作で遷移できるすべての盤面 C′について f(C′) = y であるなら x はどのように操作しても勝つことができない。
この性質より C から遷移できるすべての盤面 C′について f(C′) が求まっていれば、それらの値から f(C) を求めることができます。このような処理は再帰関数で実装できます。
再帰関数による実装では、盤面 C に対して関数 f が呼び出されたときに次のような処理を行います。
（1）C が終了状態ならば勝敗を判定して答えを返す
（2）C が終了状態でなければ C から 1 回の操作で遷移できる盤面 C′をすべて列挙して各 C′について f(C′) を計算する。計算した f(C′) の結果から f(C) の値を定める。
以上のような方法がわかればあとは実装するだけです。
C#で実装してみる
C#で実装してみることにします。
GetWinner0メソッドは縦横斜めのいずれかで3つ並んでいるかどうかを調べるためのものです。0 を返す場合はどちらのプレイヤーも縦横斜めのいずれかで3つ並べることはできていないことを意味します。1 を返すときは Takahashi の勝ち、2 を返したときは Aoki の勝ちです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Program { static int GetWinner0(int[,] selects) { for (int row = 0; row < 3; row++) { if (selects[row, 0] != 0 && selects[row, 0] == selects[row, 1] && selects[row, 0] == selects[row, 2]) return selects[row, 0]; } for (int col = 0; col < 3; col++) { if (selects[0, col] != 0 && selects[0, col] == selects[1, col] && selects[0, col] == selects[2, col]) return selects[0, col]; } if (selects[0, 0] != 0 && selects[0, 0] == selects[1, 1] && selects[0, 0] == selects[2, 2]) return selects[0, 0]; if (selects[0, 2] != 0 && selects[0, 2] == selects[1, 1] && selects[0, 2] == selects[2, 0]) return selects[0, 2]; return 0; } } |
IsAllSelectedメソッドはすべてのマスがどちらかのプレイヤーによって選択されているかどうかを調べます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Program { static bool IsAllSelected(int[,] selects) { for (int row = 0; row < 3; row++) { for (int col = 0; col < 3; col++) { if (selects[row, col] == 0) return false; } } return true; } } |
両者がすべてのマスを選択したにもかかわらず勝負がつかない場合は点数が多いほうが勝ちです。GetWinnerメソッドは縦横斜めのいずれかで3つ並んでいないか、そうでない場合、すべてのマスが選択され終わっているのであれば点数を合計を計算してゲームの勝者を調べます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Program { static int GetWinner(int[,] selects) { int winner = GetWinner0(selects); if (winner != 0) return winner; long x = 0; long y = 0; if (IsAllSelected(selects)) { for (int row = 0; row < 3; row++) { for (int col = 0; col < 3; col++) { if (selects[row, col] == 1) x += Values[row, col]; if (selects[row, col] == 2) y += Values[row, col]; } } if (x > y) return 1; else return 2; } return 0; } } |
上記の説明では（1）C が終了状態ならば勝敗を判定して答えを返す、（2）C が終了状態でなければ C から 1 回の操作で遷移できる盤面 C′をすべて列挙して各 C′について f(C′) を計算する。計算した f(C′) の結果から f(C) の値を定めることができる。これによって勝者を知ることができるとありました。ここでは（1）と（2）の処理をSolveメソッドの再帰呼び出しで実現しています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
class Program { static int Solve(int[,] selects) { int winner = GetWinner(selects); if (winner != 0) return winner; // C（ = selects） の状態が終了状態でないなら // 1 回の操作で遷移できる盤面 C′をすべて列挙して各 C′について f(C′) を計算する // 次の手の候補（未着手のマス）を取得する List<int> rows = new List<int>(); List<int> cols = new List<int>(); for (int row = 0; row < 3; row++) { for (int col = 0; col < 3; col++) { if (selects[row, col] == 0) { rows.Add(row); cols.Add(col); } } } // 次の手番はどちらか？ // これは未選択のマスの数が偶数か奇数かでわかる（奇数なら 1、偶数なら 2 の手番） int x = rows.Count % 2 == 1 ? 1 : 2; int y = rows.Count % 2 == 0 ? 1 : 2; int count = 0; for (int i = 0; i < rows.Count; i++) { int row = rows[i]; int col = cols[i]; selects[row, col] = x; // 試しに着手してみる if (Solve(selects) == x) count++; selects[row, col] = 0; // 他の手も試さなければならないので終わったら着手を取り消す } if (count > 0) // x が勝つ方法がひとつでもあるなら x の勝ち return x; else // x が勝つ方法がひとつも存在しないなら x の負け return y; } } |
あとは入力されたデータを取得して上記のメソッドで処理をするだけです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
using System; using System.Collections.Generic; using System.Linq; class Program { static int[,] Values = new int[3, 3]; // マスに書かれたスコア static void Main() { for (int row = 0; row < 3; row++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (int col = 0; col < 3; col++) Values[row, col] = vs[col]; } int[,] selects = new int[3, 3]; // 0 は空白。1 または 2 は Takahashi または Aoki によって選択されている int winner = Solve(selects); if (winner == 1) Console.WriteLine("Takahashi"); else Console.WriteLine("Aoki"); } } |
解説を見たので AC になりました。
が、これで終わらせては面白くありません。これをネタにゲームをつくってしまいましょう♪ ただ、詳細は次回となります。
