-rw-r--r-- | noncore/games/go/killable.c | 373 |
1 files changed, 373 insertions, 0 deletions
diff --git a/noncore/games/go/killable.c b/noncore/games/go/killable.c new file mode 100644 index 0000000..3ed2d2e --- a/dev/null +++ b/noncore/games/go/killable.c | |||
@@ -0,0 +1,373 @@ | |||
1 | /* By Stoney Ballard */ | ||
2 | /* Ported from Pascal to C by Todd R. Johnson */ | ||
3 | |||
4 | #include "go.h" | ||
5 | #include "goplayutils.h" | ||
6 | #include "amigo.h" | ||
7 | |||
8 | extern intBoard bord, groupIDs; | ||
9 | extern boolBoard legal; | ||
10 | extern groupRec gList[maxGroup]; | ||
11 | extern short gMap[maxGroup], adjInAtari, adj2Libs, playMark, treeLibLim, | ||
12 | utilPlayLevel, killFlag, depthLimit, dbStop, showTrees; | ||
13 | extern pointList plist2; | ||
14 | |||
15 | /* | ||
16 | returns true if the group (at x, y) is killable. | ||
17 | if so, returns the point to play at in killx, killy. | ||
18 | */ | ||
19 | |||
20 | short me, him, depth, i, j, tryCount, tl, topMark, tkMark, mark2; | ||
21 | char sChar; | ||
22 | sPointList lList, dList; | ||
23 | point tp; | ||
24 | short libList[maxSPoint+1]; | ||
25 | short esc; | ||
26 | |||
27 | short mtNbrs(x, y) | ||
28 | short x, y; | ||
29 | { /* mtNbrs */ | ||
30 | short n = 0; | ||
31 | if ((x > 0) && (bord[x - 1][y] == 0)) | ||
32 | n = n + 1; | ||
33 | if ((x < maxPoint) && (bord[x + 1][y] == 0)) | ||
34 | n = n + 1; | ||
35 | if ((y > 0) && (bord[x][y - 1] == 0)) | ||
36 | n = n + 1; | ||
37 | if ((y < maxPoint) && (bord[x][y + 1] == 0)) | ||
38 | n = n + 1; | ||
39 | return n; | ||
40 | } /* mtNbrs */ | ||
41 | |||
42 | short killTree(tx, ty, gx, gy, escape, tkMark) | ||
43 | short tx, ty, gx, gy, *escape, tkMark; | ||
44 | { /* killTree */ | ||
45 | short curMark, mark2, mark3, i, j, k, tl, dStart, result; | ||
46 | sPointList lList1, lList2; | ||
47 | short libList[maxSPoint+1]; | ||
48 | point tp; | ||
49 | short esc = FALSE; | ||
50 | tryCount = tryCount + 1; | ||
51 | if (tryCount > tryLimit) | ||
52 | { | ||
53 | undoTo(tkMark); | ||
54 | /* for (i = 1; i <= depth - 1; i++) | ||
55 | { | ||
56 | sClearChar(sChar, rXor); | ||
57 | } */ | ||
58 | depth = 1; | ||
59 | return FALSE; | ||
60 | } | ||
61 | /* write(sChar); */ | ||
62 | depth = depth + 1; | ||
63 | curMark = playMark; | ||
64 | tryPlay(tx, ty, me); /* try my move */ | ||
65 | pause(); | ||
66 | if (gList[gMap[groupIDs[tx][ty]]].libC == 0) /* I'm dead */ | ||
67 | { | ||
68 | result = FALSE; | ||
69 | goto one; | ||
70 | } | ||
71 | else if (killFlag) /* I killed something of his */ | ||
72 | { | ||
73 | result = TRUE; | ||
74 | goto one; | ||
75 | } | ||
76 | else if (gList[gMap[groupIDs[gx][gy]]].libC > treeLibLim) /* safe */ | ||
77 | { | ||
78 | result = FALSE; | ||
79 | goto one; | ||
80 | } | ||
81 | else | ||
82 | { | ||
83 | sSpanGroup(gx, gy, &lList1); /* find his liberties */ | ||
84 | if (gList[gMap[groupIDs[tx][ty]]].libC == 1) /* he can kill me */ | ||
85 | { | ||
86 | if (lList1.indx < maxSPoint) /* add that option to his list */ | ||
87 | { | ||
88 | lList1.indx = lList1.indx + 1; | ||
89 | spanGroup(tx, ty, &plist2); /* find my liberty */ | ||
90 | lList1.p[lList1.indx].px = plist2.p[1].px; | ||
91 | lList1.p[lList1.indx].py = plist2.p[1].py; | ||
92 | } | ||
93 | else | ||
94 | { | ||
95 | result = FALSE; | ||
96 | goto one; | ||
97 | } | ||
98 | } | ||
99 | for (i = 1; i <= maxSPoint; i++) /* init liblist so diags can be marked */ | ||
100 | libList[i] = -1; | ||
101 | if ((utilPlayLevel > 4) && | ||
102 | (lList1.indx > 1) && | ||
103 | (gList[gMap[groupIDs[gx][gy]]].libC > 1)) /* try diags */ | ||
104 | { | ||
105 | listDiags(gx, gy, &dList); | ||
106 | j = 0; | ||
107 | i = lList1.indx; | ||
108 | while ((j < dList.indx) && | ||
109 | (i < maxSPoint)) | ||
110 | { | ||
111 | j = j + 1; | ||
112 | i = i + 1; | ||
113 | libList[i] = 0; /* mark this as a diag */ | ||
114 | lList1.p[i].px = dList.p[j].px; | ||
115 | lList1.p[i].py = dList.p[j].py; | ||
116 | } | ||
117 | lList1.indx = i; | ||
118 | } | ||
119 | if (lList1.indx > 1) /* sort by decreasing lib count */ | ||
120 | { | ||
121 | for (i = 1; i <= lList1.indx; i++) | ||
122 | if (libList[i] != 0) /* diags are tried last */ | ||
123 | { | ||
124 | mark2 = playMark; | ||
125 | tryPlay(lList1.p[i].px, lList1.p[i].py, him); | ||
126 | libList[i] = gList[gMap[groupIDs[gx][gy]]].libC; | ||
127 | if ((libList[i] > treeLibLim) || | ||
128 | ((libList[i] > (depthLimit - depth)) && | ||
129 | (libList[i] > 2))) | ||
130 | { | ||
131 | *escape = TRUE; | ||
132 | result = FALSE; | ||
133 | goto one; | ||
134 | } | ||
135 | undoTo(mark2); | ||
136 | } | ||
137 | for (i = 1; i <= lList1.indx - 1; i++) | ||
138 | for (j = i + 1; j <= lList1.indx; j++) | ||
139 | if (libList[i] < libList[j]) | ||
140 | { | ||
141 | tl = libList[i]; | ||
142 | libList[i] = libList[j]; | ||
143 | libList[j] = tl; | ||
144 | tp = lList1.p[i]; | ||
145 | lList1.p[i] = lList1.p[j]; | ||
146 | lList1.p[j] = tp; | ||
147 | } | ||
148 | } | ||
149 | for (i = 1; i <= lList1.indx + 1; i++) /* try his responses */ | ||
150 | { | ||
151 | mark2 = playMark; | ||
152 | if (i <= lList1.indx) /* try his move */ | ||
153 | { | ||
154 | tryPlay(lList1.p[i].px, lList1.p[i].py, him); /* play his response */ | ||
155 | pause(); | ||
156 | if (gList[gMap[groupIDs[lList1.p[i].px] | ||
157 | [lList1.p[i].py]]].libC < 2) | ||
158 | goto two; /* a bogus move */ | ||
159 | } | ||
160 | else if (gList[gMap[groupIDs[gx][gy]]].libC <= 1) | ||
161 | { | ||
162 | result = TRUE; | ||
163 | goto one; | ||
164 | } | ||
165 | if (gList[gMap[groupIDs[gx][gy]]].libC > treeLibLim) | ||
166 | { | ||
167 | *escape = TRUE; | ||
168 | result = FALSE; | ||
169 | goto one; | ||
170 | } | ||
171 | if (gList[gMap[groupIDs[gx][gy]]].libC > 1) | ||
172 | { /* look at my responses */ | ||
173 | sSpanGroup(gx, gy, &lList2); /* list his liberties */ | ||
174 | dStart = lList2.indx + 1; | ||
175 | if (adjInAtari) /* he wins */ | ||
176 | { | ||
177 | result = FALSE; | ||
178 | goto one; | ||
179 | } | ||
180 | if ((lList2.indx > 2) && adj2Libs) /* he wins */ | ||
181 | { | ||
182 | result = FALSE; | ||
183 | goto one; | ||
184 | } | ||
185 | for (k = 1; k <= maxSPoint; k++) | ||
186 | libList[k] = -1; | ||
187 | if (utilPlayLevel > 4) /* account for diagonal moves */ | ||
188 | { | ||
189 | listDiags(gx, gy, &dList); | ||
190 | j = 0; | ||
191 | k = lList2.indx; | ||
192 | while ((j < dList.indx) && | ||
193 | (k < maxSPoint)) | ||
194 | { | ||
195 | j = j + 1; | ||
196 | k = k + 1; | ||
197 | libList[k] = 100; | ||
198 | lList2.p[k].px = dList.p[j].px; | ||
199 | lList2.p[k].py = dList.p[j].py; | ||
200 | } | ||
201 | lList2.indx = k; | ||
202 | } | ||
203 | if (lList2.indx > 1) /* sort by increasing lib count */ | ||
204 | { | ||
205 | for (k = 1; k <= lList2.indx; k++) | ||
206 | if (libList[k] != 100) /* diags go last */ | ||
207 | { | ||
208 | mark3 = playMark; | ||
209 | tryPlay(lList2.p[k].px, lList2.p[k].py, me); | ||
210 | libList[k] = gList[gMap[groupIDs[gx][gy]]].libC; | ||
211 | undoTo(mark3); | ||
212 | } | ||
213 | for (k = 1; k <= lList2.indx - 1; k++) | ||
214 | for (j = k + 1; j <= lList2.indx; j++) | ||
215 | if (libList[k] > libList[j]) | ||
216 | { | ||
217 | tl = libList[k]; | ||
218 | libList[k] = libList[j]; | ||
219 | libList[j] = tl; | ||
220 | tp = lList2.p[k]; | ||
221 | lList2.p[k] = lList2.p[j]; | ||
222 | lList2.p[j] = tp; | ||
223 | } | ||
224 | else if ((libList[k] == libList[j]) && | ||
225 | (libList[k] == 1)) | ||
226 | if (mtNbrs(lList2.p[k].px, lList2.p[k].py) < | ||
227 | mtNbrs(lList2.p[j].px, lList2.p[j].py)) | ||
228 | { | ||
229 | tl = libList[k]; | ||
230 | libList[k] = libList[j]; | ||
231 | libList[j] = tl; | ||
232 | tp = lList2.p[k]; | ||
233 | lList2.p[k] = lList2.p[j]; | ||
234 | lList2.p[j] = tp; | ||
235 | } | ||
236 | } | ||
237 | for (j = 1; j <= lList2.indx; j++) | ||
238 | { | ||
239 | if (killTree(lList2.p[j].px, lList2.p[j].py, gx, | ||
240 | gy, &esc, tkMark)) | ||
241 | goto two; /* this kills him */ | ||
242 | if (esc && (j >= dStart)) | ||
243 | { | ||
244 | result = FALSE; | ||
245 | goto one; /* don't bother with more diags if escapes */ | ||
246 | } | ||
247 | } | ||
248 | result = FALSE; /* none of my responses kills him */ | ||
249 | goto one; | ||
250 | } | ||
251 | two: | ||
252 | undoTo(mark2); | ||
253 | } | ||
254 | result = TRUE; /* none of his responses saves him */ | ||
255 | } | ||
256 | one: | ||
257 | undoTo(curMark); | ||
258 | /* sClearChar(sChar, rXor); */ | ||
259 | depth = depth - 1; | ||
260 | return result; | ||
261 | } /* killTree */ | ||
262 | |||
263 | short tKillTree(tx, ty, gx, gy) | ||
264 | short tx, ty, gx, gy; | ||
265 | { /* tKillTree */ | ||
266 | short tkMark, escape; | ||
267 | tryCount = 0; | ||
268 | tkMark = playMark; | ||
269 | return killTree(tx, ty, gx, gy, &escape, tkMark); | ||
270 | } /* tKillTree */ | ||
271 | |||
272 | short killable(gx, gy, killx, killy) | ||
273 | short gx, gy, *killx, *killy; | ||
274 | { /* killable */ | ||
275 | #ifdef DEBUG | ||
276 | printf( "killable\n" ); | ||
277 | showTrees = TRUE; | ||
278 | #endif | ||
279 | dbStop = TRUE; | ||
280 | him = bord[gx][gy]; /* find out who I am */ | ||
281 | me = -him; | ||
282 | /* if (me == 1) | ||
283 | sChar = '>'; | ||
284 | else | ||
285 | sChar = '|'; */ | ||
286 | /* write(sChar); */ | ||
287 | depth = 1; | ||
288 | topMark = playMark; | ||
289 | sSpanGroup(gx, gy, &lList); /* find his liberties */ | ||
290 | if (lList.indx == 1) | ||
291 | { | ||
292 | *killx = lList.p[1].px; | ||
293 | *killy = lList.p[1].py; | ||
294 | return TRUE; | ||
295 | } | ||
296 | else if (lList.indx > treeLibLim) | ||
297 | return FALSE; | ||
298 | else if (adjInAtari) | ||
299 | return FALSE; | ||
300 | else if ((lList.indx > 2) && adj2Libs) | ||
301 | return FALSE; | ||
302 | else | ||
303 | { | ||
304 | for (i = 1; i <= maxSPoint; i++) | ||
305 | libList[i] = -1; | ||
306 | if (utilPlayLevel > 4) /* account for diagonal moves */ | ||
307 | { | ||
308 | listDiags(gx, gy, &dList); | ||
309 | j = 0; | ||
310 | i = lList.indx; | ||
311 | while ((j < dList.indx) && | ||
312 | (i < maxSPoint)) | ||
313 | { | ||
314 | j = j + 1; | ||
315 | i = i + 1; | ||
316 | libList[i] = 100; | ||
317 | lList.p[i].px = dList.p[j].px; | ||
318 | lList.p[i].py = dList.p[j].py; | ||
319 | } | ||
320 | lList.indx = i; | ||
321 | } | ||
322 | if (lList.indx > 1) /* sort by increasing lib count */ | ||
323 | { | ||
324 | for (i = 1; i <= lList.indx; i++) | ||
325 | if (libList[i] != 100) /* diags go last */ | ||
326 | { | ||
327 | mark2 = playMark; | ||
328 | tryPlay(lList.p[i].px, lList.p[i].py, me); | ||
329 | libList[i] = gList[gMap[groupIDs[gx][gy]]].libC; | ||
330 | undoTo(mark2); | ||
331 | } | ||
332 | for (i = 1; i <= lList.indx - 1; i++) | ||
333 | for (j = i + 1; j <= lList.indx; j++) | ||
334 | if (libList[i] > libList[j]) | ||
335 | { | ||
336 | tl = libList[i]; | ||
337 | libList[i] = libList[j]; | ||
338 | libList[j] = tl; | ||
339 | tp = lList.p[i]; | ||
340 | lList.p[i] = lList.p[j]; | ||
341 | lList.p[j] = tp; | ||
342 | } | ||
343 | else if ((libList[i] == libList[j]) && | ||
344 | (libList[i] == 1)) | ||
345 | if (mtNbrs(lList.p[i].px, lList.p[i].py) < | ||
346 | mtNbrs(lList.p[j].px, lList.p[j].py)) | ||
347 | { | ||
348 | tl = libList[i]; | ||
349 | libList[i] = libList[j]; | ||
350 | libList[j] = tl; | ||
351 | tp = lList.p[i]; | ||
352 | lList.p[i] = lList.p[j]; | ||
353 | lList.p[j] = tp; | ||
354 | } | ||
355 | } | ||
356 | for (i = 1; i <= lList.indx; i++) | ||
357 | { | ||
358 | if (legal[lList.p[i].px][lList.p[i].py]) | ||
359 | { | ||
360 | *killx = lList.p[i].px; | ||
361 | *killy = lList.p[i].py; | ||
362 | if (tKillTree(*killx, *killy, gx, gy)) | ||
363 | { | ||
364 | /* sClearChar(sChar, rXor); */ | ||
365 | return TRUE; | ||
366 | } | ||
367 | } | ||
368 | } | ||
369 | return FALSE; | ||
370 | } | ||
371 | /* sClearChar(sChar, rXor); */ | ||
372 | } /* killable */ | ||
373 | |||