/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.ArrayList;
class Node {
boolean isMin;
boolean isMax;
boolean isTerminal;
int value;
int depth;
}
class AlphaBeta {
static Node alphaBetaSearch(Node state){
state.value = max_value(state,-99999,99999);
System.
out.
println(state.
value);
return null;
}
static int max_value(Node state, int alpha, int beta){
if (state.isTerminal){
System.
out.
println("visited leaf with value " + state.
value); return state.value;
}
state.value = -99999;
for (Node a: state.children){
state.
value = Math.
max(state.
value , min_value
(a, alpha, beta
)); if (state.value >= beta){
return state.value;
}
alpha
= Math.
max(alpha, state.
value); }
return state.value;
}
static int min_value(Node state, int alpha, int beta){
if (state.isTerminal)
return state.value;
state.value = 99999;
for (Node a: state.children){
state.
value = Math.
min(state.
value, max_value
(a, alpha, beta
)); if (state.value >= alpha){
return state.value;
}
beta
= Math.
min(beta, state.
value); }
return state.value;
}
public static void main
(String[] args
) {
Node t1 = new Node();
// t1.value = 4;
t1.value = 3;
t1.depth =2;
t1.isTerminal = true;
Node t2 = new Node();
// t2.value = 8;
t2.value = 12;
t2.depth=2;
t2.isTerminal= true;
Node t3 = new Node();
// t3.value = 7;
t3.value = 8;
t3.depth=2;
t3.isTerminal= true;
Node min1 = new Node();
min1.isTerminal=false;
min1.depth=1;
min1.isMin=true;
min1.children.add(t1);
min1.children.add(t2);
min1.children.add(t3);
Node t4 = new Node();
// t4.value = 5;
t4.value = 2;
t4.depth =2;
t4.isTerminal = true;
Node t5 = new Node();
//t5.value = 2;
t5.value =3;
t5.depth=2;
t5.isTerminal= true;
Node t6 = new Node();
// t6.value = 1;
t6.value=9;
t6.depth=2;
t6.isTerminal= true;
Node min2 = new Node();
min2.isMin=true;
min2.isTerminal=false;
min2.depth=1;
min2.children.add(t4);
min2.children.add(t5);
min2.children.add(t6);
Node t7 = new Node();
// t7.value = 1;
t7.value=14;
t7.depth =2;
t7.isTerminal = true;
Node t8 = new Node();
// t8.value = 6;
t8.value=1;
t8.depth=2;
t8.isTerminal= true;
Node t9 = new Node();
// t9.value = 0;
t9.value=8;
t9.depth=2;
t9.isTerminal= true;
Node min3 = new Node();
min3.isMin=true;
min3.isTerminal=false;
min3.depth=1;
min3.children.add(t7);
min3.children.add(t8);
min3.children.add(t9);
Node max1 = new Node();
max1.isMax=true;
max1.isTerminal=false;
max1.depth=0;
max1.children.add(min1);
max1.children.add(min2);
max1.children.add(min3);
alphaBetaSearch (max1);
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgppbXBvcnQgamF2YS51dGlsLkFycmF5TGlzdDsKCmNsYXNzIE5vZGUgewoKICAgIGJvb2xlYW4gaXNNaW47CiAgICBib29sZWFuIGlzTWF4OwogICAgYm9vbGVhbiBpc1Rlcm1pbmFsOwogICAgaW50IHZhbHVlOwogICAgaW50IGRlcHRoOwogICAgQXJyYXlMaXN0IDxOb2RlPiBjaGlsZHJlbiA9IG5ldyBBcnJheUxpc3QgPE5vZGU+KCk7Cgp9CmNsYXNzIEFscGhhQmV0YSB7CgoKICAgIHN0YXRpYyBOb2RlIGFscGhhQmV0YVNlYXJjaChOb2RlIHN0YXRlKXsKCiAgICAgICAgc3RhdGUudmFsdWUgPSBtYXhfdmFsdWUoc3RhdGUsLTk5OTk5LDk5OTk5KTsKCiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKHN0YXRlLnZhbHVlKTsKCiAgICByZXR1cm4gbnVsbDsKICAgIH0gCgoKICAgIHN0YXRpYyBpbnQgbWF4X3ZhbHVlKE5vZGUgc3RhdGUsIGludCBhbHBoYSwgaW50IGJldGEpewoKCiAgICAgICAgaWYgKHN0YXRlLmlzVGVybWluYWwpewogICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oInZpc2l0ZWQgbGVhZiB3aXRoIHZhbHVlICIgKyBzdGF0ZS52YWx1ZSk7CiAgICAgICAgICAgIHJldHVybiBzdGF0ZS52YWx1ZTsKICAgICAgICB9CgogICAgICAgIHN0YXRlLnZhbHVlID0gLTk5OTk5OwoKICAgICAgICBmb3IgKE5vZGUgYTogc3RhdGUuY2hpbGRyZW4pewoKICAgICAgICAgICAgc3RhdGUudmFsdWUgPSBNYXRoLm1heChzdGF0ZS52YWx1ZSAsIG1pbl92YWx1ZShhLCBhbHBoYSwgYmV0YSkpOwogICAgICAgICAgICBpZiAoc3RhdGUudmFsdWUgPj0gYmV0YSl7CgogICAgICAgICAgICAgICAgcmV0dXJuIHN0YXRlLnZhbHVlOyAgICAgICAgICAgICAgICAKICAgICAgICAgICAgfQogICAgICAgICAgICBhbHBoYSA9IE1hdGgubWF4KGFscGhhLCBzdGF0ZS52YWx1ZSk7CiAgICAgICAgfQogICAgICAgIHJldHVybiBzdGF0ZS52YWx1ZTsKICAgIH0KCiAgICBzdGF0aWMgaW50IG1pbl92YWx1ZShOb2RlIHN0YXRlLCBpbnQgYWxwaGEsIGludCBiZXRhKXsKCgogICAgICAgIGlmIChzdGF0ZS5pc1Rlcm1pbmFsKSAKICAgICAgICAgICAgcmV0dXJuIHN0YXRlLnZhbHVlOwoKICAgICAgICBzdGF0ZS52YWx1ZSA9IDk5OTk5OwoKICAgICAgICBmb3IgKE5vZGUgYTogc3RhdGUuY2hpbGRyZW4pewoKICAgICAgICAgICAgc3RhdGUudmFsdWUgPSBNYXRoLm1pbihzdGF0ZS52YWx1ZSwgbWF4X3ZhbHVlKGEsIGFscGhhLCBiZXRhKSk7CiAgICAgICAgICAgIGlmIChzdGF0ZS52YWx1ZSA+PSBhbHBoYSl7CgogICAgICAgICAgICAgICAgcmV0dXJuIHN0YXRlLnZhbHVlOwoKICAgICAgICAgICAgfQogICAgICAgICAgICBiZXRhID0gTWF0aC5taW4oYmV0YSwgc3RhdGUudmFsdWUpOwogICAgICAgIH0KICAgICAgICByZXR1cm4gc3RhdGUudmFsdWU7CiAgICB9CgoKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKCiAgICAgICAgTm9kZSB0MSA9IG5ldyBOb2RlKCk7Ci8vICAgICAgICAgICAgdDEudmFsdWUgPSA0OyAKICAgICAgICAgICAgdDEudmFsdWUgPSAzOwogICAgICAgICAgICB0MS5kZXB0aCA9MjsKICAgICAgICAgICAgdDEuaXNUZXJtaW5hbCA9IHRydWU7CgogICAgICAgIE5vZGUgdDIgPSBuZXcgTm9kZSgpOwovLyAgICAgICAgICAgICB0Mi52YWx1ZSA9IDg7CiAgICAgICAgICAgICB0Mi52YWx1ZSA9IDEyOwogICAgICAgICAgICAgdDIuZGVwdGg9MjsKICAgICAgICAgICAgIHQyLmlzVGVybWluYWw9IHRydWU7CgogICAgICAgIE5vZGUgdDMgPSBuZXcgTm9kZSgpOwogICAgICAgICAgICAvLyB0My52YWx1ZSA9IDc7CiAgICAgICAgICAgICB0My52YWx1ZSA9IDg7CiAgICAgICAgICAgICB0My5kZXB0aD0yOwogICAgICAgICAgICAgdDMuaXNUZXJtaW5hbD0gdHJ1ZTsKCiAgICAgICAgTm9kZSBtaW4xID0gbmV3IE5vZGUoKTsKICAgICAgICAgICAgIG1pbjEuaXNUZXJtaW5hbD1mYWxzZTsKICAgICAgICAgICAgIG1pbjEuZGVwdGg9MTsKICAgICAgICAgICAgIG1pbjEuaXNNaW49dHJ1ZTsKICAgICAgICAgICAgIG1pbjEuY2hpbGRyZW4uYWRkKHQxKTsKICAgICAgICAgICAgIG1pbjEuY2hpbGRyZW4uYWRkKHQyKTsKICAgICAgICAgICAgIG1pbjEuY2hpbGRyZW4uYWRkKHQzKTsKCiAgICAgICAgTm9kZSB0NCA9IG5ldyBOb2RlKCk7Ci8vICAgICAgICAgICAgdDQudmFsdWUgPSA1OwogICAgICAgICAgICB0NC52YWx1ZSA9IDI7CiAgICAgICAgICAgIHQ0LmRlcHRoID0yOwogICAgICAgICAgICB0NC5pc1Rlcm1pbmFsID0gdHJ1ZTsKCiAgICAgICAgTm9kZSB0NSA9IG5ldyBOb2RlKCk7CiAgICAgICAgICAgICAvL3Q1LnZhbHVlID0gMjsKICAgICAgICAgICAgIHQ1LnZhbHVlID0zOwogICAgICAgICAgICAgdDUuZGVwdGg9MjsKICAgICAgICAgICAgIHQ1LmlzVGVybWluYWw9IHRydWU7CgogICAgICAgIE5vZGUgdDYgPSBuZXcgTm9kZSgpOwovLyAgICAgICAgICAgICB0Ni52YWx1ZSA9IDE7CiAgICAgICAgICAgICB0Ni52YWx1ZT05OwogICAgICAgICAgICAgdDYuZGVwdGg9MjsKICAgICAgICAgICAgIHQ2LmlzVGVybWluYWw9IHRydWU7CgogICAgICAgIE5vZGUgbWluMiA9IG5ldyBOb2RlKCk7CiAgICAgICAgICAgICBtaW4yLmlzTWluPXRydWU7CiAgICAgICAgICAgICBtaW4yLmlzVGVybWluYWw9ZmFsc2U7CiAgICAgICAgICAgICBtaW4yLmRlcHRoPTE7CiAgICAgICAgICAgICBtaW4yLmNoaWxkcmVuLmFkZCh0NCk7CiAgICAgICAgICAgICBtaW4yLmNoaWxkcmVuLmFkZCh0NSk7CiAgICAgICAgICAgICBtaW4yLmNoaWxkcmVuLmFkZCh0Nik7ICAKCgogICAgICAgIE5vZGUgdDcgPSBuZXcgTm9kZSgpOwovLyAgICAgICAgICAgICB0Ny52YWx1ZSA9IDE7IAogICAgICAgICAgICAgdDcudmFsdWU9MTQ7CiAgICAgICAgICAgICB0Ny5kZXB0aCA9MjsKICAgICAgICAgICAgIHQ3LmlzVGVybWluYWwgPSB0cnVlOwoKICAgICAgICBOb2RlIHQ4ID0gbmV3IE5vZGUoKTsKLy8gICAgICAgICAgICAgdDgudmFsdWUgPSA2OwogICAgICAgICAgICAgdDgudmFsdWU9MTsKICAgICAgICAgICAgIHQ4LmRlcHRoPTI7CiAgICAgICAgICAgICB0OC5pc1Rlcm1pbmFsPSB0cnVlOwoKICAgICAgICBOb2RlIHQ5ID0gbmV3IE5vZGUoKTsKLy8gICAgICAgICAgICAgdDkudmFsdWUgPSAwOwogICAgICAgICAgICAgdDkudmFsdWU9ODsKICAgICAgICAgICAgIHQ5LmRlcHRoPTI7CiAgICAgICAgICAgICB0OS5pc1Rlcm1pbmFsPSB0cnVlOwoKICAgICAgICBOb2RlIG1pbjMgPSBuZXcgTm9kZSgpOwogICAgICAgICAgICAgbWluMy5pc01pbj10cnVlOwogICAgICAgICAgICAgbWluMy5pc1Rlcm1pbmFsPWZhbHNlOwogICAgICAgICAgICAgbWluMy5kZXB0aD0xOwogICAgICAgICAgICAgbWluMy5jaGlsZHJlbi5hZGQodDcpOwogICAgICAgICAgICAgbWluMy5jaGlsZHJlbi5hZGQodDgpOwogICAgICAgICAgICAgbWluMy5jaGlsZHJlbi5hZGQodDkpOwoKICAgICAgICAgTm9kZSBtYXgxID0gbmV3IE5vZGUoKTsKICAgICAgICAgICAgICBtYXgxLmlzTWF4PXRydWU7CiAgICAgICAgICAgICAgbWF4MS5pc1Rlcm1pbmFsPWZhbHNlOwogICAgICAgICAgICAgIG1heDEuZGVwdGg9MDsKICAgICAgICAgICAgICBtYXgxLmNoaWxkcmVuLmFkZChtaW4xKTsKICAgICAgICAgICAgICBtYXgxLmNoaWxkcmVuLmFkZChtaW4yKTsKICAgICAgICAgICAgICBtYXgxLmNoaWxkcmVuLmFkZChtaW4zKTsKCgoKICAgICAgICAgICAgICBhbHBoYUJldGFTZWFyY2ggKG1heDEpOwoKCgogICAgfQp9