Minimax-Algorithm

—

title: Minimax Algorithm

date: 2020-08-14 20:03:12

tags:

categories: Algorithm

—

https://segmentfault.com/a/1190000013527949
const maxDepth = 4;
let counter = 1;

const dataTree = [
[
[
[3, 17], [2, 12]
],
[
[15], [25, 0]
]
],
[
[
[2, 5], [3]
]
[
[2, 14]
]
]
];

constructor(data, type, depth) {
this.data = data;
this.type = type; // 区分此节点的种类是max或min
this.depth = depth;
}

function changeType(type) {
return type === ‘max’ ? ‘min’ : ‘max’;
}

score() {
// 到达了最大深度后，此时的data是数组最内层的数字
if (this.depth >= 4) {
return this.data;
}

// 对于max节点，返回的是子节点中的最大值
if (this.type === 'max') {
    let maxScore = -1000;

    for (let i=0; i < this.data.length; i++) {
        const d = this.data[i];
        // 生成新的节点，子节点的type会和父节点不同
        const childNode = new Node(d, changeType(this.type), this.depth+1);
        // 递归获取其分数
        const childScore = childNode.score();

        if (childScore > maxScore) {
            maxScore = childScore;
        }
    }
    return maxScore;
}

// 对于min节点，返回的是子节点中的最小值
if (this.type === 'min') {
    let minScore = 1000;

    for (let i=0; i < this.data.length; i++) {
        const d = this.data[i];
        // 生成新的节点，子节点的type会和父节点不同
        const childNode = new Node(d, changeType(this.type), this.depth+1);
        // 递归获取其分数
        const childScore = childNode.score();

        if (childScore > minScore) {
            minScore = childScore;
        }
    }
    return minScore;
}

}

const testNode = new Node(dataTree, ‘max’, 0);
console.log(testNode.score());

---

Alpha-beta 剪枝算法的实现
是minimax的改进

class Node{
constructor(data, type, depth) {
this.data = data;
this.type = type; // 区分此节点的种类是max或min
this.depth = depth;

    this.alpha = alpha || -Infinity;
    this.beta = beta || Infinity;
}

score() {

}

}