java 的最后一课是大家写 Othello 的对战程序然后联机到学校的服务器对打 觉得好玩就记录一下。奥赛罗作为完全信息的对战游戏，现在说好像最优解是平局
老师写了 beta cut 的策略，我们一般是在此基础上做补充或者修改。规则是每一手限时 20 秒，beta 好像先手的时候优势很大，但是后手就输得很惨。
我先记录过程然后记录思路。
有些人没有用满时间很快就结束了，我因为递归了 9 层比较慢，而且还超时了 4 局，麻了。重新看其实输了很多能赢的局，因为前面优势大反而算太久不必要的可能性有点浪费了。
N 基本无双了只输了 3 把。我从他手里拿下一把只能说还蛮开心的。后面说思路的时候大概分两种，一种是不动基础值，在 beta 方法的基础上修改具体的评价方法，比如加入不会被吃的位置和让自己能落子更多的位置，增加这些位置的权重。还有一种是分为序盘，中盘和终盘阶段分 3 个评价表，仍然用 beta。3 个并列的第二的基本这两个思路，还有一个人是使用了定石，也就是开局前几手指定一些常见的落子方式然后接着 beta，非常耍赖，但真的很有用。我也属于第一种思路。第一比较新，他是逆 beta，beta 算最大值，他算最小值，这样还节约时间。只能说想太多了不如一点做好。
注意这张表的 12 名 G=gpt，是教授纯让 gpt 写的，赢下 8 场橄榄了 13~15 名。16~17 是 accident 不算数。
○: 先手勝，×: 後手勝, 0: 対戦中, 2: 変な手による0の勝ち, 3: 変な手による1の勝ち, 4: 一手のタイムアウト(20秒)による 0の勝ち, 5: 一手のタイムアウト(20秒)による 1の勝ち, 6: IO Exceptionによる0の勝ち, 7: IO Exception による 1 の勝ち
表 有些 xo 标记是反的 横着看左边数字比右边大代表那一行的人赢了 竖着看右边大的话赢
ai 把标志搞混了所以 x，o 不能看了，要看具体数字。
比如说横着看 katsu 那行， 和 N 那一场，第五行第一个，katsu33 N31 是 katsu 先手胜，ai 总结搞错了 唉幻觉。
然后竖着看 katsu 那列，和 N 那一场第一行第五个，N33，katsu31，katsu 后手输了。
不过这两场思路不一样的程序跑出来结果如此相似，还挺有意思的。
贴上核心程序和思路，思路交日语作业了所以懒得翻译了。
protected int[][] ban = BanOperation.newBan();
// 盤の状態 0, 1 : 石 -1: 空白, -2: 盤外
protected int xy; // 最後の手番で打たれた x
protected int turn; // どちらの turn
protected int end; // 終了状態なら 1 以上，そうでないなら 0
protected int zero; // 0 の個数
protected int one; // 1 の個数
protected int zerotime; // 先手(0) の経過時間
protected int onetime; // 後手(1) の経過時間
protected String myname = ""; // 自分の名前
protected String oname = ""; // 相手の名前の希望，実際の相手はサーバーが指定
protected int myturn = 0; // 自分の手番の希望，実際の手番はサーバーが指定
Socket s;
BufferedReader in;
PrintStream out;
int level = 9;
int total_turn = 64;
int same_color_turn = 10;
int left_turn = total_turn - zero - one;
private boolean check = false; // 後手のチェックをしたかどうか
private boolean secondPlayer = false; // 後手がどうか
int[][] hyokati = new int[][] {
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 120, -20, 20, 5, 5, 20, -20, 120, 0 },
{ 0, -20, -40, -5, -5, -5, -5, -40, -20, 0 },
{ 0, 20, -5, 15, 3, 3, 15, -5, 20, 0 },
{ 0, 5, -5, 3, 3, 3, 3, -5, 5, 0 },
{ 0, 5, -5, 3, 3, 3, 3, -5, 5, 0 },
{ 0, 20, -5, 15, 3, 3, 15, -5, 20, 0 },
{ 0, -20, -40, -5, -5, -5, -5, -40, -20, 0 },
{ 0, 120, -20, 20, 5, 5, 20, -20, 120, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } };
public int countO(int[][] ban, int turn) {
int count = 0;
for (int i = 1; i <= 8; i++) {
for (int j = 1; j <= 8; j++) {
if (ban[i][j] == 0) {
count += 1;
} else if (ban[i][j] == 1) {
count -= 1;
}
}
}
if (turn == 1)
count = -count;
return count;
}
int[] evaluateMove(int[][] thisban, int turn, int level, int beta) {
if(level==0){
return (new int[] { countO(thisban, turn), -1 });
}
int xx = -1, yy = -1;
int max = -100000; // とりあえず最小値
int[][] newban = new int[10][10];
out: for (int x = 1; x <= 8; x++) {
for (int y = 1; y <= 8; y++) {
if (BanOperation.possible(thisban, turn, x * 10 + y)) {
BanOperation.copyBan(thisban, newban);
BanOperation.updateban(newban, turn, x * 10 + y);
int v = -evaluateMove(newban, 1 - turn, level - 1, -max)[0];
// System.out.println(v);
if (v >= beta) {
max = v;
xx = x;
yy = y;
break out;
}
if (v > max) {
max = v;
xx = x;
yy = y;
}
}
}
}
if (max == -100000) { // 打つ手がない
max = -evaluateMove(thisban, 1 - turn, level - 1, -max)[0]; // 相手の手にわたして評価
}
// System.out.println(eval);
return (new int[] { max, xx * 10 + yy });
}
public int hyokaC(int[][] ban, int turn) {
int eval = 0;
for (int i = 1; i <= 8; i++) {
for (int j = 1; j <= 8; j++) {
if (ban[i][j] == 0) {
eval += hyokati[i][j];
} else if (ban[i][j] == 1) {
eval -= hyokati[i][j];
}
}
}
eval = Math.round(eval * ((left_turn) / 64));
if ((64 - 15) > left_turn) {
eval += Math.round((countO(ban, turn)) * ((left_turn) / 10));
}
if (turn == 1)
eval = -eval;
return eval;
}
int[] betaC(int[][] thisban, int turn, int level, int beta) {
if (level == 0) {
return (new int[] { hyokaC(thisban, turn), -1 });
}
int xx = -1, yy = -1;
int max = -100000; // とりあえず最小値
int[][] newban = new int[10][10];
out: for (int x = 1; x <= 8; x++) {
for (int y = 1; y <= 8; y++) {
if (BanOperation.possible(thisban, turn, x * 10 + y)) {
BanOperation.copyBan(thisban, newban);
BanOperation.updateban(newban, turn, x * 10 + y);
int v = -betaC(newban, 1 - turn, level - 1, -max)[0];
// System.out.println(v);
if (v >= beta) {
max = v;
xx = x;
yy = y;
break out;
}
if (v > max) {
max = v;
xx = x;
yy = y;
}
}
}
}
if (max == -100000) { // 打つ手がない
max = -betaC(thisban, 1 - turn, level - 1, -max)[0]; // 相手の手にわたして評価
}
// System.out.println(eval);
return (new int[] { max, xx * 10 + yy });
}
public int myturn() {
int left_turn = total_turn - zero - one;
System.out.format("私の手番： 最後の手： (%d), 黒：%d, 白：%d, 黒時間：%d, 白時間：%d\n",
xy, zero, one, zerotime, onetime);
if (!check) { // 初回だけに判断する
secondPlayer = (turn == 1);
check = true;
}
if (secondPlayer) {
if (0<= left_turn && left_turn < (64 - 15)) {
return betaC(ban, turn, level, 10000)[1];
} else {
return evaluateMove(ban, turn, 7, 10000)[1];
}
}
else {
if (0<= left_turn && left_turn < (64 - 15)) {
return betaC(ban, turn, level, 10000)[1];
} else {
return evaluateMove(ban, turn, level, 10000)[1];
}
}
}目標はbeta.javaに先手でも後手でも勝つことです。
第一に、プログラムは、ゲームの進行状況に応じて動的に評価しようとしています。残りのターン数（left_turn）を基に、ゲームのどの段階にあるかを判断します。（相手の動きも含めて最初の15手を序盤としています）
eval = Math.round(eval * ((left_turn) / 64)); のようにturnが少なくなると、「いいところ」の評価の重要性は下がります。（オセロのウェブサイトなどを見て隅の重要性は終盤の最後はそこまで高くないと知りました。）
そして、if ((64 - 10) > left_turn) {
eval += Math.round((countO(ban, turn)) * ((left_turn) / 10));
}で、取れる石の数も評価します。そして、こちらのコードに関して、授業の発表の時に**間違いがありました**。
CountOはその一手を数えていますが、hyokaCメソッド自体は9手読んだ最後に使うので、**９手先に取れる石の数を評価値に入れて評価しています。**つまり、取れる石の数も、置くところの評価値も9手先のものです。
第二に、levelを9にして9手先を読む時、時間オーバーする恐れがあります。特に後手の場合はbeta.javaと戦うときに時間オーバーしました。したがって、先手か後手かを判断して、後手の場合には、序盤のlevelを7にしています。
最後に、最初にbeta.javaと戦う時、自分の置けるところを多くにして、相手の置けるところを少なくするようにする策などを試しましたが、後手の時はなかなか上手くいかず、結果としては評価値と取れる石の数で評価するようにしました。
反省点としては、4戦ほど時間オーバーしてしまって、時間をコントロールするメソッドなどを実装した方が良かったと思います。