用Java实现简单的井字棋程序（α-β剪枝）

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
import java.util.Random;
import java.util.Scanner;

public class main {
    static char[][] chess = new char[4][4];
    static char player;
    static char computer;
    static Scanner input=new Scanner(System.in);

    public static void main(String[] args){


        StartGame();

        String current = "player";
        while (!main.Win(main.computer) && !main.Win(main.player) && !main.isEmpty()) {
            //当有一方获胜或者棋盘是空的时候终止。
            switch (current) {
                case "player":
                    main.playerGo();
                    current = "computer";
                    break;//当玩家下完后轮到电脑下
                case "computer":
                    main.computerGo();
                    current = "player";
                    break;
                default:
                    break;
            }
        }

        //最终的结果界面 显示结果
        if (main.Win(main.computer)) {
            System.out.println("Computer win！");
        } else if (main.Win(main.player)) {
            System.out.println("player win!");
        } else {
            System.out.println("it ends in a draw！");
        }

    }

    //游戏开始界面
    public static void StartGame() {
        for (int i = 1; i < 4; i++)
            for (int j = 1; j < 4; j++)
                chess[i][j] = '-';
        //首先让用户选择使用的符号：1为符号X,2为符号O
        System.out.println("Welcome to tic tac toe man-machine interface");
        System.out.println("Please select your game symbol: X / O, enter the number 1 as X and the number 2 as O!");


        int a = input.nextInt();

        if (a == 1) {

            player = 'X';
            computer = 'O';

        } else if (a == 2) {

            player = 'O';
            computer = 'X';
        } else {

            player = 'X';
            computer = 'O';

            System.out.println("Input error, the player defaults to the symbol X");

        }

        //玩家选择先手还是后手 先手为1后手为2
        System.out.println("Enter 1 to select the first hand, and enter 2 to select the second hand");

        int hand= input.nextInt();
        if (hand == 1) {
            //玩家选择先手则先将棋盘绘制出
            Print();

        } else if (hand == 2) {
            //玩家后手则电脑下棋
            Random rand = new Random();
            int row = rand.nextInt(3) + 1;
            int col = rand.nextInt(3) + 1;
            chess[row][col] = computer;
            //电脑下完棋之后绘制棋盘
            Print();
        } else {
            //输入了错误的字符，默认玩家先手，绘制棋盘
            System.out.println("Input wrong characters, default player first!");
            Print();
        }

    }

    //绘制棋盘
    static void Print() {
        System.out.println("**********");
        for (int i = 1; i < 4; i++) {
            for (int j = 1; j < 4; j++) {
                System.out.print("| ");
                System.out.print(chess[i][j] + " ");
                if (j == 3) System.out.println("|");
            }
            if (i == 3) System.out.println("**********");
        }

    }


    //判断输赢 共有八种可能
    public static Boolean Win(char player) {
        //水平直线 竖直直线
        if (chess[1][1] == player && chess[1][2] == player && chess[1][3] == player) {
            return true;
        }
        if (chess[2][1] == player && chess[2][2] == player && chess[2][3] == player) {
            return true;
        }
        if (chess[3][1] == player && chess[3][2] == player && chess[3][3] == player) {
            return true;
        }
        if (chess[1][1] == player && chess[2][1] == player && chess[3][1] == player) {
            return true;
        }
        if (chess[1][2] == player && chess[2][2] == player && chess[3][2] == player) {
            return true;
        }
        if (chess[1][3] == player && chess[2][3] == player && chess[3][3] == player) {
            return true;
        }
        //斜线
        if (chess[1][1] == player && chess[2][2] == player && chess[3][3] == player) {
            return true;
        }
        return chess[1][3] == player && chess[2][2] == player && chess[3][1] == player;
    }


    //判断棋盘是否还有地方能下棋子
    public static boolean isEmpty() {
        //判断棋盘是否为空
        for (int i = 1; i < 4; i++) {
            for (int j = 1; j < 4; j++) {
                if (chess[i][j] == '-')
                    return false;
            }
        }
        return true;
    }

    //玩家开始下棋
    public static void playerGo() {

        System.out.println("--------------------------：                                    1，2，3");
        System.out.println("It's your turn to go. Please enter the chess piece position:    4，5，6");
        System.out.println("--------------------------：                                    7，8，9");

        int row, col;
        int a = input.nextInt();

        if (a >= 1 && a <= 9) {

            if (a % 3 == 0) row = a / 3;
            else row = a / 3 + 1;
            col = a - 3 * (row - 1);
            if (chess[row][col] != '-') {
                //判断玩家选择的位置是否有已经有棋子
                System.out.println("There are already pieces in this position");
                playerGo();
            }

            chess[row][col] = player;
            Print();

        } else {
            //输入错误给予提示
            System.out.println("Your character input is wrong, please re-enter!");
            playerGo();

        }

    }

    //电脑开始下棋
    public static void computerGo() {

        int best = 0;
        int bestScore = -1000;
        int score;
        for (int i = 1; i <= 3; i++) {
            for (int j = 1; j <= 3; j++) {
                if (chess[i][j] == '-') {
                    chess[i][j] = computer;
                    score = bestInput("player", "computer", -10000, 10000);//剪枝算法
                    if (score >=bestScore) {
                        //在同一层的节点里面需要不断试探性递归，用回溯法找到最合适的下棋点使自己胜算最大
                        bestScore = score;
                        best = (i - 1) * 3 + j;
                    }
                    chess[i][j] = '-';
                }
            }
        }
        int row, col;
        if (best % 3 == 0)
            row = best / 3;
        else
            row = best / 3 + 1;
        col = best - (row - 1) * 3;
        chess[row][col] = computer;
        Print();


    }

    //剪枝算法（-1玩家赢，1电脑赢，0平局）
    /*
    alpha剪枝思路：
   1.检查当前局面是否已分胜负。如果已分，返回结果，否则进入步骤2。
   2.如果本层是max层，搜索下一层可能的局面，根据可能的值更新本层的alpha，并且返回本层的beta给上层。否则更新本层的beta,并且把本层的alpha返回上一层
     */
    static int bestInput(String state, String nextState, int alpha, int beta) {
        //输入，调用剪枝的过程
        char ch;
        if (state.equals("computer")) {
            ch = computer;
        } else {
            ch = player;
        }

        if (Win(ch)) {
            if (state.equals("computer")) {
                //电脑赢
                return 1;
            } else {
                //玩家赢
                return -1;
            }
        } else if (isEmpty()) {
            //平局
            return 0;
        } else {
            int score;
            for (int i = 1; i < 4; i++) {
                for (int j = 1; j < 4; j++) {
                    if (chess[i][j] == '-') {
                        chess[i][j] = ch;
                        score = bestInput(nextState, state, alpha, beta);
                        chess[i][j] = '-';
                        if (state.equals("computer")) {
                            //max层
                            if (score >= alpha) {
                                alpha = score;
                            }
                            if (alpha > beta) {
                                return beta;
                            }
                        } else {
                            //min层
                            if (score < beta) {
                                beta = score;
                            }
                            if (beta <= alpha) {
                                return alpha;
                            }
                        }
                    }
                }
            }
            if (state.equals("computer")) {
                return alpha;
            } else {
                return beta;
            }
        }
    }


}