--- /dev/null
+/*
+ * Copyright (C) 2008 Carl Worth
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see http://www.gnu.org/licenses/ .
+ *
+ * Author: Carl Worth <cworth@cworth.org>
+ */
+
+#include "loudgame.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+
+#include <string.h>
+#include <ctype.h>
+#include <assert.h>
+
+typedef int loa_bool_t;
+
+#ifndef FALSE
+#define FALSE 0
+#endif
+#ifndef TRUE
+#define TRUE 1
+#endif
+
+typedef enum {
+ PLAYER_BLACK,
+ PLAYER_WHITE
+} player_t;
+
+typedef enum {
+ CELL_BLACK = PLAYER_BLACK,
+ CELL_WHITE = PLAYER_WHITE,
+ CELL_EMPTY
+} cell_t;
+
+/* The implementation of board_group_size depends on the square of
+ * BOARD_SIZE being less than or equal to 64. */
+#define BOARD_SIZE 8
+#define DIAG_ARRAY_SIZE (2 * BOARD_SIZE - 1)
+
+typedef struct {
+ cell_t cells[BOARD_SIZE][BOARD_SIZE];
+
+ /* Number of black and white pieces */
+ int num_pieces[2];
+
+ /* Number of pieces (of either color) in each row, column, and
+ * diagonal. */
+ int row_pieces[BOARD_SIZE];
+ int col_pieces[BOARD_SIZE];
+ int diag_grave_pieces[DIAG_ARRAY_SIZE];
+ int diag_acute_pieces[DIAG_ARRAY_SIZE];
+} board_t;
+
+typedef struct _loa_game {
+ loudgame_t lg;
+ board_t board;
+ player_t current;
+} loa_game_t;
+
+static int
+board_group_size_recursive (board_t *board, int x, int y,
+ cell_t cell,
+ uint64_t *visited)
+{
+ uint64_t bit;
+
+ if (x < 0 || y < 0)
+ return 0;
+
+ if (x >= BOARD_SIZE || y >= BOARD_SIZE)
+ return 0;
+
+ bit = 1ll << (x * BOARD_SIZE + y);
+ if (*visited & bit)
+ return 0;
+
+ *visited |= bit;
+
+ if (board->cells[x][y] != cell)
+ return 0;
+
+ return 1 +
+ board_group_size_recursive (board, x-1, y-1, cell, visited) +
+ board_group_size_recursive (board, x-1, y , cell, visited) +
+ board_group_size_recursive (board, x-1, y+1, cell, visited) +
+ board_group_size_recursive (board, x , y-1, cell, visited) +
+ board_group_size_recursive (board, x , y , cell, visited) +
+ board_group_size_recursive (board, x , y+1, cell, visited) +
+ board_group_size_recursive (board, x+1, y-1, cell, visited) +
+ board_group_size_recursive (board, x+1, y , cell, visited) +
+ board_group_size_recursive (board, x+1, y+1, cell, visited);
+}
+
+static int
+board_group_size (board_t *board, int x, int y)
+{
+ uint64_t visited = 0ll;
+ cell_t cell = board->cells[x][y];
+
+ return board_group_size_recursive (board, x, y, cell, &visited);
+}
+
+static int
+board_is_won (board_t *board, int x, int y)
+{
+ cell_t cell = board->cells[x][y];
+
+ if (cell == CELL_EMPTY)
+ return 0;
+
+ if (board_group_size (board, x, y) == board->num_pieces[cell])
+ return 1;
+
+ return 0;
+}
+
+/* Given an (x,y) position on the board, return the index of the array
+ * used to count pieces in diagonal rows running from upper-left to
+ * lower-right, (like a grave accent: à or like a backslash: \).
+ *
+ * This is the array to look into when a move occurs with dx and dy of
+ * the same sign. */
+static int
+_grave_index (int x, int y)
+{
+ return x - y + BOARD_SIZE - 1;
+}
+
+/* Given an (x,y) position on the board, return the index of the array
+ * used to count pieces in diagonal rows running from lower-left to
+ * upper-right, (like an acute accent: á or like a forward slash: /).
+ *
+ * This is the array to look into when a move occurs with dx and dy of
+ * opposite sign, (one positive, one negative). */
+static int
+_acute_index (int x, int y)
+{
+ return x + y;
+}
+
+static loa_bool_t
+board_move_legal (board_t *board, int x1, int y1, int x2, int y2, char **error)
+{
+ int x, y;
+ int dx, dy;
+ int step_x, step_y;
+
+ if (board->cells[x1][y1] == CELL_EMPTY) {
+ *error = "There is no piece there to move";
+ return FALSE;
+ }
+
+ if (board->cells[x2][y2] == board->cells[x1][y1]) {
+ *error = "You cannot capture your own piece";
+ return FALSE;
+ }
+
+ dx = x2 - x1;
+ dy = y2 - y1;
+
+ /* Here's the meat of Lines of Action legaility: Does the distance
+ * moved exactly match the number of pieces (of either color) in
+ * the row, column, or diagonal of the movement. */
+ if (dx == 0) {
+ /* Column */
+ if (abs (dy) != board->col_pieces[x1]) {
+ *error = "The move distance does not match the number of pieces in that column";
+ return FALSE;
+ }
+ } else if (dy == 0) {
+ /* Row */
+ if (abs (dx) != board->row_pieces[y1]) {
+ *error = "The move distance does not match the number of pieces in that row";
+ return FALSE;
+ }
+ } else {
+ if (abs (dx) != abs (dy)) {
+ *error = "That move is not in a row, column, or diagonal";
+ return FALSE;
+ }
+ /* Diagonal */
+ if ((dx > 0) == (dy > 0)) {
+ if (abs (dx) != board->diag_grave_pieces[_grave_index (x1, y1)]) {
+ *error = "The move distance does not match the number of pieces in that diagonal";
+ return FALSE;
+ }
+ } else {
+ if (abs (dx) != board->diag_acute_pieces[_acute_index (x1, y1)]) {
+ *error = "The move distance does not match the number of pieces in that diagonal";
+ return FALSE;
+ }
+ }
+ }
+
+ /* Finally, we have to ensure that no opponent pieces are being
+ * jumped. */
+ step_x = dx ? ((dx < 0) ? -1 : +1) : 0;
+ step_y = dy ? ((dy < 0) ? -1 : +1) : 0;
+ for (x = x1 + step_x, y = y1 + step_y;
+ x != x2 || y != y2;
+ x += step_x, y += step_y)
+ {
+ if (board->cells[x][y] != CELL_EMPTY &&
+ board->cells[x][y] != board->cells[x1][y1])
+ {
+ *error = "You cannot jump an opponent's piece";
+ return FALSE;
+ }
+ }
+
+ return TRUE;
+}
+
+static void
+board_add_piece (board_t *board, int x, int y, cell_t cell)
+{
+ assert (cell == CELL_BLACK || cell == CELL_WHITE);
+ assert (board->cells[x][y] == CELL_EMPTY);
+
+ board->col_pieces[x]++;
+ board->row_pieces[y]++;
+ board->diag_grave_pieces[_grave_index (x, y)]++;
+ board->diag_acute_pieces[_acute_index (x, y)]++;
+
+ board->num_pieces[cell]++;
+
+ board->cells[x][y] = cell;
+}
+
+static cell_t
+board_remove_piece (board_t *board, int x, int y)
+{
+ cell_t cell;
+
+ cell = board->cells[x][y];
+
+ if (cell == CELL_EMPTY)
+ return CELL_EMPTY;
+
+ board->col_pieces[x]--;
+ board->row_pieces[y]--;
+ board->diag_grave_pieces[_grave_index (x, y)]--;
+ board->diag_acute_pieces[_acute_index (x, y)]--;
+
+ board->num_pieces[cell]--;
+
+ board->cells[x][y] = CELL_EMPTY;
+
+ return cell;
+}
+
+static void
+board_init (board_t *board)
+{
+ int i, x, y;
+
+ for (x = 0; x < BOARD_SIZE; x++)
+ for (y = 0; y < BOARD_SIZE; y++)
+ board->cells[x][y] = CELL_EMPTY;
+
+ board->num_pieces[CELL_BLACK] = 0;
+ board->num_pieces[CELL_WHITE] = 0;
+
+ for (i = 0; i < BOARD_SIZE; i++) {
+ board->row_pieces[i] = 0;
+ board->col_pieces[i] = 0;
+ }
+
+ for (i = 0; i < DIAG_ARRAY_SIZE; i++) {
+ board->diag_grave_pieces[i] = 0;
+ board->diag_acute_pieces[i] = 0;
+ }
+
+ for (i = 1; i < BOARD_SIZE - 1; i++) {
+ board_add_piece (board, i, 0, CELL_BLACK);
+ board_add_piece (board, i, BOARD_SIZE - 1, CELL_BLACK);
+ board_add_piece (board, 0, i, CELL_WHITE);
+ board_add_piece (board, BOARD_SIZE - 1, i, CELL_WHITE);
+ }
+}
+
+/* A few different ideas for displaying boards:
+ *
+ * 8│ │●│●│●│●│●│●│ | 8| |*|*|*|*|*|*| |
+ * 7│○│ │ │ │ │ │ │○| 7|o| | | | | | |o|
+ * 6│○│ │ │ │ │ │ │○| 6|o| | | | | | |o|
+ * 5│○│ │ │ │ │ │ │○| 5|o| | | | | | |o|
+ * 4│○│ │ │ │ │ │ │○| 4|o| | | | | | |o|
+ * 3│○│ │ │ │ │ │ │○| 3|o| | | | | | |o|
+ * 2│○│ │ │ │ │ │ │○| 2|o| | | | | | |o|
+ * 1│ │●│●│●│●│●│●│ | 1| |*|*|*|*|*|*| |
+ * A B C D E F G H A B C D E F G H
+ *
+ * ┌───┬───┬───┬───┬───┬───┬───┬───┐ -------------------------------
+ * 8│ │ ● │ ● │ ● │ ● │ ● │ ● │ │ 8| | * | * | * | * | * | * | |
+ * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
+ * 7│ ○ │ │ │ │ │ │ │ ○ │ 7| o | | | | | | | o |
+ * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
+ * 6│ ○ │ │ │ │ │ │ │ ○ │ 6| o | | | | | | | o |
+ * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
+ * 5│ ○ │ │ │ │ │ │ │ ○ │ 5| o | | | | | | | o |
+ * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
+ * 4│ ○ │ │ │ │ │ │ │ ○ │ 4| o | | | | | | | o |
+ * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
+ * 3│ ○ │ │ │ │ │ │ │ ○ │ 3| o | | | | | | | o |
+ * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
+ * 2│ ○ │ │ │ │ │ │ │ ○ │ 2| o | | | | | | | o |
+ * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
+ * 1│ │ ● │ ● │ ● │ ● │ ● │ ● │ │ 1| | * | * | * | * | * | * | |
+ * └───┴───┴───┴───┴───┴───┴───┴───┘ -------------------------------
+ * A B C D E F G H A B C D E F G H
+ */
+static char *
+board_to_string (board_t *board)
+{
+ int x, y;
+ /* In order of BLACK, WHITE, EMPTY */
+ const char* cell_strings[] = {"●","○"," "};
+ const char board_header[] = "┌───┬───┬───┬───┬───┬───┬───┬───┐";
+ const char row_header[] = "│ ";
+ const char cell_separator[] = " │ ";
+ const char row_footer[] = " │";
+ const char row_separator[] = "├───┼───┼───┼───┼───┼───┼───┼───┤";
+ const char board_footer[] = "└───┴───┴───┴───┴───┴───┴───┴───┘";
+ char *board_string = g_strdup ("");
+
+#define APPEND(str) do { \
+ char *_new = g_strconcat (board_string, (str), NULL); \
+ free (board_string); \
+ board_string = _new; \
+} while (0)
+
+#define APPENDF(format, ...) do { \
+ char *str = g_strdup_printf (format, ## __VA_ARGS__); \
+ APPEND (str); \
+ free (str); \
+} while (0)
+
+ APPENDF (" %s\n", board_header);
+ for (y = 0; y < BOARD_SIZE; y++) {
+ APPENDF ("%d%s", BOARD_SIZE - y, row_header);
+ for (x = 0; x < BOARD_SIZE; x++) {
+ APPENDF ("%s", cell_strings[board->cells[x][y]]);
+ if (x != BOARD_SIZE - 1)
+ APPENDF ("%s", cell_separator);
+ }
+ APPENDF ("%s\n", row_footer);
+ if (y != BOARD_SIZE -1)
+ APPENDF (" %s\n", row_separator);
+ }
+ APPENDF (" %s\n", board_footer);
+
+ APPENDF (" ");
+ for (x = 0; x < BOARD_SIZE; x++) {
+ APPENDF ("%c", 'A' + x);
+ if (x != BOARD_SIZE - 1)
+ APPENDF (" ");
+ }
+ APPENDF ("\n");
+
+ return board_string;
+}
+
+static void
+loa_game_new_game (loa_game_t *game)
+{
+ board_init (&game->board);
+ game->current = PLAYER_BLACK;
+}
+
+static void
+loa_game_next_player (loa_game_t *game)
+{
+ if (game->current == PLAYER_BLACK)
+ game->current = PLAYER_WHITE;
+ else
+ game->current = PLAYER_BLACK;
+}
+
+static loa_bool_t
+loa_game_move (loa_game_t *game, const char * peer,
+ int x1, int y1, int x2, int y2)
+{
+ board_t *board = &game->board;
+ cell_t cell;
+ char *error;
+
+ if (x1 < 0 || y1 < 0 || x1 >= BOARD_SIZE || y1 >= BOARD_SIZE) {
+ loudgame_sendf (&game->lg, peer, "Invalid coordinates (not on board).");
+ return FALSE;
+ }
+
+ if (board->cells[x1][y1] != game->current) {
+ loudgame_sendf (&game->lg, peer, "Cell at (%d,%d) does not belong to current player.",
+ x1, y1);
+ return FALSE;
+ }
+
+ if (! board_move_legal (&game->board, x1, y1, x2, y2, &error)) {
+ loudgame_sendf (&game->lg, peer, "Illegal move: %s.");
+ return FALSE;
+ }
+
+ cell = board_remove_piece (board, x1, y1);
+ board_remove_piece (board, x2, y2);
+ board_add_piece (board, x2, y2, cell);
+
+ loa_game_next_player (game);
+
+ return TRUE;
+}
+
+static void
+loa_game_handle_show (loa_game_t *game,
+ const char *peer)
+{
+ LmMessage *reply;
+ LmMessageNode *html, *body, *span;
+ gboolean result;
+ GError *error = NULL;
+ char *board_string;
+ char *line, *newline;
+
+ reply = lm_message_new (peer, LM_MESSAGE_TYPE_MESSAGE);
+ html = lm_message_node_add_child (reply->node, "html", "");
+ lm_message_node_set_attribute (html,
+ "xmlns",
+ "http://jabber.org/protocol/xhtml-im");
+ body = lm_message_node_add_child (html, "body", "");
+ lm_message_node_set_attribute (body,
+ "xmlns",
+ "http://www.w3.org/1999/xhtml");
+
+ if (game->current == PLAYER_BLACK)
+ lm_message_node_add_child (body, "span", "Black to move:");
+ else
+ lm_message_node_add_child (body, "span", "White to move:");
+
+ board_string = board_to_string (&game->board);
+
+ line = board_string;
+ while (1) {
+ newline = strchr (line, '\n');
+ if (newline)
+ *newline = '\0';
+ lm_message_node_add_child (body, "br", "");
+ span = lm_message_node_add_child (body, "span", line);
+ lm_message_node_set_attribute (span, "style",
+ "font-family: Monospace;");
+ if (! newline)
+ break;
+ line = newline + 1;
+ }
+
+ free (board_string);
+
+ result = lm_connection_send (game->lg.connection, reply, &error);
+ lm_message_unref (reply);
+
+ if (! result) {
+ g_error ("lm_connection_send failed: %s\n",
+ error->message);
+ loudgame_quit (&game->lg, 1);
+ }
+}
+
+static void
+loa_game_handle_move (loa_game_t *game,
+ const char *peer,
+ const char *move)
+{
+ char xc1, xc2;
+ int x1, y1, x2, y2;
+ int matched;
+
+ matched = sscanf (move, " %c %d %c %d ", &xc1, &y1, &xc2, &y2);
+ if (matched != 4) {
+ loudgame_sendf (&game->lg, peer,
+ "Error: The 'move' command requires a move of the form 'b1d3'");
+ return;
+ }
+
+ x1 = tolower (xc1) - 'a';
+ x2 = tolower (xc2) - 'a';
+ /* We use an upper-left origin internally. */
+ y1 = BOARD_SIZE - y1;
+ y2 = BOARD_SIZE - y2;
+ if (! loa_game_move (game, peer, x1, y1, x2, y2))
+ return;
+
+ loudgame_broadcastf (&game->lg, "%c%d%c%d",
+ 'a' + x1, BOARD_SIZE - y1,
+ 'a' + x2, BOARD_SIZE - y2);
+
+ if (board_is_won (&game->board, x2, y2))
+ loudgame_broadcastf (&game->lg, "%s wins", peer);
+}
+
+static void
+loa_game_handle_pass (loa_game_t *game, const char *peer)
+{
+ loudgame_broadcastf (&game->lg, "%s passes", peer);
+
+ loa_game_next_player (game);
+}
+
+static void
+loa_game_handle_help (loa_game_t *game, const char *peer)
+{
+ loudgame_sendf (&game->lg, peer,
+ "I'm a bot that allows you to play the game Lines of Action.\n"
+ "Here are some commands I understand:\n"
+ "\tshow \t\tShow the current board\n"
+ "\tmove aNbN\tMove a piece, (eg. 'move b1d3')\n"
+ "\tpass \t\tSkip a turn (only legal if no moves are possible)\n"
+ "\tnew \t\tBegin a new game\n"
+ "\thelp \t\tThis help message\n"
+ "\trules \t\tA description of the Lines of Action rules\n"
+ "\n"
+ "Lines of Action was invented by Claude Soucie and first made popular\n"
+ "when its rules were published by Sid Sackson in \"A Gamut of Games\" (1969).\n"
+ "\n"
+ "If you are new to Lines of Action, type 'rules' now to learn the rules.\n");
+}
+
+static void
+loa_game_handle_rules (loa_game_t *game, const char *peer)
+{
+ loudgame_sendf (&game->lg, peer,
+ "Lines of Action can be played with a standard (English) checkers set,\n"
+ "that is an 8x8 board and 12 markers each of contrasting colors ('black' and\n"
+ "'white'). The initial placement has 6 each of the black pieces on the top\n"
+ "and bottom rows, and 6 each of the white pieces on the left and right columns\n"
+ "leaving the four corner spaces empty. Play begins with the black player and\n"
+ "then alternates.\n"
+ "\n"
+ "On each move a piece is moved in a straight line in any of eight directions,\n"
+ "(similar to a queen's move in chess), but must be moved exactly the same\n"
+ "number of spaces as there are pieces (of either color) in the row, column,\n"
+ "or diagonal of the move. A piece may jump over pieces of its own color, but\n"
+ "may not jump a piece of the opposite color. The final square of the move can\n"
+ "be either empty or can contain a piece of the opposing color, in which case\n"
+ "that piece is removed from the game.\n"
+ "\n"
+ "If a player has no possible move, then that player must pass, (but if the\n"
+ "player has a possible move, then the player cannot pass).\n"
+ "\n"
+ "The goal of the game is to connect all of your remaining pieces into\n"
+ "a single, connected group. Pieces that are diagonally adjacent are\n"
+ "considered connected.\n"
+ "\n"
+ "If a move simultaneously creates a winning condition for both players, this\n"
+ "is considered a win for the player making the move.\n"
+ "\n"
+ "Notes on this implementation:\n"
+ "\n"
+ "This implementation enforces the move rules described above, but will\n"
+ "allow any person to make moves, (that is, you can control both\n"
+ "colors). Think of it as being somewhat like a physical board where\n"
+ "any person could move the pieces at any time, but generally two people\n"
+ "will take turns and others will politely watch.\n"
+ "\n"
+ "Also, the game won't currently show you the board again after a\n"
+ "player makes a move, so you'll need to keep typing 'show' to see\n"
+ "updates. Yes, this is a bug, and yes it will be fixed soon.\n"
+ "\n"
+ "Lines of Action was invented by Claude Soucie and first made popular\n"
+ "when its rules were published by Sid Sackson in \"A Gamut of Games\" (1969).\n");
+}
+
+static void
+loa_game_handle_new (loa_game_t *game, const char *peer)
+{
+ loudgame_broadcastf (&game->lg, "%s has started a new game", peer);
+ loa_game_new_game (game);
+}
+
+static void
+loa_game_handle_message (loudgame_t *lg,
+ const char *peer,
+ const char *message)
+{
+ loa_game_t *game = (loa_game_t *) lg;
+
+ if (strcmp (message, "show") == 0)
+ loa_game_handle_show (game, peer);
+ else if (strncmp (message, "move", 4) == 0)
+ loa_game_handle_move (game, peer, message + 4);
+ else if (strcmp (message, "pass") == 0)
+ loa_game_handle_pass (game, peer);
+ else if (strcmp (message, "new") == 0)
+ loa_game_handle_new (game, peer);
+ else if (strcmp (message, "help") == 0)
+ loa_game_handle_help (game, peer);
+ else if (strcmp (message, "rules") == 0)
+ loa_game_handle_rules (game, peer);
+ else
+ loudgame_sendf (lg, peer, "Unknown command: '%s'. Use 'help' to get a list of valid commands.", message);
+}
+
+static int
+loa_game_init (loa_game_t *game, int argc, char *argv[])
+{
+ int err;
+
+ err = loudgame_init (&game->lg, argc, argv);
+ if (err)
+ return err;
+
+ loa_game_new_game (game);
+
+ return 0;
+}
+
+int
+main (int argc, char **argv)
+{
+ loa_game_t game;
+ int err;
+
+ err = loa_game_init (&game, argc, argv);
+ if (err)
+ return err;
+
+ game.lg.handle_message = loa_game_handle_message;
+
+ err = loudgame_run (&game.lg);
+ if (err)
+ return err;
+
+ return 0;
+}
projects / loudgame / commitdiff