Chess engine in braifuck

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
maksimKorzh
Posts: 81
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Chess engine in braifuck

Post by maksimKorzh » Mon Mar 04, 2019 8:39 am

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
Posts: 3040
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Chess engine in braifuck

Post by Michael Sherwin » Mon Mar 04, 2019 12:27 pm

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

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. :D

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.
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

User avatar
flok
Posts: 159
Joined: Tue Jul 03, 2018 8:19 am
Full name: Folkert van Heusden
Contact:

Re: Chess engine in braifuck

Post by flok » Mon Mar 04, 2019 2:47 pm

maksimKorzh wrote:
Mon Mar 04, 2019 8:39 am
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
www.vanheusden.com: Micah / Embla / PuppetMaster / DeepBrutePos / Pos / Feeks

Michael Sherwin
Posts: 3040
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Chess engine in braifuck

Post by Michael Sherwin » Mon Mar 04, 2019 8:30 pm

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;
}
:mrgreen:
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

odomobo
Posts: 59
Joined: Thu Jul 05, 2018 11:09 pm
Location: Chicago, IL
Full name: Josh Odom

Re: Chess engine in braifuck

Post by odomobo » Mon Mar 04, 2019 10:47 pm

Michael Sherwin wrote:
Mon Mar 04, 2019 8:30 pm
// 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
Posts: 59
Joined: Thu Jul 05, 2018 11:09 pm
Location: Chicago, IL
Full name: Josh Odom

Re: Chess engine in braifuck

Post by odomobo » Tue Mar 05, 2019 1:45 am

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.

User avatar
hgm
Posts: 23481
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Chess engine in braifuck

Post by hgm » Tue Mar 05, 2019 6:42 am

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
Posts: 3040
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Chess engine in braifuck

Post by Michael Sherwin » Tue Mar 05, 2019 2:30 pm

hgm wrote:
Tue Mar 05, 2019 6:42 am
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 hate if statements. Pawns demand if statements. Therefore I hate pawns.

User avatar
flok
Posts: 159
Joined: Tue Jul 03, 2018 8:19 am
Full name: Folkert van Heusden
Contact:

Re: Chess engine in braifuck

Post by flok » Tue Mar 05, 2019 2:35 pm

Michael Sherwin wrote:
Tue Mar 05, 2019 2:30 pm
hgm wrote:
Tue Mar 05, 2019 6:42 am
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.
www.vanheusden.com: Micah / Embla / PuppetMaster / DeepBrutePos / Pos / Feeks

maksimKorzh
Posts: 81
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: Chess engine in braifuck

Post by maksimKorzh » Wed Mar 06, 2019 10:46 am

odomobo wrote:
Tue Mar 05, 2019 1:45 am
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.

Post Reply