終於有可以完賽的感覺了，本來預期介紹完位元運算，要接著介紹電腦對局競賽推坑大家參賽，然後就結束，現在還剩下三天要寫單人對局或多人對局好像都有點困難，有點苦惱要介紹什麼...
hackMD原稿

今天要來詳細分享一些使用bitboard的好處，可以如何快速操作盤面、優化程式碼，順便分享自己當年有多蠢，給大家一個錯誤示範。

蜜月橋牌Bitboard

研究所時期我因為程度太差，所以沒能發揮出bitboard的強大，當時我還是使用Array來表示手牌，因為實際上我們還是需要知道那張牌是什麼，二元序列只表達了牌的相對大小關係，所以只有在做Minimax跟查詢殘局庫時才會轉成二元序列做操作。
但實際上我們可以用一個64位元的無號整數來表達蜜月橋牌的手牌，按照蜜月橋牌程式叫牌與換牌階段的策略改進中的設計方式如下圖：

每13個bit表示一個花色，按照點數大小A~2做排列，依序為梅花、方塊、紅心、黑桃，剩下12個bit當作保留區，標記為1代表有這張牌、0代表沒這張牌，最後使用3個bitboard分別來記錄我方手牌、對方手牌、棄牌堆。

這邊為了方便我們需要先建立幾個遮罩，首先是花色的遮罩，方便我們快速的切割不同花色，再來是前n位的遮罩。

uint64_t flowerMasks[4]={0x0000000000001fff,
                         0x0000000003ffe000,
                         0x0000007ffc000000,
                         0x0000fff8000000000}
uint64_t masks[53] = {0x00...0, 0x00...1, 0x00...3, 0x00...7, ...}

一些基本操作請看前幾天的bitboard基本操作，這邊簡單示範一下遮罩的用法。

bitboard &= flowerMasks[n] // 這樣可以只留下其中一個花色的牌
bitboard ^= masks[n] // 將前n個位元0跟1交換

這樣要將bitboard轉換成二元序列只需要簡單兩行：
first為先手方的牌，second為後手方的牌
做OR運算後可以得到所有的牌，再使用_pext_u64將先手方的中的這些bit給取出來，就可以得到1代表先手方0代表後手方的二元序列了。

_pext_u64是BMI2指令集的內建函式，用來提取特定的位元。

cards = first | second;
board = _pext_u64(first, cards);

想要得到各花色張數也非常快，利用flowerMasks來快速切出四個花色，再利用_mm_popcnt_u64來數有幾個1，nums[]用來儲存各花色張數。

_mm_popcnt_u64是POPCNT指令集的內建函式，用來計算位元中1的個數。

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為更新手牌二元序列的函式

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為選出的那張牌

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為要取出的牌

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)出來結果是一樣的。

 board = 0110101100
-board = 1001010100
     p = board & -board
     p = 0000000100
board ^= p
 board = 0110101000

從一開始的for迴圈需要執行10次，現在這個while迴圈只需要跑5次，盤面更新也非常簡單快速，就一行搞定，其實到這我已經是跪著看了，然而還不只是這樣...
我們可以發現雖然這邊迴圈執行次數變少了，但是並沒有判斷連續1的剪枝，所以就繼續看下去！

優化第二版：

while (board) {
    auto p = board & -board; // uint32_t p = _blsi_u32(board);
    board &= board + p;
    // do thing...
}

這邊一樣直接給範例，一開始跟前面一樣，不一樣的是board &= board + p，這樣會非常神奇的把後面連續的1都給消掉。
如此這個while迴圈只需要執行3次！！！！！！
真的是跪到天花板了，到底是多神才能想到這種寫法，感恩吉神讚嘆吉神！

    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
• 蜜月橋牌程式開發及殘局庫的建立
• 蜜月橋牌程式叫牌與換牌階段的策略改進