---
# System prepended metadata

title: 10/8 Arcade也能學演算法Ouo!? 演算法遊戲(4)
tags: [2022 iThome 鐵人賽]

---

---
tags: 2022 iThome 鐵人賽 
title: 10/8 Arcade也能學演算法Ouo!? 演算法遊戲(4)
AUTHOR: 鍾佳龍
---
# Arcade再進化
## Arcade也能學演算法Ouo!? 演算法遊戲!(4)
### **第四篇：棋類遊戲-黑白棋演算法篇**

> ### 大綱
> * 遊戲內容
> * 關於黑白棋的規則
> * 確認可以連線
> * 連線後?
> * 結束了?
> * 範例程式

## 遊戲內容
![](https://i.imgur.com/KIlG9uh.gif)
(此畫面是由空白網頁執行javascript，可以根據需求改造成nodejs讓其可以在本機執行)
輸入位置後下棋
然後更新棋盤

## 關於黑白棋的規則
黑白棋下棋的規則
1. 影響棋子的方式是 由兩個同色的棋子包夾，則中間的棋子被同化。
2. 每次下棋必須影響對方至少一顆旗子
![](https://i.imgur.com/F6xBX0f.png)
3. 如果你無法下棋的話，你該局就pass
4. 如果雙方都無法下棋則結束遊戲，場上棋多者勝

## 如何確認連線
思路:
> 1. 往八個方向搜尋，如果搜尋到對手的棋再搜到自己的棋則為可行的方位
> 2. 為了節省時間，我們增加條件式:如果往外找的時候發現此位置不是對手的棋
> (自己的棋/沒有棋)那這個方位就不成立，所以直接跳出迴圈

想好之後就上程式碼!!
```javascript    
function check_put_legitimate(X, Y, turn){
```
我預設需要的參數有 現在的位置(`X,Y`)跟現在是誰的回合(`turn`)
```javascript    
function check_put_legitimate(X, Y, turn){
    let check = turn == "O" ? "X" : "O";
    let legitimate = false;
```
`let check = turn == "O" ? "X" : "O";`
我將白色用O黑色用X標記
所以我如果`turn`是`O` `check`就要是`X` 反之亦然
`legitimate` 是之後要回傳的值代表是否成立
接下來就是搜尋的部分
還記的我們上一次八個方位洋洋灑灑寫了快80行嗎
我們今天就要來優化搜尋的部分
大家可以發現我們搜尋的部分就很簡單
基本上就是某個值再加減 然後判斷
所以其實真正再變的是要不要加減
通過這個想法我們可以來做一個列表來裝這些東西
```javascript
let search_mode = [
    [0, 1], [1, 0], [0, -1], [-1, 0], // down, right, up, left
    [1, 1], [1, -1], [-1, 1], [-1, -1] // down-right, down-left, up-right, up-left
]
```
我們建立後列表後在裡面再創一個列表放置`Y`跟`X`要加減的值
例如 如果往上找`X--` `Y`不用動 所以`[0, -1]`
剩下就以此類推
有了搜尋模式後 我們只要依序餵給迴圈就好
```javascript
    for(let i = 0; i < search_mode.length; i++){ // mode
        let x = X + search_mode[i][0];
        let y = Y + search_mode[i][1];
        ...
        while (x>=0 && x<=7 && y>=0 && y<=7){
            if(Data[y][x] == check){
                ...
                x += search_mode[i][0];
                y += search_mode[i][1];
            ...
        }
```
這樣就完成簡單的縮減了
然後是判斷式
我們前面提到如果不成立合法方位的話就跳出迴圈
可是如果找玩了的話也要跳出迴圈阿
我怎麼知道我有沒有成功找到呢
所以我先宣告一個變數`check_legitimate`還有`check_count`紀錄中間連線的次數方便之後要判斷用
```javascript
    for(let i = 0; i < search_mode.length; i++){
        let x = X + search_mode[i][0];
        let y = Y + search_mode[i][1];
        let check_count = 0;
        let check_legitimate = false;
        ...
```
接下來就是搜尋了
```javascript
        ...
        while (x>=0 && x<=7 && y>=0 && y<=7){
            if(Data[y][x] == check){
                check_count++;
                x += search_mode[i][0];
                y += search_mode[i][1];
            }else if(Data[y][x] == turn && check_count > 0){
                check_legitimate = true;
                break;
            }else{
                break;
            }
        }
        ...
```
如果找到對方的棋子就繼續找，並且計數加一
阿如果找到對方的棋子還有一個可能
那就是找到自己的
那找到自己的話還要看中間有沒有對手的棋子
所以我們要看所以我們要看`check_count`有沒有大於0
如果大於0也就是說有夾棋子然後找到自己的棋子
所以這個方向是成立的
那麼我就紀錄方位的代碼跟我夾了幾個棋子方便之後利用的時候不用再跑一次判斷
最後 如果都沒有成立 代表這個方向是不合法的 就直接跳離迴圈
最後判斷式會長這樣
```javascript
    for(let i = 0; i < search_mode.length; i++){
        let x = X + search_mode[i][0];
        let y = Y + search_mode[i][1];
        let check_count = 0;
        let check_legitimate = false;
        while (x>=0 && x<=7 && y>=0 && y<=7){
            if(Data[y][x] == check){
                check_count++;
                x += search_mode[i][0];
                y += search_mode[i][1];
            }else if(Data[y][x] == turn && check_count > 0){
                check_legitimate = true;
                break;
            }else{
                break;
            }
        }
```
最後做個結合
判斷是不是合法位置的演算法就好了
```javascript
function check_put_legitimate(X, Y, turn){
    if (X < 0 || X > 7 || Y < 0 || Y > 7 || Data[Y][X] != " "){
        return [false, [-2], [0]];
    }
    // setting
    let check = turn == "O" ? "X" : "O";
    let legitimate = false;
    let mode = [-1];
    let count = [0];
    // check
    for(let i = 0; i < search_mode.length; i++){
        let x = X + search_mode[i][0];
        let y = Y + search_mode[i][1];
        let check_count = 0;
        let check_legitimate = false;
        while (x>=0 && x<=7 && y>=0 && y<=7){
            if(Data[y][x] == check){
                check_count++;
                x += search_mode[i][0];
                y += search_mode[i][1];
            }else if(Data[y][x] == turn && check_count > 0){
                check_legitimate = true;
                break;
            }else{
                break;
            }
        }
        if(check_legitimate){
            legitimate = true;
            mode.push(i);
            count.push(check_count);
        }
    }

    return [legitimate, mode, count];
}
```

## 下棋
確認他的位置是合法之後我們就要來下棋拉
首先我用一個二微陣列儲存資料
```javascript
let Data = [ // white;O black;X
    // 0    1    2    3    4    5    6    7
    [" ", " ", " ", " ", " ", " ", " ", " "],// 0
    [" ", " ", " ", " ", " ", " ", " ", " "],// 1
    [" ", " ", " ", " ", " ", " ", " ", " "],// 2
    [" ", " ", " ", "O", "X", " ", " ", " "],// 3
    [" ", " ", " ", "X", "O", " ", " ", " "],// 4
    [" ", " ", " ", " ", " ", " ", " ", " "],// 5
    [" ", " ", " ", " ", " ", " ", " ", " "],// 6
    [" ", " ", " ", " ", " ", " ", " ", " "] // 7
]
```
接下來是寫入檔案
```javascript
function play(X, Y, turn, mode, count){
}
```
還記得我們上次回傳值是什麼嗎
是不是[是否合法, [方向], [夾心個數]]
是否合法的部份我們留給判斷式 如果成立就執行我們這個程式
也就是下棋
```javascript
function play(X, Y, turn, mode, count){
    for(let i = 1; i < mode.length; i++){
        let x = X + search_mode[mode[i]][0];
        let y = Y + search_mode[mode[i]][1];
}
```
依序從記錄的方向提出來做翻棋
並且設定`x`,`y`為現在座標
然後就把對手的棋改成我方的棋
```javascript
function play(X, Y, turn, mode, count){
    for(let i = 1; i < mode.length; i++){
        let x = X + search_mode[mode[i]][0];
        let y = Y + search_mode[mode[i]][1];
        for(let j = 0; j < count[i]+1; j++){
            Data[y][x] = turn;
            x += search_mode[mode[i]][0];
            y += search_mode[mode[i]][1];
        }
    }
}
```
這樣下棋的部分就解決了

## 結束了?
最後一個難點是判斷結束以及pass
還記得我們前面提到黑白棋的規則嗎
> 3. 如果你無法下棋的話，你該局就pass
> 4. 如果雙方都無法下棋則結束遊戲，場上棋多者勝

所以首先先來做判斷單人的
兩人都不能下的話就只是執行兩次而已

那我們的想法也很簡單喔
什麼叫做都不能下
是不是就是所有位置都是不合法位置
ㄟ! 判斷合不合法
不就是剛剛寫的嗎
所以我們就抓每一格沒有旗子的格子來判斷就行了
(這不是最省時的方法，最省時的方法應是找出邊緣才拿去判斷
可是我們棋盤最多就`8*8-4`格而已，所以意義不大。暴力破解即可)
```javascript
function check_end(turn){
    let end = true;
    for(let i = 0; i < 8; i++){
        for(let j = 0; j < 8; j++){
            if(Data[i][j] == " "){
                if(check_put_legitimate(j, i, turn)[0]){
                    end = false;
                }
            }
        }
    }
    return end;
}
```
最後在輸出結果就好

## 誰贏了
當兩人都不能下的時候就結束了 
棋子最多的獲勝
所以就是數棋子拉
這邊也是很簡單
就每個都看一下 真●計數
```javascript
function check_win(){
    let count = [0, 0];
    for(let i = 0; i < 8; i++){
        for(let j = 0; j < 8; j++){
            if(Data[i][j] == "O"){
                count[0]++;
            }else if(Data[i][j] == "X"){
                count[1]++;
            }
        }
    }
    return count[0] > count[1] ? "white" : "black";
}
```

恭喜到這邊你已經會做黑白棋了
那下面就用今天所學的做成一個網頁跑的遊戲吧

---
## 範例程式
```javascript=
/*
* AUTHOR rlongdragon
* DATE   2022-10-08
* VISON  1.2
* 
* this probject used copilot
*/



let Data = [ // white;O black;X
    // 0    1    2    3    4    5    6    7
    [" ", " ", " ", " ", " ", " ", " ", " "],// 0
    [" ", " ", " ", " ", " ", " ", " ", " "],// 1
    [" ", " ", " ", " ", " ", " ", " ", " "],// 2
    [" ", " ", " ", "O", "X", " ", " ", " "],// 3
    [" ", " ", " ", "X", "O", " ", " ", " "],// 4
    [" ", " ", " ", " ", " ", " ", " ", " "],// 5
    [" ", " ", " ", " ", " ", " ", " ", " "],// 6
    [" ", " ", " ", " ", " ", " ", " ", " "] // 7
]
let search_mode = [
    [0, 1], [1, 0], [0, -1], [-1, 0], // down, right, up, left
    [1, 1], [1, -1], [-1, 1], [-1, -1] // down-right, down-left, up-right, up-left
]

// function
function check_put_legitimate(X, Y, turn){
    if (X < 0 || X > 7 || Y < 0 || Y > 7 || Data[Y][X] != " "){
        return [false, [-2], [0]];
    }
    // setting
    let check = turn == "O" ? "X" : "O";
    let legitimate = false;
    let mode = [-1];
    let count = [0];
    // check
    for(let i = 0; i < search_mode.length; i++){
        let x = X + search_mode[i][0];
        let y = Y + search_mode[i][1];
        let check_count = 0;
        let check_legitimate = false;
        while (x>=0 && x<=7 && y>=0 && y<=7){
            if(Data[y][x] == check){
                check_count++;
                x += search_mode[i][0];
                y += search_mode[i][1];
            }else if(Data[y][x] == turn && check_count > 0){
                check_legitimate = true;
                break;
            }else{
                break;
            }
        }
        if(check_legitimate){
            legitimate = true;
            mode.push(i);
            count.push(check_count);
        }
    }

    return [legitimate, mode, count];
}

function play(X, Y, turn, mode, count){
    Data[Y][X] = turn;
    for(let i = 1; i < mode.length; i++){
        let x = X + search_mode[mode[i]][0];
        let y = Y + search_mode[mode[i]][1];
        for(let j = 0; j < count[i]; j++){
            Data[y][x] = turn;
            x += search_mode[mode[i]][0];
            y += search_mode[mode[i]][1];
        }
    }
}

function print(){
    let str = "  0 1 2 3 4 5 6 7";
    for(let i = 0; i < 8; i++){
        str += "\n" + i + " ";
        for(let j = 0; j < 8; j++){
            str += Data[i][j] + "|";
        }
    }
    console.log(str);
}

function check_end(turn){
    let end = true;
    for(let i = 0; i < 8; i++){
        for(let j = 0; j < 8; j++){
            if(Data[i][j] == " "){
                if(check_put_legitimate(j, i, turn)[0]){
                    end = false;
                }
            }
        }
    }
    return end;
}

function check_win(){
    let count = [0, 0];
    for(let i = 0; i < 8; i++){
        for(let j = 0; j < 8; j++){
            if(Data[i][j] == "O"){
                count[0]++;
            }else if(Data[i][j] == "X"){
                count[1]++;
            }
        }
    }
    return count[0] > count[1] ? "white" : "black";
}

// main
print();
let turn = "O";
let count = 0;
while(true){
    let put = false;
    // wait input
    let input = prompt(`is ${turn == "O" ? "white" : "black"} turn input X Y`);
    let X = parseInt(input.split(" ")[0]);
    let Y = parseInt(input.split(" ")[1]);

    // check put
    let check = check_put_legitimate(X, Y, turn);
    if(check[0]){
        put = true;
        play(X, Y, turn, check[1], check[2]);
    }
    if(put){
        print();
        turn = turn == "O" ? "X" : "O";
        if(check_end(turn)){
            turn = turn == "O" ? "X" : "O";
            if (check_end(turn)){
                break;
            }
        }
    }
}
```
---
> ## 下期預告
> **棋類遊戲-黑白棋實作篇**
> \>\_將網頁遊戲做到arcade
> 
