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 loa_board_next_player (loa_board_t *board)
79 if (board->player == PLAYER_BLACK)
80 board->player = PLAYER_WHITE;
82 board->player = PLAYER_BLACK;
86 loa_board_group_size_recursive (loa_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 loa_board_group_size_recursive (board, x-1, y-1, cell, visited) +
109 loa_board_group_size_recursive (board, x-1, y , cell, visited) +
110 loa_board_group_size_recursive (board, x-1, y+1, cell, visited) +
111 loa_board_group_size_recursive (board, x , y-1, cell, visited) +
112 loa_board_group_size_recursive (board, x , y , cell, visited) +
113 loa_board_group_size_recursive (board, x , y+1, cell, visited) +
114 loa_board_group_size_recursive (board, x+1, y-1, cell, visited) +
115 loa_board_group_size_recursive (board, x+1, y , cell, visited) +
116 loa_board_group_size_recursive (board, x+1, y+1, cell, visited);
120 loa_board_group_size (loa_board_t *board, int x, int y)
122 uint64_t visited = 0ll;
123 cell_t cell = board->cells[x][y];
125 return loa_board_group_size_recursive (board, x, y, cell, &visited);
129 loa_board_is_won (loa_board_t *board, int x, int y)
131 cell_t cell = board->cells[x][y];
133 if (cell == CELL_EMPTY)
136 if (loa_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 loa_board_move_legal (loa_board_t *board,
176 if (board->cells[x1][y1] == CELL_EMPTY) {
177 *error = "There is no piece there to move";
181 if (board->cells[x2][y2] == board->cells[x1][y1]) {
182 *error = "You cannot capture your own piece";
189 /* Here's the meat of Lines of Action legaility: Does the distance
190 * moved exactly match the number of pieces (of either color) in
191 * the row, column, or diagonal of the movement. */
194 if (abs (dy) != board->col_pieces[x1]) {
195 *error = "The move distance does not match the number of pieces in that column";
198 } else if (dy == 0) {
200 if (abs (dx) != board->row_pieces[y1]) {
201 *error = "The move distance does not match the number of pieces in that row";
205 if (abs (dx) != abs (dy)) {
206 *error = "That move is not in a row, column, or diagonal";
210 if ((dx > 0) == (dy > 0)) {
211 if (abs (dx) != board->diag_grave_pieces[_grave_index (x1, y1)]) {
212 *error = "The move distance does not match the number of pieces in that diagonal";
216 if (abs (dx) != board->diag_acute_pieces[_acute_index (x1, y1)]) {
217 *error = "The move distance does not match the number of pieces in that diagonal";
223 /* Finally, we have to ensure that no opponent pieces are being
225 step_x = dx ? ((dx < 0) ? -1 : +1) : 0;
226 step_y = dy ? ((dy < 0) ? -1 : +1) : 0;
227 for (x = x1 + step_x, y = y1 + step_y;
229 x += step_x, y += step_y)
231 if (board->cells[x][y] != CELL_EMPTY &&
232 board->cells[x][y] != board->cells[x1][y1])
234 *error = "You cannot jump an opponent's piece";
243 loa_board_add_piece (loa_board_t *board, int x, int y, cell_t cell)
245 assert (cell == CELL_BLACK || cell == CELL_WHITE);
246 assert (board->cells[x][y] == CELL_EMPTY);
248 board->col_pieces[x]++;
249 board->row_pieces[y]++;
250 board->diag_grave_pieces[_grave_index (x, y)]++;
251 board->diag_acute_pieces[_acute_index (x, y)]++;
253 board->num_pieces[cell]++;
255 board->cells[x][y] = cell;
259 loa_board_remove_piece (loa_board_t *board, int x, int y)
263 cell = board->cells[x][y];
265 if (cell == CELL_EMPTY)
268 board->col_pieces[x]--;
269 board->row_pieces[y]--;
270 board->diag_grave_pieces[_grave_index (x, y)]--;
271 board->diag_acute_pieces[_acute_index (x, y)]--;
273 board->num_pieces[cell]--;
275 board->cells[x][y] = CELL_EMPTY;
281 loa_board_init (loa_board_t *board)
285 for (x = 0; x < BOARD_SIZE; x++)
286 for (y = 0; y < BOARD_SIZE; y++)
287 board->cells[x][y] = CELL_EMPTY;
289 board->num_pieces[CELL_BLACK] = 0;
290 board->num_pieces[CELL_WHITE] = 0;
292 for (i = 0; i < BOARD_SIZE; i++) {
293 board->row_pieces[i] = 0;
294 board->col_pieces[i] = 0;
297 for (i = 0; i < DIAG_ARRAY_SIZE; i++) {
298 board->diag_grave_pieces[i] = 0;
299 board->diag_acute_pieces[i] = 0;
302 for (i = 1; i < BOARD_SIZE - 1; i++) {
303 loa_board_add_piece (board, i, 0, CELL_BLACK);
304 loa_board_add_piece (board, i, BOARD_SIZE - 1, CELL_BLACK);
305 loa_board_add_piece (board, 0, i, CELL_WHITE);
306 loa_board_add_piece (board, BOARD_SIZE - 1, i, CELL_WHITE);
309 board->player = PLAYER_BLACK;
312 /* A few different ideas for displaying boards:
314 * 8│ │●│●│●│●│●│●│ | 8| |*|*|*|*|*|*| |
315 * 7│○│ │ │ │ │ │ │○| 7|o| | | | | | |o|
316 * 6│○│ │ │ │ │ │ │○| 6|o| | | | | | |o|
317 * 5│○│ │ │ │ │ │ │○| 5|o| | | | | | |o|
318 * 4│○│ │ │ │ │ │ │○| 4|o| | | | | | |o|
319 * 3│○│ │ │ │ │ │ │○| 3|o| | | | | | |o|
320 * 2│○│ │ │ │ │ │ │○| 2|o| | | | | | |o|
321 * 1│ │●│●│●│●│●│●│ | 1| |*|*|*|*|*|*| |
322 * A B C D E F G H A B C D E F G H
324 * ┌───┬───┬───┬───┬───┬───┬───┬───┐ -------------------------------
325 * 8│ │ ● │ ● │ ● │ ● │ ● │ ● │ │ 8| | * | * | * | * | * | * | |
326 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
327 * 7│ ○ │ │ │ │ │ │ │ ○ │ 7| o | | | | | | | o |
328 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
329 * 6│ ○ │ │ │ │ │ │ │ ○ │ 6| o | | | | | | | o |
330 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
331 * 5│ ○ │ │ │ │ │ │ │ ○ │ 5| o | | | | | | | o |
332 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
333 * 4│ ○ │ │ │ │ │ │ │ ○ │ 4| o | | | | | | | o |
334 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
335 * 3│ ○ │ │ │ │ │ │ │ ○ │ 3| o | | | | | | | o |
336 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
337 * 2│ ○ │ │ │ │ │ │ │ ○ │ 2| o | | | | | | | o |
338 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
339 * 1│ │ ● │ ● │ ● │ ● │ ● │ ● │ │ 1| | * | * | * | * | * | * | |
340 * └───┴───┴───┴───┴───┴───┴───┴───┘ -------------------------------
341 * A B C D E F G H A B C D E F G H
344 loa_board_to_string (loa_board_t *board)
347 /* In order of BLACK, WHITE, EMPTY */
348 const char* cell_strings[] = {"●","○"," "};
349 const char board_header[] = "┌───┬───┬───┬───┬───┬───┬───┬───┐";
350 const char row_header[] = "│ ";
351 const char cell_separator[] = " │ ";
352 const char row_footer[] = " │";
353 const char row_separator[] = "├───┼───┼───┼───┼───┼───┼───┼───┤";
354 const char board_footer[] = "└───┴───┴───┴───┴───┴───┴───┴───┘";
355 char *board_string = g_strdup ("");
357 #define APPEND(str) do { \
358 char *_new = g_strconcat (board_string, (str), NULL); \
359 free (board_string); \
360 board_string = _new; \
363 #define APPENDF(format, ...) do { \
364 char *str = g_strdup_printf (format, ## __VA_ARGS__); \
369 APPENDF (" %s\n", board_header);
370 for (y = 0; y < BOARD_SIZE; y++) {
371 APPENDF ("%d%s", BOARD_SIZE - y, row_header);
372 for (x = 0; x < BOARD_SIZE; x++) {
373 APPENDF ("%s", cell_strings[board->cells[x][y]]);
374 if (x != BOARD_SIZE - 1)
375 APPENDF ("%s", cell_separator);
377 APPENDF ("%s\n", row_footer);
378 if (y != BOARD_SIZE -1)
379 APPENDF (" %s\n", row_separator);
381 APPENDF (" %s\n", board_footer);
384 for (x = 0; x < BOARD_SIZE; x++) {
385 APPENDF ("%c", 'A' + x);
386 if (x != BOARD_SIZE - 1)
395 loa_game_new_game (loa_game_t *game)
397 loa_board_init (&game->board);
401 loa_game_move (loa_game_t *game, const char * peer,
402 int x1, int y1, int x2, int y2)
404 loa_board_t *board = &game->board;
408 if (x1 < 0 || y1 < 0 || x1 >= BOARD_SIZE || y1 >= BOARD_SIZE) {
409 loudgame_sendf (&game->lg, peer, "Invalid coordinates (not on board).");
413 if (board->cells[x1][y1] != board->player) {
414 loudgame_sendf (&game->lg, peer, "Cell at (%d,%d) does not belong to current player.",
419 if (! loa_board_move_legal (&game->board, x1, y1, x2, y2, &error)) {
420 loudgame_sendf (&game->lg, peer, "Illegal move: %c%d%c%d",
421 'a' + x1, BOARD_SIZE - y1,
422 'a' + x2, BOARD_SIZE - y2);
426 cell = loa_board_remove_piece (board, x1, y1);
427 loa_board_remove_piece (board, x2, y2);
428 loa_board_add_piece (board, x2, y2, cell);
430 loa_board_next_player (board);
436 loa_game_handle_show (loa_game_t *game,
440 LmMessageNode *html, *body, *span;
442 GError *error = NULL;
444 char *line, *newline;
446 reply = lm_message_new (peer, LM_MESSAGE_TYPE_MESSAGE);
447 html = lm_message_node_add_child (reply->node, "html", "");
448 lm_message_node_set_attribute (html,
450 "http://jabber.org/protocol/xhtml-im");
451 body = lm_message_node_add_child (html, "body", "");
452 lm_message_node_set_attribute (body,
454 "http://www.w3.org/1999/xhtml");
456 if (game->board.player == PLAYER_BLACK)
457 lm_message_node_add_child (body, "span", "Black to move:");
459 lm_message_node_add_child (body, "span", "White to move:");
461 board_string = loa_board_to_string (&game->board);
465 newline = strchr (line, '\n');
468 lm_message_node_add_child (body, "br", "");
469 span = lm_message_node_add_child (body, "span", line);
470 lm_message_node_set_attribute (span, "style",
471 "font-family: Monospace;");
479 result = lm_connection_send (game->lg.connection, reply, &error);
480 lm_message_unref (reply);
483 g_error ("lm_connection_send failed: %s\n",
485 loudgame_quit (&game->lg, 1);
490 loa_game_handle_move (loa_game_t *game,
498 matched = sscanf (move, " %c %d %c %d ", &xc1, &y1, &xc2, &y2);
500 loudgame_sendf (&game->lg, peer,
501 "Error: The 'move' command requires a move of the form 'b1d3'");
505 x1 = tolower (xc1) - 'a';
506 x2 = tolower (xc2) - 'a';
507 /* We use an upper-left origin internally. */
508 y1 = BOARD_SIZE - y1;
509 y2 = BOARD_SIZE - y2;
510 if (! loa_game_move (game, peer, x1, y1, x2, y2))
513 loudgame_broadcastf (&game->lg, "%c%d%c%d",
514 'a' + x1, BOARD_SIZE - y1,
515 'a' + x2, BOARD_SIZE - y2);
517 if (loa_board_is_won (&game->board, x2, y2))
518 loudgame_broadcastf (&game->lg, "%s wins", peer);
522 loa_game_handle_pass (loa_game_t *game, const char *peer)
524 loudgame_broadcastf (&game->lg, "%s passes", peer);
526 loa_board_next_player (&game->board);
530 loa_game_handle_help (loa_game_t *game, const char *peer)
532 loudgame_sendf (&game->lg, peer,
533 "I'm a bot that allows you to play the game Lines of Action.\n"
534 "Here are some generic commands I understand:\n"
537 "And some game-specific commands:\n"
538 "\tshow \t\tShow the current board\n"
539 "\tmove aNbN\tMove a piece, (eg. 'move b1d3')\n"
540 "\tpass \t\tSkip a turn (only legal if no moves are possible)\n"
541 "\tnew \t\tBegin a new game\n"
542 "\thelp \t\tThis help message\n"
543 "\trules \t\tA description of the Lines of Action rules\n"
545 "Lines of Action was invented by Claude Soucie and first made popular\n"
546 "when its rules were published by Sid Sackson in \"A Gamut of Games\" (1969).\n"
548 "If you are new to Lines of Action, type 'rules' now to learn the rules.\n");
552 loa_game_handle_rules (loa_game_t *game, const char *peer)
554 loudgame_sendf (&game->lg, peer,
555 "Lines of Action can be played with a standard (English) checkers set,\n"
556 "that is an 8x8 board and 12 markers each of contrasting colors ('black' and\n"
557 "'white'). The initial placement has 6 each of the black pieces on the top\n"
558 "and bottom rows, and 6 each of the white pieces on the left and right columns\n"
559 "leaving the four corner spaces empty. Play begins with the black player and\n"
562 "On each move a piece is moved in a straight line in any of eight directions,\n"
563 "(similar to a queen's move in chess), but must be moved exactly the same\n"
564 "number of spaces as there are pieces (of either color) in the row, column,\n"
565 "or diagonal of the move. A piece may jump over pieces of its own color, but\n"
566 "may not jump a piece of the opposite color. The final square of the move can\n"
567 "be either empty or can contain a piece of the opposing color, in which case\n"
568 "that piece is removed from the game.\n"
570 "If a player has no possible move, then that player must pass, (but if the\n"
571 "player has a possible move, then the player cannot pass).\n"
573 "The goal of the game is to connect all of your remaining pieces into\n"
574 "a single, connected group. Pieces that are diagonally adjacent are\n"
575 "considered connected.\n"
577 "If a move simultaneously creates a winning condition for both players, this\n"
578 "is considered a win for the player making the move.\n"
580 "Notes on this implementation:\n"
582 "This implementation enforces the move rules described above, but will\n"
583 "allow any person to make moves, (that is, you can control both\n"
584 "colors). Think of it as being somewhat like a physical board where\n"
585 "any person could move the pieces at any time, but generally two people\n"
586 "will take turns and others will politely watch.\n"
588 "Also, the game won't currently show you the board again after a\n"
589 "player makes a move, so you'll need to keep typing 'show' to see\n"
590 "updates. Yes, this is a bug, and yes it will be fixed soon.\n"
592 "Lines of Action was invented by Claude Soucie and first made popular\n"
593 "when its rules were published by Sid Sackson in \"A Gamut of Games\" (1969).\n");
597 loa_game_handle_new (loa_game_t *game, const char *peer)
599 loudgame_broadcastf (&game->lg, "%s has started a new game", peer);
600 loa_game_new_game (game);
604 loa_game_handle_message (loudgame_t *lg,
608 loa_game_t *game = (loa_game_t *) lg;
610 if (strcmp (message, "show") == 0)
611 loa_game_handle_show (game, peer);
612 else if (strncmp (message, "move", 4) == 0)
613 loa_game_handle_move (game, peer, message + 4);
614 else if (strcmp (message, "pass") == 0)
615 loa_game_handle_pass (game, peer);
616 else if (strcmp (message, "new") == 0)
617 loa_game_handle_new (game, peer);
618 else if (strcmp (message, "help") == 0)
619 loa_game_handle_help (game, peer);
620 else if (strcmp (message, "rules") == 0)
621 loa_game_handle_rules (game, peer);
623 loudgame_sendf (lg, peer, "Unknown command: '%s'. Use 'help' to get a list of valid commands.", message);
627 loa_game_init (loa_game_t *game, int argc, char *argv[])
631 err = loudgame_init (&game->lg, argc, argv);
635 loa_game_new_game (game);
641 main (int argc, char **argv)
646 err = loa_game_init (&game, argc, argv);
650 game.lg.handle_message = loa_game_handle_message;
652 err = loudgame_run (&game.lg);