Day29 從象棋比賽作弊事件探討資料傳輸與資料結構2
===
今天要繼續來認真的學術探討，雖然我邊寫邊笑，以後下棋不能說單手讓你了，要說我用括約肌讓你。

## 研究方法與步驟
研究了ptt上眾多**肛之編碼術師**的文章，激發出我的~~便意~~靈感，要**集各位肛之編碼術師的優點於一身，創造出能夠保護肛之棋士的最強編碼！**

### 固定長度編碼
ptt上大部分的編碼都是以固定長度編碼為主，這樣方便辨識，簡單易懂。
以Chinese Chess為例，包含空格有7種共13字元。
我們用3個bit來對每個字元做編碼。

就算傳來連續的訊息，因為是固定長度的編碼，我們也能夠輕鬆的分辨出每個字元。
`000001010011100101100110000001100101101`
`000 001 010 011 100 101 100 110 000 001 100 101 101`

但是缺點也顯而易見，如果每個字元出現的頻率差距很大，但都還是得使用相同長度的編碼，造成編碼效率較低。

回頭看中式記譜法也會有空間浪費的問題，比如表示座標需要有4個bit來表示11種可能，但不是所有的棋種都能有這麼多的走步，象棋中走步最多的就是車跟炮了，可是得涵蓋所有棋種的走步，這就造成了空間的浪費。
**那能不能根據不同棋種給出不同長度的編碼呢？**

### Huffman Code
為了要能夠有變動長度的編碼，又不能像摩斯密碼那樣會產生混淆的情況，因為摩斯密碼用來隔開字元的方式在二進位的環境中並不好用。
這時我就想起了修演算法課學過的Huffman Code，~~不知道老師看到我把Huffman Code用在這種地方會是什麼想法XDD~~，這也算是一種學以致用吧？！

**Huffman Code就是一個可以壓縮狀態又不失真的編碼方式**，他會根據字元出現的頻率對其編碼，出現頻率高的字元就盡可能的編碼短一點，不常使用的字元當然就可以用較長的編碼。
看一下Huffman Tree會更清楚，他是從頻率出現最少的節點開始由下往上合併。

圖片產生自[Huffman Tree 生成網站](https://www.csfieldguide.org.nz/en/interactives/huffman-tree/)

最後得到的編碼如下：

使用Huffman Code就不會有混淆的問題，只要查表一樣能輕易辨識。
`10111011101111000100100101110000101`

`101 110 1110 1111 00 01 00 100 101 1110 00 01 01`

因為Huffman Code不會有重複的前綴碼，比如有1111的編碼就不會有111，這種會造成混淆的情況。
前面的固定長度編碼需要 3 x 13 = 39碼，而使用了Huffman Code只需要35碼，如果字串更長且字元出現頻率更極端一點，壓縮效果會更明顯。

**同理我們可以將象棋中移動頻率最高的棋種較少的編碼，這樣整盤棋下來平均的震動次數將會大幅減少。**

正當我要去爬象棋棋譜網站想要來統計各棋種的頻率時，看到了方法4的走步轉換法，正是這位網友給了我新靈感，最後想出了一個新編碼，**有方法1中式記譜法好記的特性，又使用了方法2中的相對位置思考、方法3的變動長度編碼、方法4的走步轉換法，集各位肛之編碼術師的優點於一身，創造出能夠保護肛之棋士的最強編碼！。**

## Chinese Chess Straight Protocol
簡稱**CCSP**：針對人類設計的象棋通訊協定！
**專門為肛之棋士們設計的一個簡短且好記的象棋走步通訊協定。**
由於編碼方式為 23456，所以用 Straight(撲克中順子的意思)命名。

### 編碼方式
* 長震為1、短震為0
* 將、士：3碼
* 馬：4碼
* 象、卒：5碼
* 車、炮：6碼
* 車、炮第17種走步：2碼

### 1. 將、士：
`將`為`0`、`士`為`1`
第1個bit表示棋子
後2個bit表示走步
總共3個bit

依照順時針的順序往下走，依序為：
`00`：往前(`士`為往右上)
`01`：往右(右下)
`10`：往下(左下)
`11`：往左(左上)

例：`001` -> `0` `01` -> `將`的第`2`種走步(往右)

下圖為兩隻士的所有位置對應情況，因為兩個士沒有辦法同時往同個方向移動，所以只要知道走步就能確定是哪一隻士。

### 2. 馬：
第一個`馬`為`0`、第二個`馬`為`1`
區分相同棋種方式為從右至左，先遇到的則定為第一個，如果在同一條線上則順序為從上至下，以下皆使用這種方式辨認棋子。

第1個bit表示棋子
後3個bit表示走步
總共4個bit

下圖為走步編碼方式，一樣是順時針的方式相當好記：

例：`1011` -> `1` `011` -> 第二個`馬`的第`4`種走步(往5點鐘方向走)

### 3. 象、卒：
`象`：`000` `001`
`卒`依序為：`010` `011` `100` `101` `110`

前3個bit表示棋子
後2個bit表示走步
總共5個bit

走步跟將、士將同
`00`：往前(`象`為往右上)
`01`：往右(右下)
`10`：往下(左下)
`11`：往左(左上)

例：`01101` -> `011` `01` -> 第二個`卒`的第`2`種走步(往右)

### 4. 車、炮：
車：`00` `01`
炮：`10` `11`

前2個bit表示棋子
後4個bit表示走步
總共6個bit

根據車、炮在棋盤上的位置能走的格數也不一樣，所以只表達往前跟往右，超出棋盤的部分就從棋盤另一端開始繼續數。

如下圖車往右7的話，其實就是往左2格：

`0000` ~ `0111` 代表往右1格到8格
`1000` ~ `1111` 代表往前1格到8格

因為車、炮共有17種走步(直9橫8)，為了多出的一種走步就要增加一個bit實在是有點太浪費了，所以就將第17種走步列為特殊情況。
特例情況：2個bit，直接表示該棋子的第17種走步，這邊將第17種走步設為往前9格。

例：`000001` -> `00` `0001` -> 第一個`車`的第`2`種走步(往右2)
`10` -> 第一個`炮`的第`17`種走步(往前9)

當只有收到兩次震動時，就是特殊情況，2碼就代表棋子，因為走步已經固定了。

這樣**震動次數最多就為6次**，而且非常的好記，只要記得各棋種是幾碼，回想一下他的棋子數量與走步方式就知道怎麼去切割，**歡迎各位肛之棋士採用此編碼**，**能有效保護您的括約肌**。

我寫了一個簡易的轉換程式範例[CCSP](https://github.com/Marsgoat/Chinese-Chess-Straight-Protocol)，如果覺得有趣的話麻煩幫我的「賽」project按個星吧！

## 實驗結果
接下來就是眾所期待的實驗階段了！！！！！！！
但是非常可惜的找不到志願者，所以目前尚未有實驗結果，也非常歡迎大家報名當志願者。
當然我們不是用什麼「肛珠」，我找到了一個更好的方式，那就是震動鞋墊，一雙不到500台幣，如下圖：


圖片來源為蝦皮賣場，但那個賣場下架了...我找不到原始圖源了...

現在很多比賽都會有安檢，萬一那個探測棒揮到你屁股時開始叫，那得多尷尬，藏在腳底就非常難被發現，並且可以一腳接收訊息一腳發送訊息，發送訊息時踩腳的動作也比使用括約肌自然多了。

**祭品文：**
**只要這篇超過50個讚或是我的[「賽」project](https://github.com/Marsgoat/Chinese-Chess-Straight-Protocol)超過50顆星，我就請我在當youtuber的好友直接拍成影片上傳與大家分享，他說超過100讚或100顆星他會認真考慮塞屁股。**

## 免責聲明
本通訊協定（以下簡稱“協定”）僅供學術研究和娛樂用途。
本協定的創建者和貢獻者不對使用本協定所引發的任何直接或間接後果負責。
本協定不鼓勵、支持或容忍任何形式的不誠實行為，包括但不限於作弊或欺詐。
使用本協定的個人或團體應自行承擔相應的法律和道德責任。

## Reference
* [Huffman Code](https://en.wikipedia.org/wiki/Huffman_coding)
* [方法1 中式記譜法](https://www.ptt.cc/bbs/C_Chat/M.1703567961.A.0A4.html)
* [方法2 5種震法](https://www.ptt.cc/bbs/C_Chat/M.1703588431.A.29F.html)
* [方法4 走步轉換法](https://www.ptt.cc/bbs/C_Chat/M.1703595379.A.FE9.html)
* [編碼大師](https://www.ptt.cc/bbs/C_Chat/M.1703607941.A.2C3.html)
* [10震法](https://www.ptt.cc/bbs/C_Chat/M.1703566544.A.866.html)

## 其他電腦對局通訊方式
寫完才發現漏掉了一個很重要的事情，如果大家想要參加電腦對局競賽要特別注意，各遊戲的對戰方式不同，有些熱門的遊戲都有對戰平台，雙方可以直接連線對戰，這樣會快很多，不用一手一手在那邊輸入，在寫程式時就要記得按照這些平台的通訊協定規範來寫。
* **GTP**：[Go Text Protocol](https://www.lysator.liu.se/~gunnar/gtp/)，圍棋通訊協定。
* **DCTP**：[Dark Chess Text Protocol](https://web.ntpu.edu.tw/~jcchen/clients/ver5/Readme.pdf)，暗棋通訊協定。