Bookmark this: tool.io/game-search/alpha-beta-uct/source-code
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.