DEV Community: SnowballSH

Avalanche Chess Engine... Part 1

SnowballSH — Thu, 27 Jan 2022 03:11:22 +0000

Introduction

After successfully building a 5x5 shogi engine in C#, I thought I would make my own chess engine, totally from scratch. This would enhance my skills with low-level instructions, and give me something to constantly improve and challenge myself.

In this series of posts, I will talk about steps to create a chess engine as well as my progress in making one.

The source code of Avalanche Chess Engine will be here: github.com/SnowballSH/Avalanche. Feel free to follow along!

Choice of Programming Language

I was originally going to use Rust. However, when making a chess-playing program, you don't need safety -- or rather you don't want safety -- you only care about speed and all the safety checks should be done at debug time. Sure, you can disable checks in Rust, but the code would be bloated by unsafe keywords.

I choose Zig because it's an interesting C alternative. GCC works badly on my machine, so C wouldn't work. Zig uses LLVM to compile code that optimizes for different machines and is able to cross-compile to different platforms. So, here is my first Zig project.

Phases of developing a chess (or any other board game) engine

Board representation

For any game, you will need a state to represent the current position of the game. This is usually a struct containing board(s), turn, move count, and other information.

A chessboard has 8x8 = 64 squares, which is exactly the number of bits in a 64-bit unsigned integer! We can use the bitboard board representation for chess. There's 12 kinds of pieces in chess (6 for each color), so we only need 12 u64 to represent the entire board. each set bit (1) at index k of board p means there is p at the kth square on the board. We can also store the combination of pieces of each color to 2 separate u64s -- so we don't need to OR 6 numbers everytime we need the full occupancy.

Example of bitboard:

This will be position.bitboards.white_pawns after the move 1. e4. This bitboard can be represented as 0x1000ef00 as a single number -- or 0b10000000000001110111100000000. Credits to Tearth's great bitboard debugger.

This is the layout of squares in my engine (and most engines). This is convenient, because >> 1 moves right, << 1 moves left, >> 8 moves down, << 8 moves up, very intuitive.

Btw, Bit twiddling

To check if a square is set, we can do @truncate(u1, bb >> sq) in Zig.

To toggle a square, we can do bb ^= 1 << sq.

To set a square, we can do bb |= 1 << sq.

To clear a square, we can do bb &= ~(1 << sq), which means parts of bb that does not intersect with 1 << sq.

We also need a turn (0 for white and 1 for black), En Passant square (null or 0-63), Castling rights (4-bit bitflag, WhiteKing = 1, WhiteQueen = 2, BlackKing = 4, BlackQueen = 8, we can AND and OR them to get different combinations).

Move generation & attacks

You don't just play with a board. The program needs knowledge about which moves are legal.

With bitboards, it is easy to pre-compute attack tables for leapers (Pawn, King, Knight). With Zig, it is even easier to generate code at compile-time:

pub const KingDelta: [8][2]i8 = .{
    .{ -1, -1 },
    .{ -1, 0 },
    .{ -1, 1 },
    .{ 0, -1 },
    .{ 0, 1 },
    .{ 1, -1 },
    .{ 1, 0 },
    .{ 1, 1 },
};

pub const KingPatterns: [64]u64 align(64) = init: {
    @setEvalBranchQuota(64 * 8 * 3); // force compiler to compute this
    var patterns: [64]u64 align(64) = undefined;
    for (patterns) |*pt, idx| {
        const r: i8 = BB.rank_of(idx);
        const f: i8 = BB.file_of(idx);
        var bb: u64 = 0;
        for (KingDelta) |delta| {
            bb |= rank_file_to_bb(r + delta[0], f + delta[1]);
        }
        pt.* = bb;
    }
    break :init patterns;
};

And... Done! We just finished the move generator for Kings.
KingPatterns[sq] will be a bitboard containing all legal moves of the king.

Let's say sq is 20. (Refer to the image above for location)

This is KingPatterns[20], in which we can use bitscan to find the first square that is set and send it to the search function. bitscan can also be replaced with a single CPU instruction on most modern machines - ctz, or least-significant bit, or "count trailing zeroes". This makes sure bitboard is faster than representing the board with 2-dimensional arrays.

Ending

I will talk about some different techniques to generate slider (bishop, rook, queen) moves in the next post, since I barely figured out how to use Magic Bitboards myself. Normal algorithms would definitely work (which is what Avalanche has now) -- but Magic Bitboard signifies the true magic of bitboards -- computing all attacks with a single multiplication!

Avalanche can now complete basic perft positions (perft stands for Performance Test, testing the speed and accuracy of move generation) and is correct 99.9% of the time. There's some small bugs I'll fix while it is playing games and some performance issues (currently 2x slower than a C# Magic-bitboard generator).

Thank you for reading, and I'll see you in the next post.
github.com/SnowballSH/Avalanche

Go With Assembly

SnowballSH — Mon, 19 Apr 2021 02:40:21 +0000

Recently I just found out that you can use Go with Assembly. The Assembly isn't x86_64 or ARM, it is Go's special Assembly format, using syntax inspired by the Plan 9 Assembler.

This post is a short introduction for it.

Lets say we have some Go code.

package main

func add(x, y int64) int64 {
    return x + y
}

func main() {
    println(add(2, 3))
}

try online

Pretty simple, right? Prints "5\n" to stderr.

Now we want to power it up with Go's Assembler.
Create a file called add.s in the same directory with main.go. Use this code:

TEXT ·add(SB), $0-24
    MOVQ x+0(FP), BX
    MOVQ y+8(FP), BP
    ADDQ BP, BX
    MOVQ BX, ret+16(FP)
    RET

Let me explain the code:

TEXT tells the assembler that this is a function.
The syntax to declare a function is

TEXT package_name·function_name(SB), $frame_size-argument_size

Note that the dot is ·(Unicode 0xB7), not ..
In this example, TEXT ·add(SB), $0-24 declares a function called main·add with frame size of 0 (registers are enough) and argument size of 24 (3 * 8).

MOVQ x+0(FP), BX moves *x to the BX register.
MOVQ a, b moves a 64-bit value a to b. Q stands for quadword.
x+0(FP) accesses the argument x. symbol+offset(register) accesses the symbol from register using the offset. FP is the register for the function arguments.

Similarly, MOVQ y+8(FP), BP moves *y to the BP register.

ADDQ BP, BX adds BP and BX, storing the result to BX.

MOVQ BX, ret+16(FP) moves the result to the return register. +16 because we have a size of 24 and each argument used 8, so ret needs to use 16-23.

RET simply returns the last result ret.

With all those complex assembly explained, we can use it now.

Change the main.go to

package main

func add(x, y int64) int64

func main() {
    println(add(2, 3))
}

Make sure add.s is in the same directory as main.go.

Compile using go build or run with go run. You will still see 5 for the result!

In case you are wondering, you can print hello world with this:

#include "textflag.h"

DATA world<>+0(SB)/8, $"hello wo"
DATA world<>+8(SB)/4, $"rld "

GLOBL world<>+0(SB), RODATA, $12

TEXT ·hello(SB),$88-0
    SUBQ    $88, SP
    MOVQ    BP, 80(SP)
    LEAQ    80(SP), BP

    LEAQ    world<>+0(SB), AX 
    MOVQ    AX, my_string+48(SP)        
    MOVQ    $11, my_string+56(SP)
    MOVQ    $0, autotmp_0+64(SP)
    MOVQ    $0, autotmp_0+72(SP)
    LEAQ    type·string(SB), AX
    MOVQ    AX, (SP)
    LEAQ    my_string+48(SP), AX        
    MOVQ    AX, 8(SP)

    CALL    runtime·convT2E(SB)           
    MOVQ    24(SP), AX
    MOVQ    16(SP), CX                    
    MOVQ    CX, autotmp_0+64(SP)        
    MOVQ    AX, autotmp_0+72(SP)
    LEAQ    autotmp_0+64(SP), AX        
    MOVQ    AX, (SP)                      
    MOVQ    $1, 8(SP)                      
    MOVQ    $1, 16(SP)

    CALL    fmt·Println(SB)

    MOVQ 80(SP), BP
    ADDQ $88, SP
    RET

(Credit: davidwong.fr/goasm/hello)

According to some benchmark, using Go's assembler makes Go faster.
However, I don't recommend using it in real projects.

First, you lose Go's automatic garbage collecting. It will result in heavy memory usage if you do a lot of arrays using Assembly.

Second, you lose Go's simplicity. Go is aimed for simple and efficient, but Assembly is clearly not simple at all. A small add function turns into 6 lines of assembly code... You won't be able to complete a project using it.

Third, you lose the ability to debug and manage your project. Go's assembler provides bad error messages and the worst error I have encountered is unexpected return pc followed by 30 binary numbers. If you encounter a bug, you will probably spend 1 hour to fix it!

Despite all of that, Assembly in Go is still very interesting! :)

Resources:

davidwong.fr/goasm
Go doc for asm

[Part 0] Create your own programming language, in Python

SnowballSH — Tue, 26 Jan 2021 05:02:38 +0000

So, you think you have enough programming skills?

If so, why not do something really fun -- create your own programming language!

Who am I?

I am SnowballSH, a programmer and music producer. I have a decent experience in lexical analysing, parsing, and language designing. Gorilla is the best programming language I have made, in golang. Feel free to play it here online!

Why Python?

To be clear, I definitely do not suggest making programming languages in Python.

It is slow
It is dynamic -- more random errors will occur to the user

However, I chose Python to show you the basic principles and terms in language designing. Therefore, I think Python is clean and very good to explain basics.
I will document the types of almost every argument of functions so you can catch on with any static-typed programming languages too!

If you are wondering what is Python...

This is Python:

(Just kidding)

Uhh, OK, but I have absolutely no idea how a programming language like Python is made!

Well, if you know how one is made, why are you even here? We are here exactly talking about the fundamentals and basics.

Here is the process of an interpreted programming language:

Credit: Marc-André Cournoyer

The process of a compiled programming language:

Differences between "Compiled" and "Interpreted"

Compiled Language:

Contains Lexer and Parser
Has a compiler that compiles user's code into a low-level machine code. It can either be Web Assembly, Machine Code, Assembly, JVM, or even your custom byte code.
Pro: It is fast due to its runtime is based on the native machine
Con: Extremely hard to manage. The native commands and opcodes differ with the system/OS, therefore making it harder to add more features.

Interpreted Language:

Conatins Lexer and Parser
Has a special interpreter that accepts Abstract Syntax Trees (Code outline) and runs through it. By doing this way, there is no native runtime. Everything is ran by higher-level languages (e.g. Python, C++) directly.
Pro: Easy to manage. The language you are writing your language with has done the compliation for you -- you only have to manage one single case -- The language you are written in. This way you can add features pretty easily and fast by just using one function!
Con: It is slow due to it is ran on a high-level programming language. How slow is it? Well, you will see right below.

Most of the times, language makers create their own Virtual Machines and Bytecode (a series of instructions similar to assembly) too.
For example, Python is compiled to "Python Bytecode" using C, and "Python Bytecode" executes the bytecode using C too. This way the Bytecode is flattened and makes the language about 3x faster than normal.

Real World Examples

Interpreted

Compiles to Bytecode
- Python
- Ruby
- Java (Compiles to JVM Bytecode)
- C# (Compiles to CIL)
Fully Interpreted
- JavaScript
- R
- PHP

Compiled

Compiles to Machine Code
- C
- C++
- Ada
- Go/Golang
- Crystal (LLVM)
- Lisp
- Pascal
Compiles to Bytecode
- Java (as said, to JVM)
- C# (to CIL)

What we are going to make

For the sake of this tutorial (my first tutorial ever), we will be building a dynamic, object-oriented, fully-interpreted programming language.

Why?

As a said, an interpreted language is easy to manage.

Although it is slow, it can really show you guys the process of making a language easily!

If you have a strong opinion making a compiled language, I won't disagree -- in fact I love compiled languages. I chose it to be interpreted just to make everyone clear!

Conclusion

Thanks for reading until here! We will talk about the syntax of our language, and start up with lexical analyzer!