alpha_beta.ts

// two person zero-sum game

type node = number[];

enum player {
	max = 1,
	min = -1,
};

enum outcome {
	win = 1,
	draw = 0,
	lose = -1,
}

const defaultNode = [
	0, 0, 0,
	0, 0, 0,
	0, 0, 0,
];

const resultIndices = [
	[0, 1, 2],
	[0, 3, 6],
	[0, 4, 8],

	[1, 4, 7],

	[2, 5, 8],

	[3, 5, 7],

	[6, 7, 8],
];

const max = Math.max;
const min = Math.min;

const terminal = (n: node) => {
	if (utility(n) === outcome.draw) {
		for (const b of n) {
			if (b === 0) {
				return false;
			}
		}	
	} else {
		return true;
	}
}

const utility = (n: node): outcome => {

	for (const r of resultIndices) {
		switch (n[r[0]] + n[r[1]] + n[r[2]]) {
			case outcome.win * 3:
				return outcome.win;
			case outcome.lose * 3:
				return outcome.lose;
		}
	}

	return outcome.draw;
}

const children = (node: node, player: player) => {
    return node.reduce<number[][]>((prev, curr, idx) => {
        if (curr === 0) {
            let n = node.slice(0);
            n[idx] = player;
            prev.push(n);
        }
        return prev
    }, []);
}

const alphabeta= (n: node, p: player, alpha = -10, beta = 10) => {
	// basecase
    if (terminal(n)) {
		return utility(n);
	}
	
    if (p === player.max) {
        for(const child of children(n, p)) {
            alpha = max(alpha, alphabeta(child, player.min, alpha, beta));
            
            if (alpha >= beta) {
                break; // pruning the sibling nodes
            }
        }
        
        return alpha;
    } else {
        for (const child of children(n, p)) {
            beta = min(beta, alphabeta(child, player.max, alpha, beta));
            
            if (alpha >= beta) {
                break; // pruning the sibling nodes
            }
        }
        
        return beta;
    }
}

export {
	terminal,
	utility,
	alphabeta,
	children,
	node,
	player,
	outcome,
}

alpha_beta_test.ts

import * as test from 'tape';
import * as ab from './alpha_beta';

// ------------- children -------------- //
type ceType = {
    in: {
        n: ab.node,
        p: ab.player,
    }
    out: ab.node[]
}

// children expectations
const childrenExp: ceType[] = [
    {
        in: {
            n: [
                0,0,0,
                0,0,0,
                0,0,0,
            ],
            p: ab.player.max
        }, 
        out:[
            [
                1,0,0,
                0,0,0,
                0,0,0,
            ],
            [
                0,1,0,
                0,0,0,
                0,0,0,
            ],
            [
                0,0,1,
                0,0,0,
                0,0,0,
            ],
            [
                0,0,0,
                1,0,0,
                0,0,0,
            ],
            [
                0,0,0,
                0,1,0,
                0,0,0,
            ],
            [
                0,0,0,
                0,0,1,
                0,0,0,
            ],
            [
                0,0,0,
                0,0,0,
                1,0,0,
            ],
            [
                0,0,0,
                0,0,0,
                0,1,0,
            ],
            [
                0,0,0,
                0,0,0,
                0,0,1,
            ],
        ],
    },
    {
        in: {
            n: [
                 1,-1, 1,
                -1, 1,-1,
                 1, 0, 0,
            ],
            p: ab.player.min,
        },
        out: [
            [
                 1,-1, 1,
                -1, 1,-1,
                 1, -1, 0,
            ],
            [
                 1,-1, 1,
                -1, 1,-1,
                 1, 0, -1,
            ],
        ]
    },
    {
        in: {
            n: [
                 1,-1, 1,
                -1, 1,-1,
                 1, 1, -1,
            ],
            p: ab.player.max,
        },
        out: [],
    }
]

test("testing children", (t) => {
   for(const c of childrenExp) {
       t.deepEqual(ab.children(c.in.n, c.in.p), c.out);
   }
   t.end(); 
});

// -------- utility -------- //

type ueType = {
    in: ab.node
    out: ab.outcome
}

const utilityExp: ueType[] = [
    {
        in: [
            1, -1, 0,
            1, -1, 1,
            0, -1, 0
        ],
        out: ab.outcome.lose,
    },
    {
        in: [
            1, -1, 0,
            1, -1, 1,
            1,  0, 0,
        ],
        out: ab.outcome.win,
    },
    {
        in: [
            1, -1, 0,
            1, -1, 1,
            0,  0, 0
        ],
        out: ab.outcome.draw,
    },
]; 

test("testing utility", (t) => {
   for(const c of utilityExp) {
       t.deepEqual(ab.utility(c.in), c.out);
   }
   t.end(); 
});


// --------- terminal ---------- //

type teType = {
    in: ab.node
    out: boolean
} 

const terminalExp: teType[] = [
    {
        in: [
            1, -1, 0,
            1, -1, 1,
            0, -1, 0
        ],
        out: true,
    },
    {
        in: [
            1, -1, 0,
            1, -1, 1,
            1,  0, 0,
        ],
        out: true,
    },
    {
        in: [
            1, -1, 0,
            1, -1, 1,
            0,  0, 0
        ],
        out: false,
    },
];

test("testing terminal nodes", (t) => {
   for(const c of terminalExp) {
       t.deepEqual(ab.terminal(c.in), c.out);
   }
   t.end(); 
});