Skip to content

Main content

Alpha-Beta-UCT Search Demonstrator Source Code

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

type StartingPlayer = 'maximizing' | 'minimizing';

interface SearchNode {
	children?: SearchNode[];
	move: string;
	value?: number;
	valueSum: number;
	visits: number;
}

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): SearchNode | null => {
	if (typeof input !== 'string' || input.trim() === '')
		return null;

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

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

			if (
				nodeCount > MAX_NODES ||
				depth > MAX_DEPTH ||
				typeof node !== 'object' ||
				node === null
			) {
				return false;
			}

			const candidate = node as Record<string, unknown>;

			if (
				typeof candidate.move !== 'string' ||
				candidate.move.trim() === '' ||
				typeof candidate.visits !== 'number' ||
				!Number.isSafeInteger(candidate.visits) ||
				candidate.visits < 0 ||
				typeof candidate.valueSum !== 'number' ||
				!Number.isFinite(candidate.valueSum)
			) {
				return false;
			}

			if (candidate.children === undefined) {
				return (
					typeof candidate.value === 'number' &&
					Number.isFinite(candidate.value)
				);
			}

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

		return valid(tree, 0) &&
			(tree as SearchNode).children !== undefined
			? (tree as SearchNode)
			: null;
	} catch {
		return null;
	}
};

const collectLeaves = (
	node: SearchNode,
	path: string[]
): string[] => {
	const nextPath =
		node.move === 'root' ? path : [...path, node.move];

	if (node.children === undefined)
		return [nextPath.join(' > ')];

	return node.children.flatMap((child) =>
		collectLeaves(child, nextPath)
	);
};

const round = (value: number): number =>
	Number(value.toPrecision(12));

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

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

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

	const search = (
		node: SearchNode,
		path: string[],
		maximizing: boolean,
		alpha: number,
		beta: number
	): number => {
		const nextPath =
			node.move === 'root' ? path : [...path, node.move];

		if (node.children === undefined) {
			visited.push({
				path: nextPath.join(' > '),
				value: node.value!
			});
			return node.value!;
		}

		const scoredChildren = node.children
			.map((child, index) => {
				const mean =
					child.visits === 0
						? 0
						: child.valueSum / child.visits;
				const bonus =
					exploration *
					Math.sqrt(
						Math.log(Math.max(1, node.visits) + 1) /
							(child.visits + 1)
					);
				const score = maximizing ? mean + bonus : mean - bonus;

				if (![mean, bonus, score].every(Number.isFinite)) {
					throw new RangeError('Non-finite UCT score');
				}

				return {
					child,
					index,
					score
				};
			})
			.sort(
				(first, second) =>
					(maximizing
						? second.score - first.score
						: first.score - second.score) ||
					first.index - second.index
			);

		orderedNodes.push({
			order: scoredChildren.map(({ child }) => child.move),
			path: nextPath.join(' > ') || 'root',
			scores: scoredChildren.map(({ score }) => round(score))
		});

		let value = maximizing ? -Infinity : Infinity;

		for (
			let orderedIndex = 0;
			orderedIndex < scoredChildren.length;
			orderedIndex += 1
		) {
			const childValue = search(
				scoredChildren[orderedIndex].child,
				nextPath,
				!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 = orderedIndex + 1;
					prunedIndex < scoredChildren.length;
					prunedIndex += 1
				) {
					pruned.push(
						...collectLeaves(
							scoredChildren[prunedIndex].child,
							nextPath
						)
					);
				}
				break;
			}
		}

		return value;
	};

	let value: number;

	try {
		value = search(
			tree,
			[],
			startingPlayerInput === 'maximizing',
			alphaStart,
			betaStart
		);
	} catch {
		return '';
	}

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

const DEFAULT_TREE = JSON.stringify({
	move: 'root',
	visits: 30,
	valueSum: 0,
	children: [
		{
			move: 'A',
			visits: 18,
			valueSum: 10,
			children: [
				{ move: 'A1', visits: 9, valueSum: 3, value: 3 },
				{ move: 'A2', visits: 9, valueSum: 7, value: 5 }
			]
		},
		{
			move: 'B',
			visits: 12,
			valueSum: 3,
			children: [
				{ move: 'B1', visits: 6, valueSum: 1, value: 1 },
				{ move: 'B2', visits: 6, valueSum: 2, value: 2 }
			]
		}
	]
});

export const Tool: TypeTool = {
	name: 'Alpha-Beta-UCT Search Demonstrator',
	slug: 'game-search/alpha-beta-uct',
	intro:
		'Order a finite game tree with UCT scores, then evaluate it using alpha–beta pruning.',
	tool: demonstrateAlphaBetaUct,
	i: [
		{
			example: DEFAULT_TREE,
			help: 'Every node needs move, visits, and valueSum. Leaves also need value; branches need children.',
			label: 'Search Tree',
			placeholder: 'JSON tree with search statistics',
			render: 'textarea',
			type: 'text',
			value: DEFAULT_TREE
		},
		{
			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: '1.41421356237',
			label: 'Exploration Constant',
			placeholder: 'Non-negative UCT exploration weight',
			type: 'number',
			value: Math.SQRT2
		},
		{
			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": 3, "orderedNodes": [] }',
			label: 'Search Result',
			placeholder:
				'UCT ordering and alpha–beta result will appear here...',
			render: 'textarea',
			type: 'text'
		}
	],
	cite: [
		{
			title: 'Monte Carlo tree search — Wikipedia',
			url: 'https://en.wikipedia.org/wiki/Monte_Carlo_tree_search'
		},
		{
			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-UCT Search Demonstrator.

References

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

Similar or alternative tools