Day27 Bitwise Operation
===
今天要來詳細分享一些使用bitboard的好處，可以如何快速操作盤面、優化程式碼，順便分享自己當年有多蠢，給大家一個錯誤示範。
## 蜜月橋牌Bitboard
研究所時期我因為程度太差，所以沒能發揮出bitboard的強大，當時我還是使用Array來表示手牌，因為實際上我們還是需要知道那張牌是什麼，二元序列只表達了牌的相對大小關係，所以只有在做Minimax跟查詢殘局庫時才會轉成二元序列做操作。
但實際上我們可以用一個**64位元的無號整數**來表達蜜月橋牌的手牌，按照[蜜月橋牌程式叫牌與換牌階段的策略改進](http://doi.org/10.6345/NTNU202201230)中的設計方式如下圖：
每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
再看一次前幾天提到的蜜月橋牌表示法：
因為我們使用了二元序列的資料結構，做Minimax要展開合法走步時，就是選擇1的部分展開，若是到下一層發生先後手轉換的情形，則把盤面與`11111...111`(幾張牌就幾個1，此時前面的遮罩就發揮作用了)做XOR運算，這樣就可以把0跟1交換，一樣選擇1的部分展開就可以了。
### 剪枝
然後這邊可以做一個最簡單的剪枝，以梅花為例，我們會發現盤面`000111`中不論我們選擇哪張牌，之後盤面都將變為`00011`，所以相鄰的1我們只需要做一次即可。
## 實作過程
這邊我們要做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)
Sign in with Wallet
Connect another wallet