#include <stdio.h> const int MaxSize = 14; const int MaxValue = 2 * 4782969; const int MaxKoMoves = 6; const int Delta = 100; const int MaxScore = 10000; const int Unknown = 1000; const int Left = 0; const int Right = 1; const int Empty = 2; int power3 [MaxSize]; int value [MaxSize] [MaxValue]; int nbKoMovesLeft [MaxValue], nbKoMovesRight [MaxValue]; int koMovesLeft [MaxValue] [MaxKoMoves], koMovesRight [MaxValue] [MaxKoMoves]; int valueLeft [MaxValue] [MaxKoMoves + 1], valueRight [MaxValue] [MaxKoMoves + 1]; class Woodpush { public: int size, board [MaxSize], ko; void init (int s) { size = s; for (int i = 0; i < size; i++) board [i] = Empty; if (size <= 5) { board [0] = Left; board [size - 1] = Right; } else { board [0] = Left; //board [5] = Left; board [2] = Left; board [size - 1] = Right; //board [size - 6] = Right; board [size - 3] = Right; } ko = hash (); } bool legal (int move, int color) { if (move >= Delta) { move = move - Delta; if (board [move] != color) return false; if (color == Left) { if (move == 0) return false; if (board [move - 1] != Right) return false; } else { if (move == size - 1) return false; if (board [move + 1] != Left) return false; } Woodpush w = *this; w.play (move + Delta, color); if (w.hash () == ko) return false; } if (board [move] != color) return false; return true; } int koMove (int color) { for (int move = 0; move < size; move++) { if (board [move] != color) continue; if (color == Left) { if (move == 0) continue; if (board [move - 1] != Right) continue; } else { if (move == size - 1) continue; if (board [move + 1] != Left) continue; } Woodpush w = *this; w.play (move + Delta, color); if (w.hash () == ko) return move + Delta; } return -1; } void play (int move, int color) { bool done = false; ko = hash (); if (color == Left) { if (move >= Delta) { move = move - Delta; if (board [move - 1] == Right) { int first = 0; for (int i = move - 1; i > -1; i--) if (board [i] == Empty) { first = i; break; } /* if ((first == move - 2) && (board [first] == Empty)) */ /* ko = move - 2; */ for (int i = first; i < move; i++) board [i] = board [i + 1]; board [move] = Empty; done = true; } } if (!done) { int last = size; for (int i = move + 1; i < size; i++) if (board [i] == Empty) { last = i; break; } board [move] = Empty; if (last < size) board [last] = color; } } else { if (move >= Delta) { move = move - Delta; if (board [move + 1] == Left) { int first = size - 1; for (int i = move + 1; i < size; i++) if (board [i] == Empty) { first = i; break; } /* if ((first == move + 2) && (board [first] == Empty)) */ /* ko = move + 2; */ for (int i = first; i > move; i--) board [i] = board [i - 1]; board [move] = Empty; done = true; } } if (!done) { int last = -1; for (int i = move - 1; i > -1; i--) if (board [i] == Empty) { last = i; break; } board [move] = Empty; if (last > -1) board [last] = color; } } } void print (FILE * fp = stderr) { //fprintf (fp, "%d %d\n", value [size] [hash ()], value [size] [power3 [size] + hash ()]); for (int i = 0; i < size; i++) fprintf (fp, " %d", i); fprintf (fp, "\n"); for (int i = 0; i < size; i++) { fprintf (fp, "|"); if (board [i] == Empty) fprintf (fp, " "); else if (board [i] == Left) fprintf (fp, "L"); else if (board [i] == Right) fprintf (fp, "R"); } fprintf (fp, "|\n"); fprintf (fp, "hash = %d\n", hash ()); int m = bestMoveKo (Left); fprintf (fp, "Left plays at %d and scores %d (%d)\n", m, bestValueKo (Left), findValueLeftMoveKo (m)); m = bestMoveKo (Right); fprintf (fp, "Right plays at %d and scores %d (%d)\n", m, bestValueKo (Right), findValueRightMoveKo (m)); } int bestMove (int player) { int bestval, best = -1; if (player == Left) { bestval = -MaxScore; for (int i = 0; i < size; i++) { if (legal (i, Left)) { Woodpush w = *this; w.play (i, Left); int v = value [size] [power3 [size] + w.hash ()]; if (v > bestval) { best = i; bestval = v; } } if (legal (Delta + i, Left)) { Woodpush w = *this; w.play (Delta + i, Left); int v = value [size] [power3 [size] + w.hash ()]; if (v > bestval) { best = Delta + i; bestval = v; } } } } else { // Right to play bestval = MaxScore; for (int i = 0; i < size; i++) { if (legal (i, Right)) { Woodpush w = *this; w.play (i, Right); int v = value [size] [w.hash ()]; if (v < bestval) { best = i; bestval = v; } } if (legal (Delta + i, Right)) { Woodpush w = *this; w.play (Delta + i, Left); int v = value [size] [w.hash ()]; if (v < bestval) { best = Delta + i; bestval = v; } } } } return best; } int bestValue (int player) { int bestval, best = -1; if (player == Left) { bestval = -MaxScore; for (int i = 0; i < size; i++) { if (legal (i, Left)) { Woodpush w = *this; w.play (i, Left); int v = value [size] [power3 [size] + w.hash ()]; if (v == Unknown) v = MaxScore; if (v > bestval) { best = i; bestval = v; } } if (legal (Delta + i, Left)) { Woodpush w = *this; w.play (Delta + i, Left); int v = value [size] [power3 [size] + w.hash ()]; if (v == Unknown) v = MaxScore; if (v > bestval) { best = Delta + i; bestval = v; } } } } else { // Right to play bestval = MaxScore; for (int i = 0; i < size; i++) { if (legal (i, Right)) { Woodpush w = *this; w.play (i, Right); int v = value [size] [w.hash ()]; if (v == Unknown) v = -MaxScore; if (v < bestval) { best = i; bestval = v; } } if (legal (Delta + i, Right)) { Woodpush w = *this; w.play (Delta + i, Left); int v = value [size] [w.hash ()]; if (v == Unknown) v = -MaxScore; if (v < bestval) { best = Delta + i; bestval = v; } } } } return bestval; } int findValueLeftMoveKo (int move) { Woodpush w = *this; w.play (move, Left); int h = w.hash (); int v = valueRight [h] [0]; int km = w.koMove (Right); if (km != -1) { int indice = -1; for (int n = 0; n < nbKoMovesRight [h]; n++) if (koMovesRight [h] [n] == km) indice = n; if (indice == -1) fprintf (stderr, "pb koMovesRight [%d] != %d\n", h, km); else v = valueRight [h] [indice + 1]; } return v; } int findValueRightMoveKo (int move) { Woodpush w = *this; w.play (move, Right); int h = w.hash (); int v = valueLeft [h] [0]; int km = w.koMove (Left); if (km != -1) { int indice = -1; for (int n = 0; n < nbKoMovesLeft [h]; n++) if (koMovesLeft [h] [n] == km) indice = n; if (indice == -1) { fprintf (stderr, "pb koMovesLeft [%d] != %d\n", h, km); print (); w.print (); } else v = valueLeft [h] [indice + 1]; } return v; } int bestValueKo (int player) { int bestval, best = -1; if (player == Left) { bestval = -MaxScore; for (int i = 0; i < size; i++) { if (legal (i, Left)) { int v = findValueLeftMoveKo (i); if (v == Unknown) v = MaxScore; if (v > bestval) { best = i; bestval = v; } } if (legal (Delta + i, Left)) { int v = findValueLeftMoveKo (Delta + i); if (v == Unknown) v = MaxScore; if (v > bestval) { best = Delta + i; bestval = v; } } } } else { // Right to play bestval = MaxScore; for (int i = 0; i < size; i++) { if (legal (i, Right)) { int v = findValueRightMoveKo (i); if (v == Unknown) v = -MaxScore; if (v < bestval) { best = i; bestval = v; } } if (legal (Delta + i, Right)) { int v = findValueRightMoveKo (Delta + i); if (v == Unknown) v = -MaxScore; if (v < bestval) { best = Delta + i; bestval = v; } } } } return bestval; } int bestMoveKo (int player) { int bestval, best = -1; if (player == Left) { bestval = -MaxScore; for (int i = 0; i < size; i++) { if (legal (i, Left)) { int v = findValueLeftMoveKo (i); if (v == Unknown) v = MaxScore; if (v > bestval) { best = i; bestval = v; } } if (legal (Delta + i, Left)) { int v = findValueLeftMoveKo (Delta + i); if (v == Unknown) v = MaxScore; if (v > bestval) { best = Delta + i; bestval = v; } } } } else { // Right to play bestval = MaxScore; for (int i = 0; i < size; i++) { if (legal (i, Right)) { int v = findValueRightMoveKo (i); if (v == Unknown) v = -MaxScore; if (v < bestval) { best = i; bestval = v; } } if (legal (Delta + i, Right)) { int v = findValueRightMoveKo (Delta + i); if (v == Unknown) v = -MaxScore; if (v < bestval) { best = Delta + i; bestval = v; } } } } return best; } int bestValueKoLeftStep () { int bestval, best = -1; bestval = -MaxScore; for (int i = 0; i < size; i++) { if (legal (i, Left)) { int v = findValueLeftMoveKo (i); if (v != Unknown) if (v > bestval) { best = i; bestval = v; } } if (legal (Delta + i, Left)) { int v = findValueLeftMoveKo (Delta + i); if (v != Unknown) if (v > bestval) { best = Delta + i; bestval = v; } } } return bestval; } int bestValueKoRightStep () { int bestval, best = -1; bestval = MaxScore; for (int i = 0; i < size; i++) { if (legal (i, Right)) { int v = findValueRightMoveKo (i); if (v == Unknown) bestval = -MaxScore; else if (v < bestval) { best = i; bestval = v; } } if (legal (Delta + i, Right)) { int v = findValueRightMoveKo (Delta + i); if (v == Unknown) bestval = -MaxScore; else if (v < bestval) { best = Delta + i; bestval = v; } } } return bestval; } bool noOne (int player) { for (int i = 0; i < size; i++) if (board [i] == player) return false; return true; } int score (int player) { int s = 0; if (player == Left) { for (int i = 0; i < size; i++) if (board [i] == player) s += size - i; } else { for (int i = 0; i < size; i++) if (board [i] == player) s += i + 1; } return s; } int hash () { int h = 0; for (int i = 0; i < size; i++) h += board [i] * power3 [i]; return h; } }; Woodpush wood; int depth; bool printNew = false; void computePower () { power3 [0] = 1; for (int i = 1; i < MaxSize; i++) power3 [i] = 3 * power3 [i - 1]; } int nbThousands (int size, int * value) { int nb = 0; for (int i = 0; i < power3 [size]; i++) if (value [i] == Unknown) nb++; return nb; } void initSolve (int i, int size, int * value) { if (i == size) { int h = wood.hash (); value [h] = Unknown; value [power3 [size] + h] = Unknown; if (wood.noOne (Left)) { value [h] = -wood.score (Right); value [power3 [size] + h] = -wood.score (Right); } else if (wood.noOne (Right)) { value [h] = wood.score (Left); value [power3 [size] + h] = wood.score (Left); } return; } for (int c = 0; c < 3; c++) { wood.board [i] = c; initSolve (i + 1, size, value); } } bool iterateSolve (int color, int i, int size, int * value) { bool change = false; if (i == size) { int h = wood.hash (); wood.ko = -1; if (((color== Left) && (value [h] == Unknown)) || ((color== Right) && (value [power3 [size] + h] == Unknown))) { int bestval; if (color == Left) { bestval = -MaxScore; for (int i = 0; ((i < size) && (bestval < MaxScore)); i++) { if (wood.legal (i, Left)) { Woodpush w = wood; w.play (i, Left); int v = value [power3 [size] + w.hash ()]; if (v == Unknown) bestval = MaxScore; else if (v > bestval) bestval = v; } if (wood.legal (Delta + i, Left)) { Woodpush w = wood; w.play (Delta + i, Left); int v = value [power3 [size] + w.hash ()]; if (v == Unknown) bestval = MaxScore; else if (v > bestval) bestval = v; } } } else { // Right to play bestval = MaxScore; for (int i = 0; ((i < size) && (bestval > -MaxScore)); i++) { if (wood.legal (i, Right)) { Woodpush w = wood; w.play (i, Right); int v = value [w.hash ()]; if (v == Unknown) bestval = -MaxScore; else if (v < bestval) bestval = v; } if (wood.legal (Delta + i, Right)) { Woodpush w = wood; w.play (Delta + i, Right); int v = value [w.hash ()]; if (v == Unknown) bestval = -MaxScore; else if (v < bestval) bestval = v; } } } if ((bestval != MaxScore) && (bestval != -MaxScore)) { change = true; if (color == Left) value [h] = bestval; else value [power3 [size] + h] = bestval; if (printNew) { //if (true) { wood.print (); fprintf (stderr, "val = %d\n", bestval); } } } return change; } for (int c = 0; c < 3; c++) { wood.board [i] = c; if (iterateSolve (color, i + 1, size, value)) change = true; } return change; } bool iterateSolveKo (int color, int i, int size, int * value) { bool change = false; if (i == size) { int h = wood.hash (); wood.ko = -1; if (((color== Left) && (value [h] == Unknown)) || ((color== Right) && (value [power3 [size] + h] == Unknown))) { int bestval; if (color == Left) { bestval = -MaxScore; for (int i = 0; ((i < size) && (bestval < MaxScore)); i++) { if (wood.legal (i, Left)) { Woodpush w = wood; w.play (i, Left); int v = value [power3 [size] + w.hash ()]; if (v == Unknown) bestval = MaxScore; else if (v > bestval) bestval = v; } if (wood.legal (Delta + i, Left)) { // ne pas jouer le coups qui amenent a des positions qui ont un ko // car cela veut dire qu'on a pu arriver a la position courante // avec ce coup interdit par ko Woodpush w = wood; w.play (Delta + i, Left); int v = value [power3 [size] + w.hash ()]; //if (v == Unknown) v = w.bestValue (Right); if ((v == Unknown) || (v == -MaxScore)) bestval = MaxScore; else if (v > bestval) bestval = v; } } } else { // Right to play bestval = MaxScore; for (int i = 0; ((i < size) && (bestval > -MaxScore)); i++) { if (wood.legal (i, Right)) { Woodpush w = wood; w.play (i, Right); int v = value [w.hash ()]; if (v == Unknown) bestval = -MaxScore; else if (v < bestval) bestval = v; } if (wood.legal (Delta + i, Right)) { Woodpush w = wood; w.play (Delta + i, Right); int v = value [w.hash ()]; //if (v == Unknown) v = w.bestValue (Left); if ((v == Unknown) || (v == MaxScore)) bestval = -MaxScore; else if (v < bestval) bestval = v; } } } if ((bestval != MaxScore) && (bestval != -MaxScore)) { change = true; if (color == Left) value [h] = bestval; else value [power3 [size] + h] = bestval; if (printNew) { //if (true) { wood.print (); fprintf (stderr, "val = %d\n", bestval); } } } return change; } for (int c = 0; c < 3; c++) { wood.board [i] = c; if (iterateSolveKo (color, i + 1, size, value)) change = true; } return change; } void solve (int size, int * value) { int maxValue = power3 [size]; wood.init (size); /* for (int i = 0; i < maxValue; i++) */ /* value [i] = 0; */ initSolve (0, size, value); /* for (int i = 0; i < 2 * maxValue; i++) */ /* fprintf (stderr, "%d,", value [i]); */ /* fprintf (stderr, "\n"); */ depth = 1; bool change = true; printNew = false; while (change) { change = false; int nbUnknown = nbThousands (size, value); if (nbUnknown < 10) printNew = true; fprintf (stderr, "iterate Left, zeros = %d, depth = %d\n", nbUnknown , depth); //if (iterateSolve (Left, 0, size, value)) if (iterateSolveKo (Left, 0, size, value)) change = true; fprintf (stderr, "iterate Right\n"); //if (iterateSolve (Right, 0, size, value)) if (iterateSolveKo (Right, 0, size, value)) change = true; depth += 2; } /* for (int i = 0; i < 2 * maxValue; i++) */ /* fprintf (stderr, "%d,", value [i]); */ /* fprintf (stderr, "\n"); */ } void playGame (int human) { int currentPlayer = Left, computer, move; if (human == Left) computer = Right; else computer = Left; while (true) { if (currentPlayer == human) { bool legal = false; while (!legal) { wood.print (stderr); fprintf (stderr, "Enter Move: "); fscanf (stdin, "%d", &move); legal = wood.legal (move, currentPlayer); if (!legal) fprintf (stderr, "illegal\n"); } wood.play (move, currentPlayer); } else { wood.print (stderr); int best = wood.bestMove (currentPlayer); if (best != -1) wood.play (best, currentPlayer); } int next; if (currentPlayer == Left) next = Right; else next = Left; if (wood.noOne (currentPlayer)) { wood.print (stderr); fprintf (stderr, "game over, score = %d\n", wood.score (next)); break; } if (wood.noOne (next)) { wood.print (stderr); fprintf (stderr, "game over, score = %d\n", wood.score (currentPlayer)); break; } currentPlayer = next; } } bool addKoMove (int move, int *nb, int *moves) { int present = false; for (int i = 0; i < *nb; i++) if (moves [i] == move) present = true; if (!present) { if (*nb >= MaxKoMoves) fprintf (stderr, "MaxKoMoves = %d est trop petit\n", MaxKoMoves); else { moves [*nb] = move; *nb = *nb + 1; } } return !present; } void initNbKoMoves (int i, int size) { if (i == size) { for (int m = 0; m < size; m++) { if (wood.legal (m, Left)) { Woodpush w = wood; w.play (m, Left); int km = w.koMove (Right); int kh = w.hash (); if (km != -1) addKoMove (km, &nbKoMovesRight [kh], koMovesRight [kh]); } if (wood.legal (Delta + m, Left)) { Woodpush w = wood; w.play (Delta + m, Left); int km = w.koMove (Right); int kh = w.hash (); if (km != -1) addKoMove (km, &nbKoMovesRight [kh], koMovesRight [kh]); } if (wood.legal (m, Right)) { Woodpush w = wood; w.play (m, Right); int km = w.koMove (Left); int kh = w.hash (); if (km != -1) addKoMove (km, &nbKoMovesLeft [kh], koMovesLeft [kh]); } if (wood.legal (Delta + m, Right)) { Woodpush w = wood; w.play (Delta + m, Right); int km = w.koMove (Left); int kh = w.hash (); if (km != -1) addKoMove (km, &nbKoMovesLeft [kh], koMovesLeft [kh]); } } return; } for (int c = 0; c < 3; c++) { wood.board [i] = c; initNbKoMoves (i + 1, size); } } void initSolveKo (int i, int size) { if (i == size) { int h = wood.hash (); for (int n = 0; n <= nbKoMovesLeft [h]; n++) { valueLeft [h] [n] = Unknown; if (wood.noOne (Left)) { valueLeft [h] [n] = -wood.score (Right); } else if (wood.noOne (Right)) { valueLeft [h] [n] = wood.score (Left); } } for (int n = 0; n <= nbKoMovesRight [h]; n++) { valueRight [h] [n] = Unknown; if (wood.noOne (Left)) { valueRight [h] [n] = -wood.score (Right); } else if (wood.noOne (Right)) { valueRight [h] [n] = wood.score (Left); } } return; } for (int c = 0; c < 3; c++) { wood.board [i] = c; initSolveKo (i + 1, size); } } bool iterateSolveKoLeft (int i, int size) { bool change = false; if (i == size) { int h = wood.hash (); wood.ko = -1; /* if (h == 1356) { */ /* wood.print (); */ /* } */ for (int n = 0; n <= nbKoMovesLeft [h]; n++) if (valueLeft [h] [n] == Unknown) { int bestval = -MaxScore; for (int m = 0; ((m < size) && (bestval < MaxScore)); m++) { if (wood.legal (m, Left)) { if (n > 0) if (koMovesLeft [h] [n - 1] == m) continue; Woodpush w = wood; w.play (m, Left); int v = w.bestValueKo (Right); //v = valueRight [w.hash ()] [0]; v = wood.findValueLeftMoveKo (m); if ((v == Unknown) || (v == -MaxScore)) bestval = MaxScore; else if (v > bestval) bestval = v; } if (wood.legal (Delta + m, Left)) { if (n > 0) if (koMovesLeft [h] [n - 1] == Delta + m) continue; Woodpush w = wood; w.play (Delta + m, Left); int v = w.bestValueKo (Right); v = wood.findValueLeftMoveKo (Delta + m); if ((v == Unknown) || (v == -MaxScore)) bestval = MaxScore; else if (v > bestval) bestval = v; } } if (bestval != MaxScore) { change = true; valueLeft [h] [n] = bestval; if (printNew) { wood.print (); fprintf (stderr, "val = %d\n", bestval); } } } return change; } for (int c = 0; c < 3; c++) { wood.board [i] = c; if (iterateSolveKoLeft (i + 1, size)) change = true; } return change; } bool iterateSolveKoRight (int i, int size) { bool change = false; if (i == size) { int h = wood.hash (); /* if (h == 1882) { */ /* wood.ko = MaxScore; */ /* wood.print (); */ /* } */ wood.ko = -1; for (int n = 0; n <= nbKoMovesRight [h]; n++) if (valueRight [h] [n] == Unknown) { int bestval = MaxScore; for (int m = 0; ((m < size) && (bestval > -MaxScore)); m++) { if (wood.legal (m, Right)) { if (n > 0) if (koMovesRight [h] [n - 1] == m) continue; Woodpush w = wood; w.play (m, Right); int v = w.bestValueKo (Left); //v = valueLeft [w.hash ()] [0]; v = wood.findValueRightMoveKo (m); if ((v == Unknown) || (v == MaxScore)) bestval = -MaxScore; else if (v < bestval) bestval = v; } if (wood.legal (Delta + m, Right)) { if (n > 0) if (koMovesRight [h] [n - 1] == Delta + m) continue; Woodpush w = wood; w.play (Delta + m, Right); int v = w.bestValueKo (Left); v = wood.findValueRightMoveKo (Delta + m); if ((v == Unknown) || (v == MaxScore)) bestval = -MaxScore; else if (v < bestval) bestval = v; } } if (bestval != -MaxScore) { change = true; valueRight [h] [n] = bestval; if (printNew) { wood.print (); fprintf (stderr, "val = %d\n", bestval); } } } return change; } for (int c = 0; c < 3; c++) { wood.board [i] = c; if (iterateSolveKoRight (i + 1, size)) change = true; } return change; } bool iterateSolveKoLeftAvoidLoop (int i, int size) { bool change = false; if (i == size) { int h = wood.hash (); wood.ko = -1; /* if (h == 1868) { */ /* wood.print (); */ /* } */ for (int n = 0; n <= nbKoMovesLeft [h]; n++) if (valueLeft [h] [n] == Unknown) { //wood.print (); int bestval = -MaxScore; for (int m = 0; m < size; m++) { if (wood.legal (m, Left)) { if (n > 0) if (koMovesLeft [h] [n - 1] == m) continue; Woodpush w = wood; w.play (m, Left); int v = w.bestValueKo (Right); //int v = valueRight [w.hash ()] [0]; v = wood.findValueLeftMoveKo (m); if ((v == Unknown) || (v == -MaxScore)) ; else if (v > bestval) bestval = v; } if (wood.legal (Delta + m, Left)) { if (n > 0) if (koMovesLeft [h] [n - 1] == Delta + m) continue; Woodpush w = wood; w.play (Delta + m, Left); int v = w.bestValueKo (Right); //int v = valueRight [w.hash ()] [0]; v = wood.findValueLeftMoveKo (Delta + m); if ((v == Unknown) || (v == -MaxScore)) ; else if (v > bestval) bestval = v; } } if ((bestval != MaxScore) && (bestval != -MaxScore) && (bestval > 0)) { change = true; valueLeft [h] [n] = bestval; if (printNew) { wood.print (); fprintf (stderr, "val = %d\n", bestval); } } } return change; } for (int c = 0; c < 3; c++) { wood.board [i] = c; if (iterateSolveKoLeftAvoidLoop (i + 1, size)) change = true; } return change; } bool iterateSolveKoRightAvoidLoop (int i, int size) { bool change = false; if (i == size) { int h = wood.hash (); wood.ko = -1; for (int n = 0; n <= nbKoMovesRight [h]; n++) if (valueRight [h] [n] == Unknown) { int bestval = MaxScore; for (int m = 0; ((m < size) && (bestval > -MaxScore)); m++) { if (wood.legal (m, Right)) { if (n > 0) if (koMovesRight [h] [n - 1] == m) continue; Woodpush w = wood; w.play (m, Right); int v = w.bestValueKo (Left); //int v = valueLeft [w.hash ()] [0]; v = wood.findValueRightMoveKo (m); if ((v == Unknown) || (v == MaxScore)) ; else if (v < bestval) bestval = v; } if (wood.legal (Delta + m, Right)) { if (n > 0) if (koMovesRight [h] [n - 1] == Delta + m) continue; Woodpush w = wood; w.play (Delta + m, Right); int v = w.bestValueKo (Left); //int v = valueLeft [w.hash ()] [0]; v = wood.findValueRightMoveKo (Delta + m); if ((v == Unknown) || (v == MaxScore)) ; else if (v < bestval) bestval = v; } } if ((bestval != MaxScore) && (bestval != -MaxScore) && (bestval < 0)) { change = true; valueRight [h] [n] = bestval; if (printNew) { wood.print (); fprintf (stderr, "val = %d\n", bestval); } } } return change; } for (int c = 0; c < 3; c++) { wood.board [i] = c; if (iterateSolveKoRightAvoidLoop (i + 1, size)) change = true; } return change; } bool iterateSolveKoLeftAgain (int i, int size) { bool change = false; if (i == size) { int h = wood.hash (); wood.ko = -1; /* if (h == 1356) { */ /* wood.print (); */ /* } */ if (wood.noOne (Left) || wood.noOne (Right)) return change; for (int n = 0; n <= nbKoMovesLeft [h]; n++) { int previousScore = valueLeft [h] [n]; int bestval = -MaxScore; for (int m = 0; ((m < size) && (bestval < MaxScore)); m++) { if (wood.legal (m, Left)) { if (n > 0) if (koMovesLeft [h] [n - 1] == m) continue; int v = wood.findValueLeftMoveKo (m); if ((v == Unknown) || (v == -MaxScore)) bestval = MaxScore; else if (v > bestval) bestval = v; } if (wood.legal (Delta + m, Left)) { if (n > 0) if (koMovesLeft [h] [n - 1] == Delta + m) continue; int v = wood.findValueLeftMoveKo (Delta + m); if ((v == Unknown) || (v == -MaxScore)) bestval = MaxScore; else if (v > bestval) bestval = v; } } if ((bestval != previousScore) && (bestval != MaxScore)) { change = true; valueLeft [h] [n] = bestval; if (printNew) { wood.print (); fprintf (stderr, "val = %d\n", bestval); } } } return change; } for (int c = 0; c < 3; c++) { wood.board [i] = c; if (iterateSolveKoLeftAgain (i + 1, size)) change = true; } return change; } bool iterateSolveKoRightAgain (int i, int size) { bool change = false; if (i == size) { int h = wood.hash (); /* if (h == 1882) { */ /* wood.ko = MaxScore; */ /* wood.print (); */ /* } */ wood.ko = -1; if (wood.noOne (Left) || wood.noOne (Right)) return change; for (int n = 0; n <= nbKoMovesRight [h]; n++) { int previousScore = valueRight [h] [n]; int bestval = MaxScore; for (int m = 0; ((m < size) && (bestval > -MaxScore)); m++) { if (wood.legal (m, Right)) { if (n > 0) if (koMovesRight [h] [n - 1] == m) continue; int v = wood.findValueRightMoveKo (m); if ((v == Unknown) || (v == MaxScore)) bestval = -MaxScore; else if (v < bestval) bestval = v; } if (wood.legal (Delta + m, Right)) { if (n > 0) if (koMovesRight [h] [n - 1] == Delta + m) continue; int v = wood.findValueRightMoveKo (Delta + m); if ((v == Unknown) || (v == MaxScore)) bestval = -MaxScore; else if (v < bestval) bestval = v; } } if ((bestval != previousScore) && (bestval != -MaxScore)) { change = true; valueRight [h] [n] = bestval; if (printNew) { wood.print (); fprintf (stderr, "val = %d\n", bestval); } } } return change; } for (int c = 0; c < 3; c++) { wood.board [i] = c; if (iterateSolveKoRightAgain (i + 1, size)) change = true; } return change; } int nbUnknownLeft (int size) { int nb = 0; for (int h = 0; h < power3 [size]; h++) { for (int n = 0; n <= nbKoMovesLeft [h]; n++) if (valueLeft [h] [n] == Unknown) nb++; } return nb; } int setUnknownToZero (int size) { int nb = 0; for (int h = 0; h < power3 [size]; h++) { for (int n = 0; n <= nbKoMovesLeft [h]; n++) if (valueLeft [h] [n] == Unknown) valueLeft [h] [n] = 0; for (int n = 0; n <= nbKoMovesRight [h]; n++) if (valueRight [h] [n] == Unknown) valueRight [h] [n] = 0; } return nb; } int nbUnknownRight (int size) { int nb = 0; for (int h = 0; h < power3 [size]; h++) { for (int n = 0; n <= nbKoMovesRight [h]; n++) if (valueRight [h] [n] == Unknown) nb++; } return nb; } int nbPositionsLeft (int size) { int nb = 0; for (int h = 0; h < power3 [size]; h++) { nb += nbKoMovesLeft [h] + 1; } return nb; } void solveKo (int size) { int maxValue = power3 [size]; wood.init (size); for (int i = 0; i < MaxValue; i++) { nbKoMovesLeft [i] = 0; nbKoMovesRight [i] = 0; } initNbKoMoves (0, size); fprintf (stderr, "nbPositionsLeft = %d\n", nbPositionsLeft (size)); initSolveKo (0, size); depth = 1; bool change = true; printNew = false; while (change) { change = false; int nbUnknown = nbUnknownLeft (size); if (nbUnknown < 10) printNew = true; fprintf (stderr, "iterate Left, zeros = %d, depth = %d\n", nbUnknown , depth); if (iterateSolveKoLeft (0, size)) change = true; depth++; fprintf (stderr, "iterate Right, zeros = %d, depth = %d\n", nbUnknownRight (size) , depth); if (iterateSolveKoRight (0, size)) change = true; depth++; } } void playGameKo (int human) { int currentPlayer = Left, computer, move; if (human == Left) computer = Right; else computer = Left; while (true) { if (currentPlayer == human) { bool legal = false; while (!legal) { wood.print (stderr); fprintf (stderr, "Enter Move: "); fscanf (stdin, "%d", &move); legal = wood.legal (move, currentPlayer); if (!legal) fprintf (stderr, "illegal\n"); } wood.play (move, currentPlayer); } else { wood.print (stderr); int best = wood.bestMoveKo (currentPlayer); if (best != -1) wood.play (best, currentPlayer); } int next; if (currentPlayer == Left) next = Right; else next = Left; if (wood.noOne (currentPlayer)) { wood.print (stderr); fprintf (stderr, "game over, score = %d\n", wood.score (next)); break; } if (wood.noOne (next)) { wood.print (stderr); fprintf (stderr, "game over, score = %d\n", wood.score (currentPlayer)); break; } currentPlayer = next; } } int main () { computePower (); wood.init (7); solveKo (7); wood.init (7); playGameKo (Right); }