主題

【公告】上次 19x19 五子棋程式優化處理

梗 | 2018-08-10 00:43:07 | 巴幣 6 | 人氣 286

　　幹我覺得我寫個程式又是出錯又是發覺優化問題實在很雷，真是不好意思啊哈哈。

　　上一篇貼文已經重新更新過已優化的結果了，現在是結果是我所想到的最真實直覺的模擬方式，實際上上一個的寫法硬要說也沒有錯，只是效率慢又多餘然後又難懂，破而已。

　　差別一樣能看懂就看吧哈哈，總之就是獲勝判斷上有所歧異。

我的獲勝判斷邏輯，在上一個的寫法是：

        boolWinner=false;//獲勝初始為否
        for(int i=0;i<19;i++){//搜尋全地圖
            for(intj=0;j<19;j++){
               if(map[i][j]==Player) Winner=winner(5,Player,i,j,map);
               if(Winner==true) break;//若有玩家獲勝，結束第一個搜圖迴圈
           }if(Winner==true) break;//若有玩家獲勝，結束第二個搜圖迴圈
        }
        if(Winner==true) {//若有玩家獲勝，輸出提示後結束第三個全遊戲迴圈
           cout<<Player<<" 贏了。\n";
              break;
        }

　　這個意思是：

搜尋全地圖(掃圖)，找到一個是當前棋子的座標。

判斷該座標隔壁的棋子是否連著一樣的棋子。

是的話就連子數+1，否的話就跳出函數。

跳出函式後，判斷連子數是否大等於設置數(5子棋就是5顆)。

如果大等於設置數，結束掃圖迴圈並輸出勝利提示而結束遊戲迴圈。

　　也就是說，這是一個『單項搜索』的方式，因為他會找到五子的兩個端點之一就可以結束搜尋了，也就是說勝利判斷搜尋式應該要這樣寫：

bool RowWin(int Long,char Player,int x,int y,charmap[19][19]){
    int Connect=1;//初始(因為初始本身就是一顆棋子，所以為1)
    for(int i=1;;i++){//1為起始(因為+0就是基底做標本身，所以從1開始)的加法無限迴圈
        if(map[y+i][x]==Player) Connect++;//如果Y座標+1(直線向上)是相同的旗子，初始+1
        else break;//若不是，則結束迴圈
    }
    if(Connect>=Long) return true;//如果最終結果大於等於連棋長度，則獲勝
    else return false;
}

　　看懂嗎？這是指搜尋其中一邊的『單側搜尋』寫法。

　　其實這就夠用了，因為它是從兩端開始跑起，如果不是從第一顆開始算就是從最後一顆，總之做到底就會滿足條件。

但是我的寫法是兩邊都有搜尋的『雙側搜尋』，也就是：

bool RowWin(int Long,char Player,int x,int y,charmap[19][19]){
    int Connect=1;//初始(因為初始本身就是一顆棋子，所以為1)
    for(int i=1;;i++){//1為起始(因為+0就是基底做標本身，所以從1開始)的加法無限迴圈
        if(map[y+i][x]==Player) Connect++;//如果Y座標+1(直線向上)是相同的旗子，初始+1
        else break;//若不是，則結束迴圈
    }
    for(int i=1;;i++){
        if(map[y-i][x]==Player) Connect++;//如果Y座標-1(直線向下)是相同的旗子，初始+1
        else break;
    }
    if(Connect>=Long) return true;//如果最終結果大於等於連棋長度，則獲勝
    else return false;
}

　　如果是用圖搜，『雙側搜尋』其實很雞肋，因為一定有一半是跑不到的，如果配合好的話讓所有搜尋從靠近左上開始做(因為圖搜的起點[0][0]就是左上角，會比較靠近)，甚至連增加效率都做不到，也就是章魚茶提及的：

章魚茶：
還有五子棋連線的判定明明就可以省一半的時間，往上往下選一個找就夠了啦O3O

　　哼哼，太天真了。

　　之所以會這麼寫，就是因為如果有人要把它改成點擊的圖形顯示模組，從最後一顆點擊位置開始算起的話，那麼就不能確保它該是五子內的第幾顆，所以就上下都要找一輪才行，也就是『雙側搜尋』……

　　呃……

　　　　那是不是圖形介面……

　　　　　　　　　　又有什麼關係……= =

梗：

然後我實際上我一開始也是只寫一個，因為是從右上往左下，所以我也只保留靠右或靠上的那一個這樣效率比較好

但是假設後來有人要把它改成圖形介面，就要從『最後一顆』點擊棋子開始看效率才會高，如果這個樣子的話那麼這個邏輯就會直接變成一個bug，然後我要發揮我的綜藝咖精神了各位觀眾

對耶！就算不是圖形介面我也可以這麼辦啊！幹幹幹等等就這樣改！

章魚茶：
梗大，你突破盲腸了OuOb

　　幹，爆菊，不對是爆擊。

所以接著就被我改成了：

       if(winner(5,Player,XSwitch,YSwitch,map)==true) {//剛才所下的棋子為基準(最後一子)，作八方勝利掃查判斷
           cout<<Player<<" 獲勝。\n";//若有玩家獲勝，輸出提示後結束第三個全遊戲迴圈
           break;
        }

　　這個意思是：