什麼叫牡丹
演算法
,大概是
C語言
的永恆主題。
不管拿C語言去寫什麼,難的永遠不是C語言本身,而是相關的演算法。
在用C語言寫國際象棋遊戲的時候,一個問題就是:怎麼去判斷對方的
雙聯兵
?
要求這個判斷的
時間複雜度
必須是
O(1)
的。
即:只能有
if else語句
,不能有for / while迴圈,當然也不能有
遞迴
。
如下圖:
黑白雙方的兩個“
堡壘象
”各自控制1條大斜線,同時它們也被對方的雙聯兵阻擋。
象最怕雙聯兵,而且雙聯兵離象越近,物件的活動範圍壓縮的越厲害。
上圖的雙聯兵在F線和G線,如果在D線和E線的話,這兩個象就完全沒法活動了。
怎麼判斷這種情況?
最簡單的是用for迴圈去遍歷斜線上的8個格子。
int diff = x - y; // x, y是象的座標,與主斜線平行的情況下x - y的差相同
for (int i = x + 1; i < 8; i++) {
int j = i - diff;
if (j > 7) break;
if (board[i][j] == 兵) {
i ++;
j = i - diff;
if (i < 8 && j < 8 && board[i][j] == 兵) //第二個兵
printf(“雙聯兵\n”);
} // 第一個兵
}
但這個演算法是
O(N)
的,在圖中的情況下需要
遍歷5個格子
才可以發現象是頂著雙聯兵的。
程式碼的效率老是比
人眼
差,就是因為程式碼使用
靜態的資訊
,而人眼是使用
動態的資訊
。
上圖的那個局面,當然不是一下子就那樣的,而是一步步的走成那樣的。
每一步棋都是動態的資訊,所以人眼是可以瞬間發現頂著雙聯兵的。
在黑棋的
兵F6
之後,白棋的象就頂著雙聯兵了。
為了也讓程式碼可以處理動態的資訊,就需要
記錄每條斜線上的兵
的情況。
國際象棋裡共有30條斜線,其中15條與主斜線A1-H8平行,另外15條與反斜線A8-H1平行(4個角上的1格也被看作1條斜線)。
圖中藍線圈出來的部分,就是記錄斜線上的兵的情況的程式碼。
diagonals[2][2][16],第1個2表示黑白雙方,第2個2表示主反斜線,最後的16表示15條斜線。
為了讓記憶體大小是2個冪,餘著1個就餘著吧。
每當走兵的時候,就改變這個陣列的情況。
斜線上的兵的情況,
只需用x座標
就可以。
因為x - y或x + y是固定的,斜線上的x和y並不是獨立的變數,而是
線性相關
的。。
兵在哪個位置,就把哪個位置的掩碼設定為1。
實際上只需要
uint8_t
就夠了,國際象棋每條斜線上最多隻有8個格。
黑棋的兵F6導致的斜線狀態變化就是:
diagonals[BLACK][0][5 - 5 + 7] |= (1 << 5);
F6
在C語言裡的座標是
(5,5),C語言從0開始計數
,國象從1開始計數。
F6所在的主斜線的x - y是0。
因為x - y有可能出現負數,而
負數不能用作C陣列的索引
,所以這裡把
x - y + 7
作為陣列索引。
在只有8格的情況下陣列索引最大就是7,x - y + 7肯定是 >= 0
的
。
反斜線上x + y的和就可以作為陣列索引,直接表示反斜線的編號。
兵如果從F6繼續到達F5,那麼F6所在斜線的掩碼就要清除:
diagonals[BLACK][0][5 - 5 + 7] &= ~(1 << 5);
C語言設定二進位制位用
或運算|
,清除二進位制位用
與運算&
。
藍框裡的雙聯兵
象正頂著雙聯兵時,從象的角度看過去,斜線掩碼的二進位制必然是0000 1100。
如果總是把
象所在的位置
看作
低位
,把
兵所在的位置
看作
高位
,那麼高位有
連續2個1
的情況就是雙聯兵。
這個判斷是O(1)的,如果n0是斜線上的兵的掩碼:
n1 = n0 & (n0 - 1); //這樣就可以清除
最靠近
低位的那個1
p0 = n0 - n1; // 這就是第1個兵的掩碼1
雙聯兵的情況下,第2個兵必然緊鄰著第1個,所以:
if (
p0 && (n0 & (p0 << 1))
) 必然為
真(TRUE)
。
雙聯兵的二進位制碼如果去掉
所有是0的低位
,那麼就是
十六進位制的0x3
。
如果是
黑棋看主斜線
的話,首先看到的是二進位制碼的最高位的1。
黑棋視角的主斜線,二進位制碼0000 0110
黑棋從高位往低位看,G7象的x座標比C3兵的大,要透過去掉高位的1來判斷雙聯兵。
去掉最低位的1可以用n & (n - 1),但去掉最高位的1就比較麻煩,不知道它具體在哪一位。
我就乾脆做了個數組與它對應了,1100 0000對應的就是0000 0011,即0xc0對應著0x3。
C語言裡沒有反轉二進位制位的運算子,
intel手冊裡
也沒查到
反轉二進位制
的彙編碼。
這樣拿到掩碼之後可以直接查表,n0 = reverse[mask],然後再n0 & (n0 - 1),與白棋的情況一樣了。
反正這個掩碼的情況最多隻有256種,uint8_t reverse[256],提前把這個陣列填好就可以。
C語言裡,n - 1必然會導致n的
最低位的1被清零
,並且所有
低於這個1的位
被置1。
例如6個二進位制碼是110,6 - 1 = 5的
二進位制減法
必然會
從最低的1借位。
十進位制的高位1
被借1之後還
剩下9
,但
二進位制的高位1
被借1之後就只能
剩下0
了,
同時它的
所有低位
都會變成1。
如果
最低位本來就是1
的話n - 1不需要借位,只會把最低位清零。
5的二進位制碼是101,第2位的1被清零了,第1位的0變成了1。
3 - 1的情況下是不需要借位的,3的二進位制碼是11,3 - 1 = 2,2的二進位制碼是10,最低位的1被清零。
C語言的書可以看看
C Primer Plus
,二進位制碼的運算大概也就C語言還在玩。
因為C語言可以拿來寫需要
高效運算
的軟體,例如國際象棋的AI。
我寫這個程式用clock_gettime()檢視到
納秒
,gettimeofday()的
微秒
太大了(汗)。
想了解更多精彩內容,快來關注閒聊程式碼