解題區/解題區 - UVa

UVa 10838 - The Pawn Chess

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution
    1. 4.1. alpha-beta pruning
      1. 4.1.1. 策略

Problem

在縮小版本國際象棋中，兩個人只能操控士兵 (Pawn)，其中白色先手並且位於棋盤下方，操控棋子為大寫 P，黑色後手為小寫 p。

士兵在移動時，只能往敵方軍營前進，只能往前一步走到空的，或者是吃掉對方斜著走。也就是當敵方在斜角時才能往斜角走。

將對方逼得無路可走時 (全滅)，或者是我方棋子抵達對方底線時遊戲宣告結束。請問白色先手最少要幾步才能獲勝？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
2
 
.ppp
....
.PPP
....
 
...p
...p
pP.P
...P

Sample Output

1
2
white (7)
black (2)

Solution

一種很傳統的博弈問題，一般而言對於劃分狀態最小化即可。但是效率會很差，因為狀態分化的太多，必須走訪所有的狀態才能知道結果。基於這一點，有了 alpha-beta 剪枝，但這種剪枝相當依賴走訪順序，因此也不保證是比較好的搜索，但已經提供相當不錯的思路。

pruning 中文翻譯：修剪

alpha-beta pruning

主要為博弈剪枝用，求最少步數獲勝 (對於是否必勝的判斷在效率上有待考量。)

策略

假設 [999, -999] 作為步數的決策 (用實際數值來假設)

  • 正數表示先手必勝的步數，越大表示需要的步數越少，
  • 負數表示後手必勝的步數，越小表示需要的步數越少。

根據博弈的遞迴寫法，步數從深度 999 往下找，先手要最大化其結果 (最後最少步數用 999 - 結果)，後手要最小化其結果 (最後最少步數用 999 + 結果)。分層討論的話，就是取最大 - 取最小 - 取最大 … 交錯。

我們把已知的兩個結果做討論，定義當前搜索過程中得到的 alpha 是先手最佳化，beta 是後手最佳化。

父節點會將已經找到的部分解傳遞給孩子繼續搜索，假使父親是取最大值，還是則都是要取最小值，如果其中一個孩子的最小值 p 已知，另一個孩子搜索到一半時，發現其中它的孩子回傳 q < p，其實可以放棄搜索，因為這一層還要取最小，隨後回父親要取最大，不可能比 p 還要大。直接放棄 son 的所有分支搜索。

1
2
3
4
5
  parent (first player maximum) alpha = maximum(p, son, ...)
 /     \
p      son (second player minimum) beta = minimum(q, ...)
       /
      q

發現思路其實相當簡單，關鍵在於如何表示最小化、最大化之間對於博弈的定義。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <stdio.h> 
#include <algorithm>
using namespace std;
struct state {
    char g[4][5];
    int isEnd() {
        int b = 0, w = 0;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++)  {
                if (g[i][j] == 'p')
                    b++;
                if (g[i][j] == 'P')
                    w++;
            }
        }
        if (b == 0 || w == 0)	return 1;
        for (int i = 0; i < 4; i++) {
            if (g[0][i] == 'P')	return 1;
            if (g[3][i] == 'p')	return 1;
        }
        return 0;
    }
};
int alpha_beta(state board, int depth, int alpha, int beta) {
    if (board.isEnd())
        return depth%2 == 0 ? -depth : depth;
    int movable = 0;
    if (depth%2 == 0) { // first player
        for (int i = 1; i < 4; i++)  {
            for (int j = 0; j < 4; j++) {
                if (board.g[i][j] == 'P') {
                    for (int k = j - 1; k <= j + 1; k++) {
                        if (k < 0 || k >= 4)
                            continue;
                        if ((k != j && board.g[i-1][k] == 'p') || (k == j && board.g[i-1][k] == '.')) {
                            state s = board;
                            s.g[i][j] = '.', s.g[i-1][k] = 'P';
                            alpha = max(alpha, alpha_beta(s, depth - 1, alpha, beta));
                            if (beta <= alpha)
                                return alpha;
                            movable = 1;
                        }
                    }
                }
            }
        }
        if (!movable)	return -depth;
        return alpha;
    } else {
        for (int i = 0; i < 3; i++)  {
            for (int j = 0; j < 4; j++) {
                if (board.g[i][j] == 'p') {
                    for (int k = j - 1; k <= j + 1; k++) {
                        if (k < 0 || k >= 4)
                            continue;
                        if ((k != j && board.g[i+1][k] == 'P') || (k == j && board.g[i+1][k] == '.')) {
                            state s = board;
                            s.g[i][j] = '.', s.g[i+1][k] = 'p';
                            beta = min(beta, alpha_beta(s, depth - 1, alpha, beta));
                            if (beta <= alpha)
                                return beta;
                            movable = 1;
                        }
                    }
                }
            }
        }
        if (!movable)	return depth;
        return beta;
    }
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        state init;
        for (int i = 0; i < 4; i++)
            scanf("%s", init.g[i]);
        int ret = alpha_beta(init, 36, -9999, 9999);
        if (ret >= 0)
            printf("white (%d)\n", 36 - ret);
        else
            printf("black (%d)\n", 36 + ret);
    }
    return 0;
}
/*
2
.ppp
....
.PPP
....
...p
...p
pP.P
...P
*/