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];
69 typedef struct _loa_game {
76 board_group_size_recursive (board_t *board, int x, int y,
85 if (x >= BOARD_SIZE || y >= BOARD_SIZE)
88 bit = 1ll << (x * BOARD_SIZE + y);
94 if (board->cells[x][y] != cell)
98 board_group_size_recursive (board, x-1, y-1, cell, visited) +
99 board_group_size_recursive (board, x-1, y , cell, visited) +
100 board_group_size_recursive (board, x-1, y+1, cell, visited) +
101 board_group_size_recursive (board, x , y-1, cell, visited) +
102 board_group_size_recursive (board, x , y , cell, visited) +
103 board_group_size_recursive (board, x , y+1, cell, visited) +
104 board_group_size_recursive (board, x+1, y-1, cell, visited) +
105 board_group_size_recursive (board, x+1, y , cell, visited) +
106 board_group_size_recursive (board, x+1, y+1, cell, visited);
110 board_group_size (board_t *board, int x, int y)
112 uint64_t visited = 0ll;
113 cell_t cell = board->cells[x][y];
115 return board_group_size_recursive (board, x, y, cell, &visited);
119 board_is_won (board_t *board, int x, int y)
121 cell_t cell = board->cells[x][y];
123 if (cell == CELL_EMPTY)
126 if (board_group_size (board, x, y) == board->num_pieces[cell])
132 /* Given an (x,y) position on the board, return the index of the array
133 * used to count pieces in diagonal rows running from upper-left to
134 * lower-right, (like a grave accent: à or like a backslash: \).
136 * This is the array to look into when a move occurs with dx and dy of
139 _grave_index (int x, int y)
141 return x - y + BOARD_SIZE - 1;
144 /* Given an (x,y) position on the board, return the index of the array
145 * used to count pieces in diagonal rows running from lower-left to
146 * upper-right, (like an acute accent: á or like a forward slash: /).
148 * This is the array to look into when a move occurs with dx and dy of
149 * opposite sign, (one positive, one negative). */
151 _acute_index (int x, int y)
157 board_move_legal (board_t *board, int x1, int y1, int x2, int y2, char **error)
163 if (board->cells[x1][y1] == CELL_EMPTY) {
164 *error = "There is no piece there to move";
168 if (board->cells[x2][y2] == board->cells[x1][y1]) {
169 *error = "You cannot capture your own piece";
176 /* Here's the meat of Lines of Action legaility: Does the distance
177 * moved exactly match the number of pieces (of either color) in
178 * the row, column, or diagonal of the movement. */
181 if (abs (dy) != board->col_pieces[x1]) {
182 *error = "The move distance does not match the number of pieces in that column";
185 } else if (dy == 0) {
187 if (abs (dx) != board->row_pieces[y1]) {
188 *error = "The move distance does not match the number of pieces in that row";
192 if (abs (dx) != abs (dy)) {
193 *error = "That move is not in a row, column, or diagonal";
197 if ((dx > 0) == (dy > 0)) {
198 if (abs (dx) != board->diag_grave_pieces[_grave_index (x1, y1)]) {
199 *error = "The move distance does not match the number of pieces in that diagonal";
203 if (abs (dx) != board->diag_acute_pieces[_acute_index (x1, y1)]) {
204 *error = "The move distance does not match the number of pieces in that diagonal";
210 /* Finally, we have to ensure that no opponent pieces are being
212 step_x = dx ? ((dx < 0) ? -1 : +1) : 0;
213 step_y = dy ? ((dy < 0) ? -1 : +1) : 0;
214 for (x = x1 + step_x, y = y1 + step_y;
216 x += step_x, y += step_y)
218 if (board->cells[x][y] != CELL_EMPTY &&
219 board->cells[x][y] != board->cells[x1][y1])
221 *error = "You cannot jump an opponent's piece";
230 board_add_piece (board_t *board, int x, int y, cell_t cell)
232 assert (cell == CELL_BLACK || cell == CELL_WHITE);
233 assert (board->cells[x][y] == CELL_EMPTY);
235 board->col_pieces[x]++;
236 board->row_pieces[y]++;
237 board->diag_grave_pieces[_grave_index (x, y)]++;
238 board->diag_acute_pieces[_acute_index (x, y)]++;
240 board->num_pieces[cell]++;
242 board->cells[x][y] = cell;
246 board_remove_piece (board_t *board, int x, int y)
250 cell = board->cells[x][y];
252 if (cell == CELL_EMPTY)
255 board->col_pieces[x]--;
256 board->row_pieces[y]--;
257 board->diag_grave_pieces[_grave_index (x, y)]--;
258 board->diag_acute_pieces[_acute_index (x, y)]--;
260 board->num_pieces[cell]--;
262 board->cells[x][y] = CELL_EMPTY;
268 board_init (board_t *board)
272 for (x = 0; x < BOARD_SIZE; x++)
273 for (y = 0; y < BOARD_SIZE; y++)
274 board->cells[x][y] = CELL_EMPTY;
276 board->num_pieces[CELL_BLACK] = 0;
277 board->num_pieces[CELL_WHITE] = 0;
279 for (i = 0; i < BOARD_SIZE; i++) {
280 board->row_pieces[i] = 0;
281 board->col_pieces[i] = 0;
284 for (i = 0; i < DIAG_ARRAY_SIZE; i++) {
285 board->diag_grave_pieces[i] = 0;
286 board->diag_acute_pieces[i] = 0;
289 for (i = 1; i < BOARD_SIZE - 1; i++) {
290 board_add_piece (board, i, 0, CELL_BLACK);
291 board_add_piece (board, i, BOARD_SIZE - 1, CELL_BLACK);
292 board_add_piece (board, 0, i, CELL_WHITE);
293 board_add_piece (board, BOARD_SIZE - 1, i, CELL_WHITE);
297 /* A few different ideas for displaying boards:
299 * 8│ │●│●│●│●│●│●│ | 8| |*|*|*|*|*|*| |
300 * 7│○│ │ │ │ │ │ │○| 7|o| | | | | | |o|
301 * 6│○│ │ │ │ │ │ │○| 6|o| | | | | | |o|
302 * 5│○│ │ │ │ │ │ │○| 5|o| | | | | | |o|
303 * 4│○│ │ │ │ │ │ │○| 4|o| | | | | | |o|
304 * 3│○│ │ │ │ │ │ │○| 3|o| | | | | | |o|
305 * 2│○│ │ │ │ │ │ │○| 2|o| | | | | | |o|
306 * 1│ │●│●│●│●│●│●│ | 1| |*|*|*|*|*|*| |
307 * A B C D E F G H A B C D E F G H
309 * ┌───┬───┬───┬───┬───┬───┬───┬───┐ -------------------------------
310 * 8│ │ ● │ ● │ ● │ ● │ ● │ ● │ │ 8| | * | * | * | * | * | * | |
311 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
312 * 7│ ○ │ │ │ │ │ │ │ ○ │ 7| o | | | | | | | o |
313 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
314 * 6│ ○ │ │ │ │ │ │ │ ○ │ 6| o | | | | | | | o |
315 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
316 * 5│ ○ │ │ │ │ │ │ │ ○ │ 5| o | | | | | | | o |
317 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
318 * 4│ ○ │ │ │ │ │ │ │ ○ │ 4| o | | | | | | | o |
319 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
320 * 3│ ○ │ │ │ │ │ │ │ ○ │ 3| o | | | | | | | o |
321 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
322 * 2│ ○ │ │ │ │ │ │ │ ○ │ 2| o | | | | | | | o |
323 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
324 * 1│ │ ● │ ● │ ● │ ● │ ● │ ● │ │ 1| | * | * | * | * | * | * | |
325 * └───┴───┴───┴───┴───┴───┴───┴───┘ -------------------------------
326 * A B C D E F G H A B C D E F G H
329 board_to_string (board_t *board)
332 /* In order of BLACK, WHITE, EMPTY */
333 const char* cell_strings[] = {"●","○"," "};
334 const char board_header[] = "┌───┬───┬───┬───┬───┬───┬───┬───┐";
335 const char row_header[] = "│ ";
336 const char cell_separator[] = " │ ";
337 const char row_footer[] = " │";
338 const char row_separator[] = "├───┼───┼───┼───┼───┼───┼───┼───┤";
339 const char board_footer[] = "└───┴───┴───┴───┴───┴───┴───┴───┘";
340 char *board_string = g_strdup ("");
342 #define APPEND(str) do { \
343 char *_new = g_strconcat (board_string, (str), NULL); \
344 free (board_string); \
345 board_string = _new; \
348 #define APPENDF(format, ...) do { \
349 char *str = g_strdup_printf (format, ## __VA_ARGS__); \
354 APPENDF (" %s\n", board_header);
355 for (y = 0; y < BOARD_SIZE; y++) {
356 APPENDF ("%d%s", BOARD_SIZE - y, row_header);
357 for (x = 0; x < BOARD_SIZE; x++) {
358 APPENDF ("%s", cell_strings[board->cells[x][y]]);
359 if (x != BOARD_SIZE - 1)
360 APPENDF ("%s", cell_separator);
362 APPENDF ("%s\n", row_footer);
363 if (y != BOARD_SIZE -1)
364 APPENDF (" %s\n", row_separator);
366 APPENDF (" %s\n", board_footer);
369 for (x = 0; x < BOARD_SIZE; x++) {
370 APPENDF ("%c", 'A' + x);
371 if (x != BOARD_SIZE - 1)
380 loa_game_new_game (loa_game_t *game)
382 board_init (&game->board);
383 game->current = PLAYER_BLACK;
387 loa_game_next_player (loa_game_t *game)
389 if (game->current == PLAYER_BLACK)
390 game->current = PLAYER_WHITE;
392 game->current = PLAYER_BLACK;
396 loa_game_move (loa_game_t *game, const char * peer,
397 int x1, int y1, int x2, int y2)
399 board_t *board = &game->board;
403 if (x1 < 0 || y1 < 0 || x1 >= BOARD_SIZE || y1 >= BOARD_SIZE) {
404 loudgame_sendf (&game->lg, peer, "Invalid coordinates (not on board).");
408 if (board->cells[x1][y1] != game->current) {
409 loudgame_sendf (&game->lg, peer, "Cell at (%d,%d) does not belong to current player.",
414 if (! board_move_legal (&game->board, x1, y1, x2, y2, &error)) {
415 loudgame_sendf (&game->lg, peer, "Illegal move: %c%d%c%d",
416 'a' + x1, BOARD_SIZE - y1,
417 'a' + x2, BOARD_SIZE - y2);
421 cell = board_remove_piece (board, x1, y1);
422 board_remove_piece (board, x2, y2);
423 board_add_piece (board, x2, y2, cell);
425 loa_game_next_player (game);
431 loa_game_handle_show (loa_game_t *game,
435 LmMessageNode *html, *body, *span;
437 GError *error = NULL;
439 char *line, *newline;
441 reply = lm_message_new (peer, LM_MESSAGE_TYPE_MESSAGE);
442 html = lm_message_node_add_child (reply->node, "html", "");
443 lm_message_node_set_attribute (html,
445 "http://jabber.org/protocol/xhtml-im");
446 body = lm_message_node_add_child (html, "body", "");
447 lm_message_node_set_attribute (body,
449 "http://www.w3.org/1999/xhtml");
451 if (game->current == PLAYER_BLACK)
452 lm_message_node_add_child (body, "span", "Black to move:");
454 lm_message_node_add_child (body, "span", "White to move:");
456 board_string = board_to_string (&game->board);
460 newline = strchr (line, '\n');
463 lm_message_node_add_child (body, "br", "");
464 span = lm_message_node_add_child (body, "span", line);
465 lm_message_node_set_attribute (span, "style",
466 "font-family: Monospace;");
474 result = lm_connection_send (game->lg.connection, reply, &error);
475 lm_message_unref (reply);
478 g_error ("lm_connection_send failed: %s\n",
480 loudgame_quit (&game->lg, 1);
485 loa_game_handle_move (loa_game_t *game,
493 matched = sscanf (move, " %c %d %c %d ", &xc1, &y1, &xc2, &y2);
495 loudgame_sendf (&game->lg, peer,
496 "Error: The 'move' command requires a move of the form 'b1d3'");
500 x1 = tolower (xc1) - 'a';
501 x2 = tolower (xc2) - 'a';
502 /* We use an upper-left origin internally. */
503 y1 = BOARD_SIZE - y1;
504 y2 = BOARD_SIZE - y2;
505 if (! loa_game_move (game, peer, x1, y1, x2, y2))
508 loudgame_broadcastf (&game->lg, "%c%d%c%d",
509 'a' + x1, BOARD_SIZE - y1,
510 'a' + x2, BOARD_SIZE - y2);
512 if (board_is_won (&game->board, x2, y2))
513 loudgame_broadcastf (&game->lg, "%s wins", peer);
517 loa_game_handle_pass (loa_game_t *game, const char *peer)
519 loudgame_broadcastf (&game->lg, "%s passes", peer);
521 loa_game_next_player (game);
525 loa_game_handle_help (loa_game_t *game, const char *peer)
527 loudgame_sendf (&game->lg, peer,
528 "I'm a bot that allows you to play the game Lines of Action.\n"
529 "Here are some generic commands I understand:\n"
532 "And some game-specific commands:\n"
533 "\tshow \t\tShow the current board\n"
534 "\tmove aNbN\tMove a piece, (eg. 'move b1d3')\n"
535 "\tpass \t\tSkip a turn (only legal if no moves are possible)\n"
536 "\tnew \t\tBegin a new game\n"
537 "\thelp \t\tThis help message\n"
538 "\trules \t\tA description of the Lines of Action rules\n"
540 "Lines of Action was invented by Claude Soucie and first made popular\n"
541 "when its rules were published by Sid Sackson in \"A Gamut of Games\" (1969).\n"
543 "If you are new to Lines of Action, type 'rules' now to learn the rules.\n");
547 loa_game_handle_rules (loa_game_t *game, const char *peer)
549 loudgame_sendf (&game->lg, peer,
550 "Lines of Action can be played with a standard (English) checkers set,\n"
551 "that is an 8x8 board and 12 markers each of contrasting colors ('black' and\n"
552 "'white'). The initial placement has 6 each of the black pieces on the top\n"
553 "and bottom rows, and 6 each of the white pieces on the left and right columns\n"
554 "leaving the four corner spaces empty. Play begins with the black player and\n"
557 "On each move a piece is moved in a straight line in any of eight directions,\n"
558 "(similar to a queen's move in chess), but must be moved exactly the same\n"
559 "number of spaces as there are pieces (of either color) in the row, column,\n"
560 "or diagonal of the move. A piece may jump over pieces of its own color, but\n"
561 "may not jump a piece of the opposite color. The final square of the move can\n"
562 "be either empty or can contain a piece of the opposing color, in which case\n"
563 "that piece is removed from the game.\n"
565 "If a player has no possible move, then that player must pass, (but if the\n"
566 "player has a possible move, then the player cannot pass).\n"
568 "The goal of the game is to connect all of your remaining pieces into\n"
569 "a single, connected group. Pieces that are diagonally adjacent are\n"
570 "considered connected.\n"
572 "If a move simultaneously creates a winning condition for both players, this\n"
573 "is considered a win for the player making the move.\n"
575 "Notes on this implementation:\n"
577 "This implementation enforces the move rules described above, but will\n"
578 "allow any person to make moves, (that is, you can control both\n"
579 "colors). Think of it as being somewhat like a physical board where\n"
580 "any person could move the pieces at any time, but generally two people\n"
581 "will take turns and others will politely watch.\n"
583 "Also, the game won't currently show you the board again after a\n"
584 "player makes a move, so you'll need to keep typing 'show' to see\n"
585 "updates. Yes, this is a bug, and yes it will be fixed soon.\n"
587 "Lines of Action was invented by Claude Soucie and first made popular\n"
588 "when its rules were published by Sid Sackson in \"A Gamut of Games\" (1969).\n");
592 loa_game_handle_new (loa_game_t *game, const char *peer)
594 loudgame_broadcastf (&game->lg, "%s has started a new game", peer);
595 loa_game_new_game (game);
599 loa_game_handle_message (loudgame_t *lg,
603 loa_game_t *game = (loa_game_t *) lg;
605 if (strcmp (message, "show") == 0)
606 loa_game_handle_show (game, peer);
607 else if (strncmp (message, "move", 4) == 0)
608 loa_game_handle_move (game, peer, message + 4);
609 else if (strcmp (message, "pass") == 0)
610 loa_game_handle_pass (game, peer);
611 else if (strcmp (message, "new") == 0)
612 loa_game_handle_new (game, peer);
613 else if (strcmp (message, "help") == 0)
614 loa_game_handle_help (game, peer);
615 else if (strcmp (message, "rules") == 0)
616 loa_game_handle_rules (game, peer);
618 loudgame_sendf (lg, peer, "Unknown command: '%s'. Use 'help' to get a list of valid commands.", message);
622 loa_game_init (loa_game_t *game, int argc, char *argv[])
626 err = loudgame_init (&game->lg, argc, argv);
630 loa_game_new_game (game);
636 main (int argc, char **argv)
641 err = loa_game_init (&game, argc, argv);
645 game.lg.handle_message = loa_game_handle_message;
647 err = loudgame_run (&game.lg);