Add connect-3 demo app

"connect 3" in a 3x4 grid. Slightly more interesting than tic-tac-toe

Signed-off-by: Keith Packard <keithp@keithp.com>

1 files changed, 585 insertions, 0 deletions

diff --git a/examples/connect-3.5c b/examples/connect-3.5c
new file mode 100644
index 0000000..ce607c8
--- /dev/null
+++ b/examples/connect-3.5c
@@ -0,0 +1,585 @@
+/*
+ * Copyright © 2012 Keith Packard
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ *
+ * The Original Code is the cairo graphics library.
+ *
+ * The Initial Developer of the Original Code is Keith Packard
+ *
+ * Contributor(s):
+ *      Keith Packard <keithp@keithp.com>
+ */
+
+/*
+ * Connect-3 in a 3x4 grid
+ */
+
+autoload Mutex;
+autoimport Cairo;
+autoimport PRNG;
+autoimport Nichrome;
+autoload Nichrome::Button;
+autoload Nichrome::Label;
+autoload Nichrome::Box;
+
+import Widget;
+import Nichrome;
+import Button;
+import Button;
+import Box;
+import Label;
+
+dev_srandom (32);
+
+typedef int piece_t;
+
+piece_t piece__ = 0;
+piece_t piece_x = 1;
+piece_t piece_o = 2;
+
+int cols = 3;
+int rows = 4;
+int row = min(cols,rows);
+
+typedef piece_t[rows, cols] board_t;
+
+typedef struct {
+    int x, y;
+} position_t;
+
+/*
+ * Encode the current game state, which is
+ * either 'in progress' or 'player foo has
+ * won with pieces from p1 to p2'
+ */
+typedef union {
+    void    playing;
+    struct {
+	piece_t	    winner;
+	position_t  p1, p2;
+    } finished;
+} status_t;
+
+typedef status_t game_status_t;
+/*
+ * Game state
+ */
+typedef struct {
+    mutex	    lock;
+    bool	    quiting;
+    semaphore	    waiter;
+    board_t	    board;
+    status_t	    status;
+    piece_t	    turn;
+    piece_t	    computer;
+} game_t;
+
+void
+set_color (cairo_t cr, piece_t piece)
+{
+    switch (piece) {
+    case piece_x:
+	set_source_rgba (cr, 1, 0, 0, 1);
+	break;
+    case piece_o:
+	set_source_rgba (cr, 0, 0, 1, 1);
+	break;
+    case piece__:
+	break;
+    }
+}
+
+/*
+ * Set up cr to draw the game board
+ */
+void
+scale_board (cairo_t cr)
+{
+    scale (cr, Cairo::width (cr), Cairo::height (cr));
+}
+
+void
+draw_grid (cairo_t cr)
+{
+    set_source_rgba (cr, 0, 0, 0, 1);
+    for (int line = 0; line < cols - 1; line++)
+    {
+	move_to (cr, (line + 1) / cols, .05);
+	line_to (cr, (line + 1) / cols, rows/cols - .05);
+    }
+    for (int line = 0; line < rows - 1; line++)
+    {    
+	move_to (cr, .05, (line + 1) / rows * rows/cols);
+	line_to (cr, .95, (line + 1) / rows * rows/cols);
+    }
+    stroke (cr);
+}
+
+void
+draw_piece (cairo_t cr, piece_t piece)
+{
+    new_path (cr);
+    set_line_width (cr, 0.2);
+    set_line_cap (cr, line_cap_t.ROUND);
+    switch (piece) {
+    case piece__:
+	return;
+    case piece_x:
+	move_to (cr, -.4, -.4);
+	line_to (cr, .4, .4);
+	move_to (cr, .4, -.4);
+	line_to (cr, -.4, .4);
+	break;
+    case piece_o:
+	arc (cr, 0, 0, 0.4, 0, 2 * pi);
+	break;
+    }
+    set_color (cr, piece);
+    stroke (cr);
+}
+
+/*
+ * Draw the whole board
+ */
+void
+draw_pieces (cairo_t cr, &board_t board)
+{
+    for (int y = 0; y < rows; y++)
+	 for (int x = 0; x < cols; x++)
+	 {
+	    save (cr);
+	    translate (cr, (x + 1/2) / cols, (y + 1/2) / rows * rows/cols);
+	    scale (cr, 1/(cols * 4/3), 1/(rows * 4/3) * rows/cols);
+	    draw_piece (cr, board[y,x]);
+	    restore (cr);
+	 }
+}
+
+/*
+ * Draw a line through the three winning pieces
+ */
+void
+draw_win_line (cairo_t cr, &status_t status)
+{
+    union switch (status) {
+    case finished f:
+	if (f.winner == piece__)
+	    break;
+	set_color (cr, f.winner);
+	real x1, x2, y1, y2;
+	if (f.p1.x == f.p2.x)
+	    x2 = x1 = (f.p1.x + .5) / cols;
+	else {
+	    if (f.p1.x < f.p2.x) {
+		x1 = f.p1.x / cols + 0.05;
+		x2 = (f.p2.x + 1) / cols - 0.05;
+	    } else {
+		x1 = (f.p1.x + 1) / cols - 0.05;
+		x2 = f.p2.x / cols + 0.05;
+	    }
+	}
+	if (f.p1.y == f.p2.y)
+	    y2 = y1 = (f.p1.y + .5) / rows;
+	else {
+	    y1 = f.p1.y / rows + 0.05;
+	    y2 = (f.p2.y + 1) / rows - 0.05;
+	}
+	move_to (cr, x1, y1 * rows/cols);
+	line_to (cr, x2, y2 * rows/cols);
+	stroke (cr);
+	break;
+    case playing:
+	break;
+    }
+}
+
+/*
+ * Figure out the current game status
+ */
+status_t get_status (&board_t board)
+{
+    position_t	p1, p2;
+    
+    bool in_a_row (piece_t piece, position_t p, position_t d) {
+	p1 = p;
+	for (int i = 0; i < row; i++) {
+	    if (board[p.y,p.x] != piece)
+		return false;
+	    p2 = p;
+	    p.x += d.x;
+	    p.y += d.y;
+	}
+	return true;
+    }
+    
+    static piece_t[*] pieces = { piece_x, piece_o };
+    
+    status_t make_winner (piece_t piece) {
+	return (status_t) { finished = { winner = piece, p1 = p1, p2 = p2 } };
+    }
+
+    position_t make_pos (x, y) = (position_t) { x = x, y = y };
+    
+    for (int p = 0; p < dim (pieces); p++) {
+	piece_t piece = pieces[p];
+	for (int x = 0; x < cols; x++) {
+	    for (int y = 0; y <= rows - row; y++) {
+		if (in_a_row (piece, make_pos (x, y), make_pos (0, 1)))
+		    return make_winner (piece);
+	    }
+	}
+	for (int y = 0; y < rows; y++) {
+	    for (int x = 0; x <= cols - row; x++) {
+		if (in_a_row (piece, make_pos (x, y), make_pos (1, 0)))
+		    return make_winner (piece);
+	    }
+	}
+	for (int y = 0; y <= rows - row; y++) {
+	    for (int x = 0; x <= cols - row; x++) {
+		if (in_a_row (piece, make_pos (x, y), make_pos (1, 1)))
+		    return make_winner (piece);
+		if (in_a_row (piece, make_pos (x + row - 1, y), make_pos (-1, 1)))
+		    return make_winner (piece);
+	    }
+	}
+    }
+    for (int y = 0; y < rows; y++)
+	for (int x = 0; x < cols; x++)
+	    if (board[y,x] == piece__)
+		return (status_t) { playing = ◊ };
+    return make_winner (piece__);
+}
+
+/*
+ * Make a move and return true if the space is empty,
+ * otherwise return false
+ */
+bool move (&board_t board, int x, int y, piece_t piece)
+{
+    if (board[y,x] != piece__)
+	return false;
+    if (y > 0 && board[y-1,x] == piece__)
+	return false;
+    board[y,x] = piece;
+    return true;
+}
+
+piece_t other_player (piece_t piece)
+{
+    if (piece == piece_x)
+	return piece_o;
+    return piece_x;
+}
+
+/*
+ * Minmax score computation -- very simple, just 0, 2, -2
+ * depending on whether the game is in progress, won by us,
+ * or won by the other player. A special -1 value is returned
+ * for a cats game
+ */
+int score (&board_t board, piece_t turn)
+{
+    status_t	status = get_status (&board);
+
+    union switch (status) {
+    case playing:
+	return 0;
+    case finished f:
+	if (f.winner == piece__)
+	    return -1;
+	else if (f.winner == turn)
+	    return 2;
+	else
+	    return -2;
+    }
+}
+
+typedef struct {
+    position_t	position;
+    int		score;
+} move_t;
+
+int moves = 0;
+int memos = 0;
+int rands = 0;
+
+move_t[board_t] memo;
+
+void reset_stats () {
+    moves = 0;
+    memos = 0;
+    rands = 0;
+}
+
+bool pick_random () {
+    ++rands;
+    return randbits(1) != 0;
+}
+
+/*
+ * Compute the best move using minmax search
+ */
+move_t best_move (&board_t board, piece_t turn) {
+    ++moves;
+
+    move_t  best = {
+	position = { x = -1, y = -1 },
+	score = score(&board, turn)
+    };
+    
+    if (best.score != 0) {
+	return best;
+    }
+    
+    /*
+     * Check to see if this position has already
+     * been scored
+     */
+    if (hash_test (memo, board)) {
+	++memos;
+	return memo[board];
+    }
+    
+    piece_t next_turn = other_player (turn);
+    
+    best.score = -3;
+    /*
+     * Search the whole board for possible moves
+     */
+    for (int y = 0; y < rows; y++)
+	for (int x = 0; x < cols; x++) {
+	    if (move (&board, x, y, turn)) {
+		move_t next = best_move (&board, next_turn);
+		/*
+		 * Minimize our opponents best possible move.
+		 * When two moves are equal, pick randomly
+		 */
+		if (-next.score > best.score || 
+		    -next.score == best.score && pick_random())
+		{
+		    best.position.x = x;
+		    best.position.y = y;
+		    best.score = -next.score;
+		}
+		/*
+		 * Undo this move
+		 */
+		board[y,x] = piece__;
+	    }
+	}
+    
+    /*
+     * Remember this move for next time
+     */
+    memo[board] = best;
+    return best;
+}
+
+void reset_game (&game_t game)
+{
+    game.board = (board_t) { { piece__ ... } ... };
+    game.status.playing = ◊;
+    game.turn = piece_x;
+    memo = (move_t[board_t]) {};
+    Semaphore::signal (game.waiter);
+}
+
+bool make_move (&game_t game, int x, int y)
+{
+    if (move (&game.board, x, y, game.turn))
+    {
+	game.turn = other_player (game.turn);
+	game.status = get_status (&game.board);
+        Semaphore::signal (game.waiter);
+	return true;
+    }
+    return false;
+}
+
+void computer_player (&game_t game, &label_t label)
+{
+    Mutex::acquire (game.lock);
+    while (!game.quiting) {
+	Mutex::release (game.lock);
+	Semaphore::wait (game.waiter);
+	Mutex::acquire (game.lock);
+	if (game.status == game_status_t.playing &&
+	    game.turn == game.computer) 
+	{
+	    Label::relabel (&label, "thinking...");
+	    Widget::redraw (&label);
+	    board_t best_board = game.board;
+	    move_t computer = best_move (&best_board, game.turn);
+	    assert (computer.position.x != -1, "no move");
+	    printf("score: %d\n", computer.score);
+	    make_move (&game, computer.position.x, computer.position.y);
+	    Label::relabel (&label, "");
+	    Widget::redraw (&label);
+	}
+    }
+    Mutex::release (game.lock);
+}
+
+void set_computer (&game_t game, piece_t player)
+{
+    twixt (Mutex::acquire (game.lock); Mutex::release (game.lock)) {
+	game.computer = player;
+        Semaphore::signal (game.waiter);
+    }
+}
+
+extend namespace Nichrome {
+    public namespace Gridwidget {
+	public typedef widget_t + struct {
+	    int down_x, down_y;
+	    &game_t game;
+	} grid_widget_t;
+
+	/*
+	 * Draw the current state of the game
+	 */
+
+	void draw (cairo_t cr, &grid_widget_t widget) {
+	    scale (cr, widget.geometry.width, -widget.geometry.height*cols/rows);
+	    translate (cr, 0, -rows/cols);
+	    set_line_width (cr, 0.05);
+	    set_line_cap (cr, line_cap_t.ROUND);
+	    draw_grid (cr);
+	    draw_pieces (cr, &widget.game.board);
+	    draw_win_line (cr, &widget.game.status);
+	}
+
+	void outline (cairo_t cr, &grid_widget_t widget) {
+	    rectangle (cr, 0, 0, widget.geometry.width,
+		       widget.geometry.height);
+	}
+	    
+	void natural (cairo_t cr, &grid_widget_t widget)
+	{
+	    rectangle (cr, 0, 0, cols * 100, rows * 100);
+	}
+	
+	void button (&grid_widget_t widget, &button_event_t event) {
+	    &game_t game = &widget.game;
+	    int x_i = floor (event.x * cols / widget.geometry.width);
+	    int y_i = rows - 1 - floor (event.y * rows / widget.geometry.height);
+	    if (event.type == button_type_t.press) {
+		widget.down_x = x_i;
+		widget.down_y = y_i;
+	    } else {
+		Mutex::acquire (game.lock);
+		if (widget.game.status == game_status_t.playing &&
+		    widget.game.turn != widget.game.computer &&
+		    x_i == widget.down_x &&
+		    y_i == widget.down_y)
+		{
+		    if (make_move (&widget.game, x_i, y_i))
+			Widget::redraw (&widget);
+		}
+		Mutex::release (game.lock);
+	    }
+	}
+	
+	public *grid_widget_t new (&nichrome_t nichrome, &game_t game) {
+	    grid_widget_t    widget;
+	    
+	    Widget::init (&nichrome, &widget);
+	    widget.button = button;
+	    widget.draw = draw;
+	    widget.outline = outline;
+	    widget.natural = natural;
+	    &widget.game = &game;
+	    return &widget;
+	}
+    }
+}
+
+import Nichrome::Gridwidget;
+
+/*
+ * Play tic tac toe
+ */
+void play ()
+{
+    Widget::default_font = "Comic Sans MS-16";
+    &nichrome_t	    nichrome = Nichrome::new ("Connect-3");
+    game_t  game = {
+	lock = Mutex::new (),
+	waiter = Semaphore::new (),
+	quiting = false,
+	board = { { piece__ ... } ... },
+	status = { playing = ◊ },
+	turn = piece_x,
+	computer = piece_o,
+    };
+    
+    &button_t	    quit = Nichrome::Button::new (&nichrome, "Quit",
+						void func (&widget_t w, bool state) {
+						    w.nichrome.running = false;
+						    game.quiting = true;
+						    Semaphore::signal (game.waiter);
+						});
+
+    &button_t	    new = Nichrome::Button::new (&nichrome, "New",
+					       void func (&widget_t w, bool state) {
+						    reset_game (&game);
+					       });
+    &button_t	    computer;
+    void computer_callback (&widget_t w, bool state) {
+	set_computer (&game,
+		      other_player (game.computer));
+	Button::relabel (&computer,
+			 "Computer: " + 
+			 (game.computer == piece_x ? "x" : "o"));
+    }
+    
+    &computer = Nichrome::Button::new (&nichrome, "Computer: o",
+					void func (&widget_t w, bool state) {
+					    set_computer (&game,
+							  other_player (game.computer));
+					    Button::relabel (&computer,
+							     "Computer: " + 
+							     (game.computer == piece_x ? "x" : "o"));
+					});
+
+    &label_t	    thinking = Nichrome::Label::new (&nichrome, "");
+    
+    &grid_widget_t   widget = Nichrome::Gridwidget::new (&nichrome, &game);
+	
+    &box_t	    menu = Nichrome::Box::new (Box::dir_t.horizontal,
+					       Box::widget_item (&new, 0),
+					       Box::widget_item (&quit, 0),
+					       Box::widget_item (&computer, 0),
+					       Box::glue_item (1),
+					       Box::widget_item (&thinking, 0));
+    &box_t	    box = Nichrome::Box::new (Box::dir_t.vertical,
+					      Box::box_item (&menu),
+					      Box::widget_item (&widget));
+    Nichrome::set_box (&nichrome, &box);
+    fork computer_player (&game, &thinking);
+    Nichrome::main_loop (&nichrome);
+}
+
+play ();