commit 85ffb39bdde4cca75d32d1bf2fe00d85a7c9908c
parent 38b4db2714781bf08d020022f973fe7e61f2f808
Author: benjamin paul <bpaul@bpaul.xyz>
Date: Sun, 8 Aug 2021 15:23:42 +1000
computer chess! this will be published to gopher
Diffstat:
2 files changed, 172 insertions(+), 0 deletions(-)
diff --git a/chess-programming/1-intro.md b/chess-programming/1-intro.md
@@ -0,0 +1,155 @@
+7 august 2021
+
+# Intro
+
+I decided that I want to write a chess engine so here you go.
+
+First of all, this isn't my first time writing a chess engine. I stopped developing my previous engine because I didn't like how much code I had copied.
+
+So what is a chess engine? At its core (I think) a chess engine which takes a chess position as input and outputs the best move (or at least what the engine thinks is the best move). In order to implement this, we need some sort of protocol to communicate to the engine which position to look at.
+
+## UCI Protocol
+
+UCI (Universal Chess Interface) is the most commonly used chess protocol. The engine sends stuff to stdout, then a gui will read the stuff and process it. The stuff is specified in UCI.
+
+There are a few basic commands in UCI that can be implemented without programming anything chess related. I'll leave out the exact specifics of how you do UCI until it is implemented. These commands are
+
+`uci`
+: Meant to be used to tell the engine to use uci instead of something else.
+: Give the various options that may be set to change how the engine behaves
+: The engine is meant to identify itself in response
+
+`isready`
+: This command is meant to "synchronise the engine with the gui"
+: All you have to do is print "isready"
+
+`quit`
+: Just quit the engine
+
+I'm only going to cover these commands for the rest of this article, so no chess just yet.
+
+```
+inline bool
+cmd(const char *b, const char c) {
+ return strncmp(b, c, strlen(c)) == 0;
+}
+
+int
+main() {
+ char buf[2048];
+
+ while (1) {
+ fgets(buf, 2048, stdin);
+
+ if (cmd(buf, "uci")) {
+ puts("id name bpaul-chess v0.0.1");
+ puts("id author Benjamin Paul");
+ puts("uciok");
+ } else if (cmd(buf, "isready")) {
+ puts("readyok");
+ } else if (cmd(buf, "quit")) {
+ break;
+ }
+ }
+
+ return 0;
+}
+```
+
+A uci command has the format "command arg1 arg2 ... argn\n". The \n is important as it represents the end of a command.
+
+The buffer size of 2048 is to handle the size of other commands in the protocol, although the number 2048 is pretty arbitrary. I only chose it because it is a power of 2.
+
+strncmp was used because maybe (as a human and not as a gui) I may enter a command such as "uci ". strcmp would say that this is not the same as "uci", but strncmp with n=3 would say that they are the same.
+
+There may be room to optimize out the strlen in the strncmp.
+
+WARNING this is completely useless.
+
+The command c is always constant, and running strlen on a constant will always give the same results, so feeding in the constant would improve speed over using strlen. This can be implemented using the C preprocessor instead of just writing the constant value of strlen for each command.
+
+```
+#define CMD(s) strncmp(buf, s, sizeof(s)-1) == 0
+.
+.
+.
+if (CMD("uci")) {
+ ...
+} else if (CMD("isready")) {
+ ...
+} else if (CMD("quit")) {
+ ...
+}
+```
+
+sizeof gives the length of the string including the null byte at the end, but strlen ignores the null byte, so 1 is subtracted to get rid of the null byte from the count.
+
+These two versions of the program can now be compared. I am using the `perf(1)` command which is part of linux I think. These two versions are compiled with just -O3.
+
+I ran the command `perf stat -e instructions:u ./prog < commands` on both versions and read the result. The commands file contains:
+```
+uci
+isready
+quit
+```
+essentially testing all of the commands so far implemented.
+
+The first version had about 138505 instructions and the second version had about 138500. The difference was only 5 instructions??? As it turns out there is a gcc flag `-foptimize-strlen` which is enabled by -O2 or -O3, but it is interesting that using the macro still saved a bit of time.
+
+After some more testing, it turns out that there is actually no improvement. For some reason, changing the binary file's name caused the program to use 5 more instructions, and it had nothing to do with the code.
+
+By the way these optimizations are completely useless.
+
+The next article will probably start going into the making of a board representation. Thanks for reading! Have a good day/night.
+
+Update:
+OMG I saved like 4000 instructions somehow by rewriting strncmp!!
+
+Old strncmp: 138505
+New strncmp: 134630
+
+I couldn't figure out why the second version was better but I found it trying to optimize for SIMD. Lets hope the improvement did actually come from SIMD and not something else.
+
+New strncmp code
+```
+bool
+new_strncmp(const char *s1, const char *s2, unsigned long n) {
+ int i;
+ char c[4];
+
+ if (n >= 4) {
+ unsigned long n4 = n >> 2;
+ do {
+ for (i = 0; i < 4; i++) {
+ c[i] = s1[i] - s2[i];
+ if (s1[i] == '\0' || c[i] != 0) {
+ return c[i];
+ }
+ }
+
+ s1+=4;
+ s2+=4;
+ n4--;
+ } while (n4 > 0);
+ n &= 3;
+ }
+
+ while (n > 0) {
+ c[0] = *s1 - *s2;
+ if (*s1 == '\0' || c[0] != 0) {
+ return c[0];
+ }
+ s1++;
+ s2++;
+ }
+
+ return c[0];
+}
+```
+
+## Links
+
+UCI protocol specification
+http://wbec-ridderkerk.nl/html/UCIProtocol.html
+strncmp in glibc source
+https://sourceware.org/git/?p=glibc.git;a=blob;f=string/strncmp.c;hb=HEAD
diff --git a/chess-programming/2-bitboards.md b/chess-programming/2-bitboards.md
@@ -0,0 +1,17 @@
+# Bitboards
+
+Nowadays, chess programs represent the board using bitboards.
+
+Blah blah what are bitboards
+
+I want to optimize the usage of bitboards for SIMD stuff.
+
+The functions that are called the most are:
+Move make
+Move unmake
+Move generate
+
+vectorize these somehow.
+
+Move make function:
+move a piece from a square to another square
