For all you faithful readers, I have to apologize.  If I didn’t have work, I’d post here more often, but lately, work has been draining my motivation to work on personal projects.  Poor excuse, I know, but I needed a reason to categorize this post under “excuses”.

As most of you know, I created a weak chess engine as an independent study, for my last semester of school.  After I completed it, wrote a paper about it, and gave a presentation, I didn’t look back.  It’s not that I didn’t enjoy it as a project, it’s just that I stressed myself a lot over the project, and it was nice to be away from it for a long while.

Well, now I am revisiting the project, trying to correct a lot of the mistakes I made for my “release” version of my independent study.  Here are some of the mistakes I made, and how I plan to resolve them with my new chess engine:

• Objective-C.  Now, Objective-C isn’t a bad language, especially for GUIs and event-driven applications, but for something logical, rigid, and procedural (like a chess engine), the object-orientedness and message handling just turns into overhead and causes overly-complex code.  My resolution for this: implement everything in  pure c.
• Profiling.  I inlined a bunch of macros and preprocessor definitions which I could turn off and on at compile time, which would keep track of how many times each function was called, and how many times an operation was performed in each function.  This is fine, until you realize how ugly and unreadable it made the code.  My resolution: to use GDB or some other product designed to analyze running code.
• Premature optimization.  This was a twofold problem.  First, it caused me to write functions and procedures in an unreadable, inflexible way.  Second, it took up a lot of time that needed to be spent elsewhere.  An example of this would be where I created a heap object for the sole purpose of pushing moves into it, and pulling them out in a sorted, best-first order.  Note that the average number of moves from a specific position is somewhere around 30.  I could have gotten away with a fixed array which I sorted with insertion sort.  This would have caused no noticeable slowdown in the program, and would have saved me a good week of work.  The solution to premature optimization is this: don’t ever do it.
• Interface.  When I was finished with the project, I created my own Java-based GUI, which allowed straightforward input of moves.  However, that meant I couldn’t play it against other chess engines.  This wasn’t a mistake, so much as a choice when I was running out of time to give it a usable interface.  This time I think it’s necessary to do it right.  I want to create a library which can talk with both the Xboard Chess Engine Communication Protocol and with the Universal Chess Interface.  That way, it will be easy to casually play against my engine, and it should be straightforward for my engine to talk to other engines.  Also, my library could reasonably be a springboard for chess projects anyone else might work on.

There are also a few things I didn’t implement which would substantially increase the strength/speed of my program.

• Iterative deepening
• Quiescence search
• Positional-based/strategy-based static evaluation function (as opposed to pure material)

Iterative deepening is just an algorithm and would be straightforward to implement, but those last two are crucial to making a chess engine strong.  However, I am too much a novice at chess to know what I should tell the engine.  ”This is a volatile board position” and “White has the positional advantage” both seem like very subjective statements to me, and I can’t think of a practical way to make those objective.  My long-term plan is to get good at chess.  Maybe practical experience will help me to understand what it means to have “positional advantage”, in a way that a computer will understand.  I am probably joining a chess club…

My current focus is the interface.  I think that it’s one of the most useful parts of this project, in that other projects should be able to use it.  Also, it will be crucial for troubleshooting and testing my engine, once I have the engine working.  Let’s hope I make good progress on the interface.  I’ll keep you posted.

Josh

I feel like I will insult everyone’s intelligence, but I feel the need to formally define the process of escaping:

1. There needs to exist an “escape” function which will output arbitrary data which contains no “control characters” (where control characters are defined elsewhere).
   There needs to exist an “escape” function which will output arbitrary data, which either contains no “control characters”, or at least where every inline control character is unambiguously distinguishable from a control character itself.
2. There needs to exist an “unescape function” which will unambiguously transform any escaped data into its original form.

ESCAPE:
" -> \"
\ -> \\
UNESCAPE:
\\ -> \
\" -> "


A good example of self-escaping: let’s say we need to write a line of code which will print out a line of code which will print out a line of code which will print out “hello, world”.  Give that we do this in C, with C-style escaping:

print "hello, world";
print "print \"hello, world\";";
print "print \"print \\\"hello, world\\\";\";";


An even more contrived example would be escaping the quoted string “hello world” 5 times in succession:

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\"hello world\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\"

I’ve only shown the example of quoting double-quotes, but the same applies to quoting backslashes, newlines, etcetera.  Note that this exponential functionality also applies to things like escaped HTML, which has rules like this (we are only considering the less-than as a control character):

ESCAPE:
< -> &lt;
& -> &amp;
UNESCAPE:
&lt; -> <
&amp; -> &

I’ve come up with at least one clean/elegant solution to the problem of exponential size-increase.  This method of escaping only grows logarithmically, I have been unable to come up with convoluted escaping examples for it.  The rules are as follows (considering only the quote as an escape character):

ESCAPE:
" -> ["|1]
["|n] (where n is greater than 0) -> ["|n+1]
UNESCAPE:
["|1] -> ”
["|n] (where n is greater than 1) -> ["|n-1]

Note that because of the pairing of [, |, ], none of these have to be escaped in order for this to work.  Also note that for this to work, the way the numbers are represented must be precisely defined, so that only elements which have been escaped will be unescaped.  For example, if we escaped a to produce b, b would be unescaped to c, which would violate one of the properties of escaping.  So instead, when we escape a it should produce d, which would unescape back to a:

a: hello ["|1,138]
b: hello ["|1139]
c: hello ["|1138]
d: hello [["|1]|1,138]

Now, here are my two previous examples, quoted in this fashion:

print "print ["|1] print ["|2]hello, world["|2];["|1];”;
["|5]hello world["|5]


I doubt a method like this will be adopted by any language or standard, but it seems to me like it has many advantages and few disadvantages.  Assuming this post generates any interest, I am going to write up a follow-up post which analyzes the advantages and disadvantages of these rules of escaping, compared to more traditional escaping rules.

This is the usage instructions I provided with the application.  Note that “and” always has higher precedence than “or”, and there’s no way to change that.

usage: filesql.pl -d{delim} select where {CONDITIONGROUP}
usage: filesql.pl -d{delim} update set -f{number} = {TERMINAL} \
       [-f{number} = {TERMINAL} ...] [where {CONDITIONGROUP}]
usage: filesql.pl -d{delim} delete where {CONDITIONGROUP}

{CONDITIONGROUP} := {ANDGROUP} [or {ANDGROUP} ...]
{ANDGROUP}       := {CONDITION} [and {CONDITION} ...]
{CONDITION}      := {TERMINAL} {OPERATOR} {TERMINAL}
{TERMINAL}       := -f{number} | {constant}
{OPERATOR}       := -eq | -ne | -gt | -lt | -ge | -le

filesql.pl

My next project I’ve been wanting to work on is as follows: a unix tool which allows one to query a file as if it were a database.  It would only implement simple operations, but that’s all I ever find myself needing to do on a file anyhow.  Instead of actually updating the file, it would just output the updated information which could be used to replace the file (as most unix tools work anyhow).

One of the issues I’ve been trying to figure out is usage/invocation.  I’ve talked myself into putting all the “select” criteria onto the command line as arguments, but I can’t think of a clean way of pulling it off.  An example of what I have in mind:

filesql -d',' update set -f3 = "new value" where -f1 -eq "asdf" and -f2 -ne -f4 <input.csv >output.csv

If anyone else has a better idea for a “usage” paradigm, please let me know.

I’ve decided that DEFLATE (the algorithm used by “zip”, “gzip”, and a few other compression programs) would be a fun algorithm to implement. At this point, I am basically recreating the wheel, because the “zlib” library already does what I am planning on doing and more, but my ultimate goal is to analyze different compression techniques in use, so the logical place to start is by implementing them.

DEFLATE works by first taking the raw data and performing a lempel-zip encoding on the data (scanning through data for duplicates, and replacing duplicate data with a reference to where the data is duplicated). Then, this lempel-ziv encoded data is huffman-coded (codes of varying lengths are created for each symbol/character based on frequency of use). The huffman tree and the huffman-coded data are then written to the file.

This week, I have only implemented huffman-encoding. The huffman trees do not currently adhere to all the properties needed by DEFLATE, but the basic functionality of encoding symbols into a huffman tree seems to be working.

http://joshodom.net/weekly/week2.tar.gz

cat file.dat | sort | cut -d, -f4 > file.dat.tmp; mv file.dat.tmp file.dat

The issue being: if you try writing directly out to the input file (in this case, file.dat), it overwrites the file with a 0-byte file before the reading happens.  I’ve always wondered why someone can’t just make a program that will slurp in the whole intermediate file before even opening the file for writing, and then writing the whole file at once.

Well, after a few years of wondering, I’ve finally written it.  It should compile on any standard UNIX/Linux/BSD system.  Here’s the above command, using my utility:

cat file.dat | sort | cut -d, -f4 | dw file.dat

It’s very simplistic, and would need to be expanded upon to be used in live production environments, but it should be fine for simple scripts.  Enjoy!

http://joshodom.net/weekly/week1.tar.gz