Skip to content

Main content

Alpha-Beta Search Visualizer Source Code

Browse the implementation files for Alpha-Beta Search Visualizer.
tool.ts typescript
// Tool: Alpha-Beta Search Visualizer

type GameTree = number | GameTree[];
type StartingPlayer = 'maximizing' | 'minimizing';

const MAX_DEPTH = 12;
const MAX_NODES = 10_000;
const STARTING_PLAYERS: StartingPlayer[] = [
	'maximizing',
	'minimizing'
];

const parseFiniteNumber = (input: unknown): number | null => {
	if (
		(typeof input !== 'string' && typeof input !== 'number') ||
		(typeof input === 'string' && input.trim() === '')
	) {
		return null;
	}

	const value = Number(input);

	return Number.isFinite(value) ? value : null;
};

const parseTree = (input: unknown): GameTree | null => {
	if (typeof input !== 'string' || input.trim() === '')
		return null;

	try {
		const tree: unknown = JSON.parse(input);
		let nodes = 0;

		const valid = (
			node: unknown,
			depth: number
		): node is GameTree => {
			nodes += 1;

			if (nodes > MAX_NODES || depth > MAX_DEPTH) return false;
			if (typeof node === 'number')
				return Number.isFinite(node);

			return (
				Array.isArray(node) &&
				node.length > 0 &&
				node.every((child) => valid(child, depth + 1))
			);
		};

		return valid(tree, 0) && Array.isArray(tree) ? tree : null;
	} catch {
		return null;
	}
};

const leafPaths = (
	tree: GameTree,
	path: number[]
): string[] => {
	if (typeof tree === 'number') return [path.join('.')];

	return tree.flatMap((child, index) =>
		leafPaths(child, [...path, index])
	);
};

export const visualizeAlphaBetaSearch = (
	treeInput: unknown,
	startingPlayerInput: unknown,
	alphaInput: unknown,
	betaInput: unknown
): string => {
	const tree = parseTree(treeInput);
	const alphaStart = parseFiniteNumber(alphaInput);
	const betaStart = parseFiniteNumber(betaInput);

	if (
		tree === null ||
		!STARTING_PLAYERS.includes(
			startingPlayerInput as StartingPlayer
		) ||
		alphaStart === null ||
		betaStart === null ||
		alphaStart >= betaStart
	) {
		return '';
	}

	const visited: Array<{ path: string; value: number }> = [];
	const pruned: string[] = [];

	const search = (
		node: GameTree,
		path: number[],
		maximizing: boolean,
		alpha: number,
		beta: number
	): number => {
		if (typeof node === 'number') {
			visited.push({ path: path.join('.'), value: node });
			return node;
		}

		let value = maximizing ? -Infinity : Infinity;

		for (let index = 0; index < node.length; index += 1) {
			const childValue = search(
				node[index],
				[...path, index],
				!maximizing,
				alpha,
				beta
			);

			if (maximizing) {
				value = Math.max(value, childValue);
				alpha = Math.max(alpha, value);
			} else {
				value = Math.min(value, childValue);
				beta = Math.min(beta, value);
			}

			if (beta <= alpha) {
				for (
					let prunedIndex = index + 1;
					prunedIndex < node.length;
					prunedIndex += 1
				) {
					pruned.push(
						...leafPaths(node[prunedIndex], [
							...path,
							prunedIndex
						])
					);
				}
				break;
			}
		}

		return value;
	};

	const value = search(
		tree,
		[],
		startingPlayerInput === 'maximizing',
		alphaStart,
		betaStart
	);

	return Number.isFinite(value)
		? JSON.stringify(
				{
					pruned,
					prunedLeafCount: pruned.length,
					value,
					visited,
					visitedLeafCount: visited.length
				},
				null,
				2
			)
		: '';
};

export const Tool: TypeTool = {
	name: 'Alpha-Beta Search Visualizer',
	slug: 'game-search/alpha-beta',
	intro:
		'Evaluate a finite minimax tree while showing which leaves alpha–beta pruning visits and skips.',
	tool: visualizeAlphaBetaSearch,
	i: [
		{
			example: '[[[3,5],[6,9]],[[1,2],[0,-1]]]',
			label: 'Game Tree',
			placeholder: 'Nested JSON arrays with numeric leaves',
			render: 'textarea',
			type: 'text',
			value: '[[[3,5],[6,9]],[[1,2],[0,-1]]]'
		},
		{
			example: 'maximizing',
			label: 'Starting Player',
			options: [
				{
					selected: true,
					text: 'Maximizing',
					value: 'maximizing'
				},
				{ text: 'Minimizing', value: 'minimizing' }
			],
			placeholder: 'Select the player at the root',
			type: 'select',
			value: 'maximizing'
		},
		{
			example: '-1000000',
			label: 'Initial Alpha',
			placeholder: 'Finite lower bound',
			type: 'number',
			value: -1000000
		},
		{
			example: '1000000',
			label: 'Initial Beta',
			placeholder: 'Finite upper bound',
			type: 'number',
			value: 1000000
		}
	],
	o: [
		{
			example: '{ "value": 5, "visitedLeafCount": 6 }',
			label: 'Search Result',
			placeholder: 'Alpha–beta trace will appear here...',
			render: 'textarea',
			type: 'text'
		}
	],
	cite: [
		{
			title: 'Alpha–beta pruning — Wikipedia',
			url: 'https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning'
		}
	]
};

export default Tool;

Description

Browse the implementation files for Alpha-Beta Search Visualizer.

References

  1. Tool.io on GitHub
  2. Tool.io TypeScript tools library

Similar or alternative tools