diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..2576130 --- /dev/null +++ b/.gitignore @@ -0,0 +1,4 @@ +*.o +deltaGo + + diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..dd8543d --- /dev/null +++ b/Makefile @@ -0,0 +1,29 @@ +SHELL = /bin/sh +# To enable SSE, erase '#' below +CC = gcc #-DUSE_SSE + +#---optimize--- +# To disable the optimizing of gcc, comment out below line by '#'. +CFLAGS += -O3 + +# To enable SSE, erase '#' below +LDFLAGS = -lm #-mavx +DEFS = + +CSRCS = main.c init.c util.c move.c bit_util.c get_feature.c cnn_calc.c +# =========================================================================== + +OBJS = $(CSRCS:.c=.o) +TARGET = deltaGo + +.PHONY: clean +.SUFFIXES: .c .o + +$(TARGET): $(OBJS) + $(CC) -o $(TARGET) $(OBJS) $(LDFLAGS) + +.c.o: + $(CC) -c $(CFLAGS) $(DEFS) $(INCDIR) -o $@ $< $(LDFLAGS) + +clean: + $(RM) $(OBJS) $(TARGET) core *.o *~ diff --git a/bit_util.c b/bit_util.c new file mode 100644 index 0000000..6a34a77 --- /dev/null +++ b/bit_util.c @@ -0,0 +1,69 @@ +#include "go.h" + +int BIT2FIRST[256] = { + 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 +}; + + +int Get_FirstBit32(int bit) +{ + if (bit & 0xffff) { + if (bit & 0xff) { + return BIT2FIRST[bit & 0xff]; + } + else { + return BIT2FIRST[(bit >> 8) & 0xff] + 8; + } + } else if (bit & 0xffff0000) { + if (bit & 0x00ff0000) { + return BIT2FIRST[(bit >> 16) & 0xff] + 16; + } + else { + return BIT2FIRST[(bit >> 24) & 0xff] + 24; + } + } + return 0; +} + +int Get_FirstBit64(long long bit) +{ + int res, bit2 = ((int)bit); + + if (bit2){ + res = Get_FirstBit32(bit2); + return res; + } + bit2 = (int)(bit >> 32); + if (bit2){ + res = Get_FirstBit32(bit2); + return res + 32; + } + + return 0; +} + +int pop_cnt(unsigned long long bits) +{ + bits = (bits & 0x5555555555555555LL) + (bits >> 1 & 0x5555555555555555LL); + bits = (bits & 0x3333333333333333LL) + (bits >> 2 & 0x3333333333333333LL); + bits = (bits & 0x0f0f0f0f0f0f0f0fLL) + (bits >> 4 & 0x0f0f0f0f0f0f0f0fLL); + bits = (bits & 0x00ff00ff00ff00ffLL) + (bits >> 8 & 0x00ff00ff00ff00ffLL); + bits = (bits & 0x0000ffff0000ffffLL) + (bits >> 16 & 0x0000ffff0000ffffLL); + bits = (bits & 0x00000000ffffffffLL) + (bits >> 32 & 0x00000000ffffffffLL); + return (int)bits; +} diff --git a/cnn_calc.c b/cnn_calc.c new file mode 100644 index 0000000..bea0d9c --- /dev/null +++ b/cnn_calc.c @@ -0,0 +1,341 @@ +#include "go.h" +#ifdef USE_SSE +#include +#endif + +inline int get_hiddenNext_5x5(game_hdl_t *hdl, cnn_t hiddenNext[21][21][FILTER_SIZE], cnn_t hiddenPrev[23][23][CHANNEL_SIZE], + const int x, const int y, const int inputNums, const int outputNums) +{ + int input, output; + + + for (input = 0; input < inputNums; input++){ + // for (output = 0; output < outputNums; output++)for (q = 0; q < 5; q++) for (p = 0; p < 5; p++) + // hiddenNext[x][y][output] += hiddenPrev[(x) + (p) - 1][(y) + (q) - 1][input] * cnn_5x5_orig[(p) + (q) * 5] + + cnn_t i00 = hiddenPrev[(x) + (0) - 1][(y) + (0) - 1][input]; + cnn_t i01 = hiddenPrev[(x) + (0) - 1][(y) + (1) - 1][input]; + cnn_t i02 = hiddenPrev[(x) + (0) - 1][(y) + (2) - 1][input]; + cnn_t i03 = hiddenPrev[(x) + (0) - 1][(y) + (3) - 1][input]; + cnn_t i04 = hiddenPrev[(x) + (0) - 1][(y) + (4) - 1][input]; + cnn_t i10 = hiddenPrev[(x) + (1) - 1][(y) + (0) - 1][input]; + cnn_t i11 = hiddenPrev[(x) + (1) - 1][(y) + (1) - 1][input]; + cnn_t i12 = hiddenPrev[(x) + (1) - 1][(y) + (2) - 1][input]; + cnn_t i13 = hiddenPrev[(x) + (1) - 1][(y) + (3) - 1][input]; + cnn_t i14 = hiddenPrev[(x) + (1) - 1][(y) + (4) - 1][input]; + cnn_t i20 = hiddenPrev[(x) + (2) - 1][(y) + (0) - 1][input]; + cnn_t i21 = hiddenPrev[(x) + (2) - 1][(y) + (1) - 1][input]; + cnn_t i22 = hiddenPrev[(x) + (2) - 1][(y) + (2) - 1][input]; + cnn_t i23 = hiddenPrev[(x) + (2) - 1][(y) + (3) - 1][input]; + cnn_t i24 = hiddenPrev[(x) + (2) - 1][(y) + (4) - 1][input]; + cnn_t i30 = hiddenPrev[(x) + (3) - 1][(y) + (0) - 1][input]; + cnn_t i31 = hiddenPrev[(x) + (3) - 1][(y) + (1) - 1][input]; + cnn_t i32 = hiddenPrev[(x) + (3) - 1][(y) + (2) - 1][input]; + cnn_t i33 = hiddenPrev[(x) + (3) - 1][(y) + (3) - 1][input]; + cnn_t i34 = hiddenPrev[(x) + (3) - 1][(y) + (4) - 1][input]; + cnn_t i40 = hiddenPrev[(x) + (4) - 1][(y) + (0) - 1][input]; + cnn_t i41 = hiddenPrev[(x) + (4) - 1][(y) + (1) - 1][input]; + cnn_t i42 = hiddenPrev[(x) + (4) - 1][(y) + (2) - 1][input]; + cnn_t i43 = hiddenPrev[(x) + (4) - 1][(y) + (3) - 1][input]; + cnn_t i44 = hiddenPrev[(x) + (4) - 1][(y) + (4) - 1][input]; +#ifdef USE_SSE + assert (outputNums %VEC_WIDTH == 0); + + __m256 i000 = _mm256_set1_ps(i00); + __m256 i001 = _mm256_set1_ps(i01); + __m256 i002 = _mm256_set1_ps(i02); + __m256 i003 = _mm256_set1_ps(i03); + __m256 i004 = _mm256_set1_ps(i04); + + __m256 i010 = _mm256_set1_ps(i10); + __m256 i011 = _mm256_set1_ps(i11); + __m256 i012 = _mm256_set1_ps(i12); + __m256 i013 = _mm256_set1_ps(i13); + __m256 i014 = _mm256_set1_ps(i14); + + __m256 i020 = _mm256_set1_ps(i20); + __m256 i021 = _mm256_set1_ps(i21); + __m256 i022 = _mm256_set1_ps(i22); + __m256 i023 = _mm256_set1_ps(i23); + __m256 i024 = _mm256_set1_ps(i24); + + __m256 i030 = _mm256_set1_ps(i30); + __m256 i031 = _mm256_set1_ps(i31); + __m256 i032 = _mm256_set1_ps(i32); + __m256 i033 = _mm256_set1_ps(i33); + __m256 i034 = _mm256_set1_ps(i34); + + __m256 i040 = _mm256_set1_ps(i40); + __m256 i041 = _mm256_set1_ps(i41); + __m256 i042 = _mm256_set1_ps(i42); + __m256 i043 = _mm256_set1_ps(i43); + __m256 i044 = _mm256_set1_ps(i44); + + + cnn_t *weight = cnn_param->weight_cnn_5x5[input][0]; + for (output = 0; output < outputNums; output += VEC_WIDTH){ + + __m256 v = _mm256_mul_ps(_mm256_loadu_ps(&weight[0 * VEC_WIDTH]), i000); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[1 * VEC_WIDTH]), i010)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[2 * VEC_WIDTH]), i020)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[3 * VEC_WIDTH]), i030)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[4 * VEC_WIDTH]), i040)); + + + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[5 * VEC_WIDTH]), i001)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[6 * VEC_WIDTH]), i011)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[7 * VEC_WIDTH]), i021)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[8 * VEC_WIDTH]), i031)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[9 * VEC_WIDTH]), i041)); + + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[10 * VEC_WIDTH]), i002)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[11 * VEC_WIDTH]), i012)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[12 * VEC_WIDTH]), i022)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[13 * VEC_WIDTH]), i032)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[14 * VEC_WIDTH]), i042)); + + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[15 * VEC_WIDTH]), i003)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[16 * VEC_WIDTH]), i013)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[17 * VEC_WIDTH]), i023)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[18 * VEC_WIDTH]), i033)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[19 * VEC_WIDTH]), i043)); + + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[20 * VEC_WIDTH]), i004)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[21 * VEC_WIDTH]), i014)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[22 * VEC_WIDTH]), i024)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[23 * VEC_WIDTH]), i034)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[24 * VEC_WIDTH]), i044)); + + __m256 prev = _mm256_loadu_ps(&hiddenNext[x][y][output]); + _mm256_storeu_ps(&hiddenNext[x][y][output], _mm256_add_ps(prev,v)); + weight += VEC_WIDTH * 25; + } +#else + + for (output = 0; output < outputNums; output += VEC_WIDTH){ + cnn_t *weight = cnn_param->weight_cnn_5x5[input][output]; + int j; + + for (j = 0; j < VEC_WIDTH; j++){ + hiddenNext[x][y][output + j] += + i00 * weight[ 0 * 8 + j] + i10 * weight[ 1 * 8 + j] + i20 * weight[ 2 * 8 + j] + i30 * weight[ 3 * 8 + j] + i40 * weight[ 4 * 8 + j] + + i01 * weight[ 5 * 8 + j] + i11 * weight[ 6 * 8 + j] + i21 * weight[ 7 * 8 + j] + i31 * weight[ 8 * 8 + j] + i41 * weight[ 9 * 8 + j] + + i02 * weight[10 * 8 + j] + i12 * weight[11 * 8 + j] + i22 * weight[12 * 8 + j] + i32 * weight[13 * 8 + j] + i42 * weight[14 * 8 + j] + + i03 * weight[15 * 8 + j] + i13 * weight[16 * 8 + j] + i23 * weight[17 * 8 + j] + i33 * weight[18 * 8 + j] + i43 * weight[19 * 8 + j] + + i04 * weight[20 * 8 + j] + i14 * weight[21 * 8 + j] + i24 * weight[22 * 8 + j] + i34 * weight[23 * 8 + j] + i44 * weight[24 * 8 + j]; + } + } +#endif + } + + for (output = 0; output < outputNums; output++){ + if (hiddenNext[x][y][output] <= 0.0){ + hiddenNext[x][y][output] = 0.0; + } + } + return 0; +} + +static int convolution5x5 (cnn_t hiddenNext[21][21][FILTER_SIZE], cnn_t hiddenPrev[23][23][CHANNEL_SIZE], game_hdl_t *hdl, + const int outputNums, const int inputNums) +{ + int x; + + for (x = 1; x <= 19; x++){ + get_hiddenNext_5x5(hdl, hiddenNext, hiddenPrev, x, 1, inputNums, outputNums); + get_hiddenNext_5x5(hdl, hiddenNext, hiddenPrev, x, 2, inputNums, outputNums); + get_hiddenNext_5x5(hdl, hiddenNext, hiddenPrev, x, 3, inputNums, outputNums); + get_hiddenNext_5x5(hdl, hiddenNext, hiddenPrev, x, 4, inputNums, outputNums); + get_hiddenNext_5x5(hdl, hiddenNext, hiddenPrev, x, 5, inputNums, outputNums); + get_hiddenNext_5x5(hdl, hiddenNext, hiddenPrev, x, 6, inputNums, outputNums); + get_hiddenNext_5x5(hdl, hiddenNext, hiddenPrev, x, 7, inputNums, outputNums); + get_hiddenNext_5x5(hdl, hiddenNext, hiddenPrev, x, 8, inputNums, outputNums); + get_hiddenNext_5x5(hdl, hiddenNext, hiddenPrev, x, 9, inputNums, outputNums); + get_hiddenNext_5x5(hdl, hiddenNext, hiddenPrev, x,10, inputNums, outputNums); + get_hiddenNext_5x5(hdl, hiddenNext, hiddenPrev, x,11, inputNums, outputNums); + get_hiddenNext_5x5(hdl, hiddenNext, hiddenPrev, x,12, inputNums, outputNums); + get_hiddenNext_5x5(hdl, hiddenNext, hiddenPrev, x,13, inputNums, outputNums); + get_hiddenNext_5x5(hdl, hiddenNext, hiddenPrev, x,14, inputNums, outputNums); + get_hiddenNext_5x5(hdl, hiddenNext, hiddenPrev, x,15, inputNums, outputNums); + get_hiddenNext_5x5(hdl, hiddenNext, hiddenPrev, x,16, inputNums, outputNums); + get_hiddenNext_5x5(hdl, hiddenNext, hiddenPrev, x,17, inputNums, outputNums); + get_hiddenNext_5x5(hdl, hiddenNext, hiddenPrev, x,18, inputNums, outputNums); + get_hiddenNext_5x5(hdl, hiddenNext, hiddenPrev, x,19, inputNums, outputNums); + } + return 0; +} + + +inline int get_hiddenNext_3x3(game_hdl_t *hdl, cnn_t hiddenNext[21][21][FILTER_SIZE], cnn_t hiddenPrev[21][21][FILTER_SIZE], + const int x, const int y, const int inputNums, const int outputNums, const int layer) +{ + int input, output; + + for (input = 0; input < inputNums; input++){ + //for (output = 0; output < outputNums; output++)for (q = 0; q < 3; q++)for (p = 0; p < 3; p++) + // hiddenNext[x][y][output] += hiddenPrev[(x) + (p) - 1][(y) + (q) - 1][input] * cnn_3x3_orig[(p) + (q) * 3] + + cnn_t i00 = hiddenPrev[(x) + (0) - 1][(y) + (0) - 1][input]; + cnn_t i01 = hiddenPrev[(x) + (0) - 1][(y) + (1) - 1][input]; + cnn_t i02 = hiddenPrev[(x) + (0) - 1][(y) + (2) - 1][input]; + cnn_t i10 = hiddenPrev[(x) + (1) - 1][(y) + (0) - 1][input]; + cnn_t i11 = hiddenPrev[(x) + (1) - 1][(y) + (1) - 1][input]; + cnn_t i12 = hiddenPrev[(x) + (1) - 1][(y) + (2) - 1][input]; + cnn_t i20 = hiddenPrev[(x) + (2) - 1][(y) + (0) - 1][input]; + cnn_t i21 = hiddenPrev[(x) + (2) - 1][(y) + (1) - 1][input]; + cnn_t i22 = hiddenPrev[(x) + (2) - 1][(y) + (2) - 1][input]; + +#ifdef USE_SSE + assert (outputNums %VEC_WIDTH == 0); + + __m256 i000 = _mm256_set1_ps(i00); + __m256 i001 = _mm256_set1_ps(i01); + __m256 i002 = _mm256_set1_ps(i02); + __m256 i010 = _mm256_set1_ps(i10); + __m256 i011 = _mm256_set1_ps(i11); + __m256 i012 = _mm256_set1_ps(i12); + __m256 i020 = _mm256_set1_ps(i20); + __m256 i021 = _mm256_set1_ps(i21); + __m256 i022 = _mm256_set1_ps(i22); + cnn_t *weight = cnn_param->weight_cnn_3x3[layer][input][0]; + for (output = 0; output < outputNums; output += VEC_WIDTH){ + + __m256 v = _mm256_mul_ps(_mm256_loadu_ps(&weight[0 * VEC_WIDTH]), i000); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[1 * VEC_WIDTH]), i010)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[2 * VEC_WIDTH]), i020)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[3 * VEC_WIDTH]), i001)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[4 * VEC_WIDTH]), i011)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[5 * VEC_WIDTH]), i021)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[6 * VEC_WIDTH]), i002)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[7 * VEC_WIDTH]), i012)); + v = _mm256_add_ps(v, _mm256_mul_ps(_mm256_loadu_ps(&weight[8 * VEC_WIDTH]), i022)); + __m256 prev = _mm256_loadu_ps(&hiddenNext[x][y][output]); + _mm256_storeu_ps(&hiddenNext[x][y][output], _mm256_add_ps(prev,v)); + weight += VEC_WIDTH * 9; + } + +#else + int j; + for (output = 0; output < outputNums; output += VEC_WIDTH){ + cnn_t *weight = cnn_param->weight_cnn_3x3[layer][input][output]; + + for (j = 0; j < VEC_WIDTH; j++){ + hiddenNext[x][y][output + j] += i00 * weight[0 * 8 + j] + i10 * weight[1 * 8 + j] + i20 * weight[2 * 8 + j] + + i01 * weight[3 * 8 + j] + i11 * weight[4 * 8 + j] + i21 * weight[5 * 8 + j] + + i02 * weight[6 * 8 + j] + i12 * weight[7 * 8 + j] + i22 * weight[8 * 8 + j]; + } + } +#endif + } + for (output = 0; output < outputNums; output++){ + if (hiddenNext[x][y][output] <= 0.0){ + hiddenNext[x][y][output] = 0.0; + } + } + return 0; +} + +static int convolution3x3 (const int layer, cnn_t hiddenNext[21][21][FILTER_SIZE], cnn_t hiddenPrev[21][21][FILTER_SIZE], game_hdl_t *hdl, + const int outputNums, const int inputNums) +{ + int x; + + for (x = 1; x <= 19; x++){ + get_hiddenNext_3x3(hdl, hiddenNext, hiddenPrev, x, 1, inputNums, outputNums, layer); + get_hiddenNext_3x3(hdl, hiddenNext, hiddenPrev, x, 2, inputNums, outputNums, layer); + get_hiddenNext_3x3(hdl, hiddenNext, hiddenPrev, x, 3, inputNums, outputNums, layer); + get_hiddenNext_3x3(hdl, hiddenNext, hiddenPrev, x, 4, inputNums, outputNums, layer); + get_hiddenNext_3x3(hdl, hiddenNext, hiddenPrev, x, 5, inputNums, outputNums, layer); + get_hiddenNext_3x3(hdl, hiddenNext, hiddenPrev, x, 6, inputNums, outputNums, layer); + get_hiddenNext_3x3(hdl, hiddenNext, hiddenPrev, x, 7, inputNums, outputNums, layer); + get_hiddenNext_3x3(hdl, hiddenNext, hiddenPrev, x, 8, inputNums, outputNums, layer); + get_hiddenNext_3x3(hdl, hiddenNext, hiddenPrev, x, 9, inputNums, outputNums, layer); + get_hiddenNext_3x3(hdl, hiddenNext, hiddenPrev, x,10, inputNums, outputNums, layer); + get_hiddenNext_3x3(hdl, hiddenNext, hiddenPrev, x,11, inputNums, outputNums, layer); + get_hiddenNext_3x3(hdl, hiddenNext, hiddenPrev, x,12, inputNums, outputNums, layer); + get_hiddenNext_3x3(hdl, hiddenNext, hiddenPrev, x,13, inputNums, outputNums, layer); + get_hiddenNext_3x3(hdl, hiddenNext, hiddenPrev, x,14, inputNums, outputNums, layer); + get_hiddenNext_3x3(hdl, hiddenNext, hiddenPrev, x,15, inputNums, outputNums, layer); + get_hiddenNext_3x3(hdl, hiddenNext, hiddenPrev, x,16, inputNums, outputNums, layer); + get_hiddenNext_3x3(hdl, hiddenNext, hiddenPrev, x,17, inputNums, outputNums, layer); + get_hiddenNext_3x3(hdl, hiddenNext, hiddenPrev, x,18, inputNums, outputNums, layer); + get_hiddenNext_3x3(hdl, hiddenNext, hiddenPrev, x,19, inputNums, outputNums, layer); + } + return 0; +} + +static inline int convolution13 (cnn_t hiddenOut[21][21], cnn_t hiddenPrev[21][21][FILTER_SIZE], game_hdl_t *hdl, const int inputNums) +{ + int input, x, y; + + for (x = 1; x <= 19; x++){ + for (y = 1; y <= 19; y++){ + cnn_t tmp = cnn_param->weight_cnn_bias[(x - 1) + 19 * (y - 1)]; + for (input = 0; input < inputNums; input++){ + tmp += hiddenPrev[x][y][input] * cnn_param->weight_cnn_1x1[input]; + } + hiddenOut[x][y] = tmp; + } + } + + return 0; +} + +int get_cnn_prob(goban_t *ban, game_hdl_t *hdl, double pos_to_prob[XY_SIZE]) +{ + int x, y, input; + for (input = 0; input < CHANNEL_SIZE; input++){ + for (x = 1; x <= 19; x++){ + for (y = 1; y <= 19; y++){ + hdl->hiddenIn[x + 1][y + 1][input] = (cnn_t)ban->feature[input][x][y]; + } + } + } + + memset (hdl->hidden, 0, 14 * 21 * 21 * FILTER_SIZE * sizeof(cnn_t)); + memset (hdl->hiddenOut, 0, 21 * 21 * sizeof(cnn_t)); + + convolution5x5( hdl->hidden[1], hdl->hiddenIn, hdl, FILTER_SIZE, CHANNEL_SIZE); + convolution3x3(2, hdl->hidden[2], hdl->hidden[1], hdl, FILTER_SIZE, FILTER_SIZE); + convolution3x3(3, hdl->hidden[3], hdl->hidden[2], hdl, FILTER_SIZE, FILTER_SIZE); + convolution3x3(4, hdl->hidden[4], hdl->hidden[3], hdl, FILTER_SIZE, FILTER_SIZE); + convolution3x3(5, hdl->hidden[5], hdl->hidden[4], hdl, FILTER_SIZE, FILTER_SIZE); + convolution3x3(6, hdl->hidden[6], hdl->hidden[5], hdl, FILTER_SIZE, FILTER_SIZE); + convolution3x3(7, hdl->hidden[7], hdl->hidden[6], hdl, FILTER_SIZE, FILTER_SIZE); + convolution3x3(8, hdl->hidden[8], hdl->hidden[7], hdl, FILTER_SIZE, FILTER_SIZE); + convolution3x3(9, hdl->hidden[9], hdl->hidden[8], hdl, FILTER_SIZE, FILTER_SIZE); + convolution3x3(10, hdl->hidden[10], hdl->hidden[9], hdl, FILTER_SIZE, FILTER_SIZE); + convolution3x3(11, hdl->hidden[11], hdl->hidden[10], hdl, FILTER_SIZE, FILTER_SIZE); + convolution3x3(12, hdl->hidden[12], hdl->hidden[11], hdl, FILTER_SIZE, FILTER_SIZE); + convolution13( hdl->hiddenOut, hdl->hidden[12], hdl, FILTER_SIZE); + + double max = -1000000.0; + int best_pos = 0; + double prob; + // get prob_tot + double prob_tot = 0.0; + for (y = 1; y <= BOARD_EDGE_SIZE ; y++){ + for (x = 1; x <= BOARD_EDGE_SIZE; x++){ + prob = exp(hdl->hiddenOut[x][y]); + prob_tot += prob; + } + } + if (prob_tot == 0.0){ + prob_tot = 1.0; + } + // get best_pos and print prob + for (y = 1; y <= BOARD_EDGE_SIZE ; y++){ + for (x = 1; x <= BOARD_EDGE_SIZE; x++){ + int pos = X_Y_TO_POS(x, y); + double prob = exp(hdl->hiddenOut[x][y]); + pos_to_prob[pos] = prob/prob_tot; + if (ban->color[pos] == SP && judge_eff_te(pos, ban)){ + if (prob >= max){ + max = prob; + best_pos = pos; + } + } + } + } + return best_pos; +} diff --git a/get_feature.c b/get_feature.c new file mode 100644 index 0000000..ffa1eb4 --- /dev/null +++ b/get_feature.c @@ -0,0 +1,271 @@ +#include "go.h" + +static int writeColor(FILE *fp_out, const int id, const int tesuu, goban_t *ban, int index, int keep[21][21]) +{ + int x, y; + for (y = 1; y <= BOARD_EDGE_SIZE ; y++){ + for (x = 1; x <= BOARD_EDGE_SIZE; x++){ + keep[x][y] = (ban->color[X_Y_TO_POS(x, y)] == index); + } + } + + return 0; +} + +static int writeSame(FILE *fp_out, const int id, const int tesuu, goban_t *ban, int value, int keep[21][21]) +{ + int x, y; + for (y = 1; y <= BOARD_EDGE_SIZE ; y++){ + for (x = 1; x <= BOARD_EDGE_SIZE; x++){ + keep[x][y] = value; + } + } + return 0; +} + +static int writeHist(FILE *fp_out, const int id, const int tesuu, goban_t *ban, const int tesuu_hist, int keep[21][21]) +{ + int x, y; + int pos_old = 0; + if (tesuu >= tesuu_hist){ + pos_old = ban->histInfo[tesuu - tesuu_hist + 1].pos; + } + for (y = 1; y <= BOARD_EDGE_SIZE ; y++){ + for (x = 1; x <= BOARD_EDGE_SIZE; x++){ + keep[x][y] = (X_Y_TO_POS(x, y) == pos_old); + } + } + return 0; +} + +static int writeLiberty(FILE *fp_out, const int id, const int tesuu, goban_t *ban, int num, int keep[21][21]) +{ + int x, y; + for (y = 1; y <= BOARD_EDGE_SIZE ; y++){ + for (x = 1; x <= BOARD_EDGE_SIZE; x++){ + int pos = X_Y_TO_POS(x, y); + int breath = ban->renInfo[ban->renID[pos]].breathPoints; + breath = MIN(breath, 8); + keep[x][y] = (breath == num); + } + } + + return 0; +} + +static int writeLibertyAfterMoveSize(FILE *fp_out, const int id, const int tesuu, goban_t *ban, int num, int keep[21][21]) +{ + int x, y, d; + for (y = 1; y <= BOARD_EDGE_SIZE ; y++){ + for (x = 1; x <= BOARD_EDGE_SIZE; x++){ + int pos = X_Y_TO_POS(x, y); + int breath = 0; + + if (ban->color[pos] == SP){ + bb_t breathBB[BB_IDX_SIZE]; + CLEAR_BB(breathBB); + + for (d = 1; d < D_MAX; d+= 2){ /* cross */ + const int c = pos + D2DELTA[d]; + if (ban->color[c] == SP){ + ADD_AN_ELEMENT_TO_BB(breathBB, c); + } + if (ban->color[c] == TBN2COLOR(ban->tbn)){ + int renID = ban->renID[c]; + renInfo_t *g = &ban->renInfo[renID]; + MERGE_BB(breathBB, g->breathBB); + } + } + ERASE_AN_ELEMENT_FROM_BB(breathBB, pos); + breath = bb_pop_cnt(breathBB); + } + breath = MIN(breath, 8); + keep[x][y] = (breath == num); + + } + } + return 0; +} + + +static int writeCaptureSize(FILE *fp_out, const int id, const int tesuu, goban_t *ban, int num, int keep[21][21]) +{ + int x, y, d; + for (y = 1; y <= BOARD_EDGE_SIZE ; y++){ + for (x = 1; x <= BOARD_EDGE_SIZE; x++){ + int pos = X_Y_TO_POS(x, y); + int atari = 0; + if (ban->color[pos] == SP){ + bb_t atariBB[BB_IDX_SIZE]; + CLEAR_BB(atariBB); + + for (d = 1; d < D_MAX; d+= 2){ /* cross */ + const int c = pos + D2DELTA[d]; + if (ban->color[c] == OB || ban->color[c] == SP){ + continue; + } + int renID = ban->renID[c]; + + renInfo_t *g = &ban->renInfo[renID]; + if (g->breathPoints == 1 && g->color != TBN2COLOR(ban->tbn)){ + MERGE_BB(atariBB, g->occupiedBB); + } + } + atari = bb_pop_cnt(atariBB); + } + atari = MIN(atari, 8); + keep[x][y] = (atari == num); + } + } + return 0; +} + + +static int writeCapturedSize(FILE *fp_out, const int id, const int tesuu, goban_t *ban, int num, int keep[21][21]) +{ + int x, y, d; + for (y = 1; y <= BOARD_EDGE_SIZE ; y++){ + for (x = 1; x <= BOARD_EDGE_SIZE; x++){ + int pos = X_Y_TO_POS(x, y); + int atari = 0, breath = 0; + if (ban->color[pos] == SP){ + bb_t breathBB[BB_IDX_SIZE], atariBB[BB_IDX_SIZE]; + CLEAR_BB(breathBB); CLEAR_BB(atariBB); + for (d = 1; d < D_MAX; d+= 2){ /* cross */ + const int c = pos + D2DELTA[d]; + if (ban->color[c] == SP){ + ADD_AN_ELEMENT_TO_BB(breathBB, c); + } + if (ban->color[c] == TBN2COLOR(ban->tbn)){ + int renID = ban->renID[c]; + renInfo_t *g = &ban->renInfo[renID]; + MERGE_BB(atariBB, g->occupiedBB); + MERGE_BB(breathBB, g->breathBB); + } + } + ERASE_AN_ELEMENT_FROM_BB(breathBB, pos); + ADD_AN_ELEMENT_TO_BB(atariBB, pos); + breath = bb_pop_cnt(breathBB); + atari = bb_pop_cnt(atariBB); + if (breath != 1){ + atari = 0; + } + } + atari = MIN(atari, 8); + keep[x][y] = (atari == num); + } + } + return 0; +} + +static int writeLegality(FILE *fp_out, const int id, const int tesuu, goban_t *ban, int keep[21][21]) +{ + int x, y; + for (y = 1; y <= BOARD_EDGE_SIZE ; y++){ + for (x = 1; x <= BOARD_EDGE_SIZE; x++){ + int pos = X_Y_TO_POS(x, y); + keep[x][y] = (ban->color[pos] == SP && judge_eff_te(pos, ban)); + } + } + return 0; +} + +// そこに打つと、相手の石をシチョウで取れるかどうかをcheckする +static int writeLadderCapture(FILE *fp_out, const int id, const int tesuu, goban_t *ban, int keep[21][21]) +{ + int x, y, d; + + for (y = 1; y <= BOARD_EDGE_SIZE ; y++){ + for (x = 1; x <= BOARD_EDGE_SIZE; x++){ + keep[x][y] = 0; + int pos = X_Y_TO_POS(x, y); + for (d = 1; d < D_MAX; d += 2){ /* cross */ + const int c = pos + D2DELTA[d]; + if (ban->color[c] == GET_AITE(TBN2COLOR(ban->tbn))){ + int renID = ban->renID[c]; + renInfo_t *g = &ban->renInfo[renID]; + if (g->breathPoints == 2){ + int target = get_another_pos(g->breathBB, pos); + if (check_kill(pos, target, ban)){ + keep[POS_TO_X(pos)][POS_TO_Y(pos)] = 1; + } + } + } + } + } + } + + return 0; +} + + +// そこに打つと、シチョウで取られるかどうかをcheckする +static int writeLadderEscape(FILE *fp_out, const int id, const int tesuu, goban_t *ban, int keep[21][21]) +{ + int x, y; + + for (y = 1; y <= BOARD_EDGE_SIZE ; y++){ + for (x = 1; x <= BOARD_EDGE_SIZE; x++){ + keep[x][y] = 0; + int pos = X_Y_TO_POS(x, y); + if (teOK(pos, ban) && + !detect_suicide_or_capture(ban, pos)){ + if (check_dead(pos, ban)){ + keep[x][y] = 1; + } + } + + } + } + return 0; +} + +int get_feature(FILE *fp, const int i, const int tesuu, goban_t *ban) +{ + int j; + + //Stone colour 3 Player stone / opponent stone / empty + if (ban->tbn == TBN_BK){ + writeColor(fp, i, tesuu, ban, BK, ban->feature[0]); + writeColor(fp, i, tesuu, ban, WH, ban->feature[1]); + } else { + writeColor(fp, i, tesuu, ban, WH, ban->feature[0]); + writeColor(fp, i, tesuu, ban, BK, ban->feature[1]); + } + writeColor(fp, i, tesuu, ban, SP, ban->feature[2]); + //Ones 1 A constant plane filled with 1 + writeSame(fp, i, tesuu, ban, 1, ban->feature[3]); + + //Turns since 8 How many turns since a move was played + for (j = 1; j <= 8; j++){ + writeHist(fp, i, tesuu, ban, j, ban->feature[3 + j]); + } + //Liberties 8 Number of liberties (empty adjacent points) + for (j = 1; j <= 8; j++){ + writeLiberty(fp, i, tesuu, ban, j, ban->feature[11 + j]); + } + //Capture size 8 How many opponent stones would be captured + for (j = 1; j <= 8; j++){ + writeCaptureSize(fp, i, tesuu, ban, j, ban->feature[19 + j]); + } + //Self-atari size 8 How many of own stones would be captured + for (j = 1; j <= 8; j++){ + writeCapturedSize(fp, i, tesuu, ban, j, ban->feature[27 + j]); + } + //Liberties after move 8 Number of liberties after this move is played + for (j = 1; j <= 8; j++){ + writeLibertyAfterMoveSize(fp, i, tesuu, ban, j, ban->feature[35 + j]); + } + //Ladder capture 1 Whether a move at this point is a successful ladder capture + writeLadderCapture(fp, i, tesuu, ban, ban->feature[44]); // 20160616 + + //Ladder escape 1 Whether a move at this point is a successful ladder escape + writeLadderEscape(fp, i, tesuu, ban, ban->feature[45]); + + //Sensibleness 1 Whether a move is legal and does not fill its own eyes + writeLegality(fp, i, tesuu, ban, ban->feature[46]); + + //Zeros 1 A constant plane filled with 0 + writeSame(fp, i, tesuu, ban, 0, ban->feature[47]); + return 0; +} diff --git a/go.h b/go.h new file mode 100644 index 0000000..9b6a18f --- /dev/null +++ b/go.h @@ -0,0 +1,170 @@ +/* Copyright (C) 2016 Otsuki Tomoshi */ + +#ifndef _GO_H_ +#define _GO_H_ + +#include +#include +#include +#include +#include +#include +#include + +#define MIN(a,b) ((a)<(b) ? (a) : (b) ) +#define MAX(a,b) ((a)>(b) ? (a) : (b) ) +#define ABS(a) ((a)>0 ? (a) : -(a)) +#define SGN(a) ((a)==0 ? (0) : ( (a)>0 ? (1) : (-1) )) +#define IN_RANGE(a, x, b) ((a) <= (x) && (x) <= (b)) + +#define BOARD_EDGE_SIZE 19 +#define TIME_LIM 600 + +#define BB_EDGE (BOARD_EDGE_SIZE + 2) +#define XY_SIZE (BB_EDGE * BB_EDGE) +#define BB_EFF 64 +#define NUM_PER_BB 64 +#define BB_IDX_SIZE ((XY_SIZE - 1)/NUM_PER_BB + 1) + +#define VEC_WIDTH 8 + +typedef unsigned long long bb_t; + +typedef enum { SP = 0, BK, WH, OB } color_t; +typedef enum { TBN_BK = 0, TBN_WH } teban_t; +typedef enum { OFF = 0, ON } onoff_t; + +#define CROSS_MAX 4 +#define D_MAX 8 + +#define TBN_MAX 2 +#define COLOR_MAX 4 +#define GET_AITE(st) (BK + WH - (st)) +#define AITE_TBN(tbn) (TBN_BK + TBN_WH - (tbn)) +#define TBN2COLOR(tbn) ((tbn) + 1) +#define COLOR2TBN(color) ((color) - 1) + +#define TESUU_MAX (XY_SIZE * 2) +#define REN_MAX (XY_SIZE * 2) /* 連の最大数 */ +#define REN_BB_SIZE (REN_MAX/BB_EFF + 1) + +#define FRAME 512 + +#define IS_FIRST_MOVE(ban) (ban->tesuu == 1 && ban->occupiedPoints[TBN_BK] == 0 && ban->occupiedPoints[TBN_WH] == 0) +#define X_Y_TO_POS(x, y) ((y) * BB_EDGE + (x)) + +#define POS_TO_X(pos) (pos % BB_EDGE) +#define POS_TO_Y(pos) (pos / BB_EDGE) + +#define POS_TO_IDX(pos) ((pos)/NUM_PER_BB) +#define POS_TO_BIT(pos) ((pos)%NUM_PER_BB) + +#define GET_POS(idx, digit) ((idx) * NUM_PER_BB + (digit)) + +#define BELONGS_TO(bb, pos) (bb[POS_TO_IDX(pos)] & (1LL << (POS_TO_BIT(pos)))) +#define ADD_AN_ELEMENT_TO_BB(bb, pos) (bb[POS_TO_IDX(pos)] |= (1LL << (POS_TO_BIT(pos)))) +#define ERASE_AN_ELEMENT_FROM_BB(bb, pos) (bb[POS_TO_IDX(pos)] &= ~(1LL << (POS_TO_BIT(pos)))) + +#define MERGE_BB(bb, bb2) if (1){int k; for(k=0;ktesuu = 1; + ban->tbn = TBN_BK; + for (pos = 0; pos < XY_SIZE; pos++){ + x = POS_TO_X(pos); + y = POS_TO_Y(pos); + if (!(IN_RANGE(1, x, BOARD_EDGE_SIZE) && IN_RANGE(1, y, BOARD_EDGE_SIZE))){ + ban->color[pos] = OB; + } + } + return; +} + +game_hdl_t *open_game_hdl(int argc, char **argv) +{ + game_hdl_t *hdl; + + if ((hdl = calloc(1, sizeof(game_hdl_t))) == NULL || + (hdl->ban = calloc(1, sizeof(goban_t))) == NULL || + (cnn_param = calloc(1, sizeof(parameter_t))) == NULL){ + return NULL; + } + set_initial_pos(hdl->ban); + return hdl; +} + +void close_game_hdl(game_hdl_t *hdl) +{ + free(hdl->ban); + free(hdl); + return; +} diff --git a/main.c b/main.c new file mode 100644 index 0000000..b543af1 --- /dev/null +++ b/main.c @@ -0,0 +1,166 @@ +/* Copyright (C) 2016 Otsuki Tomoshi */ +#include "go.h" +#include +#ifdef _WIN32 + #include + #define GetCurrentDir _getcwd +#else + #include + #include + #define GetCurrentDir getcwd +#endif + +const char *X_CORD = {"-ABCDEFGHJKLMNOPQRST-\0"}; +const char *(Y_CORD[BOARD_EDGE_SIZE + 2]) = {"-", + "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19" +}; + +void send_gtp(const char *fmt, ...) +{ + va_list ap; + + va_start(ap, fmt); + vfprintf(stdout, fmt, ap ); // 標準出力に書き出す + va_end(ap); +} + +// 相手の手を受信 "play W D17" のように来る +int get_receive_pos(int *tbn, char *str) +{ + int pos_x = 0, pos_y = 0, x, y, y2; + + if (!strncmp(&str[5], "W", 1)){ + *tbn = TBN_WH; + } else if (!strncmp(&str[5], "B", 1)){ + *tbn = TBN_BK; + } else { + fprintf(stderr, "tbn_err\n"); + } + for (x = 1; x <= BOARD_EDGE_SIZE; x++){ + if (!strncmp(&str[7], &X_CORD[x], 1)){ + pos_x = x; + break; + } + } + + for (y = 1; y <= 9; y++){ /* 1 keta me */ + if (!strncmp(&str[8], Y_CORD[y], 1)){ + if (y == 1){ + for (y2 = 10; y2 <= 19; y2++){ /* 2 keta me */ + if (!strncmp(&str[8], Y_CORD[y2], 2)){ + y = y2; + break; + } + } + } + pos_y = BOARD_EDGE_SIZE + 1 - y; + break; + } + } + + fprintf(stderr, "x = %d, y = %d\n", pos_x, pos_y); + return X_Y_TO_POS(pos_x, pos_y); +} + + +int gtp(game_hdl_t *hdl) +{ + char str[FRAME]; + goban_t *ban = hdl->ban; + + // stdoutをバッファリングしないように。GTPで通信に失敗するので。 + setbuf(stdout, NULL); + setbuf(stderr, NULL); // stderrに書くとGoGuiに表示される。 + while (1) { + writeBan(ban); + + fprintf(stderr, " NOW: tesuu: %d, tbn: %.1s, (PREV): ", ban->tesuu, &COLOR_NAME[TBN2COLOR(ban->tbn)]); + outPos(ban->histInfo[ban->tesuu - 1].pos), fprintf(stderr, "\n"); + + if (fgets(str, FRAME, stdin)==NULL ) break; // 標準入力から読む + + if (strstr(str,"boardsize")) { + send_gtp("= \n\n"); // "boardsize 19": 19路盤 + if (atoi(&str[10]) != BOARD_EDGE_SIZE){ + fprintf(stderr, "illegal boardsize (%d != %d)\n", atoi(&str[10]), BOARD_EDGE_SIZE); + } + fprintf( stderr, "if you write in stderr, output into gogui\n"); + } else if (strstr(str,"clear_board")){ + set_initial_pos(ban); + send_gtp("= \n\n"); + } else if (strstr(str,"komi")){ + ban->komi = atof(&str[5]); + fprintf(stderr, "komi = %f\n", ban->komi); + send_gtp("= \n\n"); + } else if (strstr(str,"undo")){ + if (ban->tesuu >= 3){ + unmake_move(ban); + unmake_move(ban); + } + send_gtp("= \n\n"); + } else if (strstr(str,"name")){ + send_gtp("= deltaGo\n\n"); + } else if ( strstr(str,"protocol_version")){ + send_gtp("= 2\n\n"); + } else if ( strstr(str,"version")){ + send_gtp("= 1.0.0\n\n"); + } else if ( strstr(str,"genmove w") || strstr(str,"genmove b")){ + int x, y, pos; + double pos2prob[XY_SIZE]; + fprintf( stderr, "I'm thinking... \n"); + double time_s = Tool_GetTimeNow(); + + get_feature(NULL, 0, ban->tesuu - 1, ban); + pos = get_cnn_prob(ban, hdl, pos2prob); + if (pos == 0){ + fprintf(stderr, "PASS\n\n"); + send_gtp("= PASS\n\n"); + } else { + x = POS_TO_X(pos); + y = POS_TO_Y(pos); + fprintf(stderr, "%.1s%s\n\n", &X_CORD[x], Y_CORD[y]); + send_gtp("= %.1s%s\n\n", &X_CORD[x], Y_CORD[BOARD_EDGE_SIZE + 1 - y]); + } + outPos(pos); + fprintf(stderr, "\ntime = %f\n", Tool_GetTimeNow() - time_s); + make_move(pos, ban); + } else if ( strstr(str,"play")){ // 相手の手を受信 "play W D17" のように来る + int tbn; + int pos = get_receive_pos(&tbn, str); + if (tbn == ban->tbn){ + make_move(pos, ban); + } else { // 置き碁の場合?はPASSを挿入 + make_move(0, ban); + make_move(pos, ban); + } + send_gtp("= \n\n"); + } else { + send_gtp("= \n\n"); // それ以外のコマンドにはOKを返す + } + } + return 0; +} + +int main(int argc, char **argv) +{ + game_hdl_t *hdl; + if ((hdl = open_game_hdl(argc, argv)) == NULL){ + fprintf(stderr, "open game_hdl error\n"); + return 0; + } + // read cnn parameter + FILE *fp_in; + if ((fp_in = fopen("paramter.bin","rb")) == NULL){ + fprintf(stderr, "file open error: %s\n", "paramter.bin"); + char path[260]; + if (GetCurrentDir(path, sizeof(path)) != NULL) { + printf("please put paramter.bin into the directory: %s\n", path); + } else { + perror("getcwd"); + } + return 0; + } + int n = fread(cnn_param,sizeof(cnn_t), sizeof(parameter_t)/sizeof(cnn_t), fp_in); + gtp(hdl); + return 0; +} diff --git a/move.c b/move.c new file mode 100644 index 0000000..607ee0c --- /dev/null +++ b/move.c @@ -0,0 +1,277 @@ +#include "go.h" + +static void add_new_ren(const int xy, int nb_num[4], int nb_stones[4][4], + goban_t *ban) +{ + const int color = ban->color[xy]; + renInfo_t *renInfo = &ban->renInfo[++ban->renNum]; + int i; + + renInfo->color = color; + + renInfo->occupiedPoints = 1; + ADD_AN_ELEMENT_TO_BB(renInfo->occupiedBB, xy); + + renInfo->breathPoints = nb_num[SP]; + for (i = 0; i < nb_num[SP]; i++){ + ADD_AN_ELEMENT_TO_BB(renInfo->breathBB, nb_stones[SP][i]); + } + ban->renID[xy] = ban->renNum; + + return; +} + +static void erase_ren(goban_t *ban) +{ + renInfo_t *renInfo = &ban->renInfo[ban->renNum--]; + memset(renInfo, 0, sizeof(renInfo_t)); + + return; +} + +static void merge_ren(const int pos, int nb_num[4], int nb_stones[4][4], + history_t *histInfo, goban_t *ban) +{ + const int color = ban->color[pos]; + const int renID = ban->renID[nb_stones[color][0]]; + renInfo_t *renInfo = &ban->renInfo[renID], *renInfo2; + int i, k; + unsigned long long bit; + + histInfo->renInfo = *renInfo; + histInfo->mergeNum = 0; + histInfo->mergeRenID[histInfo->mergeNum++] = renID; + + /* renew renID, and merge occupiedBB & breathPoint */ + for (i = 1; i < nb_num[color]; i++){ + const int posNB = nb_stones[color][i]; + + renInfo2 = &ban->renInfo[ban->renID[posNB]]; + if (!BELONGS_TO(renInfo->occupiedBB, posNB)){ + histInfo->mergeRenID[histInfo->mergeNum++] = ban->renID[posNB]; + for (k = 0; k < BB_IDX_SIZE; k++){ + for (bit = renInfo2->occupiedBB[k]; bit; bit &= (bit - 1)){ + ban->renID[GET_POS(k, Get_FirstBit64(bit))] = renID; + } + } + renInfo->occupiedPoints += renInfo2->occupiedPoints; + MERGE_BB(renInfo->occupiedBB, renInfo2->occupiedBB); + MERGE_BB(renInfo->breathBB, renInfo2->breathBB); + renInfo2->deadFlag = ON; + } + } + /* update occupied info */ + renInfo->occupiedPoints++; + ADD_AN_ELEMENT_TO_BB(renInfo->occupiedBB, pos); + ban->renID[pos] = renID; + + /* update breathBB */ + ERASE_AN_ELEMENT_FROM_BB(renInfo->breathBB, pos); + + for (i = 0; i < nb_num[SP]; i++){ + ADD_AN_ELEMENT_TO_BB(renInfo->breathBB, nb_stones[SP][i]); + } + /* re calc renInfo->breathPoints */ + renInfo->breathPoints = 0; + for (k = 0; k < BB_IDX_SIZE; k++){ + renInfo->breathPoints += pop_cnt(renInfo->breathBB[k]); + } + return; +} + + +static void split_ren(const int pos, + history_t *histInfo, goban_t *ban) +{ + const int renID = histInfo->mergeRenID[0]; + renInfo_t *renInfo = &ban->renInfo[renID], *renInfo2; + int i, k; + unsigned long long bit; + + /* renew renID, and merge occupiedBB & breathPoint */ + for (i = 1; i < histInfo->mergeNum; i++){ + const int renID2 = histInfo->mergeRenID[i]; + + renInfo2 = &ban->renInfo[renID2]; + + for (k = 0; k < BB_IDX_SIZE; k++){ + for (bit = renInfo2->occupiedBB[k]; bit; bit &= (bit - 1)){ + ban->renID[GET_POS(k, Get_FirstBit64(bit))] = renID2; + } + } + renInfo2->deadFlag = OFF; + } + *renInfo = histInfo->renInfo; + + return; +} + +void make_move(const int pos, goban_t *ban) +{ + const int color = TBN2COLOR(ban->tbn); + int nb_num[4], nb_stones[4][4]; + int d, i, k, posRemove; + unsigned long long bit; + history_t *histInfo = &ban->histInfo[ban->tesuu++]; + + assert (ban->tesuu < TESUU_MAX); + assert (ban->renNum < REN_MAX); + + histInfo->removeNum = 0; + histInfo->ko = 0; + histInfo->pos = pos; + if (!pos){ + ban->tbn ^= 1; + return; + } + assert (ban->color[pos] == SP); + + ban->color[pos] = color; + ban->occupiedPoints[ban->tbn]++; + ADD_AN_ELEMENT_TO_BB(ban->occupiedBB[ban->tbn], pos); + + /* update renn */ + get_nb_stones(pos, nb_num, nb_stones, ban); + if (nb_num[color] == 0){ + add_new_ren(pos, nb_num, nb_stones, ban); + } else { + merge_ren(pos, nb_num, nb_stones, histInfo, ban); + } + /* erase opponent's breathPoint, and remove opponent's stone if any*/ + for (i = 0; i < nb_num[GET_AITE(color)]; i++){ + const int renID = ban->renID[nb_stones[GET_AITE(color)][i]]; + renInfo_t *renInfo = &ban->renInfo[renID]; + + /* erase opponent's breathPoint around pos */ + if (BELONGS_TO(renInfo->breathBB, pos)){ + if (renInfo->breathPoints > 1){ + ERASE_AN_ELEMENT_FROM_BB(renInfo->breathBB, pos); + renInfo->breathPoints--; + } else { /* remove opponent's stone if no breath point */ + histInfo->removeRenID[histInfo->removeNum++] = renID; + + SPLIT_OUT_BB(ban->occupiedBB[ban->tbn^1], ban->renInfo[renID].occupiedBB); + + ban->renInfo[renID].deadFlag = ON; + + ban->occupiedPoints[ban->tbn^1] -= renInfo->occupiedPoints; + + ban->prisoner[ban->tbn] += renInfo->occupiedPoints; + for (k = 0; k < BB_IDX_SIZE; k++){ + for (bit = renInfo->occupiedBB[k]; bit; bit &= (bit - 1)){ + + posRemove = GET_POS(k, Get_FirstBit64(bit)); + + ban->renID[posRemove] = 0; + ban->color[posRemove] = SP; + + /* update teban's breath point by stone removal*/ + for (d = 1; d < D_MAX; d += 2){ + int tgt = posRemove + D2DELTA[d]; + renInfo_t *renInfo2 = &ban->renInfo[ban->renID[tgt]]; + + if (color == ban->color[tgt]){ + if (!BELONGS_TO(renInfo2->breathBB, posRemove)){ + ADD_AN_ELEMENT_TO_BB(renInfo2->breathBB, posRemove); + renInfo2->breathPoints++; + } + } + } + } + } + } + } + } + /* judge ko */ + if (histInfo->removeNum == 1 && + ban->renInfo[ban->renID[pos]].occupiedPoints == 1 && + ban->renInfo[ban->renID[pos]].breathPoints == 1 && + ban->renInfo[histInfo->removeRenID[0]].occupiedPoints == 1){ + + + histInfo->ko = get_single_pos(ban->renInfo[histInfo->removeRenID[0]].occupiedBB); + + } + /* update tbn */ + ban->tbn ^= 1; + + + return; +} + +void unmake_move(goban_t *ban) +{ + int color, d, i, k, posReset; + unsigned long long bit; + history_t *histInfo = &ban->histInfo[--ban->tesuu]; + const int pos = histInfo->pos; + int tgt, cnt = 0; + renInfo_t *renInfo; + + /* update tbn */ + ban->tbn ^= 1; + + if (!pos){ + return; + } + + color = TBN2COLOR(ban->tbn); + assert (ban->color[pos] == color); + + ban->color[pos] = SP; + ban->renID[pos] = 0; + ERASE_AN_ELEMENT_FROM_BB(ban->occupiedBB[ban->tbn], pos); + ban->occupiedPoints[ban->tbn]--; + + for (d = 1; d < D_MAX; d += 2){ + tgt = pos + D2DELTA[d]; + cnt += (ban->color[tgt] == color); + /* add opponent's breathPoint */ + if (ban->color[tgt] == GET_AITE(color)){ + renInfo = &ban->renInfo[ban->renID[tgt]]; + if (!BELONGS_TO(renInfo->breathBB, pos)){ + ADD_AN_ELEMENT_TO_BB(renInfo->breathBB, pos); + renInfo->breathPoints++; + } + } + } + /* update mikata's ren */ + if (cnt == 0){ /* if (no mikata's stone around pos) */ + erase_ren(ban); + } else { + split_ren(pos, histInfo, ban); + } + /* re set opponent's stone if any */ + for (i = 0; i < histInfo->removeNum; i++){ + const int renID = histInfo->removeRenID[i]; + renInfo_t *renInfo = &ban->renInfo[renID]; + + ban->renInfo[renID].deadFlag = OFF; + + ban->prisoner[ban->tbn] -= renInfo->occupiedPoints; + ban->occupiedPoints[ban->tbn^1] += renInfo->occupiedPoints; + MERGE_BB(ban->occupiedBB[ban->tbn^1], renInfo->occupiedBB); + + for (k = 0; k < BB_IDX_SIZE; k++){ + for (bit = renInfo->occupiedBB[k]; bit; bit &= (bit - 1)){ + posReset = GET_POS(k, Get_FirstBit64(bit)); + ban->renID[posReset] = renID; + ban->color[posReset] = GET_AITE(color); + /* update teban's breath point by stone re set */ + for (d = 1; d < D_MAX; d += 2){ + int tgt = posReset + D2DELTA[d]; + renInfo_t *renInfo2 = &ban->renInfo[ban->renID[tgt]]; + + if (color == ban->color[tgt]){ + if (BELONGS_TO(renInfo2->breathBB, posReset)){ + ERASE_AN_ELEMENT_FROM_BB(renInfo2->breathBB, posReset); + renInfo2->breathPoints--; + } + } + } + } + } + } + + return; +} diff --git a/util.c b/util.c new file mode 100644 index 0000000..7e54158 --- /dev/null +++ b/util.c @@ -0,0 +1,297 @@ +#include "go.h" + +#define neighbor_count_at(ban, pos, color2) \ + ((ban->color[pos + D2DELTA[1]] == color2) + \ + (ban->color[pos + D2DELTA[3]] == color2) + \ + (ban->color[pos + D2DELTA[5]] == color2) + \ + (ban->color[pos + D2DELTA[7]] == color2)) + +int outPos(const int pos) +{ + fprintf(stderr, "(%d %d)", POS_TO_X(pos), POS_TO_Y(pos)); + return 0; +} + +int judgeKoNG(const int pos, goban_t *ban) +{ + history_t *histInfo = &ban->histInfo[ban->tesuu - 1]; + assert (ban->tesuu >= 1); + return (pos == histInfo->ko); +} + +/* not judging KO ng move*/ +int teOK(const int xy, goban_t *ban) +{ + const int color = TBN2COLOR(ban->tbn); + int d; + + if (xy == 0) + return 1; + if (IN_RANGE(0, xy, XY_SIZE - 1) && ban->color[xy] == SP){ + for (d = 1; d < D_MAX; d += 2){ /* cross */ + const int pos = xy + D2DELTA[d]; + const int renID = ban->renID[pos]; + const int colorD = ban->color[pos]; + if (colorD == SP){ + return 1; + } + if (colorD == color && ban->renInfo[renID].breathPoints > 1){ + return 1; + } + if (colorD == GET_AITE(color) && ban->renInfo[renID].breathPoints == 1){ + return 1; + } + } + } + return 0; +} + +/* REQUIRE : ban->color[pos] == SP + + 合法手でなければ NG + 合法手でも、四方を味方石で囲まれた位置は、 + 取られそうな場合(味方の呼吸点1の連に接する手)を除き NG (return 0), + そうでなければ return 1; */ +int judge_eff_te(const int pos, goban_t *ban) +{ + const int colorAite = GET_AITE(TBN2COLOR(ban->tbn)); + int d, tgt, colorD; + + if (neighbor_count_at(ban, pos, SP) >= 1){ + return 1; + } + if (!teOK(pos, ban) || judgeKoNG(pos, ban)){ + return 0; + } + for (d = 1; d < D_MAX; d += 2){ + tgt = pos + D2DELTA[d]; + colorD = ban->color[tgt]; + if (colorD == OB) + continue; + + if (colorD == SP || colorD == colorAite){ + return 1; + } + if (ban->renInfo[ban->renID[tgt]].breathPoints == 1){ + return 1; + } + } + return 0; +} + +void writeBan(goban_t *ban) +{ + int x, y; + + for (x = 1; x <= BOARD_EDGE_SIZE; x++){ + fprintf(stderr, "%.1s", &COLOR_NAME[ban->color[x]]); + } + fprintf(stderr, "\n ["); + for (x = 1; x <= BOARD_EDGE_SIZE; x++){ + fprintf(stderr, "%2d", x); + } + fprintf(stderr, "]\n"); + for (y = 1; y <= BOARD_EDGE_SIZE ; y++){ + fprintf(stderr, "[%2d] ", y); + for (x = 1; x <= BOARD_EDGE_SIZE; x++){ + fprintf(stderr, "%.1s ", &COLOR_NAME[ban->color[X_Y_TO_POS(x, y)]]); + } + fprintf(stderr, "\n"); + } + fprintf(stderr, "tbn = %.1s, tesuu = %d, bk: %d, wh: %d prev: %.1s", + &COLOR_NAME[ban->tbn + 1], ban->tesuu, ban->prisoner[TBN_BK], ban->prisoner[TBN_WH], &COLOR_NAME[GET_AITE(ban->tbn + 1)]); + outPos(ban->histInfo[ban->tesuu - 1].pos); + return; +} +#define LEADING_ONES(x) ((1ULL << (x)) - 1ULL) + +int get_around_bb(bb_t *aroundBB, bb_t *inBB) +{ + int k; + for (k = 0; k < BB_IDX_SIZE; k++){ + aroundBB[k] = + (inBB[k] >> 1ULL) | (inBB[k] >> BB_EDGE) + | ((inBB[k] & LEADING_ONES(NUM_PER_BB - 1)) << 1ULL) + | ((inBB[k] & LEADING_ONES(NUM_PER_BB - BB_EDGE)) << BB_EDGE); + if (k < BB_IDX_SIZE - 1 && inBB[k + 1]){ + aroundBB[k] |= + ((inBB[k + 1] & LEADING_ONES(BB_EDGE)) << (NUM_PER_BB - BB_EDGE)) + | ((inBB[k + 1] & LEADING_ONES(1)) << (NUM_PER_BB - 1)); + } + if (k > 0 && inBB[k - 1]){ + aroundBB[k] |= + (inBB[k - 1] >> (NUM_PER_BB - BB_EDGE)) + |(inBB[k - 1] >> (NUM_PER_BB - 1)); + } + } + return 0; +} + +int is_danger_around(goban_t *ban, bb_t *target_occupiedBB, const int check_tbn) +{ + int k, target; + bb_t aroundBB[BB_IDX_SIZE], bit; + get_around_bb(aroundBB, target_occupiedBB); + for (k = 0; k < BB_IDX_SIZE; k++){ + for (bit = aroundBB[k] & ban->occupiedBB[check_tbn][k]; bit; bit &= (bit - 1)){ + target = GET_POS(k, Get_FirstBit64(bit)); + if (ban->renInfo[ban->renID[target]].breathPoints == 1){ + return 1; + } + } + } + return 0; +} + +int detect_suicide_or_capture(goban_t *ban, const int pos) +{ + int d; + bb_t breathBB[BB_IDX_SIZE]; + + CLEAR_BB(breathBB); + ADD_AN_ELEMENT_TO_BB(breathBB, pos); + + for (d = 1; d < D_MAX; d += 2){ /* CROSS */ + const int target = pos + D2DELTA[d]; + if (ban->color[target] == SP){ + ADD_AN_ELEMENT_TO_BB(breathBB, target); + } + + if (ban->color[target] == TBN2COLOR(ban->tbn)){ + renInfo_t *renInfo2 = &ban->renInfo[ban->renID[target]]; + MERGE_BB(breathBB, renInfo2->breathBB); + } + if (ban->color[target] == GET_AITE(TBN2COLOR(ban->tbn))){ + renInfo_t *renInfo2 = &ban->renInfo[ban->renID[target]]; + if (renInfo2->breathPoints == 1){ /* capture */ + return 1; + } + } + } + + int breathPoints = bb_pop_cnt(breathBB); + if (breathPoints >= 3){ + return 0; + } + + assert (breathPoints == 2); + return 1; +} + +int check_kill(const int seme, const int escape, goban_t *ban) +{ + const int prePos = ban->histInfo[ban->tesuu - 1].pos; + int res = 0; + assert (seme && escape);// && ban->color[seme] == SP && ban->color[escape] == SP); + if (!teOK(seme, ban)|| judgeKoNG(seme, ban) || detect_suicide_or_capture(ban, seme)){ + return 0; + } + + make_move(seme, ban); + renInfo_t *renInfo = &ban->renInfo[ban->renID[seme]]; + if (renInfo->breathPoints >= 2 && + check_dead(escape, ban)){ + + // semeの直前の相手石の連の、周囲の石(つまりsemeの方)を取られないかをcheck + renInfo_t *renInfo2 = &ban->renInfo[ban->renID[prePos]]; + if (is_danger_around(ban, renInfo2->occupiedBB, AITE_TBN(ban->tbn))){ + res = 0; + } else { + res = 1; + } + } + unmake_move(ban); + return res; +} + + +int check_dead(const int pos, goban_t *ban) +{ + int res = 0, k, cand[2]; + if (ban->tesuu >= TESUU_MAX - 2){ + return 0; + } + make_move(pos, ban); + + renInfo_t *renInfo = &ban->renInfo[ban->renID[pos]]; + + res = (renInfo->breathPoints == 1); + + if (renInfo->breathPoints == 2){ + get_double_pos(cand, renInfo->breathBB); + for (k = 0; k < 2; k++){ + if (res == OFF){ + res = check_kill(cand[k], cand[1 - k], ban); + } + } + } + unmake_move(ban); + return res; +} + +int get_nb_stones(const int pos, int nb_num[4], int nb_stones[4][4], goban_t *ban) +{ + int d, tgt, colorD; + + assert(IN_RANGE(1, POS_TO_X(pos), BOARD_EDGE_SIZE) && IN_RANGE(1, POS_TO_Y(pos), BOARD_EDGE_SIZE)); + + nb_num[0] = nb_num[1] = nb_num[2] =nb_num[3] = 0; + + for (d = 1; d < D_MAX; d += 2){ /* cross */ + tgt = pos + D2DELTA[d]; + colorD = ban->color[tgt]; + nb_stones[colorD][nb_num[colorD]++] = tgt; + } + return 0; +} + +int bb_pop_cnt(bb_t *targetBB) +{ + int k, cnt = 0; + for (k = 0; k < BB_IDX_SIZE; k++) + cnt += pop_cnt(targetBB[k]); + return cnt; +} + +int get_double_pos(int *cand, bb_t *targetBB) +{ + int k, cnt = 0; + unsigned long long bit; + assert(bb_pop_cnt(targetBB) == 2); + + for (k = 0; k < BB_IDX_SIZE; k++){ + for (bit = targetBB[k]; bit; bit &= (bit - 1)){ + cand[cnt++] = GET_POS(k, Get_FirstBit64(bit)); + } + } + return 0; +} + +int get_single_pos(bb_t *targetBB) +{ + int k; + + for (k = 0; k < BB_IDX_SIZE; k++){ + if (targetBB[k]){ + return GET_POS(k, Get_FirstBit64(targetBB[k])); + } + } + return 0; +} + + +int get_another_pos(bb_t *targetBB, const int exclude) +{ + int cand[2]; + get_double_pos(cand, targetBB); + if (cand[0] == exclude){ + return cand[1]; + } else { + return cand[0]; + } + return 0; +} +double Tool_GetTimeNow() +{ + return clock()/(double)(CLOCKS_PER_SEC); +}