nx_search_advanced_gate.nx source

1import "nx_gate_gn.nx" 2import "nx_gate_base.nx" 3// nx_search_advanced_gate.nx -- ADVANCED SEARCH: MINIMAX with ALPHA-BETA pruning (adversarial game AI) + BEAM search 4// (bounded best-first) (operator: fill the mechanistic-AI search gap beyond A*). Minimax computes the optimal move in a 5// max-of-min game tree; alpha-beta proves the same value while EVALUATING FEWER leaves. Beam search keeps the top-k 6// frontier, finding solutions greedy (k=1) misses. Pure integer, NO LLM. 7// T0 GAME TREE: root MAX over 3 MIN children, each 3 leaves (9 leaves). 8// T1 MINIMAX: value = max(min of each child) = 3, best move = child 0. 9// T2 ALPHA-BETA: same value 3 while evaluating only 6 of 9 leaves (3 pruned) -- provably-correct pruning. 10// T3 BEAM TREE: a greedy trap -- the best layer-1 node does NOT lead to the best leaf. 11// T4 BEAM vs GREEDY: beam width 2 finds leaf 21; greedy width 1 settles for 12. 12// T5 = minimax+alpha-beta and beam search, mechanistic, no LLM. 13// license_tier: ORIGINAL 14import "nx_syscalls.nx" 15 16func grow(name: *u8, ok: i64) -> i64 { if ok==1 { gw(" PASS " as *u8) } else { gw(" FAIL " as *u8) } gw(name); gw(" 17" as *u8); return ok } 18func imin(a: i64, b: i64) -> i64 { if a<b { return a } return b } 19func imax(a: i64, b: i64) -> i64 { if a>b { return a } return b } 20 21func main() -> i64 { 22 gw("=== nx_search_advanced_gate: minimax + alpha-beta + beam search, no LLM ===\n" as *u8) 23 var pass: i64=0; var total: i64=0 24 // game tree: 3 MIN children x 3 leaves. leaves[child*3+leaf]. 25 let L: *i64=sys_mmap(64) as *i64 26 L[0]=3; L[1]=5; L[2]=6; L[3]=1; L[4]=8; L[5]=4; L[6]=9; L[7]=2; L[8]=7 27 28 total=total+1; pass=pass+1 29 gw(" [PASS] T0 GAME TREE: root MAX / 3 MIN children / leaves [[3,5,6],[1,8,4],[9,2,7]]\n" as *u8) 30 31 // T1 plain minimax: root = max over children of (min of leaves). 32 var rootval: i64=0-999; var bestmove: i64=0-1; var c: i64=0 33 while c<3 { var cv: i64=999; var j: i64=0; while j<3 { cv=imin(cv, L[c*3+j]); j=j+1 } if cv>rootval { rootval=cv; bestmove=c } c=c+1 } 34 total=total+1; if rootval==3 { if bestmove==0 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) } } else { gw(" [FAIL] " as *u8) } 35 gw("T1 MINIMAX: value=" as *u8); gn(rootval); gw(" (max of mins 3,1,2), best move=child " as *u8); gn(bestmove); gw("\n" as *u8) 36 37 // T2 alpha-beta: same value, fewer leaves. 38 var alpha: i64=0-999; var evaluated: i64=0; var abval: i64=0-999; c=0 39 while c<3 { 40 var cv: i64=999; var j: i64=0; var cut: i64=0 41 while j<3 { if cut==0 { evaluated=evaluated+1; cv=imin(cv,L[c*3+j]); if cv<=alpha { cut=1 } } j=j+1 } // MIN node: prune when cv<=alpha 42 abval=imax(abval,cv); alpha=imax(alpha,cv); c=c+1 43 } 44 total=total+1; if abval==rootval { if evaluated<9 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) } } else { gw(" [FAIL] " as *u8) } 45 gw("T2 ALPHA-BETA: value=" as *u8); gn(abval); gw(" (same), evaluated " as *u8); gn(evaluated); gw("/9 leaves (" as *u8); gn(9-evaluated); gw(" pruned)\n" as *u8) 46 47 // T3+T4 beam search: layer-1 nodes with heuristics, each 2 leaves. 48 let H: *i64=sys_mmap(32) as *i64; H[0]=10; H[1]=5 // heuristic of layer-1 nodes 49 let BL: *i64=sys_mmap(32) as *i64; BL[0]=11; BL[1]=12; BL[2]=20; BL[3]=21 // node0 leaves 11,12 ; node1 leaves 20,21 50 total=total+1; pass=pass+1 51 gw(" [PASS] T3 BEAM TREE: node0 (h=10) -> leaves 11,12 ; node1 (h=5) -> leaves 20,21 (best leaf 21 is under the WORSE-heuristic node)\n" as *u8) 52 53 // greedy width 1: pick best-heuristic node, expand only it. 54 var gnode: i64=0; if H[1]>H[0] { gnode=1 } 55 var greedy_best: i64=imax(BL[gnode*2+0], BL[gnode*2+1]) 56 // beam width 2: keep both nodes, expand all leaves. 57 var beam_best: i64=0; var i: i64=0; while i<4 { beam_best=imax(beam_best, BL[i]); i=i+1 } 58 total=total+1; if beam_best==21 { if greedy_best==12 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) } } else { gw(" [FAIL] " as *u8) } 59 gw("T4 BEAM vs GREEDY: beam(width 2) best leaf=" as *u8); gn(beam_best); gw(" ; greedy(width 1) settles for " as *u8); gn(greedy_best); gw(" (beam explores past the greedy trap)\n" as *u8) 60 61 total=total+1; if abval==rootval { if beam_best>greedy_best { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) } } else { gw(" [FAIL] " as *u8) } 62 gw("T5 ADVANCED SEARCH: minimax+alpha-beta (correct value, fewer leaves) and beam (beats greedy), no LLM\n" as *u8) 63 64 gw("\n ADVANCED SEARCH: MINIMAX found the optimal move (value 3) in the game tree; ALPHA-BETA proved the same value evaluating only\n" as *u8) 65 gw(" 6/9 leaves (correct pruning -- the basis of game AI). BEAM search (width 2) kept enough frontier to find leaf 21 where greedy\n" as *u8) 66 gw(" (width 1) was trapped at 12. Pure integer, NO LLM. Joins A* in the search row. Next: CSP arc-consistency + STRIPS planning.\n" as *u8) 67 gw("ADVANCED-SEARCH verdict=" as *u8) 68 if pass==total { gw("GREEN passes=" as *u8); gn(pass); gw("/" as *u8); gn(total); gw(" -- minimax+alpha-beta + beam search, no LLM\n" as *u8); sys_exit(0); return 0 } 69 gw("RED passes=" as *u8); gn(pass); gw("/" as *u8); gn(total); gw("\n" as *u8); sys_exit(1); return 1 70}