Chess engine in braifuck

[maksimKorzh]

Hi guys, we are starting a new crazy project - chess program in brainfuck programming language. Brainfuck is probably the most challenging language to choose to write a chess program in, but nevertheless we want to try. As far as hardware implementation of brainfuck CPU exists that means that in theory such a program could run on that sort of a computer.

ANY HELP IS APPRECIATED, even if it would be just kind words))).

We already know that:
- it's extremely difficult to code in brainfuck
- there's no proper way to implement recursion in brainfuck
- the program would be as slow as hell, especially on interpreter
- it's hard to believe that the project would ever be completed

What we intend it to be look like is a some sort of a very limited as well as simplified version of micro-Max by Harm Geert Muller.

We are now at the discussion stage, the repo for the project is available here:
https://github.com/maksimKorzh/chessfuck

[Michael Sherwin]

It is a bit too early for an April fools joke.

And it is of little (zero) interest to any serious chess programmer. Brainfuck cultist if there is such a thing might be ecstatic about the project though.

Might I suggest looking into the Euphoria interpreter for an exercise in eloquence instead of an exercise in futility. Euphoria has a Euphoria to C translator for the release version.

[flok]

Hi guys, we are starting a new crazy project - chess program in brainfuck programming language. Brainfuck is probably the most challenging language to choose to write a chess program in, but nevertheless we want to try. As far as hardware implementation of brainfuck CPU exists that means that in theory such a program could run on that sort of a computer.

ANY HELP IS APPRECIATED, even if it would be just kind words))).

We already know that:
- it's extremely difficult to code in brainfuck
- there's no proper way to implement recursion in brainfuck
- the program would be as slow as hell, especially on interpreter
- it's hard to believe that the project would ever be completed

What we intend it to be look like is a some sort of a very limited as well as simplified version of micro-Max by Harm Geert Muller.

We are now at the discussion stage, the repo for the project is available here:
https://github.com/maksimKorzh/chessfuck

This is so cool!
I wrote a compiler for brainfuck to ARM assembly (and a few other targets) a while ago. Maybe nice for comparing how it helds up.
https://vanheusden.com/misc/blog/2016-0 ... mpared.php

[Michael Sherwin]

There is a C equivalent.


(Program Start) char array[INFINITELY_LARGE_SIZE] = {0};
char *ptr=array;

brainfuck command C equivalent
> ++ptr;
< --ptr;
+ ++*ptr;
- --*ptr;
. putchar(*ptr);
, *ptr=getchar();
[ while (*ptr) {
] }

Add two numbers together example
++ Cell c0 = 2
> +++++ Cell c1 = 5
[ Start your loops with your cell pointer on the loop counter (c1 in our case)
< + Add 1 to c0
> - Subtract 1 from c1
] End your loops with the cell pointer on the loop counter

Equivalent C program to add two numbers together.

Code: Select all

int main() {
  char data[1000000000]; // do modern C compilers initialize to zero?
  char *ptr = data;
  *ptr++;  *ptr++;
  ++ptr;
  *ptr++;  *ptr++;  *ptr++;  *ptr++;  *ptr++;
  while(*ptr) {
  --ptr;  *ptr++;
  ++ptr; *ptr--;
  }
  return 0;
}

[odomobo]

// do modern C compilers initialize to zero?

Code: Select all

// This data is located in the bss segment, which is created and zero'd during program startup.
// Zeroing the bss segment of newly launched programs is an OS feature.
char zeroed[100];

int main() {
    // this data lives on the stack, so zeroing would have a cost and wouldn't be semantically-appropriate for c
    char uninitialized[100];
}

[odomobo]

Do you plan on using a minimax algorithm, a heuristic-based move selector, or simply a random move generator?

I'd recommend using a much simpler game as a proof-of-concept. Even if you do eventually implement chess, you might want to use a simple variant of chess (e.g. los alamos chess, with forced promotion to queen, and win by capturing the king, not by checkmate). This would greatly simplify the move generator, which would still be quite complicated.

Next, I'd recommend using some kind of macro system so you can write the code at a slightly higher level. That is, unless you're truly masochistic. I don't have any particular recommendation.

Make sure the brainfuck compiler you use doesn't have program-size limitations, as your program will be enormous. I imagine the default 30kb of program memory will be enough, but if not, you'll need to find an implementation which meets your needs.

You'll need to write a memory map of which variables will be located where in memory, and how they will be used. Using a macro processor will make it much easier to jump between memory locations, and make it possible to modify your memory map as required.

There may be no "proper" way to implement recursion, but it's possible. The way I know of is after your globals, to have a stack with frames of a defined size, with sentinels at each stack frame. Then it's possible to navigate between the current stack frame and the globals, by walking the sentinels. If you don't know what I'm talking about, I can give an example.

[hgm]

Wouldn't it be best to just write an interpreter for a somewhat higher-level languange in brainfuck, and then write the Chess program in that? It seems to me that writing directly in brainfuck you would basically be unrolling the interpreter loop zillions of times, leading to excessive boiler-plate code.

[Michael Sherwin]

Wouldn't it be best to just write an interpreter for a somewhat higher-level languange in brainfuck, and then write the Chess program in that? It seems to me that writing directly in brainfuck you would basically be unrolling the interpreter loop zillions of times, leading to excessive boiler-plate code.

If the op was serious I think that the motivation is to accomplish the 'impossible' human feat of actually writing a working chess engine on par with the functionality in Micromax. So it is not really about chess but rather the ego of the programmer. However, the op has not responded to any honest reply. It is like he is sitting back and watching the machinations his unrealistic proposal would cause. So it looks like the op was trolling.

But can it be done? Theoretically, yes. Practically, no. An engine at the functionality level of Micromax could take millions of commands to implement. Just not feasible in my opinion. On top of that writing it in a higher level language that outputs BF code would defeat the whole concept of, 'if it can be done in the first place'.

BF is all about the theoretical minimum instructions needed to program any task. Taking BF just a bit further could make it plausible in the real world. If the commands <>+- could be followed by a number and run on a BF spec core the core could be really tiny and a cpu could have thousands of cores. Then BF could stand for Best Friend.

[flok]

Wouldn't it be best to just write an interpreter for a somewhat higher-level languange in brainfuck, and then write the Chess program in that? It seems to me that writing directly in brainfuck you would basically be unrolling the interpreter loop zillions of times, leading to excessive boiler-plate code.

If the op was serious I think that the motivation is to accomplish the 'impossible' human feat of actually writing a working chess engine on par with the functionality in Micromax. So it is not really about chess but rather the ego of the programmer. However, the op has not responded to any honest reply. It is like he is sitting back and watching the machinations his unrealistic proposal would cause. So it looks like the op was trolling.

But can it be done? Theoretically, yes. Practically, no. An engine at the functionality level of Micromax could take millions of commands to implement. Just not feasible in my opinion. On top of that writing it in a higher level language that outputs BF code would defeat the whole concept of, 'if it can be done in the first place'.

BF is all about the theoretical minimum instructions needed to program any task. Taking BF just a bit further could make it plausible in the real world. If the commands <>+- could be followed by a number and run on a BF spec core the core could be really tiny and a cpu could have thousands of cores. Then BF could stand for Best Friend.

I know a guy who implemented the mandelbrot fractal in ascii in brainfuck.
And there's a c-to-brainfuck compiler on the web somewhere.

[maksimKorzh]

Do you plan on using a minimax algorithm, a heuristic-based move selector, or simply a random move generator?

I'd recommend using a much simpler game as a proof-of-concept. Even if you do eventually implement chess, you might want to use a simple variant of chess (e.g. los alamos chess, with forced promotion to queen, and win by capturing the king, not by checkmate). This would greatly simplify the move generator, which would still be quite complicated.

Next, I'd recommend using some kind of macro system so you can write the code at a slightly higher level. That is, unless you're truly masochistic. I don't have any particular recommendation.

Make sure the brainfuck compiler you use doesn't have program-size limitations, as your program will be enormous. I imagine the default 30kb of program memory will be enough, but if not, you'll need to find an implementation which meets your needs.

You'll need to write a memory map of which variables will be located where in memory, and how they will be used. Using a macro processor will make it much easier to jump between memory locations, and make it possible to modify your memory map as required.

There may be no "proper" way to implement recursion, but it's possible. The way I know of is after your globals, to have a stack with frames of a defined size, with sentinels at each stack frame. Then it's possible to navigate between the current stack frame and the globals, by walking the sentinels. If you don't know what I'm talking about, I can give an example.

Yes, minimax algorithm is the desired AI design to consider.

A simpler game as a proof-of-concept is just an amazing idea, thank's a lot, this would be the major direction in following work.

I'm truly masochistic, that's true. I have some reasons for that: I'm a self learner and going along the "from bottom to top" approach. I did VICE-like chess engine, than micro-Max-like, than the move generator of micro-Max in NASM assembly. Each time it was a bit "too high" level, so I wanted to dive deeper, hence brainfuck implementation idea. Guys, I'm sorry for this part of the answer for nobody probably cares about the reasons for doing this.

I've already implemented a brainfuck interpreter(forget speed) with 65536 bytes, 2 byte cell size. Thanks for the advise.

Memory map is needed for any brainfuck program, but thank's for mentioning this important point.

The recursion is one of the biggest problems actually so I would really appreciate any detailed examples, you'd help a lot.
The I was thinking to implement minimax is as follows: ++++++[//minimax_algorithm] where the number of pluses defines the search depth and the loop within square brackets is a move generator that returns(to some other cell) the best move on a given depth.