1 #include <stdio.h>
2 #include <sys/types.h>
3 #include <sys/time.h>
4 #include <unistd.h>
5 #include <string.h>
6
7 time_t time();
8
9 #include "vier.h"
10 #include "xvier.h"
11
12 int rows, columns, vnum;
13 int row_col, row_1_col, row_2_col;
14 int *brett, *weiss, *schwarz, **freip, **doublesp;
15 int frei[MAXRC], reihenfolge[MAXRC], doubles[MAXRC];
16 int (*pu)[4];
17 int *_p_h_, **pp;
18 struct oldv *stack, *sp, **zugstack;
19 int bewertung = 0;
20
21 int zugstackp = 0, level = 2;
22
23 #define WEISS 1
24 #define SCHWARZ 2
25 #define W_WINS 4
26 #define S_WINS 8
27 #define USELESS 16
28
read_char(ch)29 char read_char(ch)
30 char *ch;
31 {
32 if (read(0, ch, 1) < 1) {
33 perror("xvier_prog read failed");
34 exit(1);
35 }
36 return *ch;
37 }
38
write_char(ch)39 void write_char(ch)
40 char ch;
41 {
42 if (write(1, &ch, 1) < 1) {
43 perror("xvier_prog write failed");
44 exit(1);
45 }
46 }
47
w_test(pos)48 void w_test(pos)
49 int pos;
50 {
51 register int *p, j;
52 int oben;
53
54 /* leere Position suchen */
55 for (p = pu[pos]; brett[*p] & (WEISS | SCHWARZ); p++);
56 if (brett[j = *p] & (W_WINS | USELESS))
57 return;
58 sp -> pos = brett + j;
59 sp++ -> value = brett[j];
60 brett[j] |= W_WINS;
61 if (*doublesp[j] == SCHWARZ &&
62 j > *freip[j] &&
63 j < row_1_col &&
64 !(brett[j+columns] & USELESS)) {
65 sp -> pos = doublesp[j];
66 sp++ -> value = SCHWARZ;
67 *doublesp[j] = 0;
68 }
69 if (!*doublesp[j] &&
70 ((j > *freip[j] + columns &&
71 (brett[(oben = j) - columns] & W_WINS)) ||
72 (j > *freip[j] && j < row_1_col &&
73 (brett[oben = j + columns] & W_WINS)))) {
74 register int k;
75
76 for (k = *freip[j]; k < oben; k += columns)
77 if (brett[k] & S_WINS)
78 goto no_double;
79 sp -> pos = doublesp[j];
80 sp++ -> value = 0;
81 *doublesp[j] = WEISS;
82 }
83 no_double:
84 if (j < row_1_col &&
85 ((brett[oben = j] & S_WINS) ||
86 (j > *freip[j] && (brett[j - columns] & W_WINS)) ||
87 (j < row_2_col &&
88 (brett[oben = j + columns] & W_WINS))))
89 for (j = oben + columns;
90 j < row_col && !(brett[j] & USELESS);
91 j += columns) {
92 register int h1, h2;
93
94 /* Vierer darueber sind nutzlos */
95 sp -> pos = brett + j;
96 sp++ -> value = brett[j];
97 brett[j] |= USELESS;
98 p = pp[j];
99 while ((h1 = *(p++)) >= 0) {
100 if ((h2 = weiss[h1]) >= 0) {
101 sp -> pos = &weiss[h1];
102 sp++ -> value = h2;
103 weiss[h1] = -1;
104 bewertung -= h2;
105 }
106 if ((h2 = schwarz[h1]) >= 0) {
107 sp -> pos = &schwarz[h1];
108 sp++ -> value = h2;
109 schwarz[h1] = -1;
110 bewertung += h2;
111 }
112 }
113 }
114 }
115
s_test(pos)116 void s_test(pos)
117 int pos;
118 {
119 register int *p, j;
120 int oben;
121
122 /* leere Position suchen */
123 for (p = pu[pos]; brett[*p] & (WEISS | SCHWARZ); p++);
124 if (brett[j = *p] & (S_WINS | USELESS))
125 return;
126 sp -> pos = brett + j;
127 sp++ -> value = brett[j];
128 brett[j] |= S_WINS;
129 if (*doublesp[j] == WEISS &&
130 j > *freip[j] &&
131 j < row_1_col &&
132 !(brett[j+columns] & USELESS)) {
133 sp -> pos = doublesp[j];
134 sp++ -> value = WEISS;
135 *doublesp[j] = 0;
136 }
137 if (!*doublesp[j] &&
138 ((j > *freip[j] + columns &&
139 (brett[(oben = j) - columns] & S_WINS)) ||
140 (j > *freip[j] && j < row_1_col &&
141 (brett[oben = j + columns] & S_WINS)))) {
142 register int k;
143
144 for (k = *freip[j]; k < oben; k += columns)
145 if (brett[k] & W_WINS)
146 goto no_double;
147 sp -> pos = doublesp[j];
148 sp++ -> value = 0;
149 *doublesp[j] = SCHWARZ;
150 }
151 no_double:
152 if (j < row_1_col &&
153 ((brett[oben = j] & W_WINS) ||
154 (j > *freip[j] && (brett[j - columns] & S_WINS)) ||
155 (j < row_2_col &&
156 (brett[oben = j + columns] & S_WINS))))
157 for (j = oben + columns;
158 j < row_col && !(brett[j] & USELESS);
159 j += columns) {
160 register int h1, h2;
161
162 /* Vierer darueber sind nutzlos */
163 sp -> pos = brett + j;
164 sp++ -> value = brett[j];
165 brett[j] |= USELESS;
166 p = pp[j];
167 while ((h1 = *(p++)) >= 0) {
168 if ((h2 = weiss[h1]) >= 0) {
169 sp -> pos = &weiss[h1];
170 sp++ -> value = h2;
171 weiss[h1] = -1;
172 bewertung -= h2;
173 }
174 if ((h2 = schwarz[h1]) >= 0) {
175 sp -> pos = &schwarz[h1];
176 sp++ -> value = h2;
177 schwarz[h1] = -1;
178 bewertung += h2;
179 }
180 }
181 }
182 }
183
w_zugzwang(remain)184 int w_zugzwang(remain)
185 int remain;
186 {
187 register int i, pos, poslev = 7, p_s_p = 0;
188 int p_stack[MAXRC];
189
190 for (i = 0; i < columns; i++) {
191 register int f = frei[i];
192
193 if (f < row_col) {
194 if (brett[f] & W_WINS)
195 return 8 + 8 * remain;
196 if (brett[f] & S_WINS) {
197 pos = i;
198 poslev = 1;
199 } else if (poslev > 2) {
200 if (doubles[i] == WEISS) {
201 pos = i;
202 poslev = 2;
203 } else if (poslev > 3) {
204 if (f >= row_1_col ||
205 ((brett[f + columns] & (W_WINS | S_WINS)) == 0 &&
206 !doubles[i])) {
207 pos = i;
208 poslev = 3;
209 } else if (poslev > 4) {
210 if ((brett[f + columns] & (W_WINS | S_WINS)) == 0) {
211 pos = i;
212 poslev = 4;
213 } else if ((brett[f + columns] & S_WINS) == 0) {
214 p_stack[p_s_p++] = pos = i;
215 poslev = 5;
216 } else if (poslev > 6) {
217 pos = i;
218 poslev = 6;
219 }
220 }
221 }
222 }
223 }
224 }
225 if (poslev == 7)
226 return 0;
227 if (poslev == 5 && p_s_p > 1) {
228 int m;
229
230 frei[p_stack[0]] += columns;
231 m = s_zugzwang(remain-1);
232 frei[p_stack[0]] -= columns;
233 for (i = 1; i < p_s_p; i++) {
234 register int tmp;
235
236 frei[p_stack[i]] += columns;
237 if ((tmp = s_zugzwang(remain-1)) > m)
238 m = tmp;
239 frei[p_stack[i]] -= columns;
240 }
241 return m;
242 } else {
243 frei[pos] += columns;
244 i = s_zugzwang(remain-1);
245 frei[pos] -= columns;
246 return i;
247 }
248 }
249
s_zugzwang(remain)250 int s_zugzwang(remain)
251 int remain;
252 {
253 register int i, pos, poslev = 7, p_s_p = 0;
254 int p_stack[MAXRC];
255
256 for (i = 0; i < columns; i++) {
257 register int f = frei[i];
258
259 if (f < row_col) {
260 if (brett[f] & S_WINS)
261 return -8 - 8 * remain;
262 if (brett[f] & W_WINS) {
263 pos = i;
264 poslev = 1;
265 } else if (poslev > 2) {
266 if (doubles[i] == SCHWARZ) {
267 pos = i;
268 poslev = 2;
269 } else if (poslev > 3) {
270 if (f >= row_1_col ||
271 ((brett[f + columns] & (W_WINS | S_WINS)) == 0 &&
272 !doubles[i])) {
273 pos = i;
274 poslev = 3;
275 } else if (poslev > 4) {
276 if ((brett[f + columns] & (W_WINS | S_WINS)) == 0) {
277 pos = i;
278 poslev = 4;
279 } else if ((brett[f + columns] & W_WINS) == 0) {
280 p_stack[p_s_p++] = pos = i;
281 poslev = 5;
282 } else if (poslev > 6) {
283 pos = i;
284 poslev = 6;
285 }
286 }
287 }
288 }
289 }
290 }
291 if (poslev == 7)
292 return 0;
293 if (poslev == 5 && p_s_p > 1) {
294 int m;
295
296 frei[p_stack[0]] += columns;
297 m = w_zugzwang(remain-1);
298 frei[p_stack[0]] -= columns;
299 for (i = 1; i < p_s_p; i++) {
300 register int tmp;
301
302 frei[p_stack[i]] += columns;
303 if ((tmp = w_zugzwang(remain-1)) < m)
304 m = tmp;
305 frei[p_stack[i]] -= columns;
306 }
307 return m;
308 } else {
309 frei[pos] += columns;
310 i = w_zugzwang(remain-1);
311 frei[pos] -= columns;
312 return i;
313 }
314 }
315
comp_weiss(pos,lev,limit)316 int comp_weiss(pos, lev, limit)
317 int pos, lev, limit;
318 {
319 register int h1, h2, i, j, *p;
320 int *frp, wert;
321 struct oldv *sold;
322
323 if (brett[pos] & W_WINS)
324 return 50000 - lev;
325 /* Zug fuer Weiss ausfuehren */
326 sold = sp;
327 sp -> pos = frp = freip[pos];
328 sp++ -> value = *frp;
329 sp -> pos = brett + pos;
330 sp++ -> value = brett[pos];
331 sp -> pos = &bewertung;
332 sp++ -> value = bewertung;
333 *frp += columns;
334 brett[pos] |= WEISS;
335 p = pp[pos];
336 while ((h1 = *(p++)) >= 0) {
337 if ((h2 = weiss[h1]) >= 0) {
338 sp -> pos = &weiss[h1];
339 sp++ -> value = h2;
340 weiss[h1]++;
341 bewertung++;
342 if (h2 == 3)
343 w_test (h1);
344 }
345 if ((h2 = schwarz[h1]) >= 0) {
346 sp -> pos = &schwarz[h1];
347 sp++ -> value = h2;
348 schwarz[h1] = -1;
349 bewertung += h2;
350 }
351 }
352 h1 = -1;
353 for (i = 0; i < columns; i++) {
354 register int f = frei[i];
355
356 if (f < row_col) {
357 if (brett[f] & S_WINS) {
358 wert = -49999 + lev;
359 goto end;
360 }
361 if (brett[f] & W_WINS)
362 h1 = f;
363 }
364 }
365 if (h1 >= 0) {
366 level++;
367 wert = comp_schwarz(h1, lev + 1, 100000);
368 level--;
369 } else if (lev >= level)
370 wert = bewertung + s_zugzwang(40 - lev - zugstackp);
371 else {
372 register int zw;
373
374 wert = 100000;
375 for (i = 0; i < columns; i++) {
376 j = frei[reihenfolge[i]];
377 if (j < row_col)
378 if ((zw = comp_schwarz (j, lev + 1, wert)) < wert)
379 if ((wert = zw) <= limit)
380 break;
381 /* Schwarz wird wohl den fuer ihn guenstigsten Zug auswaehlen */
382 }
383 if (wert == 100000)
384 wert = 0; /* unentschieden */
385 }
386 end:
387 while (sp != sold) {
388 sp--;
389 *(sp -> pos) = sp -> value;
390 }
391 return (wert);
392 }
393
comp_schwarz(pos,lev,limit)394 int comp_schwarz(pos, lev, limit)
395 int pos, lev, limit;
396 {
397 register int h1, h2, i, j, *p;
398 int *frp, wert;
399 struct oldv *sold;
400
401 if (brett[pos] & S_WINS)
402 return -50000 + lev;
403 /* Zug fuer Schwarz ausfuehren */
404 sold = sp;
405 sp -> pos = frp = freip[pos];
406 sp++ -> value = *frp;
407 sp -> pos = brett + pos;
408 sp++ -> value = brett[pos];
409 sp -> pos = &bewertung;
410 sp++ -> value = bewertung;
411 *frp += columns;
412 brett[pos] |= SCHWARZ;
413 p = pp[pos];
414 while ((h1 = *(p++)) >= 0) {
415 if ((h2 = schwarz[h1]) >= 0) {
416 sp -> pos = &schwarz[h1];
417 sp++ -> value = h2;
418 schwarz[h1]++;
419 bewertung--;
420 if (h2 == 3)
421 s_test (h1);
422 }
423 if ((h2 = weiss[h1]) >= 0) {
424 sp -> pos = &weiss[h1];
425 sp++ -> value = h2;
426 weiss[h1] = -1;
427 bewertung -= h2;
428 }
429 }
430 h1 = -1;
431 for (i = 0; i < columns; i++) {
432 register int f = frei[i];
433
434 if (f < row_col) {
435 if (brett[f] & W_WINS) {
436 wert = 49999 - lev;
437 goto end;
438 }
439 if (brett[f] & S_WINS)
440 h1 = f;
441 }
442 }
443 if (h1 >= 0) {
444 level++;
445 wert = comp_weiss(h1, lev + 1, -100000);
446 level--;
447 } else if (lev >= level)
448 wert = bewertung + w_zugzwang(40 - lev - zugstackp);
449 else {
450 register int zw;
451
452 wert = -100000;
453 for (i = 0; i < columns; i++) {
454 j = frei[reihenfolge[i]];
455 if (j < row_col)
456 if ((zw = comp_weiss (j, lev + 1, wert)) > wert)
457 if ((wert = zw) >= limit)
458 break;
459 }
460 if (wert == -100000)
461 wert = 0; /* unentschieden */
462 }
463 end:
464 while (sp != sold) {
465 sp--;
466 *(sp -> pos) = sp -> value;
467 }
468 return (wert);
469 }
470
main(argc,argv)471 int main(argc, argv)
472 int argc;
473 char **argv;
474 {
475 int i, j, h1, zj, *p, wert, zi;
476 char ch, buf[10];
477 int same[MAXRC], same_n;
478
479 if (argc != 3 ||
480 (rows = atoi(argv[1])) < 4 || rows > MAXRC ||
481 (columns = atoi(argv[2])) < 4 || columns > MAXRC) {
482 fprintf(stderr, "Usage: %s <rows> <columns>\n", *argv);
483 exit(1);
484 }
485 vierinit();
486 sprintf(buf, "%dR%dC", rows, columns);
487 for (i = 0; buf[i] != '\0'; i++)
488 write_char(buf[i]);
489 srand((int) time(NULL));
490 while (1) {
491 mensch:
492 read_char(&ch);
493 switch (ch) {
494 case '0': case '1': case '2': case '3': case '4':
495 case '5': case '6': case '7': case '8': case '9':
496 write_char(ch);
497 level = ch - '0' + 2;
498 break;
499 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'g':
500 case 'h': case 'i': case 'j': case 'k': case 'l': case 'm':
501 if (ch - 'a' >= columns ||
502 (j = frei[ch - 'a']) >= row_col) {
503 write_char('x');
504 break;
505 }
506 if (brett[j] & W_WINS) {
507 write_char('w');
508 while (read_char(&ch) != 'u')
509 switch (ch) {
510 case '0': case '1': case '2': case '3': case '4':
511 case '5': case '6': case '7': case '8': case '9':
512 write_char(ch);
513 level = ch - '0' + 2;
514 break;
515 case 'n':
516 goto newgame;
517 default:
518 write_char('x');
519 break;
520 }
521 write_char('v');
522 break;
523 }
524 zugstack[zugstackp++] = sp;
525 sp -> pos = brett + j;
526 sp++ -> value = brett[j];
527 sp -> pos = frei + ch - 'a';
528 sp++ -> value = frei[ch - 'a'];
529 sp -> pos = &bewertung;
530 sp++ -> value = bewertung;
531 brett[j] |= WEISS;
532 frei[ch - 'a'] += columns;
533 p = pp[j];
534 while ((h1 = *(p++)) >= 0) {
535 if ((weiss[h1]) >= 0) {
536 sp -> pos = weiss + h1;
537 sp++ -> value = weiss[h1];
538 weiss[h1]++;
539 bewertung++;
540 if (weiss[h1] == 4)
541 w_test(h1);
542 }
543 if ((schwarz[h1]) >= 0) {
544 sp -> pos = schwarz + h1;
545 sp++ -> value = schwarz[h1];
546 bewertung += schwarz[h1];
547 schwarz[h1] = -1;
548 }
549 }
550 computer:
551 same_n = 0;
552 for (i = 0; i < columns; i++) {
553 int f = frei[i];
554
555 if (f < row_col) {
556 if (brett[f] & S_WINS) {
557 zi = i;
558 goto calculate_end;
559 }
560 if (brett[f] & W_WINS)
561 same[same_n++] = i;
562 }
563 }
564 if (same_n == 0) {
565 wert = 100000;
566 for (i = 0; i < columns; i++) {
567 register int zw;
568
569 if ((j = frei[reihenfolge[i]]) < row_col)
570 if ((zw = comp_schwarz (j, 0, wert + 1)) < wert) {
571 wert = zw;
572 same_n = 1;
573 same[0] = reihenfolge[i];
574 } else if (zw == wert)
575 same[same_n++] = reihenfolge[i];
576 }
577 }
578 if (same_n == 0) {
579 write_char('z');
580 while (read_char(&ch) != 'u')
581 switch (ch) {
582 case '0': case '1': case '2': case '3': case '4':
583 case '5': case '6': case '7': case '8': case '9':
584 write_char(ch);
585 level = ch - '0' + 2;
586 break;
587 case 'n':
588 goto newgame;
589 default:
590 write_char('x');
591 break;
592 }
593 write_char('v');
594 zugstackp--;
595 while (sp != zugstack[zugstackp]) {
596 sp--;
597 *(sp -> pos) = sp -> value;
598 }
599 break;
600 }
601 if (same_n == 1)
602 zi = same[0];
603 else
604 zi = same[rand() % same_n];
605 calculate_end:
606 zj = frei[zi];
607 if (brett[zj] & S_WINS) {
608 write_char('A' + zi);
609 while (read_char(&ch) != 'u')
610 switch (ch) {
611 case '0': case '1': case '2': case '3': case '4':
612 case '5': case '6': case '7': case '8': case '9':
613 write_char(ch);
614 level = ch - '0' + 2;
615 break;
616 case 'n':
617 goto newgame;
618 default:
619 write_char('x');
620 break;
621 }
622 write_char('u');
623 zugstackp--;
624 while (sp != zugstack[zugstackp]) {
625 sp--;
626 *(sp -> pos) = sp -> value;
627 }
628 break;
629 }
630 zugstack[zugstackp++] = sp;
631 sp -> pos = brett + zj;
632 sp++ -> value = brett[zj];
633 sp -> pos = frei + zi;
634 sp++ -> value = zj;
635 sp -> pos = &bewertung;
636 sp++ -> value = bewertung;
637 brett[zj] |= SCHWARZ;
638 frei[zi] += columns;
639 p = pp[zj];
640 while ((h1 = *(p++)) >= 0) {
641 if ((schwarz[h1]) >= 0) {
642 sp -> pos = schwarz + h1;
643 sp++ -> value = schwarz[h1];
644 schwarz[h1]++;
645 bewertung--;
646 if (schwarz[h1] == 4)
647 s_test(h1);
648 }
649 if ((weiss[h1]) >= 0) {
650 sp -> pos = weiss + h1;
651 sp++ -> value = weiss[h1];
652 bewertung -= weiss[h1];
653 weiss[h1] = -1;
654 }
655 }
656 if (frei[zi] < row_col && (brett[frei[zi]] & USELESS)) {
657 /* user didn't recognize a double */
658 for (i = frei[zi]; i < row_col; i+= columns) {
659 int w_wins = 0, s_wins = 0;
660
661 sp -> pos = brett + i;
662 sp++ -> value = brett[i];
663 brett[i] = 0;
664 p = pp[i];
665 while ((h1 = *(p++)) >= 0) {
666 int wval = 1, sval = 1;
667
668 for (j = 0; j < 4; j++) {
669 if (brett[pu[h1][j]] & USELESS) {
670 wval = -1;
671 sval = -1;
672 } else if (brett[pu[h1][j]] & WEISS) {
673 if (wval > 0)
674 wval++;
675 } else if (brett[pu[h1][j]] & SCHWARZ) {
676 if (sval > 0)
677 sval++;
678 }
679 }
680 if (wval > 0) {
681 bewertung += wval;
682 sp -> pos = weiss + h1;
683 sp++ -> value = weiss[h1];
684 weiss[h1] = wval;
685 if (wval == 4)
686 w_wins = 1;
687 }
688 if (sval > 0) {
689 bewertung -= sval;
690 sp -> pos = schwarz + h1;
691 sp++ -> value = schwarz[h1];
692 schwarz[h1] = sval;
693 if (sval == 4)
694 s_wins = 1;
695 }
696 }
697 if (w_wins && s_wins) {
698 brett[i] |= (W_WINS | S_WINS);
699 if (i > frei[zi] + columns) {
700 if (brett[i - columns] & W_WINS) {
701 if (*doublesp[i] != WEISS) {
702 sp -> pos = doublesp[i];
703 sp++ -> value = *doublesp[i];
704 *doublesp[i] = WEISS;
705 }
706 } else if (brett[i - columns] & S_WINS) {
707 if (*doublesp[i] != SCHWARZ) {
708 sp -> pos = doublesp[i];
709 sp++ -> value = *doublesp[i];
710 *doublesp[i] = SCHWARZ;
711 }
712 }
713 }
714 break;
715 } else if (w_wins) {
716 brett[i] |= W_WINS;
717 if (i > frei[zi] + columns && (brett[i - columns] & W_WINS)) {
718 if (*doublesp[i] != WEISS) {
719 sp -> pos = doublesp[i];
720 sp++ -> value = *doublesp[i];
721 *doublesp[i] = WEISS;
722 }
723 break;
724 }
725 } else if (s_wins) {
726 brett[i] |= S_WINS;
727 if (i > frei[zi] + columns && (brett[i - columns] & S_WINS)) {
728 if (*doublesp[i] != SCHWARZ) {
729 sp -> pos = doublesp[i];
730 sp++ -> value = *doublesp[i];
731 *doublesp[i] = SCHWARZ;
732 }
733 break;
734 }
735 }
736 }
737 }
738 for (i = 0; i < columns; i++)
739 if (frei[i] < row_col) {
740 write_char('a' + zi);
741 goto mensch;
742 }
743 /* unentschieden */
744 write_char('N' + zi);
745 while (read_char(&ch) != 'u')
746 switch (ch) {
747 case '0': case '1': case '2': case '3': case '4':
748 case '5': case '6': case '7': case '8': case '9':
749 write_char(ch);
750 level = ch - '0' + 2;
751 break;
752 case 'n':
753 goto newgame;
754 default:
755 write_char('x');
756 break;
757 }
758 write_char('u');
759 zugstackp -= 2;
760 while (sp != zugstack[zugstackp]) {
761 sp--;
762 *(sp -> pos) = sp -> value;
763 }
764 break;
765 case 'n':
766 newgame:
767 write_char('n');
768 zugstackp = 0;
769 while (sp != stack) {
770 sp--;
771 *(sp -> pos) = sp -> value;
772 }
773 break;
774 case 'u':
775 if (zugstackp < 2)
776 goto newgame;
777 write_char('u');
778 zugstackp -= 2;
779 while (sp != zugstack[zugstackp]) {
780 sp--;
781 *(sp -> pos) = sp -> value;
782 }
783 break;
784 case 's':
785 if (zugstackp == 0)
786 goto computer;
787 /* else fall through */
788 default:
789 write_char('x');
790 break;
791 }
792 }
793 }
794