nx_tictactoe.nx source
↩ module page · 456 lines · 15541 B
1// nx_tictactoe.nx -- bits-up source-of-truth for C0 of the bootstrap-to-generative
2// trajectory (NISHI_GAME_ENGINE_HONESTY_AND_MISSIONS_ROADMAP.md §19.1 stage C0).
3//
4// The smallest joy-bearing game on the ladder. Validates the five honesty gates
5// (G1 smokes + G2 ≥60s real playtest + G3 benchmark + G4 bits-budget + G5 joy)
6// at minimum complexity before scaling to checkers/chess/voxels/minecraftclone.
7//
8// PURE NishiLang. No third-party in the build path. No TypeScript scaffold.
9// Browser delivery (if needed for G2 family playtest) generated from this source
10// via nxc2 codegen on the last step IF the family needs to playtest in a browser
11// tab. Per [[feedback-no-third-party-in-build-path-source-of-truth-is-bits-up]].
12//
13// State layout: a heap block of 12 i64 cells holds one game state. Pure data,
14// no globals, no GC required — all allocations happen at game start; minimax
15// mutates and undoes in place to avoid recursive allocation.
16//
17// [0..8] 9 board cells: NX_TTT_EMPTY=0, NX_TTT_X=1, NX_TTT_O=2
18// [9] whose turn: NX_TTT_X or NX_TTT_O
19// [10] outcome kind: NX_TTT_ONGOING=0, NX_TTT_WIN=1, NX_TTT_DRAW=2
20// [11] winning side: NX_TTT_X, NX_TTT_O, or 0 if no win yet
21//
22// genealogy_id: nx_tictactoe_v1_2026_05_19
23// lineage_id: abstract_classic_game_state_machine
24// license: operator-as-sole-author (escalated to §23.1 of roadmap)
25// complexity: O(1) per move; O(8.6) for perfect minimax (tic-tac-toe game tree)
26
27// nx_safety_envelope:
28// intended_use: game_state_machine_c0_bootstrap
29// sil_target: SIL1
30// evidence: [game_theory_solved_3x3 + minimax_optimal + 12_unit_assertions]
31// verdict: NOT_YET_EVALUATED
32
33import "nx_syscalls.nx"
34import "nx_tier.nx"
35import "nx_prng.nx"
36const NX_MAGIC_1099511628211: i64 = 1099511628211
37
38// ===== State layout offsets ============================================
39
40const NX_TTT_OFF_CELL_0: nx_int = 0
41const NX_TTT_OFF_TURN: nx_int = 9
42const NX_TTT_OFF_OUTCOME: nx_int = 10
43const NX_TTT_OFF_WINNER: nx_int = 11
44const NX_TTT_GAME_CELLS: nx_int = 12 // hash domain ends here
45// Config cells (UI preferences) -- live in the same block for host convenience
46// but do NOT participate in state_hash; determinism of game state is preserved
47// across config changes.
48const NX_TTT_OFF_PLAYER_SIDE: nx_int = 12 // NX_TTT_X or NX_TTT_O
49const NX_TTT_OFF_OPPONENT: nx_int = 13 // -1 = human-vs-human; else NX_TTT_AI_*
50const NX_TTT_OFF_RESERVED: nx_int = 14
51const NX_TTT_STATE_CELLS: nx_int = 15
52
53// ===== Cell values =====================================================
54
55const NX_TTT_EMPTY: nx_int = 0
56const NX_TTT_X: nx_int = 1
57const NX_TTT_O: nx_int = 2
58
59// ===== Outcome kinds ===================================================
60
61const NX_TTT_ONGOING: nx_int = 0
62const NX_TTT_WIN: nx_int = 1
63const NX_TTT_DRAW: nx_int = 2
64
65// ===== AI difficulty tiers =============================================
66
67const NX_TTT_AI_EASY: nx_int = 0 // random legal move
68const NX_TTT_AI_MEDIUM: nx_int = 1 // one-ply look-ahead (win / block / center / random)
69const NX_TTT_AI_PERFECT: nx_int = 2 // minimax with alpha-beta (never loses)
70
71// ===== Allocation ======================================================
72
73func nx_ttt_new(first_mover: nx_int) -> *i64 {
74 let s: *i64 = (sys_mmap(NX_TTT_STATE_CELLS * 8)) as *i64
75 var i: nx_int = 0
76 while i < 9 {
77 s[i] = NX_TTT_EMPTY
78 i = i + 1
79 }
80 var fm: nx_int = NX_TTT_X
81 if first_mover == NX_TTT_O { fm = NX_TTT_O }
82 s[NX_TTT_OFF_TURN] = fm
83 s[NX_TTT_OFF_OUTCOME] = NX_TTT_ONGOING
84 s[NX_TTT_OFF_WINNER] = 0
85 // Default config: player plays X first; opponent = perfect minimax.
86 s[NX_TTT_OFF_PLAYER_SIDE] = NX_TTT_X
87 s[NX_TTT_OFF_OPPONENT] = NX_TTT_AI_PERFECT
88 s[NX_TTT_OFF_RESERVED] = 0
89 return s
90}
91
92// ===== Accessors =======================================================
93
94func nx_ttt_cell(s: *i64, idx: nx_int) -> nx_int {
95 if idx < 0 { return -1 }
96 if idx > 8 { return -1 }
97 return s[idx]
98}
99
100func nx_ttt_turn(s: *i64) -> nx_int {
101 return s[NX_TTT_OFF_TURN]
102}
103
104func nx_ttt_outcome(s: *i64) -> nx_int {
105 return s[NX_TTT_OFF_OUTCOME]
106}
107
108func nx_ttt_winner(s: *i64) -> nx_int {
109 return s[NX_TTT_OFF_WINNER]
110}
111
112func nx_ttt_other(side: nx_int) -> nx_int {
113 if side == NX_TTT_X { return NX_TTT_O }
114 return NX_TTT_X
115}
116
117// ===== Move legality ===================================================
118
119func nx_ttt_is_legal(s: *i64, idx: nx_int) -> nx_int {
120 if s[NX_TTT_OFF_OUTCOME] != NX_TTT_ONGOING { return 0 }
121 if idx < 0 { return 0 }
122 if idx > 8 { return 0 }
123 if s[idx] != NX_TTT_EMPTY { return 0 }
124 return 1
125}
126
127// Count legal moves remaining. Used by AI for branching.
128func nx_ttt_legal_count(s: *i64) -> nx_int {
129 if s[NX_TTT_OFF_OUTCOME] != NX_TTT_ONGOING { return 0 }
130 var n: nx_int = 0
131 var i: nx_int = 0
132 while i < 9 {
133 if s[i] == NX_TTT_EMPTY { n = n + 1 }
134 i = i + 1
135 }
136 return n
137}
138
139// ===== Win-line evaluation =============================================
140//
141// 8 win lines: 3 rows + 3 cols + 2 diagonals. Open-coded for clarity.
142// Updates s[OUTCOME] and s[WINNER] based on current cells.
143func nx_ttt_evaluate(s: *i64) {
144 // Helper macro-pattern: check (a,b,c) all equal and non-empty.
145 let c0: nx_int = s[0]
146 let c1: nx_int = s[1]
147 let c2: nx_int = s[2]
148 let c3: nx_int = s[3]
149 let c4: nx_int = s[4]
150 let c5: nx_int = s[5]
151 let c6: nx_int = s[6]
152 let c7: nx_int = s[7]
153 let c8: nx_int = s[8]
154
155 // Row 0
156 if c0 != NX_TTT_EMPTY {
157 if c0 == c1 {
158 if c1 == c2 {
159 s[NX_TTT_OFF_OUTCOME] = NX_TTT_WIN
160 s[NX_TTT_OFF_WINNER] = c0
161 return
162 }
163 }
164 }
165 // Row 1
166 if c3 != NX_TTT_EMPTY {
167 if c3 == c4 {
168 if c4 == c5 {
169 s[NX_TTT_OFF_OUTCOME] = NX_TTT_WIN
170 s[NX_TTT_OFF_WINNER] = c3
171 return
172 }
173 }
174 }
175 // Row 2
176 if c6 != NX_TTT_EMPTY {
177 if c6 == c7 {
178 if c7 == c8 {
179 s[NX_TTT_OFF_OUTCOME] = NX_TTT_WIN
180 s[NX_TTT_OFF_WINNER] = c6
181 return
182 }
183 }
184 }
185 // Col 0
186 if c0 != NX_TTT_EMPTY {
187 if c0 == c3 {
188 if c3 == c6 {
189 s[NX_TTT_OFF_OUTCOME] = NX_TTT_WIN
190 s[NX_TTT_OFF_WINNER] = c0
191 return
192 }
193 }
194 }
195 // Col 1
196 if c1 != NX_TTT_EMPTY {
197 if c1 == c4 {
198 if c4 == c7 {
199 s[NX_TTT_OFF_OUTCOME] = NX_TTT_WIN
200 s[NX_TTT_OFF_WINNER] = c1
201 return
202 }
203 }
204 }
205 // Col 2
206 if c2 != NX_TTT_EMPTY {
207 if c2 == c5 {
208 if c5 == c8 {
209 s[NX_TTT_OFF_OUTCOME] = NX_TTT_WIN
210 s[NX_TTT_OFF_WINNER] = c2
211 return
212 }
213 }
214 }
215 // Diagonal 0-4-8
216 if c0 != NX_TTT_EMPTY {
217 if c0 == c4 {
218 if c4 == c8 {
219 s[NX_TTT_OFF_OUTCOME] = NX_TTT_WIN
220 s[NX_TTT_OFF_WINNER] = c0
221 return
222 }
223 }
224 }
225 // Diagonal 2-4-6
226 if c2 != NX_TTT_EMPTY {
227 if c2 == c4 {
228 if c4 == c6 {
229 s[NX_TTT_OFF_OUTCOME] = NX_TTT_WIN
230 s[NX_TTT_OFF_WINNER] = c2
231 return
232 }
233 }
234 }
235 // No winner yet — is it a draw? If any cell is empty, still ongoing.
236 var i: nx_int = 0
237 while i < 9 {
238 if s[i] == NX_TTT_EMPTY {
239 s[NX_TTT_OFF_OUTCOME] = NX_TTT_ONGOING
240 s[NX_TTT_OFF_WINNER] = 0
241 return
242 }
243 i = i + 1
244 }
245 s[NX_TTT_OFF_OUTCOME] = NX_TTT_DRAW
246 s[NX_TTT_OFF_WINNER] = 0
247}
248
249// ===== Apply / undo (in-place; pure-function semantics preserved by caller) =====
250//
251// Returns 1 if applied, 0 if illegal (no mutation on illegal).
252// On success, mutates s. Caller is responsible for snapshotting if undo needed.
253func nx_ttt_try_apply(s: *i64, idx: nx_int) -> nx_int {
254 if nx_ttt_is_legal(s, idx) == 0 { return 0 }
255 let me: nx_int = s[NX_TTT_OFF_TURN]
256 s[idx] = me
257 s[NX_TTT_OFF_TURN] = nx_ttt_other(me)
258 nx_ttt_evaluate(s)
259 return 1
260}
261
262// Reverse a move. Caller must pass the previous (outcome, winner) snapshot
263// captured before nx_ttt_try_apply. This is the minimax-friendly path: no
264// allocation, no GC.
265func nx_ttt_undo(s: *i64, idx: nx_int, prev_outcome: nx_int, prev_winner: nx_int) {
266 let me: nx_int = s[idx]
267 s[idx] = NX_TTT_EMPTY
268 s[NX_TTT_OFF_TURN] = me
269 s[NX_TTT_OFF_OUTCOME] = prev_outcome
270 s[NX_TTT_OFF_WINNER] = prev_winner
271}
272
273// ===== State hash (for replay verification + CAS-root composition) =====
274//
275// Deterministic 64-bit fingerprint. Mixes cells + turn + outcome via a
276// FNV-1a-style multiply-and-xor chain. Same state -> same hash; different
277// states -> different hash with probability ~1 - 2^-58. Not crypto;
278// the substrate's BLAKE3 primitive is the real CAS root in production.
279func nx_ttt_state_hash(s: *i64) -> i64 {
280 var h: i64 = 14695981039346656037 as i64 // FNV offset basis (truncated)
281 let prime: i64 = NX_MAGIC_1099511628211 as i64 // FNV prime
282 var i: nx_int = 0
283 // Hash only the game-state cells (NX_TTT_GAME_CELLS = 12). Config cells
284 // (player_side / opponent) are UI preferences and must NOT change the
285 // hash -- otherwise determinism tests break across difficulty changes.
286 while i < NX_TTT_GAME_CELLS {
287 h = h ^ (s[i] as i64)
288 h = h * prime
289 i = i + 1
290 }
291 return h
292}
293
294// ===== AI: easy tier (uniform random over legal moves) =================
295
296func nx_ttt_pick_easy(s: *i64, prng_state: *i64) -> nx_int {
297 let n: nx_int = nx_ttt_legal_count(s)
298 if n <= 0 { return -1 }
299 let target: nx_int = nx_prng_range(prng_state, n as i64) as nx_int
300 var seen: nx_int = 0
301 var i: nx_int = 0
302 while i < 9 {
303 if s[i] == NX_TTT_EMPTY {
304 if seen == target { return i }
305 seen = seen + 1
306 }
307 i = i + 1
308 }
309 return -1
310}
311
312// ===== AI: medium tier (one-ply look-ahead, center-preference) =========
313
314func nx_ttt_pick_medium(s: *i64, side: nx_int) -> nx_int {
315 if s[NX_TTT_OFF_OUTCOME] != NX_TTT_ONGOING { return -1 }
316 let opp: nx_int = nx_ttt_other(side)
317 // 1) Immediate win
318 var i: nx_int = 0
319 while i < 9 {
320 if s[i] == NX_TTT_EMPTY {
321 s[i] = side
322 // Inline win-check for cell i. Simpler than running full evaluate.
323 let prev_outcome: nx_int = s[NX_TTT_OFF_OUTCOME]
324 let prev_winner: nx_int = s[NX_TTT_OFF_WINNER]
325 nx_ttt_evaluate(s)
326 let won: nx_int = s[NX_TTT_OFF_WINNER]
327 s[i] = NX_TTT_EMPTY
328 s[NX_TTT_OFF_OUTCOME] = prev_outcome
329 s[NX_TTT_OFF_WINNER] = prev_winner
330 if won == side { return i }
331 }
332 i = i + 1
333 }
334 // 2) Block immediate opponent win
335 i = 0
336 while i < 9 {
337 if s[i] == NX_TTT_EMPTY {
338 s[i] = opp
339 let prev_outcome: nx_int = s[NX_TTT_OFF_OUTCOME]
340 let prev_winner: nx_int = s[NX_TTT_OFF_WINNER]
341 nx_ttt_evaluate(s)
342 let won: nx_int = s[NX_TTT_OFF_WINNER]
343 s[i] = NX_TTT_EMPTY
344 s[NX_TTT_OFF_OUTCOME] = prev_outcome
345 s[NX_TTT_OFF_WINNER] = prev_winner
346 if won == opp { return i }
347 }
348 i = i + 1
349 }
350 // 3) Prefer center, then corners, then edges
351 if s[4] == NX_TTT_EMPTY { return 4 }
352 if s[0] == NX_TTT_EMPTY { return 0 }
353 if s[2] == NX_TTT_EMPTY { return 2 }
354 if s[6] == NX_TTT_EMPTY { return 6 }
355 if s[8] == NX_TTT_EMPTY { return 8 }
356 if s[1] == NX_TTT_EMPTY { return 1 }
357 if s[3] == NX_TTT_EMPTY { return 3 }
358 if s[5] == NX_TTT_EMPTY { return 5 }
359 if s[7] == NX_TTT_EMPTY { return 7 }
360 return -1
361}
362
363// ===== AI: perfect tier (minimax with alpha-beta) ======================
364//
365// Tic-tac-toe is solved: with perfect play from both sides, the game is
366// a draw. Perfect AI never loses. Score signature: positive favors
367// the maximizing side; subtracting depth rewards faster wins / slower
368// losses, which makes the AI choose a quick win or a delaying loss
369// rather than a random equivalent.
370//
371// Returns: score from maximizing_side's POV.
372func nx_ttt_minimax(s: *i64, maximizing_side: nx_int, depth: nx_int,
373 alpha: nx_int, beta: nx_int) -> nx_int {
374 let outcome: nx_int = s[NX_TTT_OFF_OUTCOME]
375 if outcome == NX_TTT_WIN {
376 let w: nx_int = s[NX_TTT_OFF_WINNER]
377 if w == maximizing_side { return 10 - depth }
378 return -10 + depth
379 }
380 if outcome == NX_TTT_DRAW { return 0 }
381
382 let turn: nx_int = s[NX_TTT_OFF_TURN]
383 var a: nx_int = alpha
384 var b: nx_int = beta
385 var i: nx_int = 0
386 if turn == maximizing_side {
387 var best: nx_int = -1000
388 while i < 9 {
389 if s[i] == NX_TTT_EMPTY {
390 let prev_outcome: nx_int = s[NX_TTT_OFF_OUTCOME]
391 let prev_winner: nx_int = s[NX_TTT_OFF_WINNER]
392 nx_ttt_try_apply(s, i)
393 let v: nx_int = nx_ttt_minimax(s, maximizing_side, depth + 1, a, b)
394 nx_ttt_undo(s, i, prev_outcome, prev_winner)
395 if v > best { best = v }
396 if best > a { a = best }
397 if a >= b {
398 return best
399 }
400 }
401 i = i + 1
402 }
403 return best
404 }
405 // minimizing side
406 var best2: nx_int = 1000
407 while i < 9 {
408 if s[i] == NX_TTT_EMPTY {
409 let prev_outcome: nx_int = s[NX_TTT_OFF_OUTCOME]
410 let prev_winner: nx_int = s[NX_TTT_OFF_WINNER]
411 nx_ttt_try_apply(s, i)
412 let v: nx_int = nx_ttt_minimax(s, maximizing_side, depth + 1, a, b)
413 nx_ttt_undo(s, i, prev_outcome, prev_winner)
414 if v < best2 { best2 = v }
415 if best2 < b { b = best2 }
416 if a >= b {
417 return best2
418 }
419 }
420 i = i + 1
421 }
422 return best2
423}
424
425// Top-level perfect-play move selection. Returns the index that maximizes
426// the score for `side`. Ties broken by lower index (deterministic).
427func nx_ttt_pick_perfect(s: *i64, side: nx_int) -> nx_int {
428 if s[NX_TTT_OFF_OUTCOME] != NX_TTT_ONGOING { return -1 }
429 var best_score: nx_int = -1000
430 var best_move: nx_int = -1
431 var i: nx_int = 0
432 while i < 9 {
433 if s[i] == NX_TTT_EMPTY {
434 let prev_outcome: nx_int = s[NX_TTT_OFF_OUTCOME]
435 let prev_winner: nx_int = s[NX_TTT_OFF_WINNER]
436 nx_ttt_try_apply(s, i)
437 let v: nx_int = nx_ttt_minimax(s, side, 1, -1000, 1000)
438 nx_ttt_undo(s, i, prev_outcome, prev_winner)
439 if v > best_score {
440 best_score = v
441 best_move = i
442 }
443 }
444 i = i + 1
445 }
446 return best_move
447}
448
449// ===== Dispatcher ======================================================
450
451func nx_ttt_pick(s: *i64, side: nx_int, difficulty: nx_int, prng_state: *i64) -> nx_int {
452 if difficulty == NX_TTT_AI_EASY { return nx_ttt_pick_easy(s, prng_state) }
453 if difficulty == NX_TTT_AI_MEDIUM { return nx_ttt_pick_medium(s, side) }
454 if difficulty == NX_TTT_AI_PERFECT { return nx_ttt_pick_perfect(s, side) }
455 return -1
456}