Day27 Bitwise Operation === 今天要來詳細分享一些使用bitboard的好處，可以如何快速操作盤面、優化程式碼，順便分享自己當年有多蠢，給大家一個錯誤示範。 ## 蜜月橋牌Bitboard 研究所時期我因為程度太差，所以沒能發揮出bitboard的強大，當時我還是使用Array來表示手牌，因為實際上我們還是需要知道那張牌是什麼，二元序列只表達了牌的相對大小關係，所以只有在做Minimax跟查詢殘局庫時才會轉成二元序列做操作。 但實際上我們可以用一個**64位元的無號整數**來表達蜜月橋牌的手牌，按照[蜜月橋牌程式叫牌與換牌階段的策略改進](http://doi.org/10.6345/NTNU202201230)中的設計方式如下圖： ![](https://hackmd.io/_uploads/HyU28vIJke.png) 每13個bit表示一個花色，按照點數大小A~2做排列，依序為梅花、方塊、紅心、黑桃，剩下12個bit當作保留區，**標記為1代表有這張牌、0代表沒這張牌**，最後使用3個bitboard分別來記錄我方手牌、對方手牌、棄牌堆。 這邊為了方便我們需要先建立幾個遮罩，首先是花色的遮罩，方便我們快速的切割不同花色，再來是前n位的遮罩。 ```cpp uint64_t flowerMasks[4]={0x0000000000001fff, 0x0000000003ffe000, 0x0000007ffc000000, 0x0000fff8000000000} uint64_t masks[53] = {0x00...0, 0x00...1, 0x00...3, 0x00...7, ...} ``` 一些基本操作請看前幾天的bitboard基本操作，這邊簡單示範一下遮罩的用法。 ```cpp bitboard &= flowerMasks[n] // 這樣可以只留下其中一個花色的牌 bitboard ^= masks[n] // 將前n個位元0跟1交換 ``` 這樣要將bitboard轉換成二元序列只需要簡單兩行： `first`為先手方的牌，`second`為後手方的牌 做OR運算後可以得到所有的牌，再使用`_pext_u64`將先手方的中的這些bit給取出來，就可以得到1代表先手方0代表後手方的二元序列了。 `_pext_u64`是BMI2指令集的內建函式，用來提取特定的位元。 ```cpp cards = first | second; board = _pext_u64(first, cards); ``` 想要得到各花色張數也非常快，利用`flowerMasks`來快速切出四個花色，再利用`_mm_popcnt_u64`來數有幾個1，`nums[]`用來儲存各花色張數。 `_mm_popcnt_u64`是POPCNT指令集的內建函式，用來計算位元中1的個數。 ```cpp for(int i = 0; i < 4; i++){ uint64_t flower = cards&flowerMasks[i]; nums[i] = _mm_popcnt_u64(flower); } ``` 因為這邊使用了大量的**Bitwise Operation(位元運算)**，所以速度上會比使用Array的資料結構快得非常多。 接下來我們來看一下當年懵懂無知的我，是怎麼寫出讓學長崩潰的爛code。 ## 蜜月橋牌的Minimax 再看一次前幾天提到的蜜月橋牌表示法： ![](https://i.imgur.com/3pW5Tdn.png) 因為我們使用了二元序列的資料結構，做Minimax要展開合法走步時，就是選擇1的部分展開，若是到下一層發生先後手轉換的情形，則把盤面與`11111...111`(幾張牌就幾個1，此時前面的遮罩就發揮作用了)做XOR運算，這樣就可以把0跟1交換，一樣選擇1的部分展開就可以了。 ![](https://i.imgur.com/55KxEbC.png) ### 剪枝 然後這邊可以做一個最簡單的剪枝，以梅花為例，我們會發現盤面`000111`中不論我們選擇哪張牌，之後盤面都將變為`00011`，所以相鄰的1我們只需要做一次即可。 ![](https://i.imgur.com/aixdhoL.png) ## 實作過程 這邊我們要做Minimax就是要展開所有的合法走步，也就是要先取出二元序列中所有的1的部分，有連續1的部分就只取一個。 我的想法很簡單，就是一個for迴圈掃過所有的牌，每次左移一個bit，找到1的部分，然後判斷是否有連續的1，非常直觀，寫起來如下。 ### 直覺寫法 `cards`為雙方剩餘手牌總張數 `board`為雙方手牌的二元序列 `newboard`為更新後雙方手牌的二元序列 `reorder`為更新手牌二元序列的函式 ```cpp= for (int i = 0; i < cards; i++) { if ((board & (1 << i)) == 1 && (board & (1 << (i + 1))) != 1){ unsigned int newboard = reorder(board, i, cards); //do thing... } } ``` 判斷連續的1我也是用最簡單的想法，直接再往左移一個bit，如果不是1我才取，有1的話代表有連續，則再繼續左移，這樣掃完我就可以知道我要取的1在哪些位置，然後取出來再更新盤面。 更新盤面我這邊是直接重新排手牌，要把出掉的牌給移掉。 `choose`為選出的那張牌 ```cpp= unsigned int reorder(unsigned int board, int choose, int cards){ unsigned int newboard = 0; for (int i = cards - 1; i >= 0; i--){ if (i != choose){ newboard <<= 1; if ((board & (1 << i)) == 1){ newboard = newboard + 1; } } } return newboard; } ``` 這邊忠實還原當時的我有多蠢，給大家當作錯誤示範，實在是有很大的進步空間，當時彥吉學長看了看我寫的code，搖了搖頭，**露出了關愛智障的表情**，然後直接現場改寫。 ### 優化第一版： `p`為要取出的牌 ```cpp= while (board) { auto p = board & -board; // uint32_t p = _blsi_u32(board); board ^= p; // board = _blsr_u32(board); // do thing... } ``` 這邊直接用個範例，假設雙方都還各剩5張牌的情況，`board = 0110110100`，與`-board`做AND運算就可以取得最右邊的1，最後把取出來的牌與原本的手牌二元序列做XOR運算就可以更新手牌資訊了。 `board & -board`可以直接寫成`_blsi_u32(board)`、`board ^ p`也可以寫成`_blsr_u32(board)`出來結果是一樣的。 ```cpp board = 0110101100 -board = 1001010100 p = board & -board p = 0000000100 board ^= p board = 0110101000 ``` **從一開始的for迴圈需要執行10次，現在這個while迴圈只需要跑5次**，盤面更新也非常簡單快速，就一行搞定，其實到這我已經是跪著看了，然而還不只是這樣... 我們可以發現雖然這邊迴圈執行次數變少了，但是並沒有判斷連續1的剪枝，所以就繼續看下去！ ### 優化第二版： ```cpp= while (board) { auto p = board & -board; // uint32_t p = _blsi_u32(board); board &= board + p; // do thing... } ``` 這邊一樣直接給範例，一開始跟前面一樣，不一樣的是`board &= board + p`，這樣會非常神奇的把後面連續的1都給消掉。 如此這個while迴圈**只需要執行3次！！！！！！** 真的是跪到天花板了，到底是多神才能想到這種寫法，感恩吉神讚嘆吉神！ ```cpp board = 0110101100 p = 0000000100 board + p = 0110110000 board &= board + p = 0110100000 ``` ## 結論 利用bitboard加上位元運算可以讓程式效率大幅提升，除了好的演算法，還需要搭配好的資料結構，甚至實作中都是滿滿的細節，只能說電腦對局水真的太深了。 雖然說寫程式不難，但要寫好程式真的好難。 `_blsi_u32`跟`_blsr_u32`是x86的內建函式(BMI1指令集)，包含上面的`_pext_u64`跟`_mm_popcnt_u64`，我在學長介紹之前是從來沒看過也沒用過，難怪學長們寫程式還會考慮到什麼cpu指令集，身為管院跨考資工所的半路出家仔，我連寫最基本的for迴圈都會被學長嫌效率太差，真的是被震撼教育，後來是花了大量的時間學習才勉強能跟上大家。 ## Reference * [Design and implementation aspects of a Surakarta program](https://www.researchgate.net/publication/329160216_Design_and_implementation_aspects_of_a_Surakarta_program) * [蜜月橋牌程式開發及殘局庫的建立](http://doi.org/10.6345/NTNU202001544) * [蜜月橋牌程式叫牌與換牌階段的策略改進](http://doi.org/10.6345/NTNU202201230)