codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
// dmd 2.054, dmd -O -release -inline import core.stdc.stdio, std.conv, std.typetuple; enum int WIDTH = 7; enum int HEIGHT = 6; enum int ORANGE_WINS = 1_000_000; enum int YELLOW_WINS = -ORANGE_WINS; int g_maxDepth = 7; bool g_debug = false; // manual optimization for missing DMD loop unwinding template Range(int stop) { static if (stop <= 0) alias TypeTuple!() Range; else alias TypeTuple!(Range!(stop-1), stop-1) Range; } enum MyCell : int { Barren = 0, Orange = 1, Yellow = -1 } alias MyCell[WIDTH][HEIGHT] Board; bool isInside(in int y, in int x) pure nothrow { return y >= 0 && y < HEIGHT && x >= 0 && x < WIDTH; } int scoreBoard(const ref Board board) nothrow { int[9] counters; // Horizontal spans foreach (y; 0 .. HEIGHT) { int score = board[y][0] + board[y][1] + board[y][2]; foreach (x; 3 .. WIDTH) { assert(isInside(y, x)); score += board[y][x]; counters[score + 4]++; assert(isInside(y, x - 3)); score -= board[y][x - 3]; } } // Vertical spans foreach (x; 0 .. WIDTH) { int score = board[0][x] + board[1][x] + board[2][x]; foreach (y; 3 .. HEIGHT) { assert(isInside(y, x)); score += board[y][x]; counters[score + 4]++; assert(isInside(y - 3, x)); score -= board[y - 3][x]; } } // Down-right (and up-left) diagonals foreach (y; 0 .. HEIGHT - 3) { foreach (x; Range!(WIDTH - 3)) { int score = 0; foreach (idx; Range!4) { const int yy = y + idx; const int xx = x + idx; assert(isInside(yy, xx)); score += board[yy][xx]; } counters[score + 4]++; } } // up-right (and down-left) diagonals foreach (y; 3 .. HEIGHT) { foreach (x; Range!(WIDTH - 3)) { int score = 0; foreach (idx; Range!4) { const int yy = y - idx; const int xx = x + idx; assert(isInside(yy, xx)); score += board[yy][xx]; } counters[score + 4]++; } } if (counters[0] != 0) return YELLOW_WINS; else if (counters[8] != 0) return ORANGE_WINS; else return counters[5] + 2 * counters[6] + 5 * counters[7] + 10 * counters[8] - counters[3] - 2 * counters[2] - 5 * counters[1] - 10 * counters[0]; } int dropDisk(ref Board board, in int column, in MyCell color) pure nothrow { foreach_reverse (y; 0 .. HEIGHT) if (board[y][column] == MyCell.Barren) { board[y][column] = color; return y; } return -1; } Board loadBoard(in string[] args) { Board newBoard; foreach (i, arg; args[1 .. $]) { if (arg[0] == 'o' || arg[0] == 'y') newBoard[arg[1] - '0'][arg[2] - '0'] = (arg[0] == 'o') ? MyCell.Orange : MyCell.Yellow; else if (arg == "-debug") g_debug = true; else if (arg == "-level" && i < (args.length - 2)) g_maxDepth = to!int(args[i + 2]); } return newBoard; } void abMinimax(in bool maximizeOrMinimize, in MyCell color, in int depth, ref Board board, ref int move, ref int score) { if (depth == 0) { move = -1; score = scoreBoard(board); } else { int bestScore = maximizeOrMinimize ? -10_000_000 : 10_000_000; int bestMove = -1; foreach (column; Range!WIDTH) { if (board[0][column] != MyCell.Barren) continue; int rowFilled = dropDisk(board, column, color); if (rowFilled == -1) continue; int s = scoreBoard(board); if (s == (maximizeOrMinimize ? ORANGE_WINS : YELLOW_WINS)) { bestMove = column; bestScore = s; board[rowFilled][column] = MyCell.Barren; break; } int moveInner, scoreInner; abMinimax(!maximizeOrMinimize, color == MyCell.Orange ? MyCell.Yellow : MyCell.Orange, depth - 1, board, moveInner, scoreInner); board[rowFilled][column] = MyCell.Barren; if (depth == g_maxDepth && g_debug) printf("Depth %d, placing on %d, score:%d\n", depth, column, scoreInner); if (maximizeOrMinimize) { if (scoreInner >= bestScore) { bestScore = scoreInner; bestMove = column; } } else { if (scoreInner <= bestScore) { bestScore = scoreInner; bestMove = column; } } } move = bestMove; score = bestScore; } } int main(string[] args) { Board board = loadBoard(args); int scoreOrig = scoreBoard(board); if (scoreOrig == ORANGE_WINS) { puts("I win."); return -1; } else if (scoreOrig == YELLOW_WINS) { puts("You win."); return -1; } else { int move, score; abMinimax(true, MyCell.Orange, g_maxDepth, board, move, score); if (move != -1) { printf("%d\n", move); dropDisk(board, move, MyCell.Orange); scoreOrig = scoreBoard(board); if (scoreOrig == ORANGE_WINS) { puts("I win."); return -1; } else if (scoreOrig == YELLOW_WINS) { puts("You win."); return -1; } else return 0; } else { puts("No move possible."); return -1; } } }
Private
[
?
]
Run code
Submit