這個遊戲是先手必勝還是後手必勝？

01-01

在3X3的方格里，兩人輪流不重複地填數字1-9。填的順序和位置隨意。
填滿後，先手算每一個橫排三個數相乘然後再把三個數相加為最終得分，後手算每一個豎列三個數相乘然後再把三個數相加為最終得分。誰的分數越高誰贏。

請問誰獲勝？最優方案是什麼？

編輯：編了一個簡單的H5，不明白的可以看看：Matrix Game

問題複雜度比較低，於是直接用了最土鱉的倒推窮舉思路。

去掉同型後，這遊戲共有10080個結局，其中雙方獲勝各5002局，另有76個和局。

由於第8步之後剩下的第9步沒有任何選擇，因此直接回到第8步，共有362880個（含重複）殘局。去掉同型之後181440個（去同型時採取對後手最有利的策略）。其中116417個殘局後手必勝、1368個後手可保和、63655個先手必勝。

第7步時共有1270080個殘局，去掉同型後141120個。其中107614個先手必勝，1001個先手可保和，32505個後手必勝。

第6步時共有846720個殘局，去掉同型後52920個。其中39760個後手必勝，475個可保和，12685個先手必勝。

第5步時共有264600個殘局，去掉同型後10584個。其中9350個先手必勝，70個可保和，1164個後手必勝。

第4步時共有42336個殘局，去掉同型後1260個。其中887個後手必勝，10個可保和，363個先手必勝。

第3步時共有3780個殘局（或者叫開局？），去掉同型後108個。其中104個先手必勝，4個後手必勝，不存在和局可能。後手必勝的4個開局如下：

000000019

000000029

000001002

000001003

如果先手玩家手滑走了1、2、3、9之中任何一個數字，後手玩家相應可以把12或13豎著連起來，或是19或29橫著連起來，這之後只要保持正確應對就能必勝。

如果先手玩家走了其它任何一個數字，不管後手玩家怎麼玩，先手玩家只要保持正確應對都是必勝。

換言之，這遊戲先手必勝。

——————————

雙方按照自己得分最高的策略行棋，第一步的分數表如下（和 @haoshu zhao 的結果相同）：

Data A B --------- ------ ------ 000000005 406 366 000000004 289 250 000000006 370 333 000000007 333 319 000000008 306 297 000000009 342 343 000000003 391 400 000000002 271 304 000000001 271 304

PS：我試了試把資料庫文件用7z壓縮一下，帶分值的全策略數據壓縮前是11MB，壓縮後1.5MB，看起來還算可以接受的樣子。

我算出來的是先下的贏。

下面是C#代碼。可以把代碼里的cache變數打出來看看簡單分析下。先下的最多比後下的多40分。先下的要想多40分，第一步要填5，在哪裡填都行。先下的要是只是想比後下的分多，第一步可以填4、5、6、7、8，填哪裡都行。填這些數可達到的最大分差依次為39、40、37、14、9。

using System; using System.Collections.Generic;

namespace Test { class Program { static int Score(int[] d, bool wantMax, int step, bool[] used, Dictionary&[] cache) { int k = 0; for (int i = 0; i &< d.Length; i++) k = k * 10 + d[i]; if (!cache[step].ContainsKey(k)) { if (step == d.Length) cache[step][k] = d[0] * d[1] * d[2] + d[3] * d[4] * d[5] + d[6] * d[7] * d[8] - d[0] * d[3] * d[6] - d[1] * d[4] * d[7] - d[2] * d[5] * d[8]; else { if (wantMax) cache[step][k] = int.MinValue; else cache[step][k] = int.MaxValue; for (int i = 0; i &< d.Length; i++) if (d[i] == 0) for (int j = 0; j &< used.Length; j++) if (!used[j]) { used[j] = true; d[i] = j + 1; if (wantMax) cache[step][k] = Math.Max(cache[step][k], Score(d, !wantMax, step + 1, used, cache)); else cache[step][k] = Math.Min(cache[step][k], Score(d, !wantMax, step + 1, used, cache)); used[j] = false; d[i] = 0; } } } return cache[step][k]; } static void Main(string[] args) { Dictionary&[] cache = new Dictionary&[10]; for (int i = 0; i &< cache.Length; i++) cache[i] = new Dictionary&(); int s = Score(new int[9], true, 0, new bool[9], cache); Console.Out.WriteLine(s); } } }

在 @haoshu zhao的答案的基礎上做了一點小小的優化，加上對當前狀態的最小表示法轉化。

因為顯然交換任意2行不會改變結果，交換任意2列也不會改變結果。

所以我們找出一種行和列的排列順序，使得3個行向量最小的在最前，3個列向量最小的在最前，這樣省去了大量的等價狀態的重複計算。和haoshu zhao給出的原始代碼相比，用時從~12s下降到~3s，內存峰值也只有25MB（相比之前512MB都不夠的情況……）。

跑過profile，這份代碼44%的時間花在了sort上，17%的時間花在了最小表示的函數里，9%的時間用於比較了，6%的時間才是計算的函數Score佔有的……

using System; using System.Collections.Generic;


namespace Test {

    class Vec :IComparable{

        public int[] d;

        public int id;

        public int CompareTo(object obj) {

            Vec b = (Vec)obj;

            for (int i = 0; i &< 3; i++) {
                if (d[i] != b.d[i]) {
                    return d[i] - b.d[i];
                }
            }
            return 0;
        }
    }
    class Program {
        static Vec[] rowVec = new Vec[3];
        static Vec[] colVec = new Vec[3];
        static int[] minimalRepresentation(int[] d) {
            for (int i = 0; i &< 3; i++) {
                rowVec[i].id = i;
                for (int j = 0; j &< 3; j++) {
                    rowVec[i].d[j] = d[i * 3 + j];
                }
                Array.Sort(rowVec[i].d);
            }
            Array.Sort(rowVec);

            
            for (int i = 0; i &< 3; i++) {
                colVec[i].id = i;
                for (int j = 0; j &< 3; j++) {
                    colVec[i].d[j] = d[j * 3 + i];
                }
                Array.Sort(colVec[i].d);
            }
            Array.Sort(colVec);

            int[] ans = new int[9];
            for (int i = 0; i &< 3; i++) {
                for (int j = 0; j &< 3; j++) {
                    ans[i * 3 + j] = d[rowVec[i].id * 3 + colVec[j].id];
                }
            }
            return ans;
        }
       static int Score(int[] d, bool wantMax, int step, bool[] used, Dictionary&[] cache) {

            int k = 0;

            for (int i = 0; i &< d.Length; i++)
                k = k * 10 + d[i];
            if (!cache[step].ContainsKey(k)) {
                if (step == d.Length)
                    cache[step][k] = d[0] * d[1] * d[2] + d[3] * d[4] * d[5] + d[6] * d[7] * d[8]
                        - d[0] * d[3] * d[6] - d[1] * d[4] * d[7] - d[2] * d[5] * d[8];
                else {
                    if (wantMax)
                        cache[step][k] = int.MinValue;
                    else
                        cache[step][k] = int.MaxValue;
                    for (int i = 0; i &< d.Length; i++)
                        if (d[i] == 0)
                            for (int j = 0; j &< used.Length; j++)
                                if (!used[j]) {
                                    used[j] = true;
                                    d[i] = j + 1;
                                    if (wantMax)
                                        cache[step][k] = Math.Max(cache[step][k], Score(minimalRepresentation(d), !wantMax, step + 1, used, cache));
                                    else
                                        cache[step][k] = Math.Min(cache[step][k], Score(minimalRepresentation(d), !wantMax, step + 1, used, cache));
                                    used[j] = false;
                                    d[i] = 0;
                                }
                }
            }
            return cache[step][k];
        }
        static void Main(string[] args) {
            Dictionary&[] cache = new Dictionary&[10];

            for (int i = 0; i &< cache.Length; i++)
                cache[i] = new Dictionary&();

for (int i = 0; i &< 3; i++) { rowVec[i] = new Vec(); rowVec[i].d = new int[3]; colVec[i] = new Vec(); colVec[i].d = new int[3]; } int s = Score(new int[9], true, 0, new bool[9], cache); Console.WriteLine(s); Console.WriteLine(""); for (int i = 0; i &< 10; i++) { Console.WriteLine(cache[i].Count); } } } }