Gomoku董事會代表

Question

我正在一個Gomoku遊戲，我需要一個高效的數據結構來存儲板狀態， 我想過把它存儲在一個二維數組中，但我相信有更多高效的方式。 謝謝

Answer 1

在時間效率方面，因爲我相信你會主要做索引查找，所以一個數組幾乎是最好的選擇 - 它支持持續時間的這種查找，具有低常數因子。

在空間效率方面：

每個正方形可以是空的，或由播放器填充。所以最多有3種可能性。爲了獲得最大的空間利用效率，我們可以將我們的整個電路板存儲爲3進製表示形式，但是，由於計算機工作在二進制模式，因此我們需要處理整個電路板以確定給定平方的值（因此只需索引查找就可以了需要時間與董事會的大小成正比 - 如果時間真的不是一個問題，你可以考慮這一點）。相反，我建議使用每平方2位，這將允許我們指出4種可能性中的一種（第4種未被使用）。

許多語言都有某種bitset的實現，允許你使用一系列位，這對於上述是完美的。

你也只想要一個位集（而不是2D），因爲在處理二維結構時通常會涉及一些內存開銷。從2D到1D的轉換很簡單 - 我們可以用x*height + y或y*width + x將2D索引轉換爲1D。儘管我會推薦首先確定你需要執行這種優化 - 我相信Gomoku主板通常很小，所以即使是笨重的表示也能完美工作（儘管一些AI技術可以製作很多副本，所以，如果你這樣做，最小的表示將是有意義的）。