nx_folkgame_sow_lib.nx source
↩ module page · 286 lines · 11717 B
1// nx_folkgame_sow_lib.nx -- THE SOW (MANCALA) FAMILY: pits, seeds, laps and capture.
2//
3// Seven registry rows run on this one engine: Oware, Kalah, Congkak, Omweso, Tsoro, Pallanguzhi and
4// Bao. It reuses nx_folkgame_lib's image, save/restore and terminal plumbing entirely -- cells are
5// pits and state[c] is a SEED COUNT rather than an occupancy code. There is no second parser and no
6// second position representation.
7//
8// THE INVARIANT THIS FAMILY IS PROVEN BY: sowing MOVES seeds, it never creates or destroys them.
9// Total seeds is conserved across every legal move from every reachable position, and that is
10// arithmetic rather than an opinion -- a sowing loop that is off by one anywhere breaks it, and no
11// implementation can satisfy it by accident. It is the sow family's answer to what the published
12// game-tree constant is for the align family.
13// HONEST DIFFERENCE, STATED NOT HIDDEN: unlike Tic-Tac-Toe's 255168 there is no cheap PUBLISHED
14// constant for these boards -- Oware was solved by Romein and Bal over 889 billion positions and
15// Kalah by Irving, Donkers and Uiterwijk, neither reproducible inside a gate. The external anchor
16// available to us is OpenSpiel's Oware, which its own table grades THOROUGHLY-TESTED, and wiring
17// that cross-check is the named rung. Until it lands, this family is proven by an exhaustive
18// invariant and NOT by an external count, and the gate says so in those words.
19//
20// license_tier: ORIGINAL No hw writes (Rule 26).
21import "nx_folkgame_lib.nx"
22
23// Scalar slots 0..7 are used by the shared image; 8 and 9 are this family's captured-seed counters.
24// They carry the score for boards with NO store pits (Oware), where captures leave the board
25// entirely. Where stores exist (Kalah) the store CELL is the score and these stay zero, so a seed is
26// counted in exactly one place and the conservation sum cannot double-count it.
27const FGS_S_SCORE1: i64 = 8
28const FGS_S_SCORE2: i64 = 9
29
30func fgs_perside(base: i64) -> i64 { let hd: *i64 = fg_hdr(base); return hd[FG_H_PERSIDE] }
31func fgs_has_store(base: i64) -> i64 { let hd: *i64 = fg_hdr(base); return hd[FG_H_STORE] }
32func fgs_store_cell(base: i64, side: i64) -> i64 {
33 let p: i64 = fgs_perside(base)
34 if side == 1 { return p + p }
35 return p + p + 1
36}
37// First and last pit index owned by a side, stores excluded.
38func fgs_first(base: i64, side: i64) -> i64 {
39 if side == 1 { return 0 }
40 return fgs_perside(base)
41}
42func fgs_last(base: i64, side: i64) -> i64 {
43 let p: i64 = fgs_perside(base)
44 if side == 1 { return p - 1 }
45 return p + p - 1
46}
47func fgs_owns(base: i64, side: i64, c: i64) -> i64 {
48 if c < fgs_first(base, side) { return 0 }
49 if c > fgs_last(base, side) { return 0 }
50 return 1
51}
52
53func fgs_score(base: i64, side: i64) -> i64 {
54 let sc: *i64 = fg_scal(base)
55 if fgs_has_store(base) == 1 { return fg_at(base, fgs_store_cell(base, side)) }
56 if side == 1 { return sc[FGS_S_SCORE1] }
57 return sc[FGS_S_SCORE2]
58}
59func fgs_add_score(base: i64, side: i64, n: i64) -> i64 {
60 let st: *i64 = fg_state(base)
61 let sc: *i64 = fg_scal(base)
62 if fgs_has_store(base) == 1 { let s: i64 = fgs_store_cell(base, side); st[s] = st[s] + n; return 0 }
63 if side == 1 { sc[FGS_S_SCORE1] = sc[FGS_S_SCORE1] + n; return 0 }
64 sc[FGS_S_SCORE2] = sc[FGS_S_SCORE2] + n
65 return 0
66}
67
68// THE CONSERVATION SUM: every seed on the board plus every seed captured. This must equal
69// perside*2*seeds at every position ever reached. It is the family's load-bearing tooth.
70func fgs_total(base: i64) -> i64 {
71 let hd: *i64 = fg_hdr(base)
72 var t: i64 = 0
73 var c: i64 = 0
74 while c < hd[FG_H_CELLS] { t = t + fg_at(base, c); c = c + 1 }
75 if fgs_has_store(base) == 0 {
76 let sc: *i64 = fg_scal(base)
77 t = t + sc[FGS_S_SCORE1] + sc[FGS_S_SCORE2]
78 }
79 return t
80}
81func fgs_expected(base: i64) -> i64 {
82 let hd: *i64 = fg_hdr(base)
83 return hd[FG_H_PERSIDE] * 2 * hd[FG_H_SEEDS]
84}
85
86func fgs_reset(base: i64) -> i64 {
87 let hd: *i64 = fg_hdr(base)
88 let st: *i64 = fg_state(base)
89 let sc: *i64 = fg_scal(base)
90 var c: i64 = 0
91 while c < hd[FG_H_CELLS] { st[c] = 0; c = c + 1 }
92 var p: i64 = 0
93 while p < hd[FG_H_PERSIDE] * 2 { st[p] = hd[FG_H_SEEDS]; p = p + 1 }
94 var k: i64 = 0
95 while k < FG_S_N { sc[k] = 0; k = k + 1 }
96 sc[FG_S_SIDE] = 1
97 sc[FG_S_PHASE] = FG_PH_MOVE
98 return 0
99}
100
101// The next cell a seed falls into, skipping the OPPONENT's store -- you never sow into their score.
102func fgs_next(base: i64, side: i64, c: i64) -> i64 {
103 let hd: *i64 = fg_hdr(base)
104 var n: i64 = c + 1
105 if n >= hd[FG_H_CELLS] { n = 0 }
106 if fgs_has_store(base) == 1 {
107 if n == fgs_store_cell(base, 3 - side) {
108 n = n + 1
109 if n >= hd[FG_H_CELLS] { n = 0 }
110 }
111 }
112 return n
113}
114
115// ---- SOWING. Returns the cell the LAST seed fell into, which is the only thing capture depends on.
116// Multi-lap (Bao, Omweso, Congkak) relays: if the last seed lands in a NON-EMPTY pit it is lifted
117// again and sowing continues. The relay is bounded by a derived ceiling rather than trusted to end:
118// a spec whose rules cycle would otherwise hang the engine, and an engine its own data can hang
119// measures nothing. Hitting the ceiling stops the relay and is visible as an unusually long move,
120// never as a silent truncation of the rules.
121func fgs_sow(base: i64, pit: i64) -> i64 {
122 let hd: *i64 = fg_hdr(base)
123 let st: *i64 = fg_state(base)
124 let side: i64 = fg_side(base)
125 var cur: i64 = pit
126 var n: i64 = st[pit]
127 st[pit] = 0
128 // Ceiling DERIVED from the position: no legal relay can exceed the total seeds in play times the
129 // number of cells, because each lap must move at least one seed into a distinct cell.
130 let ceiling: i64 = fgs_expected(base) * hd[FG_H_CELLS] + hd[FG_H_CELLS]
131 var steps: i64 = 0
132 var going: i64 = 1
133 while going == 1 {
134 while n > 0 {
135 cur = fgs_next(base, side, cur)
136 st[cur] = st[cur] + 1
137 n = n - 1
138 steps = steps + 1
139 }
140 going = 0
141 if hd[FG_H_LAP] == 1 {
142 if steps < ceiling {
143 var relay: i64 = 0
144 if st[cur] > 1 { relay = 1 }
145 if fgs_has_store(base) == 1 { if cur == fgs_store_cell(base, side) { relay = 0 } }
146 if relay == 1 { n = st[cur]; st[cur] = 0; going = 1 }
147 }
148 }
149 }
150 return cur
151}
152
153// Applies a move WITHOUT switching sides. Split out because the feeding rule below must look at the
154// position a move WOULD produce, and a probe that also advanced the turn could not be undone cleanly.
155func fgs_apply_raw(base: i64, pit: i64) -> i64 {
156 let hd: *i64 = fg_hdr(base)
157 let st: *i64 = fg_state(base)
158 let side: i64 = fg_side(base)
159 let opp: i64 = 3 - side
160 let last: i64 = fgs_sow(base, pit)
161 if hd[FG_H_CAPMODE] == FG_CAP_COUNT {
162 // Oware: the last seed leaves a pit in the OPPONENT's row holding capA or capB. Capture it,
163 // then walk BACKWARDS taking each preceding opponent pit that also holds one of those counts.
164 if fgs_owns(base, opp, last) == 1 {
165 var c: i64 = last
166 var taking: i64 = 1
167 while taking == 1 {
168 taking = 0
169 if fgs_owns(base, opp, c) == 1 {
170 var hit: i64 = 0
171 if st[c] == hd[FG_H_CAPA] { hit = 1 }
172 if st[c] == hd[FG_H_CAPB] { hit = 1 }
173 if hit == 1 {
174 fgs_add_score(base, side, st[c])
175 st[c] = 0
176 if c > 0 { c = c - 1; taking = 1 }
177 }
178 }
179 }
180 }
181 }
182 if hd[FG_H_CAPMODE] == FG_CAP_EMPTY {
183 // Kalah: the last seed lands in one of YOUR OWN pits that was empty, so it now holds exactly
184 // one. Take it together with the pit directly opposite.
185 if fgs_owns(base, side, last) == 1 {
186 if st[last] == 1 {
187 let p: i64 = hd[FG_H_PERSIDE]
188 let opposite: i64 = p + p - 1 - last
189 if st[opposite] > 0 {
190 fgs_add_score(base, side, st[opposite] + st[last])
191 st[opposite] = 0
192 st[last] = 0
193 }
194 }
195 }
196 }
197 return last
198}
199
200// Would this move leave the opponent with nothing to play? Oware's feeding rule forbids that while
201// any move that feeds them exists -- without it a player starves the opponent and the game stalls.
202func fgs_feeds(base: i64, pit: i64, snap: *i64) -> i64 {
203 let side: i64 = fg_side(base)
204 let opp: i64 = 3 - side
205 fg_save(base, snap)
206 fgs_apply_raw(base, pit)
207 var any: i64 = 0
208 var c: i64 = fgs_first(base, opp)
209 while c <= fgs_last(base, opp) {
210 if fg_at(base, c) > 0 { any = 1 }
211 c = c + 1
212 }
213 fg_load(base, snap)
214 return any
215}
216
217// Legal moves are the side's own non-empty pits, filtered by the feeding rule where the family has
218// one. THE FILTER IS CONDITIONAL ON ITS OWN RESULT: if no move feeds the opponent, every non-empty
219// pit is legal again -- a rule that could forbid every move would end the game by a technicality
220// rather than by play.
221func fgs_moves(base: i64, out: *i64, snap: *i64) -> i64 {
222 let hd: *i64 = fg_hdr(base)
223 let side: i64 = fg_side(base)
224 let sc: *i64 = fg_scal(base)
225 var n: i64 = 0
226 if sc[FG_S_WINNER] != 0 { return 0 }
227 var feeding: i64 = 0
228 if hd[FG_H_CAPMODE] == FG_CAP_COUNT {
229 var c0: i64 = fgs_first(base, side)
230 while c0 <= fgs_last(base, side) {
231 if fg_at(base, c0) > 0 { if fgs_feeds(base, c0, snap) == 1 { feeding = 1 } }
232 c0 = c0 + 1
233 }
234 }
235 var c: i64 = fgs_first(base, side)
236 while c <= fgs_last(base, side) {
237 if fg_at(base, c) > 0 {
238 var ok: i64 = 1
239 if feeding == 1 { if fgs_feeds(base, c, snap) == 0 { ok = 0 } }
240 if ok == 1 { out[n] = c; n = n + 1 }
241 }
242 c = c + 1
243 }
244 return n
245}
246
247func fgs_apply(base: i64, pit: i64, snap: *i64) -> i64 {
248 let hd: *i64 = fg_hdr(base)
249 let sc: *i64 = fg_scal(base)
250 let side: i64 = fg_side(base)
251 let last: i64 = fgs_apply_raw(base, pit)
252 sc[FG_S_PLIES] = sc[FG_S_PLIES] + 1
253 // Kalah grants another turn when the last seed lands in your own store. Where there is no store
254 // the condition cannot arise, so no family without one needs to opt out of it.
255 var again: i64 = 0
256 if fgs_has_store(base) == 1 { if last == fgs_store_cell(base, side) { again = 1 } }
257 if again == 0 { sc[FG_S_SIDE] = 3 - side }
258 return last
259}
260
261// A side with no seeds ends the game; the remaining seeds go to the player still holding them, which
262// is the convention both Oware and Kalah use. The winner is whoever captured more, and an equal
263// split is a DRAW rather than a win for either.
264func fgs_terminal(base: i64, snap: *i64, scratch: *i64) -> i64 {
265 let sc: *i64 = fg_scal(base)
266 if sc[FG_S_WINNER] == 1 { return FG_T_P1 }
267 if sc[FG_S_WINNER] == 2 { return FG_T_P2 }
268 let n: i64 = fgs_moves(base, scratch, snap)
269 if n > 0 { return FG_T_ONGOING }
270 // Sweep whatever is left on the board to its owner before scoring.
271 let st: *i64 = fg_state(base)
272 var s: i64 = 1
273 while s <= 2 {
274 var c: i64 = fgs_first(base, s)
275 while c <= fgs_last(base, s) {
276 if st[c] > 0 { fgs_add_score(base, s, st[c]); st[c] = 0 }
277 c = c + 1
278 }
279 s = s + 1
280 }
281 let a: i64 = fgs_score(base, 1)
282 let b: i64 = fgs_score(base, 2)
283 if a > b { return FG_T_P1 }
284 if b > a { return FG_T_P2 }
285 return FG_T_DRAW
286}