2 * Copyright (C) 2008 Carl Worth
4 * This program is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation, either version 3 of the License, or
7 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program. If not, see http://www.gnu.org/licenses/ .
17 * Author: Carl Worth <cworth@cworth.org>
30 typedef int loa_bool_t;
45 CELL_BLACK = PLAYER_BLACK,
46 CELL_WHITE = PLAYER_WHITE,
50 /* The implementation of board_group_size depends on the square of
51 * BOARD_SIZE being less than or equal to 64. */
53 #define DIAG_ARRAY_SIZE (2 * BOARD_SIZE - 1)
56 cell_t cells[BOARD_SIZE][BOARD_SIZE];
58 /* Number of black and white pieces */
61 /* Number of pieces (of either color) in each row, column, and
63 int row_pieces[BOARD_SIZE];
64 int col_pieces[BOARD_SIZE];
65 int diag_grave_pieces[DIAG_ARRAY_SIZE];
66 int diag_acute_pieces[DIAG_ARRAY_SIZE];
71 typedef struct _loa_game {
77 board_next_player (board_t *board)
79 if (board->player == PLAYER_BLACK)
80 board->player = PLAYER_WHITE;
82 board->player = PLAYER_BLACK;
86 board_group_size_recursive (board_t *board, int x, int y,
95 if (x >= BOARD_SIZE || y >= BOARD_SIZE)
98 bit = 1ll << (x * BOARD_SIZE + y);
104 if (board->cells[x][y] != cell)
108 board_group_size_recursive (board, x-1, y-1, cell, visited) +
109 board_group_size_recursive (board, x-1, y , cell, visited) +
110 board_group_size_recursive (board, x-1, y+1, cell, visited) +
111 board_group_size_recursive (board, x , y-1, cell, visited) +
112 board_group_size_recursive (board, x , y , cell, visited) +
113 board_group_size_recursive (board, x , y+1, cell, visited) +
114 board_group_size_recursive (board, x+1, y-1, cell, visited) +
115 board_group_size_recursive (board, x+1, y , cell, visited) +
116 board_group_size_recursive (board, x+1, y+1, cell, visited);
120 board_group_size (board_t *board, int x, int y)
122 uint64_t visited = 0ll;
123 cell_t cell = board->cells[x][y];
125 return board_group_size_recursive (board, x, y, cell, &visited);
129 board_is_won (board_t *board, int x, int y)
131 cell_t cell = board->cells[x][y];
133 if (cell == CELL_EMPTY)
136 if (board_group_size (board, x, y) == board->num_pieces[cell])
142 /* Given an (x,y) position on the board, return the index of the array
143 * used to count pieces in diagonal rows running from upper-left to
144 * lower-right, (like a grave accent: à or like a backslash: \).
146 * This is the array to look into when a move occurs with dx and dy of
149 _grave_index (int x, int y)
151 return x - y + BOARD_SIZE - 1;
154 /* Given an (x,y) position on the board, return the index of the array
155 * used to count pieces in diagonal rows running from lower-left to
156 * upper-right, (like an acute accent: á or like a forward slash: /).
158 * This is the array to look into when a move occurs with dx and dy of
159 * opposite sign, (one positive, one negative). */
161 _acute_index (int x, int y)
167 board_move_legal (board_t *board, int x1, int y1, int x2, int y2, char **error)
173 if (board->cells[x1][y1] == CELL_EMPTY) {
174 *error = "There is no piece there to move";
178 if (board->cells[x2][y2] == board->cells[x1][y1]) {
179 *error = "You cannot capture your own piece";
186 /* Here's the meat of Lines of Action legaility: Does the distance
187 * moved exactly match the number of pieces (of either color) in
188 * the row, column, or diagonal of the movement. */
191 if (abs (dy) != board->col_pieces[x1]) {
192 *error = "The move distance does not match the number of pieces in that column";
195 } else if (dy == 0) {
197 if (abs (dx) != board->row_pieces[y1]) {
198 *error = "The move distance does not match the number of pieces in that row";
202 if (abs (dx) != abs (dy)) {
203 *error = "That move is not in a row, column, or diagonal";
207 if ((dx > 0) == (dy > 0)) {
208 if (abs (dx) != board->diag_grave_pieces[_grave_index (x1, y1)]) {
209 *error = "The move distance does not match the number of pieces in that diagonal";
213 if (abs (dx) != board->diag_acute_pieces[_acute_index (x1, y1)]) {
214 *error = "The move distance does not match the number of pieces in that diagonal";
220 /* Finally, we have to ensure that no opponent pieces are being
222 step_x = dx ? ((dx < 0) ? -1 : +1) : 0;
223 step_y = dy ? ((dy < 0) ? -1 : +1) : 0;
224 for (x = x1 + step_x, y = y1 + step_y;
226 x += step_x, y += step_y)
228 if (board->cells[x][y] != CELL_EMPTY &&
229 board->cells[x][y] != board->cells[x1][y1])
231 *error = "You cannot jump an opponent's piece";
240 board_add_piece (board_t *board, int x, int y, cell_t cell)
242 assert (cell == CELL_BLACK || cell == CELL_WHITE);
243 assert (board->cells[x][y] == CELL_EMPTY);
245 board->col_pieces[x]++;
246 board->row_pieces[y]++;
247 board->diag_grave_pieces[_grave_index (x, y)]++;
248 board->diag_acute_pieces[_acute_index (x, y)]++;
250 board->num_pieces[cell]++;
252 board->cells[x][y] = cell;
256 board_remove_piece (board_t *board, int x, int y)
260 cell = board->cells[x][y];
262 if (cell == CELL_EMPTY)
265 board->col_pieces[x]--;
266 board->row_pieces[y]--;
267 board->diag_grave_pieces[_grave_index (x, y)]--;
268 board->diag_acute_pieces[_acute_index (x, y)]--;
270 board->num_pieces[cell]--;
272 board->cells[x][y] = CELL_EMPTY;
278 board_init (board_t *board)
282 for (x = 0; x < BOARD_SIZE; x++)
283 for (y = 0; y < BOARD_SIZE; y++)
284 board->cells[x][y] = CELL_EMPTY;
286 board->num_pieces[CELL_BLACK] = 0;
287 board->num_pieces[CELL_WHITE] = 0;
289 for (i = 0; i < BOARD_SIZE; i++) {
290 board->row_pieces[i] = 0;
291 board->col_pieces[i] = 0;
294 for (i = 0; i < DIAG_ARRAY_SIZE; i++) {
295 board->diag_grave_pieces[i] = 0;
296 board->diag_acute_pieces[i] = 0;
299 for (i = 1; i < BOARD_SIZE - 1; i++) {
300 board_add_piece (board, i, 0, CELL_BLACK);
301 board_add_piece (board, i, BOARD_SIZE - 1, CELL_BLACK);
302 board_add_piece (board, 0, i, CELL_WHITE);
303 board_add_piece (board, BOARD_SIZE - 1, i, CELL_WHITE);
306 board->player = PLAYER_BLACK;
309 /* A few different ideas for displaying boards:
311 * 8│ │●│●│●│●│●│●│ | 8| |*|*|*|*|*|*| |
312 * 7│○│ │ │ │ │ │ │○| 7|o| | | | | | |o|
313 * 6│○│ │ │ │ │ │ │○| 6|o| | | | | | |o|
314 * 5│○│ │ │ │ │ │ │○| 5|o| | | | | | |o|
315 * 4│○│ │ │ │ │ │ │○| 4|o| | | | | | |o|
316 * 3│○│ │ │ │ │ │ │○| 3|o| | | | | | |o|
317 * 2│○│ │ │ │ │ │ │○| 2|o| | | | | | |o|
318 * 1│ │●│●│●│●│●│●│ | 1| |*|*|*|*|*|*| |
319 * A B C D E F G H A B C D E F G H
321 * ┌───┬───┬───┬───┬───┬───┬───┬───┐ -------------------------------
322 * 8│ │ ● │ ● │ ● │ ● │ ● │ ● │ │ 8| | * | * | * | * | * | * | |
323 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
324 * 7│ ○ │ │ │ │ │ │ │ ○ │ 7| o | | | | | | | o |
325 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
326 * 6│ ○ │ │ │ │ │ │ │ ○ │ 6| o | | | | | | | o |
327 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
328 * 5│ ○ │ │ │ │ │ │ │ ○ │ 5| o | | | | | | | o |
329 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
330 * 4│ ○ │ │ │ │ │ │ │ ○ │ 4| o | | | | | | | o |
331 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
332 * 3│ ○ │ │ │ │ │ │ │ ○ │ 3| o | | | | | | | o |
333 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
334 * 2│ ○ │ │ │ │ │ │ │ ○ │ 2| o | | | | | | | o |
335 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
336 * 1│ │ ● │ ● │ ● │ ● │ ● │ ● │ │ 1| | * | * | * | * | * | * | |
337 * └───┴───┴───┴───┴───┴───┴───┴───┘ -------------------------------
338 * A B C D E F G H A B C D E F G H
341 board_to_string (board_t *board)
344 /* In order of BLACK, WHITE, EMPTY */
345 const char* cell_strings[] = {"●","○"," "};
346 const char board_header[] = "┌───┬───┬───┬───┬───┬───┬───┬───┐";
347 const char row_header[] = "│ ";
348 const char cell_separator[] = " │ ";
349 const char row_footer[] = " │";
350 const char row_separator[] = "├───┼───┼───┼───┼───┼───┼───┼───┤";
351 const char board_footer[] = "└───┴───┴───┴───┴───┴───┴───┴───┘";
352 char *board_string = g_strdup ("");
354 #define APPEND(str) do { \
355 char *_new = g_strconcat (board_string, (str), NULL); \
356 free (board_string); \
357 board_string = _new; \
360 #define APPENDF(format, ...) do { \
361 char *str = g_strdup_printf (format, ## __VA_ARGS__); \
366 APPENDF (" %s\n", board_header);
367 for (y = 0; y < BOARD_SIZE; y++) {
368 APPENDF ("%d%s", BOARD_SIZE - y, row_header);
369 for (x = 0; x < BOARD_SIZE; x++) {
370 APPENDF ("%s", cell_strings[board->cells[x][y]]);
371 if (x != BOARD_SIZE - 1)
372 APPENDF ("%s", cell_separator);
374 APPENDF ("%s\n", row_footer);
375 if (y != BOARD_SIZE -1)
376 APPENDF (" %s\n", row_separator);
378 APPENDF (" %s\n", board_footer);
381 for (x = 0; x < BOARD_SIZE; x++) {
382 APPENDF ("%c", 'A' + x);
383 if (x != BOARD_SIZE - 1)
392 loa_game_new_game (loa_game_t *game)
394 board_init (&game->board);
398 loa_game_move (loa_game_t *game, const char * peer,
399 int x1, int y1, int x2, int y2)
401 board_t *board = &game->board;
405 if (x1 < 0 || y1 < 0 || x1 >= BOARD_SIZE || y1 >= BOARD_SIZE) {
406 loudgame_sendf (&game->lg, peer, "Invalid coordinates (not on board).");
410 if (board->cells[x1][y1] != board->player) {
411 loudgame_sendf (&game->lg, peer, "Cell at (%d,%d) does not belong to current player.",
416 if (! board_move_legal (&game->board, x1, y1, x2, y2, &error)) {
417 loudgame_sendf (&game->lg, peer, "Illegal move: %c%d%c%d",
418 'a' + x1, BOARD_SIZE - y1,
419 'a' + x2, BOARD_SIZE - y2);
423 cell = board_remove_piece (board, x1, y1);
424 board_remove_piece (board, x2, y2);
425 board_add_piece (board, x2, y2, cell);
427 board_next_player (board);
433 loa_game_handle_show (loa_game_t *game,
437 LmMessageNode *html, *body, *span;
439 GError *error = NULL;
441 char *line, *newline;
443 reply = lm_message_new (peer, LM_MESSAGE_TYPE_MESSAGE);
444 html = lm_message_node_add_child (reply->node, "html", "");
445 lm_message_node_set_attribute (html,
447 "http://jabber.org/protocol/xhtml-im");
448 body = lm_message_node_add_child (html, "body", "");
449 lm_message_node_set_attribute (body,
451 "http://www.w3.org/1999/xhtml");
453 if (game->board.player == PLAYER_BLACK)
454 lm_message_node_add_child (body, "span", "Black to move:");
456 lm_message_node_add_child (body, "span", "White to move:");
458 board_string = board_to_string (&game->board);
462 newline = strchr (line, '\n');
465 lm_message_node_add_child (body, "br", "");
466 span = lm_message_node_add_child (body, "span", line);
467 lm_message_node_set_attribute (span, "style",
468 "font-family: Monospace;");
476 result = lm_connection_send (game->lg.connection, reply, &error);
477 lm_message_unref (reply);
480 g_error ("lm_connection_send failed: %s\n",
482 loudgame_quit (&game->lg, 1);
487 loa_game_handle_move (loa_game_t *game,
495 matched = sscanf (move, " %c %d %c %d ", &xc1, &y1, &xc2, &y2);
497 loudgame_sendf (&game->lg, peer,
498 "Error: The 'move' command requires a move of the form 'b1d3'");
502 x1 = tolower (xc1) - 'a';
503 x2 = tolower (xc2) - 'a';
504 /* We use an upper-left origin internally. */
505 y1 = BOARD_SIZE - y1;
506 y2 = BOARD_SIZE - y2;
507 if (! loa_game_move (game, peer, x1, y1, x2, y2))
510 loudgame_broadcastf (&game->lg, "%c%d%c%d",
511 'a' + x1, BOARD_SIZE - y1,
512 'a' + x2, BOARD_SIZE - y2);
514 if (board_is_won (&game->board, x2, y2))
515 loudgame_broadcastf (&game->lg, "%s wins", peer);
519 loa_game_handle_pass (loa_game_t *game, const char *peer)
521 loudgame_broadcastf (&game->lg, "%s passes", peer);
523 board_next_player (&game->board);
527 loa_game_handle_help (loa_game_t *game, const char *peer)
529 loudgame_sendf (&game->lg, peer,
530 "I'm a bot that allows you to play the game Lines of Action.\n"
531 "Here are some generic commands I understand:\n"
534 "And some game-specific commands:\n"
535 "\tshow \t\tShow the current board\n"
536 "\tmove aNbN\tMove a piece, (eg. 'move b1d3')\n"
537 "\tpass \t\tSkip a turn (only legal if no moves are possible)\n"
538 "\tnew \t\tBegin a new game\n"
539 "\thelp \t\tThis help message\n"
540 "\trules \t\tA description of the Lines of Action rules\n"
542 "Lines of Action was invented by Claude Soucie and first made popular\n"
543 "when its rules were published by Sid Sackson in \"A Gamut of Games\" (1969).\n"
545 "If you are new to Lines of Action, type 'rules' now to learn the rules.\n");
549 loa_game_handle_rules (loa_game_t *game, const char *peer)
551 loudgame_sendf (&game->lg, peer,
552 "Lines of Action can be played with a standard (English) checkers set,\n"
553 "that is an 8x8 board and 12 markers each of contrasting colors ('black' and\n"
554 "'white'). The initial placement has 6 each of the black pieces on the top\n"
555 "and bottom rows, and 6 each of the white pieces on the left and right columns\n"
556 "leaving the four corner spaces empty. Play begins with the black player and\n"
559 "On each move a piece is moved in a straight line in any of eight directions,\n"
560 "(similar to a queen's move in chess), but must be moved exactly the same\n"
561 "number of spaces as there are pieces (of either color) in the row, column,\n"
562 "or diagonal of the move. A piece may jump over pieces of its own color, but\n"
563 "may not jump a piece of the opposite color. The final square of the move can\n"
564 "be either empty or can contain a piece of the opposing color, in which case\n"
565 "that piece is removed from the game.\n"
567 "If a player has no possible move, then that player must pass, (but if the\n"
568 "player has a possible move, then the player cannot pass).\n"
570 "The goal of the game is to connect all of your remaining pieces into\n"
571 "a single, connected group. Pieces that are diagonally adjacent are\n"
572 "considered connected.\n"
574 "If a move simultaneously creates a winning condition for both players, this\n"
575 "is considered a win for the player making the move.\n"
577 "Notes on this implementation:\n"
579 "This implementation enforces the move rules described above, but will\n"
580 "allow any person to make moves, (that is, you can control both\n"
581 "colors). Think of it as being somewhat like a physical board where\n"
582 "any person could move the pieces at any time, but generally two people\n"
583 "will take turns and others will politely watch.\n"
585 "Also, the game won't currently show you the board again after a\n"
586 "player makes a move, so you'll need to keep typing 'show' to see\n"
587 "updates. Yes, this is a bug, and yes it will be fixed soon.\n"
589 "Lines of Action was invented by Claude Soucie and first made popular\n"
590 "when its rules were published by Sid Sackson in \"A Gamut of Games\" (1969).\n");
594 loa_game_handle_new (loa_game_t *game, const char *peer)
596 loudgame_broadcastf (&game->lg, "%s has started a new game", peer);
597 loa_game_new_game (game);
601 loa_game_handle_message (loudgame_t *lg,
605 loa_game_t *game = (loa_game_t *) lg;
607 if (strcmp (message, "show") == 0)
608 loa_game_handle_show (game, peer);
609 else if (strncmp (message, "move", 4) == 0)
610 loa_game_handle_move (game, peer, message + 4);
611 else if (strcmp (message, "pass") == 0)
612 loa_game_handle_pass (game, peer);
613 else if (strcmp (message, "new") == 0)
614 loa_game_handle_new (game, peer);
615 else if (strcmp (message, "help") == 0)
616 loa_game_handle_help (game, peer);
617 else if (strcmp (message, "rules") == 0)
618 loa_game_handle_rules (game, peer);
620 loudgame_sendf (lg, peer, "Unknown command: '%s'. Use 'help' to get a list of valid commands.", message);
624 loa_game_init (loa_game_t *game, int argc, char *argv[])
628 err = loudgame_init (&game->lg, argc, argv);
632 loa_game_new_game (game);
638 main (int argc, char **argv)
643 err = loa_game_init (&game, argc, argv);
647 game.lg.handle_message = loa_game_handle_message;
649 err = loudgame_run (&game.lg);