tactics/nakade.c

   1 #include <assert.h>
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4
   5 #define QUICK_BOARD_CODE
   6
   7 #define DEBUG
   8 #include "board.h"
   9 #include "debug.h"
  10 #include "move.h"
  11 #include "tactics/nakade.h"
  12
  13
  14 static inline int
  15 nakade_area(struct board *b, coord_t around, enum stone color, coord_t *area)
  16 {
  17         /* First, examine the nakade area. For sure, it must be at most
  18          * six points. And it must be within color group(s). */
  19 #define NAKADE_MAX 6
  20         int area_n = 0;
  21
  22         area[area_n++] = around;
  23
  24         for (int i = 0; i < area_n; i++) {
  25                 foreach_neighbor(b, area[i], {
  26                         if (board_at(b, c) == stone_other(color))
  27                                 return -1;
  28                         if (board_at(b, c) == S_NONE) {
  29                                 bool dup = false;
  30                                 for (int j = 0; j < area_n; j++)
  31                                         if (c == area[j]) {
  32                                                 dup = true;
  33                                                 break;
  34                                         }
  35                                 if (dup) continue;
  36
  37                                 if (area_n >= NAKADE_MAX) {
  38                                         /* Too large nakade area. */
  39                                         return -1;
  40                                 }
  41                                 area[area_n++] = c;
  42                         }
  43                 });
  44         }
  45
  46         return area_n;
  47 }
  48
  49 static inline void
  50 get_neighbors(struct board *b, coord_t *area, int area_n, int *neighbors, int *ptbynei)
  51 {
  52         /* We also collect adjecency information - how many neighbors
  53          * we have for each area point, and histogram of this. This helps
  54          * us verify the appropriate bulkiness of the shape. */
  55         memset(neighbors, 0, area_n * sizeof(int));
  56         for (int i = 0; i < area_n; i++) {
  57                 for (int j = i + 1; j < area_n; j++)
  58                         if (coord_is_adjecent(area[i], area[j], b)) {
  59                                 ptbynei[neighbors[i]]--;
  60                                 neighbors[i]++;
  61                                 ptbynei[neighbors[i]]++;
  62                                 ptbynei[neighbors[j]]--;
  63                                 neighbors[j]++;
  64                                 ptbynei[neighbors[j]]++;
  65                         }
  66         }
  67 }
  68
  69 static inline coord_t
  70 nakade_point_(coord_t *area, int area_n, int *neighbors, int *ptbynei)
  71 {
  72         /* For each given neighbor count, arbitrary one coordinate
  73          * featuring that. */
  74         coord_t coordbynei[9];
  75         for (int i = 0; i < area_n; i++)
  76                 coordbynei[neighbors[i]] = area[i];
  77
  78         switch (area_n) {
  79                 case 1: return pass;
  80                 case 2: return pass;
  81                 case 3: assert(ptbynei[2] == 1);
  82                         return coordbynei[2]; // middle point
  83                 case 4: if (ptbynei[3] != 1) return pass; // long line, L shape, or square
  84                         return coordbynei[3]; // tetris four
  85                 case 5: if (ptbynei[3] == 1 && ptbynei[1] == 1) return coordbynei[3]; // bulky five
  86                         if (ptbynei[4] == 1) return coordbynei[4]; // cross five
  87                         return pass; // long line
  88                 case 6: if (ptbynei[4] == 1 && ptbynei[2] == 3)
  89                                 return coordbynei[4]; // rabbity six
  90                         return pass; // anything else
  91                 default: assert(0);
  92         }
  93
  94         return 0; /* NOTREACHED */
  95 }
  96
  97 coord_t
  98 nakade_point(struct board *b, coord_t around, enum stone color)
  99 {
 100         assert(board_at(b, around) == S_NONE);
 101         coord_t area[NAKADE_MAX]; int area_n = 0;
 102         area_n = nakade_area(b, around, color, area);
 103         if (area_n == -1)
 104                 return pass;
 105
 106         int neighbors[area_n]; int ptbynei[9] = {area_n, 0};
 107         get_neighbors(b, area, area_n, neighbors, ptbynei);
 108
 109         return nakade_point_(area, area_n, neighbors, ptbynei);
 110 }
 111
 112
 113 bool
 114 nakade_dead_shape(struct board *b, coord_t around, enum stone color)
 115 {
 116         assert(board_at(b, around) == S_NONE);
 117         coord_t area[NAKADE_MAX]; int area_n = 0;
 118         area_n = nakade_area(b, around, color, area);
 119         if (area_n == -1)       return false;
 120         if (area_n <= 3)        return true;
 121
 122         int neighbors[area_n]; int ptbynei[9] = {area_n, 0};
 123         get_neighbors(b, area, area_n, neighbors, ptbynei);
 124
 125         if (area_n == 4 && ptbynei[2] == 4)  // square 4
 126                 return true;
 127
 128         /* nakade_point() should be able to deal with the rest ... */
 129         coord_t nakade = nakade_point_(area, area_n, neighbors, ptbynei);
 130         return  nakade != pass;
 131 }