Plakkie

Zetter/Uilskuiken

From Wilmer, 10 Years ago, written in C, viewed 769 times.
URL https://p.gaa.st/view/16751938 Embed
Download Paste or View Raw
  1. const int edges[107] = {
  2.         0, /* 1-based */
  3.         /*   1 */ 17,
  4.         /*   2 */ 16,
  5.         /*   3 */ 0,
  6.         /*   4 */ 1,
  7.         /*   5 */ 16,
  8.         /*   6 */ 0,
  9.         /*   7 */ 0,
  10.         /*   8 */ 0,
  11.         /*   9 */ 1,
  12.         /*  10 */ 16,
  13.         /*  11 */ 0,
  14.         /*  12 */ 0,
  15.         /*  13 */ 0,
  16.         /*  14 */ 0,
  17.         /*  15 */ 0,
  18.         /*  16 */ 1,
  19.         /*  17 */ 16,
  20.         /*  18 */ 0,
  21.         /*  19 */ 0,
  22.         /*  20 */ 0,
  23.         /*  21 */ 0,
  24.         /*  22 */ 0,
  25.         /*  23 */ 0,
  26.         /*  24 */ 0,
  27.         /*  25 */ 1,
  28.         /*  26 */ 16,
  29.         /*  27 */ 0,
  30.         /*  28 */ 0,
  31.         /*  29 */ 0,
  32.         /*  30 */ 0,
  33.         /*  31 */ 0,
  34.         /*  32 */ 0,
  35.         /*  33 */ 0,
  36.         /*  34 */ 0,
  37.         /*  35 */ 0,
  38.         /*  36 */ 1,
  39.         /*  37 */ 24,
  40.         /*  38 */ 0,
  41.         /*  39 */ 0,
  42.         /*  40 */ 0,
  43.         /*  41 */ 0,
  44.         /*  42 */ 0,
  45.         /*  43 */ 0,
  46.         /*  44 */ 0,
  47.         /*  45 */ 0,
  48.         /*  46 */ 0,
  49.         /*  47 */ 0,
  50.         /*  48 */ 0,
  51.         /*  49 */ 3,
  52.         /*  50 */ 8,
  53.         /*  51 */ 0,
  54.         /*  52 */ 0,
  55.         /*  53 */ 0,
  56.         /*  54 */ 0,
  57.         /*  55 */ 0,
  58.         /*  56 */ 0,
  59.         /*  57 */ 0,
  60.         /*  58 */ 0,
  61.         /*  59 */ 0,
  62.         /*  60 */ 0,
  63.         /*  61 */ 2,
  64.         /*  62 */ 8,
  65.         /*  63 */ 0,
  66.         /*  64 */ 0,
  67.         /*  65 */ 0,
  68.         /*  66 */ 0,
  69.         /*  67 */ 0,
  70.         /*  68 */ 0,
  71.         /*  69 */ 0,
  72.         /*  70 */ 0,
  73.         /*  71 */ 0,
  74.         /*  72 */ 2,
  75.         /*  73 */ 8,
  76.         /*  74 */ 0,
  77.         /*  75 */ 0,
  78.         /*  76 */ 0,
  79.         /*  77 */ 0,
  80.         /*  78 */ 0,
  81.         /*  79 */ 0,
  82.         /*  80 */ 0,
  83.         /*  81 */ 0,
  84.         /*  82 */ 2,
  85.         /*  83 */ 8,
  86.         /*  84 */ 0,
  87.         /*  85 */ 0,
  88.         /*  86 */ 0,
  89.         /*  87 */ 0,
  90.         /*  88 */ 0,
  91.         /*  89 */ 0,
  92.         /*  90 */ 0,
  93.         /*  91 */ 2,
  94.         /*  92 */ 8,
  95.         /*  93 */ 0,
  96.         /*  94 */ 0,
  97.         /*  95 */ 0,
  98.         /*  96 */ 0,
  99.         /*  97 */ 0,
  100.         /*  98 */ 0,
  101.         /*  99 */ 2,
  102.         /* 100 */ 12,
  103.         /* 101 */ 4,
  104.         /* 102 */ 4,
  105.         /* 103 */ 4,
  106.         /* 104 */ 4,
  107.         /* 105 */ 4,
  108.         /* 106 */ 6,
  109. };
  110. const int rowsize[] = {1, 3, 5, 7, 9, 11, 13, 12, 11, 10, 9, 8, 7, 0};
  111. const int edge_cells[] = {1, 2, 4, 5, 9, 10, 16, 17, 25, 26, 36, 37, 49, 50, 61, 62, 72, 73, 82, 83, 91, 92, 99, 100, 101, 102, 103, 104, 105, 106, 0};
  112. const int corner_cells[] = {1, 37, 49, 100, 106, 0};
  113. const int neighs[107][6] = {
  114.         {}, /* 1-based */
  115.         /*   1 */ {  2,  3,  4},
  116.         /*   2 */ {  1,  3,  5,  6},
  117.         /*   3 */ {  1,  2,  4,  6,  7,  8},
  118.         /*   4 */ {  1,  3,  8,  9},
  119.         /*   5 */ {  2,  6, 10, 11},
  120.         /*   6 */ {  2,  3,  5,  7, 11, 12},
  121.         /*   7 */ {  3,  6,  8, 12, 13, 14},
  122.         /*   8 */ {  3,  4,  7,  9, 14, 15},
  123.         /*   9 */ {  4,  8, 15, 16},
  124.         /*  10 */ {  5, 11, 17, 18},
  125.         /*  11 */ {  5,  6, 10, 12, 18, 19},
  126.         /*  12 */ {  6,  7, 11, 13, 19, 20},
  127.         /*  13 */ {  7, 12, 14, 20, 21, 22},
  128.         /*  14 */ {  7,  8, 13, 15, 22, 23},
  129.         /*  15 */ {  8,  9, 14, 16, 23, 24},
  130.         /*  16 */ {  9, 15, 24, 25},
  131.         /*  17 */ { 10, 18, 26, 27},
  132.         /*  18 */ { 10, 11, 17, 19, 27, 28},
  133.         /*  19 */ { 11, 12, 18, 20, 28, 29},
  134.         /*  20 */ { 12, 13, 19, 21, 29, 30},
  135.         /*  21 */ { 13, 20, 22, 30, 31, 32},
  136.         /*  22 */ { 13, 14, 21, 23, 32, 33},
  137.         /*  23 */ { 14, 15, 22, 24, 33, 34},
  138.         /*  24 */ { 15, 16, 23, 25, 34, 35},
  139.         /*  25 */ { 16, 24, 35, 36},
  140.         /*  26 */ { 17, 27, 37, 38},
  141.         /*  27 */ { 17, 18, 26, 28, 38, 39},
  142.         /*  28 */ { 18, 19, 27, 29, 39, 40},
  143.         /*  29 */ { 19, 20, 28, 30, 40, 41},
  144.         /*  30 */ { 20, 21, 29, 31, 41, 42},
  145.         /*  31 */ { 21, 30, 32, 42, 43, 44},
  146.         /*  32 */ { 21, 22, 31, 33, 44, 45},
  147.         /*  33 */ { 22, 23, 32, 34, 45, 46},
  148.         /*  34 */ { 23, 24, 33, 35, 46, 47},
  149.         /*  35 */ { 24, 25, 34, 36, 47, 48},
  150.         /*  36 */ { 25, 35, 48, 49},
  151.         /*  37 */ { 26, 38, 50},
  152.         /*  38 */ { 26, 27, 37, 39, 50, 51},
  153.         /*  39 */ { 27, 28, 38, 40, 51, 52},
  154.         /*  40 */ { 28, 29, 39, 41, 52, 53},
  155.         /*  41 */ { 29, 30, 40, 42, 53, 54},
  156.         /*  42 */ { 30, 31, 41, 43, 54, 55},
  157.         /*  43 */ { 31, 42, 44, 55, 56},
  158.         /*  44 */ { 31, 32, 43, 45, 56, 57},
  159.         /*  45 */ { 32, 33, 44, 46, 57, 58},
  160.         /*  46 */ { 33, 34, 45, 47, 58, 59},
  161.         /*  47 */ { 34, 35, 46, 48, 59, 60},
  162.         /*  48 */ { 35, 36, 47, 49, 60, 61},
  163.         /*  49 */ { 36, 48, 61},
  164.         /*  50 */ { 37, 38, 51, 62},
  165.         /*  51 */ { 38, 39, 50, 52, 62, 63},
  166.         /*  52 */ { 39, 40, 51, 53, 63, 64},
  167.         /*  53 */ { 40, 41, 52, 54, 64, 65},
  168.         /*  54 */ { 41, 42, 53, 55, 65, 66},
  169.         /*  55 */ { 42, 43, 54, 56, 66, 67},
  170.         /*  56 */ { 43, 44, 55, 57, 67, 68},
  171.         /*  57 */ { 44, 45, 56, 58, 68, 69},
  172.         /*  58 */ { 45, 46, 57, 59, 69, 70},
  173.         /*  59 */ { 46, 47, 58, 60, 70, 71},
  174.         /*  60 */ { 47, 48, 59, 61, 71, 72},
  175.         /*  61 */ { 48, 49, 60, 72},
  176.         /*  62 */ { 50, 51, 63, 73},
  177.         /*  63 */ { 51, 52, 62, 64, 73, 74},
  178.         /*  64 */ { 52, 53, 63, 65, 74, 75},
  179.         /*  65 */ { 53, 54, 64, 66, 75, 76},
  180.         /*  66 */ { 54, 55, 65, 67, 76, 77},
  181.         /*  67 */ { 55, 56, 66, 68, 77, 78},
  182.         /*  68 */ { 56, 57, 67, 69, 78, 79},
  183.         /*  69 */ { 57, 58, 68, 70, 79, 80},
  184.         /*  70 */ { 58, 59, 69, 71, 80, 81},
  185.         /*  71 */ { 59, 60, 70, 72, 81, 82},
  186.         /*  72 */ { 60, 61, 71, 82},
  187.         /*  73 */ { 62, 63, 74, 83},
  188.         /*  74 */ { 63, 64, 73, 75, 83, 84},
  189.         /*  75 */ { 64, 65, 74, 76, 84, 85},
  190.         /*  76 */ { 65, 66, 75, 77, 85, 86},
  191.         /*  77 */ { 66, 67, 76, 78, 86, 87},
  192.         /*  78 */ { 67, 68, 77, 79, 87, 88},
  193.         /*  79 */ { 68, 69, 78, 80, 88, 89},
  194.         /*  80 */ { 69, 70, 79, 81, 89, 90},
  195.         /*  81 */ { 70, 71, 80, 82, 90, 91},
  196.         /*  82 */ { 71, 72, 81, 91},
  197.         /*  83 */ { 73, 74, 84, 92},
  198.         /*  84 */ { 74, 75, 83, 85, 92, 93},
  199.         /*  85 */ { 75, 76, 84, 86, 93, 94},
  200.         /*  86 */ { 76, 77, 85, 87, 94, 95},
  201.         /*  87 */ { 77, 78, 86, 88, 95, 96},
  202.         /*  88 */ { 78, 79, 87, 89, 96, 97},
  203.         /*  89 */ { 79, 80, 88, 90, 97, 98},
  204.         /*  90 */ { 80, 81, 89, 91, 98, 99},
  205.         /*  91 */ { 81, 82, 90, 99},
  206.         /*  92 */ { 83, 84, 93,100},
  207.         /*  93 */ { 84, 85, 92, 94,100,101},
  208.         /*  94 */ { 85, 86, 93, 95,101,102},
  209.         /*  95 */ { 86, 87, 94, 96,102,103},
  210.         /*  96 */ { 87, 88, 95, 97,103,104},
  211.         /*  97 */ { 88, 89, 96, 98,104,105},
  212.         /*  98 */ { 89, 90, 97, 99,105,106},
  213.         /*  99 */ { 90, 91, 98,106},
  214.         /* 100 */ { 92, 93,101},
  215.         /* 101 */ { 93, 94,100,102},
  216.         /* 102 */ { 94, 95,101,103},
  217.         /* 103 */ { 95, 96,102,104},
  218.         /* 104 */ { 96, 97,103,105},
  219.         /* 105 */ { 97, 98,104,106},
  220.         /* 106 */ { 98, 99,105},
  221. };
  222. const int common_neighs[107][6][3] = {
  223.         {}, /* 1-based */
  224.         /*   1 */ {{  6,  2,  3}, {  8,  3,  4}},
  225.         /*   2 */ {{  4,  1,  3}, {  7,  3,  6}, { 11,  5,  6}},
  226.         /*   3 */ {{  5,  2,  6}, {  9,  8,  4}, { 12,  6,  7}, { 14,  8,  7}},
  227.         /*   4 */ {{  2,  1,  3}, {  7,  8,  3}, { 15,  8,  9}},
  228.         /*   5 */ {{  3,  2,  6}, { 12, 11,  6}, { 18, 10, 11}},
  229.         /*   6 */ {{  1,  2,  3}, {  8,  3,  7}, { 10, 11,  5}, { 13, 12,  7}, { 19, 11, 12}},
  230.         /*   7 */ {{  2,  3,  6}, {  4,  8,  3}, { 11, 12,  6}, { 15,  8, 14}, { 20, 12, 13}, { 22, 13, 14}},
  231.         /*   8 */ {{  1,  3,  4}, {  6,  3,  7}, { 13, 14,  7}, { 16,  9, 15}, { 23, 14, 15}},
  232.         /*   9 */ {{  3,  8,  4}, { 14,  8, 15}, { 24, 16, 15}},
  233.         /*  10 */ {{  6, 11,  5}, { 19, 18, 11}, { 27, 17, 18}},
  234.         /*  11 */ {{  2,  5,  6}, {  7, 12,  6}, { 17, 18, 10}, { 20, 19, 12}, { 28, 18, 19}},
  235.         /*  12 */ {{  3,  6,  7}, {  5, 11,  6}, { 14, 13,  7}, { 18, 19, 11}, { 21, 20, 13}, { 29, 19, 20}},
  236.         /*  13 */ {{  6, 12,  7}, {  8, 14,  7}, { 19, 20, 12}, { 23, 22, 14}, { 30, 20, 21}, { 32, 21, 22}},
  237.         /*  14 */ {{  3,  8,  7}, {  9,  8, 15}, { 12, 13,  7}, { 21, 13, 22}, { 24, 23, 15}, { 33, 22, 23}},
  238.         /*  15 */ {{  4,  8,  9}, {  7,  8, 14}, { 22, 14, 23}, { 25, 24, 16}, { 34, 24, 23}},
  239.         /*  16 */ {{  8,  9, 15}, { 23, 24, 15}, { 35, 24, 25}},
  240.         /*  17 */ {{ 11, 18, 10}, { 28, 18, 27}, { 38, 26, 27}},
  241.         /*  18 */ {{  5, 10, 11}, { 12, 19, 11}, { 26, 17, 27}, { 29, 19, 28}, { 39, 27, 28}},
  242.         /*  19 */ {{  6, 11, 12}, { 10, 18, 11}, { 13, 20, 12}, { 27, 18, 28}, { 30, 20, 29}, { 40, 28, 29}},
  243.         /*  20 */ {{  7, 12, 13}, { 11, 19, 12}, { 22, 13, 21}, { 28, 19, 29}, { 31, 21, 30}, { 41, 29, 30}},
  244.         /*  21 */ {{ 12, 20, 13}, { 14, 13, 22}, { 29, 20, 30}, { 33, 32, 22}, { 42, 30, 31}, { 44, 32, 31}},
  245.         /*  22 */ {{  7, 13, 14}, { 15, 14, 23}, { 20, 13, 21}, { 31, 32, 21}, { 34, 33, 23}, { 45, 32, 33}},
  246.         /*  23 */ {{  8, 14, 15}, { 13, 22, 14}, { 16, 24, 15}, { 32, 33, 22}, { 35, 24, 34}, { 46, 33, 34}},
  247.         /*  24 */ {{  9, 16, 15}, { 14, 23, 15}, { 33, 34, 23}, { 36, 25, 35}, { 47, 34, 35}},
  248.         /*  25 */ {{ 15, 24, 16}, { 34, 24, 35}, { 48, 35, 36}},
  249.         /*  26 */ {{ 18, 17, 27}, { 39, 27, 38}, { 50, 37, 38}},
  250.         /*  27 */ {{ 10, 17, 18}, { 19, 18, 28}, { 37, 26, 38}, { 40, 28, 39}, { 51, 38, 39}},
  251.         /*  28 */ {{ 11, 18, 19}, { 17, 18, 27}, { 20, 19, 29}, { 38, 27, 39}, { 41, 40, 29}, { 52, 40, 39}},
  252.         /*  29 */ {{ 12, 19, 20}, { 18, 19, 28}, { 21, 20, 30}, { 39, 40, 28}, { 42, 41, 30}, { 53, 40, 41}},
  253.         /*  30 */ {{ 13, 20, 21}, { 19, 20, 29}, { 32, 21, 31}, { 40, 41, 29}, { 43, 42, 31}, { 54, 41, 42}},
  254.         /*  31 */ {{ 20, 21, 30}, { 22, 32, 21}, { 41, 42, 30}, { 45, 32, 44}, { 55, 42, 43}, { 56, 43, 44}},
  255.         /*  32 */ {{ 13, 21, 22}, { 23, 33, 22}, { 30, 21, 31}, { 43, 44, 31}, { 46, 33, 45}, { 57, 44, 45}},
  256.         /*  33 */ {{ 14, 22, 23}, { 21, 32, 22}, { 24, 34, 23}, { 44, 32, 45}, { 47, 34, 46}, { 58, 45, 46}},
  257.         /*  34 */ {{ 15, 24, 23}, { 22, 33, 23}, { 25, 24, 35}, { 45, 33, 46}, { 48, 35, 47}, { 59, 46, 47}},
  258.         /*  35 */ {{ 16, 24, 25}, { 23, 24, 34}, { 46, 34, 47}, { 49, 48, 36}, { 60, 48, 47}},
  259.         /*  36 */ {{ 24, 25, 35}, { 47, 48, 35}, { 61, 48, 49}},
  260.         /*  37 */ {{ 27, 26, 38}, { 51, 50, 38}},
  261.         /*  38 */ {{ 17, 26, 27}, { 28, 27, 39}, { 52, 51, 39}, { 62, 50, 51}},
  262.         /*  39 */ {{ 18, 27, 28}, { 26, 27, 38}, { 29, 40, 28}, { 50, 51, 38}, { 53, 40, 52}, { 63, 51, 52}},
  263.         /*  40 */ {{ 19, 28, 29}, { 27, 28, 39}, { 30, 41, 29}, { 51, 52, 39}, { 54, 41, 53}, { 64, 52, 53}},
  264.         /*  41 */ {{ 20, 29, 30}, { 28, 40, 29}, { 31, 42, 30}, { 52, 40, 53}, { 55, 42, 54}, { 65, 53, 54}},
  265.         /*  42 */ {{ 21, 30, 31}, { 29, 41, 30}, { 44, 43, 31}, { 53, 41, 54}, { 56, 43, 55}, { 66, 54, 55}},
  266.         /*  43 */ {{ 30, 42, 31}, { 32, 44, 31}, { 54, 42, 55}, { 57, 56, 44}, { 67, 56, 55}},
  267.         /*  44 */ {{ 21, 32, 31}, { 33, 32, 45}, { 42, 43, 31}, { 55, 56, 43}, { 58, 57, 45}, { 68, 56, 57}},
  268.         /*  45 */ {{ 22, 32, 33}, { 31, 32, 44}, { 34, 33, 46}, { 56, 57, 44}, { 59, 58, 46}, { 69, 57, 58}},
  269.         /*  46 */ {{ 23, 33, 34}, { 32, 33, 45}, { 35, 34, 47}, { 57, 58, 45}, { 60, 59, 47}, { 70, 58, 59}},
  270.         /*  47 */ {{ 24, 34, 35}, { 33, 34, 46}, { 36, 48, 35}, { 58, 59, 46}, { 61, 48, 60}, { 71, 59, 60}},
  271.         /*  48 */ {{ 25, 35, 36}, { 34, 35, 47}, { 59, 60, 47}, { 72, 60, 61}},
  272.         /*  49 */ {{ 35, 48, 36}, { 60, 48, 61}},
  273.         /*  50 */ {{ 26, 37, 38}, { 39, 51, 38}, { 63, 51, 62}},
  274.         /*  51 */ {{ 27, 38, 39}, { 37, 50, 38}, { 40, 52, 39}, { 64, 52, 63}, { 73, 62, 63}},
  275.         /*  52 */ {{ 28, 40, 39}, { 38, 51, 39}, { 41, 40, 53}, { 62, 51, 63}, { 65, 64, 53}, { 74, 64, 63}},
  276.         /*  53 */ {{ 29, 40, 41}, { 39, 40, 52}, { 42, 41, 54}, { 63, 64, 52}, { 66, 65, 54}, { 75, 64, 65}},
  277.         /*  54 */ {{ 30, 41, 42}, { 40, 41, 53}, { 43, 42, 55}, { 64, 65, 53}, { 67, 66, 55}, { 76, 65, 66}},
  278.         /*  55 */ {{ 31, 42, 43}, { 41, 42, 54}, { 44, 56, 43}, { 65, 66, 54}, { 68, 56, 67}, { 77, 66, 67}},
  279.         /*  56 */ {{ 31, 43, 44}, { 42, 43, 55}, { 45, 57, 44}, { 66, 67, 55}, { 69, 57, 68}, { 78, 67, 68}},
  280.         /*  57 */ {{ 32, 44, 45}, { 43, 56, 44}, { 46, 58, 45}, { 67, 56, 68}, { 70, 58, 69}, { 79, 68, 69}},
  281.         /*  58 */ {{ 33, 45, 46}, { 44, 57, 45}, { 47, 59, 46}, { 68, 57, 69}, { 71, 59, 70}, { 80, 69, 70}},
  282.         /*  59 */ {{ 34, 46, 47}, { 45, 58, 46}, { 48, 60, 47}, { 69, 58, 70}, { 72, 60, 71}, { 81, 70, 71}},
  283.         /*  60 */ {{ 35, 48, 47}, { 46, 59, 47}, { 49, 48, 61}, { 70, 59, 71}, { 82, 72, 71}},
  284.         /*  61 */ {{ 36, 48, 49}, { 47, 48, 60}, { 71, 72, 60}},
  285.         /*  62 */ {{ 38, 50, 51}, { 52, 51, 63}, { 74, 73, 63}},
  286.         /*  63 */ {{ 39, 51, 52}, { 50, 51, 62}, { 53, 64, 52}, { 75, 64, 74}, { 83, 73, 74}},
  287.         /*  64 */ {{ 40, 52, 53}, { 51, 52, 63}, { 54, 65, 53}, { 73, 74, 63}, { 76, 65, 75}, { 84, 74, 75}},
  288.         /*  65 */ {{ 41, 53, 54}, { 52, 64, 53}, { 55, 66, 54}, { 74, 64, 75}, { 77, 66, 76}, { 85, 75, 76}},
  289.         /*  66 */ {{ 42, 54, 55}, { 53, 65, 54}, { 56, 67, 55}, { 75, 65, 76}, { 78, 67, 77}, { 86, 76, 77}},
  290.         /*  67 */ {{ 43, 56, 55}, { 54, 66, 55}, { 57, 56, 68}, { 76, 66, 77}, { 79, 68, 78}, { 87, 77, 78}},
  291.         /*  68 */ {{ 44, 56, 57}, { 55, 56, 67}, { 58, 57, 69}, { 77, 67, 78}, { 80, 69, 79}, { 88, 78, 79}},
  292.         /*  69 */ {{ 45, 57, 58}, { 56, 57, 68}, { 59, 58, 70}, { 78, 68, 79}, { 81, 80, 70}, { 89, 80, 79}},
  293.         /*  70 */ {{ 46, 58, 59}, { 57, 58, 69}, { 60, 59, 71}, { 79, 80, 69}, { 82, 81, 71}, { 90, 80, 81}},
  294.         /*  71 */ {{ 47, 59, 60}, { 58, 59, 70}, { 61, 72, 60}, { 80, 81, 70}, { 91, 81, 82}},
  295.         /*  72 */ {{ 48, 60, 61}, { 59, 60, 71}, { 81, 82, 71}},
  296.         /*  73 */ {{ 51, 62, 63}, { 64, 74, 63}, { 84, 74, 83}},
  297.         /*  74 */ {{ 52, 64, 63}, { 62, 73, 63}, { 65, 64, 75}, { 85, 75, 84}, { 92, 83, 84}},
  298.         /*  75 */ {{ 53, 64, 65}, { 63, 64, 74}, { 66, 65, 76}, { 83, 74, 84}, { 86, 76, 85}, { 93, 84, 85}},
  299.         /*  76 */ {{ 54, 65, 66}, { 64, 65, 75}, { 67, 66, 77}, { 84, 75, 85}, { 87, 77, 86}, { 94, 85, 86}},
  300.         /*  77 */ {{ 55, 66, 67}, { 65, 66, 76}, { 68, 67, 78}, { 85, 76, 86}, { 88, 78, 87}, { 95, 86, 87}},
  301.         /*  78 */ {{ 56, 67, 68}, { 66, 67, 77}, { 69, 68, 79}, { 86, 77, 87}, { 89, 88, 79}, { 96, 88, 87}},
  302.         /*  79 */ {{ 57, 68, 69}, { 67, 68, 78}, { 70, 80, 69}, { 87, 88, 78}, { 90, 80, 89}, { 97, 88, 89}},
  303.         /*  80 */ {{ 58, 69, 70}, { 68, 69, 79}, { 71, 81, 70}, { 88, 89, 79}, { 91, 81, 90}, { 98, 89, 90}},
  304.         /*  81 */ {{ 59, 70, 71}, { 69, 80, 70}, { 72, 82, 71}, { 89, 80, 90}, { 99, 90, 91}},
  305.         /*  82 */ {{ 60, 72, 71}, { 70, 81, 71}, { 90, 81, 91}},
  306.         /*  83 */ {{ 63, 73, 74}, { 75, 74, 84}, { 93, 84, 92}},
  307.         /*  84 */ {{ 64, 74, 75}, { 73, 74, 83}, { 76, 75, 85}, { 94, 85, 93}, {100, 92, 93}},
  308.         /*  85 */ {{ 65, 75, 76}, { 74, 75, 84}, { 77, 76, 86}, { 92, 84, 93}, { 95, 94, 86}, {101, 93, 94}},
  309.         /*  86 */ {{ 66, 76, 77}, { 75, 76, 85}, { 78, 77, 87}, { 93, 85, 94}, { 96, 95, 87}, {102, 94, 95}},
  310.         /*  87 */ {{ 67, 77, 78}, { 76, 77, 86}, { 79, 88, 78}, { 94, 86, 95}, { 97, 96, 88}, {103, 96, 95}},
  311.         /*  88 */ {{ 68, 78, 79}, { 77, 78, 87}, { 80, 89, 79}, { 95, 96, 87}, { 98, 97, 89}, {104, 96, 97}},
  312.         /*  89 */ {{ 69, 80, 79}, { 78, 88, 79}, { 81, 80, 90}, { 96, 88, 97}, { 99, 98, 90}, {105, 97, 98}},
  313.         /*  90 */ {{ 70, 80, 81}, { 79, 80, 89}, { 82, 81, 91}, { 97, 89, 98}, {106, 98, 99}},
  314.         /*  91 */ {{ 71, 81, 82}, { 80, 81, 90}, { 98, 90, 99}},
  315.         /*  92 */ {{ 74, 83, 84}, { 85, 84, 93}, {101,100, 93}},
  316.         /*  93 */ {{ 75, 84, 85}, { 83, 84, 92}, { 86, 85, 94}, {102,101, 94}},
  317.         /*  94 */ {{ 76, 85, 86}, { 84, 85, 93}, { 87, 86, 95}, {100,101, 93}, {103,102, 95}},
  318.         /*  95 */ {{ 77, 86, 87}, { 85, 94, 86}, { 88, 96, 87}, {101,102, 94}, {104, 96,103}},
  319.         /*  96 */ {{ 78, 88, 87}, { 86, 95, 87}, { 89, 88, 97}, {102,103, 95}, {105,104, 97}},
  320.         /*  97 */ {{ 79, 88, 89}, { 87, 96, 88}, { 90, 89, 98}, {103,104, 96}, {106,105, 98}},
  321.         /*  98 */ {{ 80, 89, 90}, { 88, 97, 89}, { 91, 90, 99}, {104,105, 97}},
  322.         /*  99 */ {{ 81, 90, 91}, { 89, 98, 90}, {105,106, 98}},
  323.         /* 100 */ {{ 84, 92, 93}, { 94,101, 93}},
  324.         /* 101 */ {{ 85, 93, 94}, { 92,100, 93}, { 95,102, 94}},
  325.         /* 102 */ {{ 86, 94, 95}, { 93,101, 94}, { 96,103, 95}},
  326.         /* 103 */ {{ 87, 96, 95}, { 94,102, 95}, { 97,104, 96}},
  327.         /* 104 */ {{ 88, 96, 97}, { 95, 96,103}, { 98,105, 97}},
  328.         /* 105 */ {{ 89, 97, 98}, { 96,104, 97}, { 99,106, 98}},
  329.         /* 106 */ {{ 90, 98, 99}, { 97,105, 98}},
  330. };
  331. const int edge_neighs[107][3] = {
  332.         {}, /* 1-based */
  333.         /*   1 */ {},
  334.         /*   2 */ {},
  335.         /*   3 */ {  1,  2,  4},
  336.         /*   4 */ {},
  337.         /*   5 */ {},
  338.         /*   6 */ {  2,  5},
  339.         /*   7 */ {},
  340.         /*   8 */ {  4,  9},
  341.         /*   9 */ {},
  342.         /*  10 */ {},
  343.         /*  11 */ {  5, 10},
  344.         /*  12 */ {},
  345.         /*  13 */ {},
  346.         /*  14 */ {},
  347.         /*  15 */ {  9, 16},
  348.         /*  16 */ {},
  349.         /*  17 */ {},
  350.         /*  18 */ { 10, 17},
  351.         /*  19 */ {},
  352.         /*  20 */ {},
  353.         /*  21 */ {},
  354.         /*  22 */ {},
  355.         /*  23 */ {},
  356.         /*  24 */ { 16, 25},
  357.         /*  25 */ {},
  358.         /*  26 */ {},
  359.         /*  27 */ { 17, 26},
  360.         /*  28 */ {},
  361.         /*  29 */ {},
  362.         /*  30 */ {},
  363.         /*  31 */ {},
  364.         /*  32 */ {},
  365.         /*  33 */ {},
  366.         /*  34 */ {},
  367.         /*  35 */ { 36, 25},
  368.         /*  36 */ {},
  369.         /*  37 */ {},
  370.         /*  38 */ { 37, 50, 26},
  371.         /*  39 */ {},
  372.         /*  40 */ {},
  373.         /*  41 */ {},
  374.         /*  42 */ {},
  375.         /*  43 */ {},
  376.         /*  44 */ {},
  377.         /*  45 */ {},
  378.         /*  46 */ {},
  379.         /*  47 */ {},
  380.         /*  48 */ { 36, 49, 61},
  381.         /*  49 */ {},
  382.         /*  50 */ {},
  383.         /*  51 */ { 50, 62},
  384.         /*  52 */ {},
  385.         /*  53 */ {},
  386.         /*  54 */ {},
  387.         /*  55 */ {},
  388.         /*  56 */ {},
  389.         /*  57 */ {},
  390.         /*  58 */ {},
  391.         /*  59 */ {},
  392.         /*  60 */ { 72, 61},
  393.         /*  61 */ {},
  394.         /*  62 */ {},
  395.         /*  63 */ { 73, 62},
  396.         /*  64 */ {},
  397.         /*  65 */ {},
  398.         /*  66 */ {},
  399.         /*  67 */ {},
  400.         /*  68 */ {},
  401.         /*  69 */ {},
  402.         /*  70 */ {},
  403.         /*  71 */ { 72, 82},
  404.         /*  72 */ {},
  405.         /*  73 */ {},
  406.         /*  74 */ { 73, 83},
  407.         /*  75 */ {},
  408.         /*  76 */ {},
  409.         /*  77 */ {},
  410.         /*  78 */ {},
  411.         /*  79 */ {},
  412.         /*  80 */ {},
  413.         /*  81 */ { 82, 91},
  414.         /*  82 */ {},
  415.         /*  83 */ {},
  416.         /*  84 */ { 83, 92},
  417.         /*  85 */ {},
  418.         /*  86 */ {},
  419.         /*  87 */ {},
  420.         /*  88 */ {},
  421.         /*  89 */ {},
  422.         /*  90 */ { 99, 91},
  423.         /*  91 */ {},
  424.         /*  92 */ {},
  425.         /*  93 */ {100,101, 92},
  426.         /*  94 */ {101,102},
  427.         /*  95 */ {102,103},
  428.         /*  96 */ {103,104},
  429.         /*  97 */ {104,105},
  430.         /*  98 */ { 99,105,106},
  431.         /*  99 */ {},
  432.         /* 100 */ {},
  433.         /* 101 */ {},
  434.         /* 102 */ {},
  435.         /* 103 */ {},
  436.         /* 104 */ {},
  437.         /* 105 */ {},
  438.         /* 106 */ {},
  439. };
  440. const int edge2corner[] = {
  441.         /*  0 */  0, /* 0 -> 0 */
  442.         /*  1 */  0, /* TOPRIGHT -> 0 */
  443.         /*  2 */  0, /* BOTTOMRIGHT -> 0 */
  444.         /*  3 */  0, /* TOPRIGHT|BOTTOMRIGHT -> 0 */
  445.         /*  4 */  0, /* BOTTOM -> 0 */
  446.         /*  5 */  0, /* TOPRIGHT|BOTTOM -> 0 */
  447.         /*  6 */  0, /* BOTTOMRIGHT|BOTTOM -> 0 */
  448.         /*  7 */  6, /* TOPRIGHT|BOTTOMRIGHT|BOTTOM -> MIDRIGHT|BOTTOMRIGHT */
  449.         /*  8 */  0, /* BOTTOMLEFT -> 0 */
  450.         /*  9 */  0, /* TOPRIGHT|BOTTOMLEFT -> 0 */
  451.         /* 10 */  0, /* BOTTOMRIGHT|BOTTOMLEFT -> 0 */
  452.         /* 11 */  2, /* TOPRIGHT|BOTTOMRIGHT|BOTTOMLEFT -> MIDRIGHT */
  453.         /* 12 */  0, /* BOTTOM|BOTTOMLEFT -> 0 */
  454.         /* 13 */  8, /* TOPRIGHT|BOTTOM|BOTTOMLEFT -> BOTTOMLEFT */
  455.         /* 14 */ 12, /* BOTTOMRIGHT|BOTTOM|BOTTOMLEFT -> BOTTOMRIGHT|BOTTOMLEFT */
  456.         /* 15 */ 14, /* TOPRIGHT|BOTTOMRIGHT|BOTTOM|BOTTOMLEFT -> MIDRIGHT|BOTTOMRIGHT|BOTTOMLEFT */
  457.         /* 16 */  0, /* TOPLEFT -> 0 */
  458.         /* 17 */  0, /* TOPRIGHT|TOPLEFT -> 0 */
  459.         /* 18 */  0, /* BOTTOMRIGHT|TOPLEFT -> 0 */
  460.         /* 19 */  3, /* TOPRIGHT|BOTTOMRIGHT|TOPLEFT -> TOP|MIDRIGHT */
  461.         /* 20 */  0, /* BOTTOM|TOPLEFT -> 0 */
  462.         /* 21 */  1, /* TOPRIGHT|BOTTOM|TOPLEFT -> TOP */
  463.         /* 22 */  4, /* BOTTOMRIGHT|BOTTOM|TOPLEFT -> BOTTOMRIGHT */
  464.         /* 23 */  7, /* TOPRIGHT|BOTTOMRIGHT|BOTTOM|TOPLEFT -> TOP|MIDRIGHT|BOTTOMRIGHT */
  465.         /* 24 */  0, /* BOTTOMLEFT|TOPLEFT -> 0 */
  466.         /* 25 */ 17, /* TOPRIGHT|BOTTOMLEFT|TOPLEFT -> TOP|MIDLEFT */
  467.         /* 26 */ 16, /* BOTTOMRIGHT|BOTTOMLEFT|TOPLEFT -> MIDLEFT */
  468.         /* 27 */ 19, /* TOPRIGHT|BOTTOMRIGHT|BOTTOMLEFT|TOPLEFT -> TOP|MIDRIGHT|MIDLEFT */
  469.         /* 28 */ 24, /* BOTTOM|BOTTOMLEFT|TOPLEFT -> BOTTOMLEFT|MIDLEFT */
  470.         /* 29 */ 25, /* TOPRIGHT|BOTTOM|BOTTOMLEFT|TOPLEFT -> TOP|BOTTOMLEFT|MIDLEFT */
  471.         /* 30 */ 28, /* BOTTOMRIGHT|BOTTOM|BOTTOMLEFT|TOPLEFT -> BOTTOMRIGHT|BOTTOMLEFT|MIDLEFT */
  472.         /* 31 */ 31, /* TOPRIGHT|BOTTOMRIGHT|BOTTOM|BOTTOMLEFT|TOPLEFT -> TOP|MIDRIGHT|BOTTOMRIGHT|BOTTOMLEFT|MIDLEFT */
  473. };
  474. const int bits[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5};
  475. #define enough_corners(i) (0xfee8e880 & (1 << (i)))
  476. #define E_TOPRIGHT            1
  477. #define E_BOTTOMRIGHT         2
  478. #define E_BOTTOM              4
  479. #define E_BOTTOMLEFT          8
  480. #define E_TOPLEFT            16
  481. #define C_TOP                 1
  482. #define C_MIDRIGHT            2
  483. #define C_BOTTOMRIGHT         4
  484. #define C_BOTTOMLEFT          8
  485. #define C_MIDLEFT            16
  486. /* Apologies for my "French". :> */
  487.  
  488. #include <stdio.h>
  489. #include <string.h>
  490. #include <stdlib.h>
  491. #include <unistd.h>
  492. #include <stdint.h>
  493. #include <time.h>
  494.  
  495.  
  496. #define MAX_DEPTH_START 3
  497. int max_depth = MAX_DEPTH_START;
  498. int verbose = 0;
  499.  
  500. #define EDGE_BITS 24
  501.  
  502. int first_moves[][40] = {{43, 0}, {55, 44, 0}, {43, 55, 44, 0}, {42, 44, 0}, {42, 43, 44, 0}, {31, 56, 0}, {31, 43, 56, 0}, {0}};
  503. //int first_moves[][40] = {{37, 51, 64, 76, 87, 97, 106, 0}, {0}};
  504. int start_paths[][2] = {{93, 48}, {38, 48}, {3, 98}, {3, 93}, {0}, /* END */ {85, 47}, {7, 89}, {39, 47}, {39, 89}, {0}};
  505. int *first_move, *start_path;
  506.  
  507. void log_options(char *tag)
  508. {
  509.         /*
  510.         FILE *fp = fopen("../options.log", "a");
  511.         fprintf(fp, "first_move %d %d %d %d start_path %d %d %s\n", first_move[0], first_move[1], first_move[2], first_move[3], start_path[0], start_path[1], tag ? tag : "");
  512.         fclose(fp);
  513.         */
  514. }
  515.  
  516. void pick_options()
  517. {
  518.         int i;
  519.        
  520.         for (i = 0; first_moves[i][0]; ++i)
  521.                 if (random() < (RAND_MAX / (i + 1)))
  522.                         first_move = first_moves[i];
  523.        
  524.         for (i = 0; start_paths[i][0]; ++i)
  525.                 if (random() < (RAND_MAX / (i + 1)))
  526.                         start_path = start_paths[i];
  527.        
  528.         log_options(NULL);
  529. }
  530.  
  531. #define LOG(log...) fprintf(stderr, log)
  532.  
  533. typedef enum {
  534.         ST_1LINE = 0,
  535.         ST_HALFLINE,
  536.         ST_HALFLINE_DONE,
  537.         ST_EXTRALINE,
  538.         ST_FILLIN,
  539.         ST_FAILED,
  540. } stage_t;
  541.  
  542. struct plans {
  543.         int todo[107];
  544.         int todolen;
  545.         stage_t stage;
  546. };
  547.  
  548. struct game {
  549.         /* Bits 0 and 1 are player white and black.
  550.            Bits EDGE_BITS+ are edges touched indirectly by this field. */
  551.         int b[107];
  552.        
  553.         /* 1-based arrray, bitfields showing which corners are owned by
  554.            each player. enough_corners() tells whether a player has won. */
  555.         int player_corners[3];
  556.        
  557.         int turn;
  558.         int cur, me;
  559.        
  560.         struct plans *plans;
  561. };
  562.  
  563. struct game *new_game(void)
  564. {
  565.         struct game *g = calloc(sizeof(struct game), 1);
  566.         int i;
  567.        
  568.         memset(g, 0, sizeof(struct game));
  569.         g->cur = g->turn = 1;
  570.         g->b[0] = -1;
  571.         for (i = 1; i <= 106; ++i)
  572.                 g->b[i] = edges[i] << EDGE_BITS;
  573.        
  574.         g->plans = calloc(sizeof(struct plans), 1);
  575.        
  576.         return g;
  577. }
  578.  
  579. void print_board(struct game *g)
  580. {
  581.         int i, j, nl;
  582.         const int *rs = rowsize;
  583.        
  584.         if (!verbose)
  585.                 return;
  586.        
  587.         nl = 0;
  588.         for (i = 1; i < 107; ++i) {
  589.                 if (nl == 0) {
  590.                         LOG("%3d  ", i);
  591.                         for (j = 0; j < (13 - *rs); j++)
  592.                                 LOG(" ");
  593.                         nl = *(rs++);
  594.                 }
  595.                 LOG("%2d", g->b[i] & 3);
  596.                 if (--nl == 0)
  597.                         LOG("\n");
  598.         }
  599. }
  600.  
  601. void print_raw(int board[107])
  602. {
  603.         int i, j, nl;
  604.         const int *rs = rowsize;
  605.        
  606.         if (!verbose)
  607.                 return;
  608.        
  609.         nl = 0;
  610.         for (i = 1; i < 107; ++i) {
  611.                 if (nl == 0) {
  612.                         LOG("%3d  ", i);
  613.                         for (j = 0; j < (13 - *rs); j++)
  614.                                 LOG("  ");
  615.                         nl = *(rs++);
  616.                 }
  617.                 LOG("%4d", board[i] & 0xffff);
  618.                 if (--nl == 0)
  619.                         LOG("\n");
  620.         }
  621. }
  622.  
  623. int find_path_count_steps(struct game *g, int src, int dst,
  624.                             int result[107], int step, int map[107])
  625. {
  626.         int i, n, best = 9999;
  627.        
  628.         /* Getting to a cell we already own is free, if it's empty it counts as a step/turn. */
  629.         if (!(g->b[src] & 3))
  630.                 ++step;
  631.         else if (!(g->b[src] & g->cur))
  632.                 return best;
  633.        
  634.         /* If we got here before with same/less effort, abort. */
  635.         if (step >= map[src])
  636.                 return best;
  637.        
  638.         /* Found a new best route to this point. */
  639.         map[src] = step;
  640.        
  641.         /* Are we at our destination yet? */
  642.         if (src == dst) {
  643.                 /* Found a new best route if we got this far. */
  644.                 if (!(g->b[src] & 3))
  645.                         result[step-1] = src;
  646.                 return step;
  647.         }
  648.        
  649.         for (i = 0; i < 6 && (n = neighs[src][i]); ++i) {
  650.                 if (!(g->b[n] & (3 ^ g->cur))) {
  651.                         int ret = find_path_count_steps(g, n, dst, result, step, map);
  652.                         if (ret < best) {
  653.                                 best = ret;
  654.                                 result[step-1] = src;
  655.                         }
  656.                 }
  657.         }
  658.        
  659.         return best;
  660. }
  661.  
  662. int find_path(struct game *g, int src, int dst, int result[107])
  663. {
  664.         int map[107] = {};
  665.         int fuck[108];
  666.         int ret = 0;
  667.        
  668.         memset(map, 0x7f, sizeof(map));
  669.        
  670.         /* TODO(wilmer): REmove the very very bad things done up here ([-1]) */
  671.         ret = find_path_count_steps(g, src, dst, fuck + 1, 0, map);
  672.         memcpy(result, fuck + 1, sizeof(int) * 107);
  673.         //ret = find_path_count_steps(g, src, dst, result, 0, map);
  674.        
  675.         /*
  676.         LOG("find_path(%d, %d) =", src, dst);
  677.         int i;
  678.         if (ret>100)
  679.                 LOG(" %d", ret);
  680.         else
  681.                 for (i = 0; i < ret; ++i)
  682.                         LOG(" %d", result[i]);
  683.         LOG("\n");
  684.         */
  685.        
  686.         return ret < 999 ? ret : 1000000;
  687. }
  688.  
  689. int find_path_triple(struct game *g, int a, int b, int c, int result[107])
  690. {
  691.         int abbc[107], acbc[107];
  692.         struct game g2[1];
  693.         int ret = 0, best = 1000000;
  694.         int bc;
  695.         int i;
  696.        
  697.         //LOG("Finding path for %d|%d|%d\n", a, b, c);
  698.        
  699.         ret = find_path(g, a, b, abbc);
  700.         if (ret >= 999)
  701.                 return best;
  702.        
  703.         memcpy(g2, g, sizeof(struct game));
  704.         for (i = 0; i < ret; ++i)
  705.                 g2->b[abbc[i]] |= g2->cur;
  706.        
  707.         bc = find_path(g2, b, c, abbc + ret);
  708.         if (bc >= 999)
  709.                 return best;
  710.        
  711.         best = ret + bc;
  712.         /* No need to try abac, since find_path() will already try that out. */
  713.        
  714.         ret = find_path(g, a, c, acbc);
  715.         /* ab and bc are reachable, so is ac, no need to check. */
  716.        
  717.         memcpy(g2, g, sizeof(struct game));
  718.         for (i = 0; i < ret; ++i)
  719.                 g2->b[acbc[i]] |= g2->cur;
  720.        
  721.         ret += find_path(g2, b, c, acbc + ret);
  722.         if (ret < best) {
  723.                 memcpy(result, acbc, sizeof(int) * ret);
  724.                 best = ret;
  725.         } else {
  726.                 memcpy(result, abbc, sizeof(int) * best);
  727.         }
  728.        
  729.         /*
  730.         LOG("find_path_triple =>");
  731.         for (i = 0; i < best; ++i)
  732.                 LOG(" %d", result[i]);
  733.         LOG("\n");
  734.         */
  735.  
  736.         return best;
  737. }
  738.  
  739. void find_safe_paths_int(struct game *g, int src, int poss[107], int depth)
  740. {
  741.         int i, n;
  742.        
  743.         if ((g->b[src] & (g->cur ^ 3)) || (poss[src] & 0x1000000))
  744.                 return;
  745.         ++poss[src];
  746.        
  747.         if (depth == 1) /* 1-based so initial depth == number of moves */
  748.                 return;
  749.        
  750.         poss[src] |= 0x1000000; /* Mark as seen, avoid cycles. */
  751.        
  752.         for (i = 0; i < 6 && (n = common_neighs[src][i][0]); ++i) {
  753.                 /* Opponent is (partially) on the way, this destination is unsafe. */
  754.                 if ((g->b[common_neighs[src][i][1]] | g->b[common_neighs[src][i][2]]) & (g->cur ^ 3))
  755.                         continue;
  756.                
  757.                 find_safe_paths_int(g, n, poss, depth - 1);
  758.         }
  759.        
  760.         poss[src] &= ~0x1000000;
  761. }
  762.  
  763. void find_safe_path_int(struct game *g, int src, int dst, int result[107], int work[107], int depth)
  764. {
  765.         int i, n;
  766.        
  767.         if ((g->b[src] & (g->cur ^ 3)) || (work[src] & 0x1000000))
  768.                 return;
  769.        
  770.         if (depth == 1) /* 1-based so initial depth == number of moves */
  771.                 return;
  772.        
  773.         if (!(g->b[src] & g->cur))
  774.                 work[src] += 1000;
  775.         work[src] |= 0x1000000; /* Mark as seen, avoid cycles. */
  776.        
  777.         if (src == dst) {
  778.                 n = 0;
  779.                 /* Fragile: Count number of moves left to do. Mandatory counts
  780.                    as 1, optional only if its counterpart is "higher". */
  781.                 for (i = 1; i < 107; ++i) {
  782.                         int w = work[i] & 0xffffff;
  783.                         if ((w >= 1000) || (w && i < w))
  784.                                 ++n;
  785.                 }
  786.                 if (n < result[0]) {
  787.                         LOG("Best one so far at depth %d, todo %d:\n", depth, n);
  788.                         print_raw(work);
  789.                         memcpy(result, work, sizeof(int) * 107);
  790.                         result[0] = n;
  791.                 }
  792.         } else {
  793.                 for (i = 0; i < 6 && (n = common_neighs[src][i][0]); ++i) {
  794.                         int mid = g->b[common_neighs[src][i][1]] | g->b[common_neighs[src][i][2]];
  795.                        
  796.                         /* Opponent is (partially) in the way, this destination is unsafe. */
  797.                         if ((mid & 3) == (g->cur ^ 3))
  798.                                 continue;
  799.                        
  800.                         if (work[common_neighs[src][i][1]] || work[common_neighs[src][i][2]])
  801.                                 continue;
  802.                        
  803.                         if (!(mid & 3)) {
  804.                                 work[common_neighs[src][i][1]] = common_neighs[src][i][2];
  805.                                 work[common_neighs[src][i][2]] = common_neighs[src][i][1];
  806.                         }
  807.                        
  808.                         find_safe_path_int(g, n, dst, result, work, depth - 1);
  809.  
  810.                         if (!(mid & 3)) {
  811.                                 work[common_neighs[src][i][1]] = 0;
  812.                                 work[common_neighs[src][i][2]] = 0;
  813.                         }
  814.                 }
  815.         }
  816.        
  817.         if (!(g->b[src] & g->cur))
  818.                 work[src] -= 1000;
  819.         work[src] &= ~0x1000000;
  820. }
  821.  
  822. int find_safe_path(struct game *g, int src, int dst, int result[107], int depth)
  823. {
  824.         int work[107] = {};
  825.         int i;
  826.        
  827.         result[0] = 999999;
  828.         find_safe_path_int(g, src, dst, result, work, depth);
  829.        
  830.         if (result[0] > 100)
  831.                 return 999999;
  832.        
  833.         for (i = 1; i < 107; ++i)
  834.                 result[i] &= ~0x1000000;
  835.        
  836.         LOG("Safe path from %d to %d:\n", src, dst);
  837.         print_raw(result);
  838.        
  839.         return result[0];
  840. }
  841.  
  842. int find_clusters_int(struct game *g, int result[107], int pos)
  843. {
  844.         int i, n;
  845.         int ret = 1;
  846.        
  847.         result[pos] |= 0x100; /* Seen. */
  848.         for (i = 0; i < 6 && (n = neighs[pos][i]); ++i) {
  849.                 if (!(result[n] & 0x100) && (g->b[n] & g->b[pos] & 3)) {
  850.                         ret += find_clusters_int(g, result, n);
  851.                 }
  852.         }
  853.        
  854.         return ret;
  855. }
  856.  
  857. void find_clusters(struct game *g, int result[107])
  858. {
  859.         int i;
  860.         for (i = 1; i < 107; ++i) {
  861.                 if (!(result[i] & 0x100) && (g->b[i] & 3)) {
  862.                         result[i] = find_clusters_int(g, result, i);
  863.                         LOG("Field size at %d: %d\n", i, result[i] &= 0xff);
  864.                 }
  865.         }
  866. }
  867.  
  868. void apply_move_update_edges(struct game *g, int pos, int new_edges)
  869. {
  870.         int i, n;
  871.        
  872.         g->b[pos] |= new_edges;
  873.        
  874.         for (i = 0; i < 6 && (n = neighs[pos][i]); ++i)
  875.                 if ((g->b[n] & g->cur) && (g->b[n] & new_edges) != new_edges)
  876.                         apply_move_update_edges(g, n, new_edges);
  877. }
  878.  
  879. void apply_move(struct game *g, int move)
  880. {
  881.         if (move != -1) {
  882.                 int i, n, new_edges = 0;
  883.                
  884.                 for (i = 0; i < 6 && (n = neighs[move][i]); ++i) {
  885.                         if (!(g->b[n] & g->cur))
  886.                                 continue;
  887.                        
  888.                         new_edges |= g->b[n];
  889.                 }
  890.                 new_edges |= g->b[move];
  891.                 new_edges &= (0xff << EDGE_BITS);
  892.                 for (i = 0; i < 6 && (n = neighs[move][i]); ++i) {
  893.                         if (!(g->b[n] & g->cur))
  894.                                 continue;
  895.                        
  896.                         if ((new_edges & g->b[n]) < new_edges)
  897.                                 apply_move_update_edges(g, n, new_edges);
  898.                 }
  899.                
  900.                 g->b[move] |= g->cur | new_edges;
  901.                 g->player_corners[g->cur] |= edge2corner[new_edges>>EDGE_BITS];
  902.         } else {
  903.                 int i;
  904.                
  905.                 /* Don't bother checking whether this is turn 2, referee does it. */
  906.                 for (i = 1; i < 107; ++i)
  907.                         if ((g->b[i] & 3)) {
  908.                                 g->b[i] ^= 3;
  909.                                 break;
  910.                         }
  911.         }
  912.        
  913.         g->cur ^= 3;
  914.         ++g->turn;
  915. }
  916.  
  917. int find_winner(struct game *g)
  918. {
  919.         int i;
  920.        
  921.         for (i = 1; i <= 2; ++i)
  922.                 if (enough_corners(g->player_corners[i])) {
  923.                         printf("Player %d has WON!\n", i);
  924.                         return i;
  925.                 }
  926.        
  927.         return 0;
  928. }
  929.  
  930. int follow_game(void)
  931. {
  932.         struct game *g = new_game();
  933.         int move;
  934.        
  935.         while(scanf("%d", &move) == 1) {
  936.                 apply_move(g, move);
  937.                 print_board(g);
  938.                 find_winner(g);
  939.         }
  940.        
  941.         return 0;
  942. }
  943.  
  944. void update_plans(struct game *g)
  945. {
  946.         int a, b, c, i;
  947.         int path[107], best_path[107], path_len, best_len = 99999;
  948.         int fields[107];
  949.        
  950.         if (!g->plans) {
  951.                 g->plans = calloc(sizeof(struct plans), 1);
  952.         }
  953.        
  954.         if (g->plans->todolen) {
  955.                 for (i = 0; i < g->plans->todolen; ++i) {
  956.                         if (g->b[g->plans->todo[i]] & (3 ^ g->cur))
  957.                                 break;
  958.                 }
  959.                
  960.                 /* Our plan should still work. */
  961.                 if (i == g->plans->todolen && g->turn & 7)
  962.                         return;
  963.         }
  964.        
  965.         if (g->turn <= 20) {
  966.                 //best_len = find_path_triple(g, 26, 100, 99, best_path);
  967.                 //best_len = find_path_triple(g, 1, 103, 82, best_path);
  968.                 //best_len = find_path_triple(g, 35, 89, 85, best_path);
  969.                 best_len = find_path(g, start_path[0], start_path[1], best_path);
  970.                 //best_len = find_path(g, 79, 105, best_path);
  971.                
  972.                 if (best_len > 20)
  973.                 for (a = 0; edge_cells[a]; ++a) {
  974.                         for (b = a + 1; edge_cells[b]; ++b) {
  975.                                 for (c = b; edge_cells[c]; ++c) {
  976.                                         if ((g->b[edge_cells[a]] | g->b[edge_cells[b]] | g->b[edge_cells[c]]) & (g->cur ^ 3))
  977.                                                 continue;
  978.                                         if (!enough_corners(g->player_corners[g->cur] |
  979.                                                            edge2corner[edges[edge_cells[a]] | edges[edge_cells[b]] | edges[edge_cells[c]]]))
  980.                                                 continue;
  981.                                        
  982.                                         if (b != c)
  983.                                                 path_len = find_path_triple(g, edge_cells[a], edge_cells[b], edge_cells[c], path);
  984.                                         else
  985.                                                 path_len = find_path(g, edge_cells[a], edge_cells[b], path);
  986.                                        
  987.                                         if (path_len < best_len) {
  988.                                                 LOG("Possible PLAN: %d|%d|%d in %d moves\n", edge_cells[a], edge_cells[b], edge_cells[c], path_len);
  989.                                                 memcpy(best_path, path, sizeof(path));
  990.                                                 best_len = path_len;
  991.                                         }
  992.                                 }
  993.                         }
  994.                 }
  995.         } else {
  996.                 int biggest = 0;
  997.                
  998.                 find_clusters(g, fields);
  999.                 for (i = 2; i < 107; ++i)
  1000.                         if ((g->b[i] & g->cur) && fields[i] > fields[biggest])
  1001.                                 biggest = i;
  1002.                
  1003.                 for (i = 0; i < corner_cells[i]; ++i) {
  1004.                         /* Might theoretically be disconnected.
  1005.                         if (g->b[corner_cells[i]] & 3)
  1006.                                 continue;
  1007.                         */
  1008.                         //if ((g->b[corner_cells[i]] &
  1009.                         path_len = find_path(g, biggest, corner_cells[i], path);
  1010.                         if (path_len > 0 && path_len < best_len) {
  1011.                                 memcpy(best_path, path, sizeof(path));
  1012.                                 best_len = path_len;
  1013.                         }
  1014.                         LOG("Still interesting: %d in %d moves\n", corner_cells[i], path_len);
  1015.                 }
  1016.                
  1017.                 if (best_len > 5)
  1018.                 for (i = 0; i < edge_cells[i]; ++i) {
  1019.                         /* Might theoretically be disconnected.
  1020.                         if (g->b[corner_cells[i]] & 3)
  1021.                                 continue;
  1022.                         */
  1023.                         if (bits[edges[edge_cells[i]]] > 1) /* Skip corners */
  1024.                                 continue;
  1025.                         if (!(((g->b[edge_cells[i]] & g->b[biggest]) >> EDGE_BITS) !=
  1026.                               (g->b[edge_cells[i]] >> EDGE_BITS)))
  1027.                                 continue;
  1028.                         path_len = find_path(g, biggest, edge_cells[i], path);
  1029.                         if (path_len > 0 && path_len < best_len) {
  1030.                                 memcpy(best_path, path, sizeof(path));
  1031.                                 best_len = path_len;
  1032.                         }
  1033.                         LOG("Still interesting: %d in %d moves\n", edge_cells[i], path_len);
  1034.                 }
  1035.         }
  1036.  
  1037.         if (best_len > 1000) {
  1038.                 LOG("Stuck :-(\n");
  1039.                 return;
  1040.         }
  1041.        
  1042.         memcpy(g->plans->todo, best_path, sizeof(best_path));
  1043.         g->plans->todolen = best_len;
  1044.        
  1045.         LOG("NEW PLAN:");
  1046.         for (i = 0; i < best_len; ++i)
  1047.                 LOG(" %d", best_path[i]);
  1048.         LOG("\n");
  1049. }
  1050.  
  1051. void list_moves(struct game *g, int moves[107])
  1052. {
  1053.         int i, j, n;
  1054.        
  1055.         memset(moves, 0, sizeof(int) * 107);
  1056.        
  1057.         if (1 || g->cur == g->me) {
  1058.                 for (i = 0; i < g->plans->todolen; ++i)
  1059.                         if (!(g->b[g->plans->todo[i]] & 3)) {
  1060.                                 moves[g->plans->todo[i]] = 50; //g->plans->todo[i] <= 49 ? 70 : 50;
  1061.                                 for (j = 0; j < 6 && (n = neighs[g->plans->todo[i]][j]); ++j) {
  1062.                                         if (!(g->b[n] & 3)) {
  1063.                                                 moves[n] += 5;
  1064.                                                 break;
  1065.                                         }
  1066.                                 }
  1067.                         }
  1068.         }  {
  1069.                 for (i = 1; i < 107; ++i) {
  1070.                         if (!(g->b[i] & 3)) {
  1071.                                 for (j = 0; j < 6 && (n = neighs[i][j]); ++j) {
  1072.                                         if (g->b[n] & g->cur) {
  1073.                                                 moves[i] += 1;
  1074.                                                 break;
  1075.                                         }
  1076.                                 }
  1077.                         }
  1078.                 }
  1079.         }
  1080. }
  1081.  
  1082. int eval_move_int(struct game *g, int move, int cur)
  1083. {
  1084.         int i, n;
  1085.         int neigh_edges = 0, common_edges = 0x1f, n_neighs = 0;
  1086.         int new_corners = 0;
  1087.         int score = 0;
  1088.        
  1089.         for (i = 0; i < 6 && (n = neighs[move][i]); ++i) {
  1090.                 if (g->b[n] & cur) {
  1091.                         neigh_edges |= g->b[n] >> EDGE_BITS;
  1092.                         common_edges &= g->b[n] >> EDGE_BITS;
  1093.                         ++n_neighs;
  1094.                 }
  1095.         }
  1096.         common_edges &= neigh_edges; /* In case neighbours are all empty, it's still 0x1f. */
  1097.        
  1098.         new_corners = edge2corner[neigh_edges | (g->b[move] >> EDGE_BITS)];
  1099.         //LOG("%d %d %d %d %d %d %d\n", move, n_neighs, neigh_edges, common_edges, new_corners, g->player_corners[cur], enough_corners(new_corners | g->player_corners[cur]));
  1100.         if (enough_corners(new_corners | g->player_corners[cur])) {
  1101.                 /* Winning move! \o/ No need to look further. */
  1102.                 return 1000000;
  1103.         }
  1104.        
  1105.         /* Slight preference for joining an existing "cluster". */
  1106.         score += n_neighs;
  1107.        
  1108.         score += 10 * bits[g->b[move] >> EDGE_BITS];
  1109.        
  1110.         /* How many edges are getting connected by this move? */
  1111.         if (neigh_edges > common_edges)
  1112.                 score += 100 * bits[neigh_edges ^ common_edges];
  1113.        
  1114.         if (new_corners > g->player_corners[cur])
  1115.                 score += 1000 * bits[new_corners];
  1116.        
  1117.         return score;
  1118. }
  1119.  
  1120. int eval_move(struct game *g, int move)
  1121. {
  1122.         int my_score = eval_move_int(g, move, g->cur);
  1123.         int their_score = eval_move_int(g, move, g->cur ^ 3);
  1124.        
  1125. //      LOG("%d %d %d %d\n", move, g->cur, my_score, their_score);
  1126.        
  1127.         /* I like to win. */
  1128.         if (my_score == 1000000) {
  1129.                 return my_score;
  1130.         }
  1131.        
  1132.         /* Opponent *not* winning is nearly as important. */
  1133.         if (their_score == 1000000) { // && (g->cur == g->me) && 0) {
  1134.                 return 8000;
  1135.         }
  1136.        
  1137.         return my_score + their_score;
  1138. }
  1139.  
  1140. int best_move(struct game *g, int depth, int *ret_eval)
  1141. {
  1142.         static int move_stack[MAX_DEPTH_START+1];
  1143.         int best_move_stack[MAX_DEPTH_START+1];
  1144.         int moves[107] = {};
  1145.         struct game g2[1];
  1146.         int move, eval, best_eval = -10000000, best = 0, next_eval;
  1147.         int opponent_wins = 0;
  1148.         int n = 0;
  1149.        
  1150.         list_moves(g, moves);
  1151.         for (move = 1; move < 107; ++move) {
  1152.                 if (moves[move] == 0 || (g->b[move] & 3))
  1153.                         continue;
  1154.                 ++n;
  1155.                 if (depth == max_depth)
  1156.                         memset(move_stack, 0, sizeof(move_stack));
  1157.                
  1158.                 eval = moves[move] += eval_move(g, move);
  1159.                 if (eval >= 8000 && eval < 10000)
  1160.                         ++opponent_wins;
  1161.                 if (eval < 1000000 && eval > 0 && depth > 0) {
  1162.                         memcpy(g2, g, sizeof(g2));
  1163.                         apply_move(g2, move);
  1164.                         best_move(g2, depth - 1, &next_eval);
  1165.                         eval -= 0.8 * next_eval;
  1166.                 }
  1167.                 if (eval > best_eval) {
  1168.                         memcpy(best_move_stack, move_stack, sizeof(move_stack));
  1169.                         best = move;
  1170.                         best_eval = eval;
  1171.                 }
  1172.                 if (depth == max_depth) {
  1173.                         int i;
  1174.                         LOG("%3d %6d because", move, eval);
  1175.                         for (i = max_depth - 1; i >= 0; --i)
  1176.                                 LOG(" %d", move_stack[i]);
  1177.                         LOG("\n");
  1178.                 }
  1179.         }
  1180.         if (opponent_wins > 1) {
  1181.                 /* To consider: If we can't possibly keep the opponent from
  1182.                    winning, don't even try and hope it's stupid. We might
  1183.                    eventually get to win ourselves. */
  1184.                 //best_eval = 1000;
  1185.         }
  1186.         memcpy(move_stack, best_move_stack, sizeof(move_stack));
  1187.         if (ret_eval)
  1188.                 *ret_eval = best ? best_eval : 0;
  1189.         move_stack[depth] = best;
  1190. //      if (g->turn >= 21)
  1191. //              LOG("Best move (out of %d) for %d at depth %d is %d (eval %d)\n", n, g->cur, depth, best, best_eval);
  1192.         return best;
  1193. }
  1194.  
  1195. void update_safe_todo_int(struct game *g, int src, int ihave, int todo[107], int *best, int c[2], int depth)
  1196. {
  1197.         int newtodo[107];
  1198.         int i, cell, st;
  1199.  
  1200.         for (i = 0; (cell = edge_cells[i]); ++i) {
  1201.                 if (!enough_corners(edge2corner[ihave | edges[cell]]))
  1202.                         continue;
  1203.                 if (g->b[cell] & (g->cur ^ 3))
  1204.                         continue;
  1205.                
  1206.                 LOG("Try %d and %d\n", src, cell);
  1207.                 st = find_safe_path(g, src, cell, newtodo, depth);
  1208.                 if (st < *best) {
  1209.                         c[0] = src;
  1210.                         c[1] = cell;
  1211.                         *best = st;
  1212.                         memcpy(todo, newtodo, sizeof(newtodo));
  1213.                 }
  1214.         }
  1215.        
  1216.         for (cell = 1; cell < 107; ++cell) {
  1217.                 int n, free = 0, nedges = 0;
  1218.                
  1219.                 if (!edge_neighs[cell][0])
  1220.                         continue;
  1221.                 if (g->b[cell] & (g->cur ^ 3))
  1222.                         continue;
  1223.                
  1224.                 for (i = 0; i < 3 && (n = edge_neighs[cell][i]); ++i) {
  1225.                         if (!(g->b[n] & (g->cur ^ 3)))
  1226.                                 ++free;
  1227.                         nedges |= edges[n];
  1228.                 }
  1229.                
  1230.                 if (free < 2)
  1231.                         continue;
  1232.                
  1233.                 if (!enough_corners(edge2corner[ihave | nedges]))
  1234.                         continue;
  1235.                
  1236.                 LOG("Try %d and %d\n", src, cell);
  1237.                 st = find_safe_path(g, src, cell, newtodo, depth);
  1238.                 if (st < *best) {
  1239.                         int j, n2;
  1240.                        
  1241.                         for (i = 0; i < 3 && (n = edge_neighs[cell][i]); ++i) {
  1242.                                 if (g->b[n] & (g->cur ^ 3))
  1243.                                         continue;
  1244.                                 for (j = i + 1; j < 3 && (n2 = edge_neighs[cell][j]); ++j) {
  1245.                                         if (g->b[n2] & (g->cur ^ 3))
  1246.                                                 continue;
  1247.                                         if (!((g->b[n] | g->b[n2]) & g->cur)) {
  1248.                                                 newtodo[n] = n2;
  1249.                                                 newtodo[n2] = n;
  1250.                                         } else {
  1251.                                                 newtodo[n] = 1000;
  1252.                                                 newtodo[n2] = 1000;
  1253.                                         }
  1254.                                 }
  1255.                         }
  1256.                        
  1257.                         *best = st;
  1258.                         memcpy(todo, newtodo, sizeof(newtodo));
  1259.                         print_raw(todo);
  1260.                        
  1261.                         c[0] = src;
  1262.                         c[1] = cell;
  1263.                 }
  1264.         }
  1265. }
  1266.  
  1267. void update_safe_todo(struct game *g, int todo[107], int c[6])
  1268. {
  1269.         int best = 999999;
  1270.         int i, cell;
  1271.         static int oldtodo[107]; /* Not threaded/nested anyway so whatever. */
  1272.        
  1273.         if (g->plans->stage == ST_1LINE) {
  1274.                 if (find_safe_path(g, c[0], c[1], todo, 10) < 100)
  1275.                         return;
  1276.                 else
  1277.                         ++g->plans->stage; /* Try to finish it somehow. */
  1278.         }
  1279.        
  1280.         if (g->plans->stage == ST_HALFLINE) {
  1281.                 /* Initial plan (one line/link to win) fully failed now.
  1282.                    See what we can make of it. */
  1283.                 int i, mid = 1;
  1284.                
  1285.                 /* Find the corner in between c[0-1]. */
  1286.                 for (i = 0; (cell = corner_cells[i]); ++i) {
  1287.                         if ((edges[cell] & edges[c[0]]) &&
  1288.                             (edges[cell] & edges[c[1]])) {
  1289.                                 mid = cell;
  1290.                                 break;
  1291.                         }
  1292.                 }
  1293.  
  1294.                 update_safe_todo_int(g, c[0], edges[c[0]], todo, &best, c + 2, 12);
  1295.                 update_safe_todo_int(g, c[1], edges[c[1]], todo, &best, c + 2, 12);
  1296.                
  1297.                 update_safe_todo_int(g, c[0], edges[c[0]] | (edges[c[1]] & ~edges[mid]), todo, &best, c + 2, 12);
  1298.                 update_safe_todo_int(g, c[1], edges[c[1]] | (edges[c[0]] & ~edges[mid]), todo, &best, c + 2, 12);
  1299.                
  1300.                 if (best < 100) {
  1301.                         print_raw(todo);
  1302.                         return;
  1303.                 }
  1304.         }      
  1305.        
  1306.         if (g->plans->stage == ST_HALFLINE_DONE) {
  1307.                 /* We've finished the mandatory todo items, yet this function
  1308.                    was called. It means we need to draw another line. Remember
  1309.                    this one because it's still unfinished. */
  1310.                
  1311.                 memcpy(oldtodo, todo, sizeof(oldtodo)); /* Urgh. */
  1312.                
  1313.                 ++g->plans->stage;
  1314.         }
  1315.        
  1316.         if (g->plans->stage == ST_EXTRALINE) {
  1317.                 int ihave = edges[c[2]] | edges[c[3]] | edges[edge_neighs[c[3]][0]]
  1318.                           | edges[edge_neighs[c[3]][1]] | edges[edge_neighs[c[3]][2]];
  1319.  
  1320.                 update_safe_todo_int(g, c[2], ihave, todo, &best, c + 4, 12);
  1321.                
  1322.                 if (best < 100) {
  1323.                         LOG("MERGE %d %d %d %d %d %d\n", c[0], c[1], c[2], c[3], c[4], c[5]);
  1324.                         print_raw(todo);
  1325.                         print_raw(oldtodo);
  1326.                         for (i = 1; i < 107; ++i)
  1327.                                 if (todo[i] >= 1000) {
  1328.                                         /* Just leave it. */   
  1329.                                 } else if (oldtodo[i] && !todo[i])
  1330.                                         todo[i] = oldtodo[i];
  1331.                                 else if (oldtodo[i] && todo[i]) {
  1332.                                         todo[todo[i]] = 0;
  1333.                                         todo[oldtodo[i]] = 0;
  1334.                                         oldtodo[todo[i]] = 0;
  1335.                                         oldtodo[oldtodo[i]] = 0;
  1336.                                         todo[i] = 1100;
  1337.                                 }
  1338.                        
  1339.                         print_raw(todo);
  1340.                         return;
  1341.                 }
  1342.         }
  1343.        
  1344.         g->plans->stage = ST_FAILED;
  1345. }
  1346.  
  1347. int play_game(char *start[])
  1348. {
  1349.         struct game *g = new_game();
  1350.         int move;
  1351.         char move_s[16];
  1352.         int i;
  1353.        
  1354.         if (start) {
  1355.                 for (i = 0; start[i]; ++i) {
  1356.                         sscanf(start[i], "%d", &move);
  1357.                         apply_move(g, move);
  1358.                 }
  1359.                 g->me = g->cur;
  1360.         } else
  1361.                 g->me = 2;
  1362.        
  1363.         while (1) {
  1364.                 if (g->cur != g->me) {
  1365.                         if (scanf("%s", move_s) != 1)
  1366.                                 break;
  1367.                        
  1368.                         if (sscanf(move_s, "%d", &move) == 1) {
  1369.                         } else if (strcasecmp(move_s, "Quit") == 0) {
  1370.                                 break;
  1371.                         } else if (strcasecmp(move_s, "Start") == 0) {
  1372.                                 /* I'm white! */
  1373.                                 g->me = 1;
  1374.                                 continue;
  1375.                         }
  1376.                        
  1377.                         if (!(move == -1 || (move >= 1 && move <= 106 && !(g->b[move] & 3)))) {
  1378.                                 LOG("INVALID!\n");
  1379.                                 continue;
  1380.                         }
  1381.                 } else if (g->plans->stage < ST_FAILED) {
  1382.                         static int c[6] = {};
  1383.                         static int todo[107] = {};
  1384.                         int last = move;
  1385.                         int n, j;
  1386.                        
  1387.                         move = 0;
  1388.                        
  1389.                         if (g->turn == 1) {
  1390.                                 move = 1;
  1391.                                 c[0] = 1;
  1392.                         } else if (g->turn == 2) {
  1393.                                 if (bits[edges[last]] > 1) {
  1394.                                         c[0] = last;
  1395.                                         move = -1;
  1396.                                 } else {
  1397.                                         for (i = 0; corner_cells[i]; ++i) {
  1398.                                                 if (g->b[corner_cells[i]] & 3)
  1399.                                                         continue;
  1400.                                                 for (j = 0; j < 6 && (n = neighs[corner_cells[i]][j]); ++j)
  1401.                                                         if (g->b[n] & 3)
  1402.                                                                 break;
  1403.                                                 if (n)
  1404.                                                         continue;
  1405.                                                
  1406.                                                 move = c[0] = corner_cells[i];
  1407.                                                 break;
  1408.                                         }
  1409.                                 }
  1410.                         } else if (last == -1) {
  1411.                                 move = c[0] = 37;
  1412.                         } else if (!c[1]) {
  1413.                                 for (i = 0; corner_cells[i]; ++i) {
  1414.                                         if (g->b[corner_cells[i]] & 3)
  1415.                                                 continue;
  1416.                                         for (j = 0; j < 6 && (n = neighs[corner_cells[i]][j]); ++j)
  1417.                                                 if (g->b[n] & 3)
  1418.                                                         break;
  1419.                                         if (n)
  1420.                                                 continue;
  1421.                                         if (edges[c[0]] & edges[corner_cells[i]])
  1422.                                                 continue;
  1423.                                        
  1424.                                         move = c[1] = corner_cells[i];
  1425.                                         break;
  1426.                                 }
  1427.                                
  1428.                                 update_safe_todo(g, todo, c);
  1429.                         } else {
  1430.                                 if (todo[last] >= 1000) {
  1431.                                         /* Opponent stole a mandatory cell of our
  1432.                                            planned path. Reroute. */
  1433.                                         LOG("Need to reroute.\n");
  1434.                                         update_safe_todo(g, todo, c);
  1435.                                 } else if (todo[last]) {
  1436.                                         /* Opponent chose a non-mandatory cell,
  1437.                                            pick its alternative now. */
  1438.                                         move = todo[last];
  1439.                                         todo[last] = 0;
  1440.                                         todo[move] = 0;
  1441.                                 }
  1442.                                
  1443.                                 if (move == 0) {
  1444.                                         for (i = 1; i < 107; ++i) {
  1445.                                                 if (!(g->b[i] & 3) && todo[i] >= 1000) {
  1446.                                                         /* Not very pretty code, this is meant
  1447.                                                            to detect whether any neighbour field
  1448.                                                            is owned by the opponent, continue if not. */
  1449.                                                         for (j = 0; j < 6 && (n = neighs[i][j]); ++j)
  1450.                                                                 if (g->b[n] & (g->cur ^ 3))
  1451.                                                                         break;
  1452.                                                         if (j == 6 || !n)
  1453.                                                                 continue;
  1454.                                                        
  1455.                                                         /* If the opponent has made a move
  1456.                                                            close to here recently, take this
  1457.                                                            cell now. */
  1458.                                                         move = i;
  1459.                                                         break;
  1460.                                                 }
  1461.                                         }
  1462.                                 }
  1463.                                
  1464.                                 if (move == 0) {
  1465.                                         for (i = 1; i < 107; ++i) {
  1466.                                                 if (!(g->b[i] & 3) && todo[i] >= 1000 &&
  1467.                                                     (!move || todo[i] > todo[move]))
  1468.                                                         move = i;
  1469.                                         }
  1470.                                 }
  1471.                                
  1472.                                 if (move == 0 && g->plans->stage == ST_HALFLINE) {
  1473.                                         /* Mandatory todo's finished, but we'll need to
  1474.                                            think of some more things. */
  1475.                                         ++g->plans->stage;
  1476.                                         update_safe_todo(g, todo, c);
  1477.                                 }
  1478.                                
  1479.                                 /* REPEAT OF THE ABOVE: We've just updated the todo so
  1480.                                    rescan for mandatory items. */
  1481.                                 if (move == 0) {
  1482.                                         for (i = 1; i < 107; ++i) {
  1483.                                                 if (!(g->b[i] & 3) && todo[i] >= 1000 &&
  1484.                                                     (!move || todo[i] > todo[move]))
  1485.                                                         move = i;
  1486.                                         }
  1487.                                 }
  1488.                                
  1489.                                 if (move == 0) {
  1490.                                         for (i = 1; i < 107; ++i) {
  1491.                                                 if (!(g->b[i] & 3) && todo[i]) {
  1492.                                                         move = i;
  1493.                                                         todo[todo[move]] = 0;
  1494.                                                         todo[move] = 0;
  1495.                                                         break;
  1496.                                                 }
  1497.                                         }
  1498.                                 }
  1499.                         }
  1500.                        
  1501.                         if (!move) {
  1502.                                 move = 1;
  1503.                                 g->plans->stage = ST_FAILED;
  1504.                         }
  1505.                        
  1506.                         /* Ensure that the move is valid, unless we're debugging. */
  1507.                         if (!verbose || g->plans->stage == ST_FAILED)
  1508.                                 while ((g->b[move] & 3))
  1509.                                         move = (move % 106) + 1;
  1510.                        
  1511.                         printf("%d\n", move);
  1512.                         fflush(stdout);
  1513.                 } else {
  1514.                         if (g->turn == 2 && edges[move] && (edges[move] & (edges[move] - 1)) > 0) {
  1515.                                 /* Is this a corner and can we steal it? If so, let's do that,
  1516.                                    because we can. :-) */
  1517.                                 move = -1;
  1518.                         } else
  1519.                                 move = 0;
  1520.                        
  1521.                         if (move == 0 && *first_move) {
  1522.                                 while (*first_move) {
  1523.                                         if (!(g->b[*first_move] & 3)) {
  1524.                                                 move = *first_move;
  1525.                                                 break;
  1526.                                         }
  1527.                                         ++first_move;
  1528.                                 }
  1529.                         }
  1530.                        
  1531.                         if (move == 0) {
  1532.                                 update_plans(g);
  1533.                                 move = best_move(g, max_depth, NULL);
  1534.                         }
  1535.                        
  1536.                         /* Safeguard to ~ensure a valid move. */
  1537.                         if (move != -1)
  1538.                                 while ((g->b[move] & 3))
  1539.                                         move = (move % 106) + 1;
  1540.                        
  1541.                         printf("%d\n", move);
  1542.                         fflush(stdout);
  1543.                 }
  1544.                        
  1545.                 LOG("%s move: %d\n", g->cur == g->me ? "My" : "Opponent", move);
  1546.                 apply_move(g, move);
  1547.                 print_board(g);
  1548.                
  1549.                 if (find_winner(g)) {
  1550.                         if (find_winner(g) == g->me)
  1551.                                 log_options("WIN");
  1552.  
  1553.                         /* To avoid "Could not write to stdin" error from referree
  1554.                            at shutdown time: */
  1555.                         usleep(100000);
  1556.                         break;
  1557.                 }
  1558.                
  1559.                 LOG("CPU time so far: %f\n", ((float) clock()) / CLOCKS_PER_SEC);
  1560.                 if (clock() / CLOCKS_PER_SEC >= 20) {
  1561.                         LOG("Time is starting to run out, time to cut some corners.\n");
  1562.                         max_depth = MAX_DEPTH_START - 1;
  1563.                 }
  1564.         }
  1565.        
  1566.         return 0;
  1567. }
  1568.  
  1569. int main(int argc, char *argv[])
  1570. {
  1571.         char **test = NULL;
  1572.         char *s;
  1573.        
  1574.         srand(time(NULL));
  1575.         pick_options();
  1576.        
  1577.         if ((s = getenv("USER")) && strcmp(s, "wilmer") == 0)
  1578.                 verbose = 1;
  1579.        
  1580.         if (argc > 1 && strcmp(argv[1], "follow") == 0) {
  1581.                 return follow_game();
  1582.         }
  1583.         if (argc > 1 && strcmp(argv[1], "test") == 0) {
  1584.                 test = argv + 2;
  1585.         }
  1586.        
  1587.         return play_game(test);
  1588. }
  1589.  

Reply to "Zetter/Uilskuiken"

Here you can reply to the paste above

Powered by Stikked