From 87492d14a38d4366ef711140836d6886bbeac9a5 Mon Sep 17 00:00:00 2001
From: Jean-loup Gailly <jloup@gailly.net>
Date: Mon, 7 Feb 2011 19:22:27 +0100
Subject: [PATCH] Support undo for pass moves

This form of undo is required by KGS to settle disputes on dead groups.
It is needed in particular for the distributed engine because replaying
the entire game is too slow and causes loss on time.
---
 board.c   | 18 +++++++++++++++++-
 board.h   |  5 +++++
 engine.h  |  2 ++
 gtp.c     | 17 +++++++++++++++++
 uct/uct.c | 12 ++++++++++++
 5 files changed, 53 insertions(+), 1 deletion(-)

diff --git a/board.c b/board.c
index 5b25d93..5ab54f5 100644
--- a/board.c
+++ b/board.c
@@ -41,7 +41,7 @@ board_setup(struct board *b)
 	b->fbookfile = fbookfile;
 
 	struct move m = { pass, S_NONE };
-	b->last_move = b->last_move2 = b->last_ko = b->ko = m;
+	b->last_move = b->last_move2 = b->last_move3 = b->last_move4 = b->last_ko = b->ko = m;
 }
 
 struct board *
@@ -1278,6 +1278,8 @@ board_play(struct board *board, struct move *m)
 	if (unlikely(is_pass(m->coord) || is_resign(m->coord))) {
 		struct move nomove = { pass, S_NONE };
 		board->ko = nomove;
+		board->last_move4 = board->last_move3;
+		board->last_move3 = board->last_move2;
 		board->last_move2 = board->last_move;
 		board->last_move = *m;
 		return 0;
@@ -1293,6 +1295,20 @@ board_play(struct board *board, struct move *m)
 	return -1;
 }
 
+/* Undo, supported only for pass moves. This form of undo is required by KGS
+ * to settle disputes on dead groups. (Undo of real moves would be more complex
+ * particularly for capturing moves.) */
+int board_undo(struct board *board)
+{
+	if (!is_pass(board->last_move.coord))
+		return -1;
+	board->last_move = board->last_move2;
+	board->last_move2 = board->last_move3;
+	board->last_move3 = board->last_move4;
+	if (board->last_ko_age == board->moves)
+		board->ko = board->last_ko;
+	return 0;
+}
 
 static inline bool
 board_try_random_move(struct board *b, enum stone color, coord_t *coord, int f, ppr_permit permit, void *permit_data)
diff --git a/board.h b/board.h
index f47c7c1..d3678e8 100644
--- a/board.h
+++ b/board.h
@@ -142,6 +142,8 @@ struct board {
 	int moves;
 	struct move last_move;
 	struct move last_move2; /* second-to-last move */
+	struct move last_move3; /* just before last_move2, only set if last_move is pass */
+	struct move last_move4; /* just before last_move3, only set if last_move & last_move2 are pass */
 	/* Whether we tried to add a hash twice; board_play*() can
 	 * set this, but it will still carry out the move as well! */
 	bool superko_violation;
@@ -311,6 +313,9 @@ int board_play(struct board *board, struct move *m);
 typedef bool (*ppr_permit)(void *data, struct board *b, struct move *m);
 void board_play_random(struct board *b, enum stone color, coord_t *coord, ppr_permit permit, void *permit_data);
 
+/*Undo, supported only for pass moves. Returns -1 on error, 0 otherwise. */
+int board_undo(struct board *board);
+
 /* Returns true if given move can be played. */
 static bool board_is_valid_play(struct board *b, enum stone color, coord_t coord);
 static bool board_is_valid_move(struct board *b, struct move *m);
diff --git a/engine.h b/engine.h
index 5a6151e..1307f07 100644
--- a/engine.h
+++ b/engine.h
@@ -9,6 +9,7 @@ struct move_queue;
 
 typedef enum parse_code (*engine_notify)(struct engine *e, struct board *b, int id, char *cmd, char *args, char **reply);
 typedef char *(*engine_notify_play)(struct engine *e, struct board *b, struct move *m);
+typedef char *(*engine_undo)(struct engine *e, struct board *b);
 typedef char *(*engine_result)(struct engine *e, struct board *b);
 typedef char *(*engine_chat)(struct engine *e, struct board *b, char *cmd);
 /* Generate a move. If pass_all_alive is true, <pass> shall be generated only
@@ -35,6 +36,7 @@ struct engine {
 	board_cprint printhook;
 	engine_notify_play notify_play;
 	engine_chat chat;
+	engine_undo undo;
 	engine_result result;
 	engine_genmove genmove;
 	engine_genmoves genmoves;
diff --git a/gtp.c b/gtp.c
index b102962..804c943 100644
--- a/gtp.c
+++ b/gtp.c
@@ -91,6 +91,7 @@ static char *known_commands =
 	"set_free_handicap\n"
 	"place_free_handicap\n"
 	"final_status_list\n"
+	"undo\n"
 	"pachi-result\n"
 	"kgs-chat\n"
 	"time_left\n"
@@ -446,6 +447,22 @@ next_group:;
 			gtp_error(id, "illegal status specifier", NULL);
 		}
 
+	} else if (!strcasecmp(cmd, "undo")) {
+		if (board_undo(board) < 0) {
+			if (DEBUGL(1)) {
+				fprintf(stderr, "undo on non-pass move %s\n", coord2sstr(board->last_move.coord, board));
+				board_print(board, stderr);
+			}
+			gtp_error(id, "cannot undo", NULL);
+			return P_OK;
+		}
+		char *reply = NULL;
+		if (engine->undo)
+			reply = engine->undo(engine, board);
+		if (DEBUGL(1) && debug_boardprint)
+			board_print(board, stderr);
+		gtp_reply(id, reply, NULL);
+
 	/* Custom commands for handling UCT opening tbook */
 	} else if (!strcasecmp(cmd, "uct_gentbook")) {
 		/* Board must be initialized properly, as if for genmove;
diff --git a/uct/uct.c b/uct/uct.c
index fe67334..2f16fe1 100644
--- a/uct/uct.c
+++ b/uct/uct.c
@@ -175,6 +175,17 @@ uct_notify_play(struct engine *e, struct board *b, struct move *m)
 }
 
 static char *
+uct_undo(struct engine *e, struct board *b)
+{
+	struct uct *u = e->data;
+
+	if (!u->t) return NULL;
+	uct_pondering_stop(u);
+	reset_state(u);
+	return NULL;
+}
+
+static char *
 uct_result(struct engine *e, struct board *b)
 {
 	struct uct *u = e->data;
@@ -1003,6 +1014,7 @@ engine_uct_init(char *arg, struct board *b)
 	e->printhook = uct_printhook_ownermap;
 	e->notify_play = uct_notify_play;
 	e->chat = uct_chat;
+	e->undo = uct_undo;
 	e->result = uct_result;
 	e->genmove = uct_genmove;
 	e->genmoves = uct_genmoves;
-- 
2.11.4.GIT