First commit

1 files changed, 662 insertions, 0 deletions

diff --git a/src/blog/comments-at-end.kuht b/src/blog/comments-at-end.kuht
new file mode 100755
index 0000000..44cdc86
--- /dev/null
+++ b/src/blog/comments-at-end.kuht
@@ -0,0 +1,662 @@
+<import "base.kuht" as "base" />
+
+<head>
+	<title>Comments at the End</title>
+	<meta name="description" content="My personal commenting style" />
+</head>
+
+<body>
+
+<article>
+
+<h1>Comments at the End</h1>
+
+<p>
+	I'm about to say something which many of you will find comically stupid. I imagine a reaction of both
+	cringe and shock. Worse, I don't think my rationale is convincing on its own. But I want you to hear
+	me out, give it a try one day, and maybe I will convince you. If you go through this process and are
+	not convinced of the benefits, that's fine. As long as you consider it, I will be happy.
+</p>
+
+<p>
+	This year, I made a new year's resolution: don't write comments until the end, preferably right
+	before you make the pull request. It's fine to make todo comments, and if you think you might forget
+	to document something later, it's okay to write it immediately. But at the end, you should go through
+	your code and write comments.
+</p>
+
+<p>
+	As is typically recommended, your comments should not explain what your code does. Your code should
+	explain what your code does. Instead, the comments should explain why you did what you did, and why
+	you did it in that particular way. Basically, imagine you're showing a co-worker your code, and
+	explaining what you did. Your comments should reflect everything that you would normally say. Code
+	that is very simple won't need comments at all. More complicated logic will.
+</p>
+
+<p>
+	The first benefit to this is that you will be in "writing mode" instead of "coding mode". You'll
+	discover many points where you need a comment, that you never thought about before. Your comments
+	will also be very in-depth. I said before that comments should reflect what you would tell someone
+	when explaining your code. If your comments are this detailed, then you'll never have to explain
+	anything. This might not work very well if you hate writing. I obviously enjoy it (when I'm not
+	being graded). I don't know if this benefit will be as big for others.
+</p>
+
+<p>
+	The bigger benefit, in my opinion, is that it might give you an opportunity to improve your code. I
+	have another rule, which says, "no apology comments". If you find yourself saying, "Sorry for not
+	making this better", then you should just fix the problem. Note that you are allowed to say "I didn't
+	do it this different way because that would be worse". If your solution is the best solution you can
+	think of, then you <em>should</em> use that solution. But when there's a better alternative, you
+	should choose the better alternative. As I'm writing comments, I often catch myself in the middle of
+	writing an apology comment. Then I go fix the problem. That means the commenting phase of my code is
+	also a minor refactoring phase.
+</p>
+
+<p>
+	One person has criticized my commenting style, saying that it takes too long to read, and should be
+	more concise. I think there is a middle ground here, that I haven't achieved yet. In the future, I
+	might try doing a second pass over my comments to shorten them if I can. I'll just have to hope that
+	over time, I learn how to make my comments concise from the start. This person has also recommended
+	that I read Steven Pinker's <em>The Sense of Style</em>. I have a copy of it, but unfortunately I
+	enjoy writing more than I enjoy reading.
+</p>
+
+<p>
+	I'm sure some people are still unconvinced, which is reasonable. So I'll provide, below, a sample of
+	code where I did this by accident, which convinced me to turn this into a habit. If you like what you
+	see, then I suggest you give my idea a try. This is a C library that allows the
+	<a href="http://www.fierz.ch/checkerboard.php">CheckerBoard UI</a> to use my
+	<a href="https://github.com/botahamec/ampere">Ampere Checkers AI</a>.
+</p>
+
+<pre>
+// File: ampere_cb.c
+// Description: Provides a bridge between Ampere and CheckerBoard
+// Author: Mica White (they/them) &lt;botahamec@outlook.com>
+// License: CC0 1.0
+
+// -------------------------- IMPORTS ------------------------------------
+
+#include &lt;math.h>
+#include &lt;stdio.h>
+#include &lt;stdlib.h>
+#include &lt;string.h>
+#include &lt;windows.h>
+
+#include "ampere.h"
+#include "cb_interface.h"
+
+
+// --------------------------- MACROS -------------------------------------
+
+// The engine should never search to a depth greater than 40
+// This number is somewhat arbitrary. I just doubled the length of the
+// shortest possible checkers game
+#define MAX_DEPTH 40
+#define MEGABYTE (1024*1024)
+// I don't think anybody will ever miss a single megabyte of RAM.
+// For computers more powerful than a Raspberry Pi Zero, I recommend
+// increasing this to eight megabytes.
+#define DEFAULT_HASH_SIZE MEGABYTE
+
+// These are the lengths of buffers which are given to us by CheckerBoard
+#define INFO_STR_LEN 255
+#define COMMAND_LEN 256
+#define CMD_REPLY_LEN 256
+#define NAME_LEN 250
+
+// I'm not actually sure when I should start calling this 0.2
+// I'm still planning on making breaking changes, so I won't call it 1.0
+#define ENGINE_NAME "Ampere 0.1"
+#define ENGINE_ABOUT \
+"\
+Ampere version 0.1\n\
+A fast and smart Checkers engine\n\
+Implements: transposition table, aspiration windows, iterative deepening\n\
+Defecits: simple evaluation function, no quiescence search\n\
+Copyright Mica White\n\
+"
+
+
+// -------------------------- STATICS ------------------------------------
+
+/// The engine itself
+// I ended up leaking this. I don't think it'll ever be possible for two
+// threads to access the transposition table at the same time, but it's
+// probably better safe than sorry. I don't actually know when this would
+// be collected anyway.
+ampere_engine_t ampere_engine = NULL;
+/// A collection of C functions which the engine may call
+// This needs to be static because it must outlive `ampere_engine`
+struct frontend frontend;
+/// The size to set the transposition table to. This can only be modified
+/// before the engine is constructed, not after.
+int hash_size = DEFAULT_HASH_SIZE;
+/// This is a buffer that CheckerBoard provides to display to the user.
+// This is static because it needs to be accessed by the `give_info` function.
+char* info_str;
+
+
+// --------------------- FRONTEND CALLBACKS -------------------------------
+// These are functions which are passed into the engine on certain events,
+// such as logging debug information, displaying evaluation progress, and
+// determining the best move. The only useful one for our purpose is
+// the `give_info` function, which is called occasionally by the engine
+// during its evaluation to give progress reports.
+
+/// The name says it all
+// This is used for both `debug` and `best_move`. We don't do anything
+// with debug information because CheckerBoard gives us no way to
+// display it. We don't need to do anything with `best_move` because
+// our evaluation runs synchronously, and the evaluation function already
+// returns the best move.
+void do_nothing(void* x) {}
+
+/// Displays information about the in-progress evaluation to the user
+void give_info(ampere_evalinfo_t info) {
+	char move_str[6] = "None"; // If no move was found, default to "None"
+	ampere_move_t move = ampere_evalinfo_bestmove(info);
+	if (move != NULL) {
+		ampere_move_string(move, move_str);
+	}
+
+	float eval = ampere_eval_tofloat(ampere_evalinfo_evaluation(info));
+	int depth = ampere_evalinfo_depth(info);
+	unsigned long long int nodes_per_sec = ampere_evalinfo_nodespersec(info);
+
+	sprintf_s(
+		info_str, INFO_STR_LEN,
+		"Move: %s; Eval: %f; Depth: %d; NPS: %llu",
+		move_str, eval, depth, nodes_per_sec
+	);
+}
+
+
+// ---------------------- HELPER FUNCTIONS --------------------------------
+
+/// Converts a CheckerBoard piece to an Ampere piece.
+/// This results in undefined behavior for: null pointers,
+/// `i` or `j` >= 8, or `index` >= 32,
+void square_convert(
+	Board8x8 board,
+	int i,
+	int j,
+	uint32_t* pieces,
+	uint32_t* colors,
+	uint32_t* kings,
+	int index
+) {
+	int value = board[i][j];
+	uint32_t piece_mask = 1 &lt;&lt; index;
+
+	if (value == CB_FREE) {
+		return;
+	}
+	else {
+		*pieces |= piece_mask;
+	}
+
+	if (value & CB_BLACK) {
+		*colors |= piece_mask;
+	}
+
+	if (value & CB_KING) {
+		*kings |= piece_mask;
+	}
+}
+
+/// Converts an Ampere piece to a CheckerBoard piece.
+/// This results in undefined behavior for a null board or `index` >= 32
+int get_cb_piece(ampere_board_t amp_board, int index) {
+	int piece = 0;
+
+	if (!ampere_board_has_piece_at(amp_board, index)) {
+		return CB_FREE;
+	}
+
+	if (ampere_board_color_at(amp_board, index) == DARK) {
+		piece |= CB_BLACK;
+	}
+	else {
+		piece |= CB_WHITE;
+	}
+
+	if (ampere_board_king_at(amp_board, index)) {
+		piece |= CB_KING;
+	}
+	else {
+		piece |= CB_MAN;
+	}
+
+	return piece;
+}
+
+/// Converts an ampere square index to a CheckerBoard square coordinate.
+/// This is undefined behavior for `amp_square` >= 32
+struct coor get_cb_square(int amp_square) {
+	struct coor coordinates;
+
+	switch (amp_square) {
+	case 0:
+	case 6:
+	case 12:
+	case 18:
+		coordinates.y = 0;
+		break;
+	case 1:
+	case 7:
+	case 13:
+	case 19:
+		coordinates.y = 1;
+		break;
+	case 8:
+	case 14:
+	case 20:
+	case 26:
+		coordinates.y = 2;
+		break;
+	case 9:
+	case 15:
+	case 21:
+	case 27:
+		coordinates.y = 3;
+		break;
+	case 16:
+	case 22:
+	case 28:
+	case 2:
+		coordinates.y = 4;
+		break;
+	case 17:
+	case 23:
+	case 29:
+	case 3:
+		coordinates.y = 5;
+		break;
+	case 24:
+	case 30:
+	case 4:
+	case 10:
+		coordinates.y = 6;
+		break;
+	case 25:
+	case 31:
+	case 5:
+	case 11:
+		coordinates.y = 7;
+		break;
+	default:
+		// this is undefined behavior
+		break;
+	}
+
+	switch (amp_square) {
+	case 18:
+	case 26:
+	case 2:
+	case 10:
+		coordinates.x = 0;
+		break;
+	case 19:
+	case 27:
+	case 3:
+	case 11:
+		coordinates.x = 1;
+		break;
+	case 12:
+	case 20:
+	case 28:
+	case 4:
+		coordinates.x = 2;
+		break;
+	case 13:
+	case 21:
+	case 29:
+	case 5:
+		coordinates.x = 3;
+		break;
+	case 6:
+	case 14:
+	case 22:
+	case 30:
+		coordinates.x = 4;
+		break;
+	case 7:
+	case 15:
+	case 23:
+	case 31:
+		coordinates.x = 5;
+		break;
+	case 0:
+	case 8:
+	case 16:
+	case 24:
+		coordinates.x = 6;
+		break;
+	case 1:
+	case 9:
+	case 17:
+	case 25:
+		coordinates.x = 7;
+		break;
+	default:
+		// this is undefined behavior
+		break;
+	}
+
+	return coordinates;
+}
+
+/// Converts a CheckerBoard board to an Ampere board.
+/// This is undefined behavior for a null `board`, or invalid `turn`.
+/// It is the caller's responsibility to free the return value using the
+/// `ampere_board_destroy` function. Otherwise this results in a memory leak.
+ampere_board_t cb_board_to_ampere_board(Board8x8 board, int turn) {
+	uint32_t pieces = 0l;
+	uint32_t colors = 0l;
+	uint32_t kings = 0l;
+	enum color ampere_turn = DARK;
+
+	square_convert(board, 0, 0, &pieces, &colors, &kings, 18);
+	square_convert(board, 2, 0, &pieces, &colors, &kings, 12);
+	square_convert(board, 4, 0, &pieces, &colors, &kings, 6);
+	square_convert(board, 6, 0, &pieces, &colors, &kings, 0);
+	square_convert(board, 1, 1, &pieces, &colors, &kings, 19);
+	square_convert(board, 3, 1, &pieces, &colors, &kings, 13);
+	square_convert(board, 5, 1, &pieces, &colors, &kings, 7);
+	square_convert(board, 7, 1, &pieces, &colors, &kings, 1);
+	square_convert(board, 0, 2, &pieces, &colors, &kings, 26);
+	square_convert(board, 2, 2, &pieces, &colors, &kings, 20);
+	square_convert(board, 4, 2, &pieces, &colors, &kings, 14);
+	square_convert(board, 6, 2, &pieces, &colors, &kings, 8);
+	square_convert(board, 1, 3, &pieces, &colors, &kings, 27);
+	square_convert(board, 3, 3, &pieces, &colors, &kings, 21);
+	square_convert(board, 5, 3, &pieces, &colors, &kings, 15);
+	square_convert(board, 7, 3, &pieces, &colors, &kings, 9);
+	square_convert(board, 0, 4, &pieces, &colors, &kings, 2);
+	square_convert(board, 2, 4, &pieces, &colors, &kings, 28);
+	square_convert(board, 4, 4, &pieces, &colors, &kings, 22);
+	square_convert(board, 6, 4, &pieces, &colors, &kings, 16);
+	square_convert(board, 1, 5, &pieces, &colors, &kings, 3);
+	square_convert(board, 3, 5, &pieces, &colors, &kings, 29);
+	square_convert(board, 5, 5, &pieces, &colors, &kings, 23);
+	square_convert(board, 7, 5, &pieces, &colors, &kings, 17);
+	square_convert(board, 0, 6, &pieces, &colors, &kings, 10);
+	square_convert(board, 2, 6, &pieces, &colors, &kings, 4);
+	square_convert(board, 4, 6, &pieces, &colors, &kings, 30);
+	square_convert(board, 6, 6, &pieces, &colors, &kings, 24);
+	square_convert(board, 1, 7, &pieces, &colors, &kings, 11);
+	square_convert(board, 3, 7, &pieces, &colors, &kings, 5);
+	square_convert(board, 5, 7, &pieces, &colors, &kings, 31);
+	square_convert(board, 7, 7, &pieces, &colors, &kings, 25);
+
+	if (turn == CB_WHITE) {
+		ampere_turn = LIGHT;
+	}
+
+	return ampere_board_new(pieces, colors, kings, ampere_turn);
+}
+
+/// Converts an Ampere board to a CheckerBoard board.
+/// This is undefined behavior if `dest` or `src` are null.
+void set_cb_board(Board8x8 dest, ampere_board_t src) {
+	dest[0][0] = get_cb_piece(src, 18);
+	dest[2][0] = get_cb_piece(src, 12);
+	dest[4][0] = get_cb_piece(src, 6);
+	dest[6][0] = get_cb_piece(src, 0);
+	dest[1][1] = get_cb_piece(src, 19);
+	dest[3][1] = get_cb_piece(src, 13);
+	dest[5][1] = get_cb_piece(src, 7);
+	dest[7][1] = get_cb_piece(src, 1);
+	dest[0][2] = get_cb_piece(src, 26);
+	dest[2][2] = get_cb_piece(src, 20);
+	dest[4][2] = get_cb_piece(src, 14);
+	dest[6][2] = get_cb_piece(src, 8);
+	dest[1][3] = get_cb_piece(src, 27);
+	dest[3][3] = get_cb_piece(src, 21);
+	dest[5][3] = get_cb_piece(src, 15);
+	dest[7][3] = get_cb_piece(src, 9);
+	dest[0][4] = get_cb_piece(src, 2);
+	dest[2][4] = get_cb_piece(src, 28);
+	dest[4][4] = get_cb_piece(src, 22);
+	dest[6][4] = get_cb_piece(src, 16);
+	dest[1][5] = get_cb_piece(src, 3);
+	dest[3][5] = get_cb_piece(src, 29);
+	dest[5][5] = get_cb_piece(src, 23);
+	dest[7][5] = get_cb_piece(src, 17);
+	dest[0][6] = get_cb_piece(src, 10);
+	dest[2][6] = get_cb_piece(src, 4);
+	dest[4][6] = get_cb_piece(src, 30);
+	dest[6][6] = get_cb_piece(src, 24);
+	dest[1][7] = get_cb_piece(src, 11);
+	dest[3][7] = get_cb_piece(src, 5);
+	dest[5][7] = get_cb_piece(src, 31);
+	dest[7][7] = get_cb_piece(src, 25);
+}
+
+
+// --------------------- LIBRARY FUNCTIONS -------------------------------
+
+/// Returns the name of the engine
+// This shouldn't be necessary since we also implemented the "name" command,
+// but this function is very easy to implement, so why not just do it?
+int enginename(char reply[NAME_LEN]) {
+	sprintf_s(reply, NAME_LEN, ENGINE_NAME);
+	return 1;
+}
+
+/// Responds to an engine command. The following commands are implemented:
+/// * name
+/// * about
+/// * help
+/// * set hashsize (only valid before getmove is called)
+/// * get hashsize
+/// * get protocolversion
+/// * get gametype
+int enginecommand(char str[COMMAND_LEN], char reply[CMD_REPLY_LEN]) {
+	// answers to the command sent by CheckerBoard.
+	char command[COMMAND_LEN] = "", param1[COMMAND_LEN] = "", param2[COMMAND_LEN] = "";
+	sscanf_s(str, "%s %s %s", command, COMMAND_LEN, param1, COMMAND_LEN, param2, COMMAND_LEN);
+
+	//by default, return "I don't understand this"
+	sprintf_s(reply, CMD_REPLY_LEN, "?");
+
+	if (strncmp(command, "name", COMMAND_LEN) == 0) {
+		sprintf_s(reply, CMD_REPLY_LEN, ENGINE_NAME);
+		return 1;
+	}
+
+	if (strncmp(command, "about", COMMAND_LEN) == 0) {
+		sprintf_s(reply, CMD_REPLY_LEN, ENGINE_ABOUT);
+		return 1;
+	}
+
+	if (strncmp(command, "help", COMMAND_LEN) == 0) {
+		sprintf_s(reply, CMD_REPLY_LEN, "amperehelp.html");
+		return 1;
+	}
+
+	if (strncmp(command, "set", COMMAND_LEN) == 0) {
+		if (strncmp(param1, "hashsize", COMMAND_LEN) == 0) {
+			if (ampere_engine == NULL) {
+				hash_size = strtol(param2, NULL, 10) * MEGABYTE;
+				return 1;
+			}
+			else {
+				// we can't change the size of the transposition table after
+				// the engine is initialized
+				return 0;
+			}
+		}
+
+		if (strncmp(param1, "book", COMMAND_LEN) == 0) {
+			return 0;
+		}
+	}
+
+	if (strncmp(command, "get", COMMAND_LEN) == 0) {
+		if (strncmp(param1, "hashsize", COMMAND_LEN) == 0) {
+			sprintf_s(reply, CMD_REPLY_LEN, "%d", hash_size / MEGABYTE);
+			return 1;
+		}
+
+		if (strncmp(param1, "book", COMMAND_LEN) == 0) {
+			// theoretically, the correct value is `CB_BOOK_NONE`, but
+			// CheckerBoard will assume that means:
+			//     "the book hasn't been loaded yet"
+			// when we actually mean:
+			//     "Ampere doesn't support opening books"
+			return 0;
+		}
+
+		if (strncmp(param1, "protocolversion", COMMAND_LEN) == 0) {
+			sprintf_s(reply, CMD_REPLY_LEN, "2");
+			return 1;
+		}
+
+		if (strncmp(param1, "gametype", COMMAND_LEN) == 0) {
+			sprintf_s(reply, CMD_REPLY_LEN, "%d", GT_ENGLISH);
+			return 1;
+		}
+	}
+
+	return 0;
+}
+
+/// Asks the engine to make a move
+int WINAPI getmove(
+	Board8x8 board,
+	int color,
+	double maxtime,
+	char str[INFO_STR_LEN],
+	int* playnow,
+	int info,
+	int moreinfo,
+	struct CBmove* move
+) {
+	// this will be modified on every call, just in case CheckerBoard decides
+	// to reallocate it later
+	info_str = str;
+
+	if (ampere_engine == NULL) {
+		// initialize the frontend
+		frontend.debug = (void (*)(char*)) do_nothing;
+		frontend.info = give_info;
+		frontend.report_bestmove = do_nothing;
+
+		// initialize the engine with the frontend and table size
+		ampere_engine = ampere_new_engine(hash_size, &frontend);
+	}
+
+	int current_turn = DARK;
+	if (color == CB_WHITE) {
+		current_turn = LIGHT;
+	}
+
+	// set up Ampere's clock
+	int increment_info = (info >> 2) & 3;
+	ampere_clock_t clock;
+	if (increment_info != 0) {
+		int inc_factor = 1;
+		if (increment_info == 2) {
+			inc_factor = 10;
+		}
+		else if (increment_info == 3) {
+			inc_factor = 100;
+		}
+
+		int time_remaining = ((moreinfo >> 16) & 0xffff) * inc_factor;
+		int increment = (moreinfo & 0xffff) * inc_factor;
+		clock = ampere_clock_incremental(time_remaining, time_remaining, increment, increment, 0, 0);
+	}
+	else {
+		int time = floor(maxtime * 1000.0);
+		clock = ampere_clock_timepermove(time);
+	}
+
+	ampere_board_t amp_board = cb_board_to_ampere_board(board, color);
+	ampere_set_position(ampere_engine, amp_board);  // the board might change between calls
+
+	struct eval_result result = ampere_evaluate(ampere_engine, (bool*)playnow, 0, MAX_DEPTH, clock);
+	ampere_move_t best = result.best_move;
+	ampere_eval_t evaluation = result.evaluation;
+
+	// we calculate the result at the beginning, in case we need to return early
+	int eval = CB_UNKNOWN;
+	if (ampere_eval_is_force_win(evaluation)) {
+		eval = CB_WIN;
+	}
+	else if (ampere_eval_is_force_loss(evaluation)) {
+		eval = CB_LOSS;
+	}
+
+	// the move will be null if there are no legal moves...
+	// which means we lost, ergo we could've returned when we got the eval
+	// i don't really wanna change it now
+	if (best == NULL) {
+		return eval;
+	}
+
+	// I don't think this is actually necessary. CheckerBoard is usually able
+	// to figure this out automatically for American Checkers. I didn't learn
+	// that until after I wrote all this code, so I'll leave it in case it
+	// prevents a bug later.
+	move->jumps = 0;
+	move->from = get_cb_square(ampere_move_start(best));
+	move->oldpiece = get_cb_piece(amp_board, ampere_move_start(best));
+	if (ampere_move_is_jump(best)) {
+		move->del[move->jumps] = get_cb_square(ampere_move_jump_position(best));
+		move->delpiece[move->jumps] = get_cb_piece(amp_board, ampere_move_jump_position(best));
+		move->jumps = 1;
+	}
+
+	// we figure out the new board position, in case we need to double jump
+	ampere_play_move(ampere_engine, best);
+	ampere_board_destroy(amp_board);
+	amp_board = ampere_current_position(ampere_engine);
+
+	// Ampere and CheckerBoard don't align in their definition of a move
+	// In Ampere, a move is a single slide or jump. But in CheckerBoard,
+	// double jumps are considered to be one move. This is a very sensible
+	// decision. But Ampere is very fast partially because it can optimize
+	// the move struct down to a single byte. So in order for it to work with
+	// CheckerBoard, we need to go down the line and return any extra jumps
+	while (*ampere_board_turn(amp_board) == current_turn) {
+		move->path[move->jumps] = get_cb_square(ampere_move_end(best));
+
+		// the move should be in the transposition table, so it's ok to set the depth to 1
+		result = ampere_evaluate(ampere_engine, (bool*)playnow, 0, 1, 0);
+		ampere_move_destroy(best);
+		best = result.best_move;
+		if (best == NULL) {
+			return eval;
+		}
+
+		if (ampere_move_is_jump(best)) {
+			move->del[move->jumps] = get_cb_square(ampere_move_jump_position(best));
+			move->delpiece[move->jumps] =
+				get_cb_piece(amp_board, ampere_move_jump_position(best));
+			move->jumps += 1;
+		}
+
+		ampere_play_move(ampere_engine, best);
+		ampere_board_destroy(amp_board);
+		amp_board = ampere_current_position(ampere_engine);
+	}
+
+	move->to = get_cb_square(ampere_move_end(best));
+	move->newpiece = get_cb_piece(amp_board, ampere_move_end(best));
+
+	// this is the part that CheckerBoard actually relies upon to figure out what move was played
+	set_cb_board(board, amp_board);
+
+	ampere_move_destroy(best);
+	ampere_eval_destroy(evaluation);
+	ampere_board_destroy(amp_board);
+	return eval;
+}
+</pre>
+
+</article>
+</body>