Chess engine in braifuck

[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.

[maksimKorzh]

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.

Thanks for your feedback, Mr.Muller, it's as always the great honor for me to get your reply to some of my posts, especially such a crazy one.

Yes, the idea of "somewhat higher-level languange in brainfuck" has been coming to my mind quite a several times, so that's a kind of the major alternative approaches. Did you mean to write in brainfuck something assembly-like involving stack implementation with goto label statements and simple arithmetical/logical operators?

[maksimKorzh]

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.

Hi Mike, it seems like you feel insulted. I didn't really mean to insult you and the reason for your first posts were left without answer is because first: I had some internet connection troubles for a couple of days and second: your posts didn't contain any questions. But still you make me feel a bit guilty. The op wasn't ever meant to be a trolling. I can't consider myself as a chess programmer even though accomplished 3 chess programs in my life(all very poor from the strength perspective, involving only the very basic beginner's techniques for search and evaluation(my original aim was always minimalism in terms of design parts as well as code size)) but this doesn't mean that "he is sitting back and watching the machinations his unrealistic proposal would cause". I just thought that writing a few real chess programs(I've been posting about and had numerous discussions here that helped me a lot especially in implementing the quiescence search(thanks to HGM and Marco Belli)) did make me the part of this great community and gave me the right to share my project idea with the community, so I have no idea why do you consider my op to be the trolling. I apologize again if I have ever insulted anybody here, I didn't mean that and I'm just looking for some helpful tips.

"So it is not really about chess but rather the ego of the programmer"
Yes, it's not really about chess, BUT it's not about my ego either(It could've been so if I did already post the source code of such a program in brainfuck). One of the main inner motivasions to start this project was to make it a COMMUNITY project. Originally I've posted the idea to right a chess program in brainfuck at reddit's brainfuck community. It has been hanging there for a while and then some people desired to join others - just to follow the project. So I want to learn to work in a team. I have some experience in maintaining one-person projects but I don't want this bf chess to be one of them, I want the collaboration instead and you might argue that the idea for this project is not best fits the purpose of learning to work in team, but my original idea was to invent the project which stays the most far from the realife/business projects in order to not being disturbed by the common problems there. Well may be I'm wrong. Hope it's a bit more clear now, Mike, I just didn't want to post these of my thoughts here because they doesn't relate to chess programming, so question was about the "implementation details", so as far as I've been consulted by brainfuck programmers, now it's time to consult from chess programmers, hence I'm here.

"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."

And this is probably the most useful REAL reply to my op, even though it replies to HGM... And for this part I'd like to thank you, Mike, for providing reasonable information along with your decent thoughts is much more helpful compare to the "April fool's day"

[Michael Sherwin]

Hi Mike, it seems like you feel insulted. I didn't really mean to insult you and the reason for your first posts were left without answer is because first: I had some internet connection troubles for a couple of days and second: your posts didn't contain any questions. But still you make me feel a bit guilty. The op wasn't ever meant to be a trolling. I can't consider myself as a chess programmer even though accomplished 3 chess programs in my life(all very poor from the strength perspective, involving only the very basic beginner's techniques for search and evaluation(my original aim was always minimalism in terms of design parts as well as code size)) but this doesn't mean that "he is sitting back and watching the machinations his unrealistic proposal would cause". I just thought that writing a few real chess programs(I've been posting about and had numerous discussions here that helped me a lot especially in implementing the quiescence search(thanks to HGM and Marco Belli)) did make me the part of this great community and gave me the right to share my project idea with the community, so I have no idea why do you consider my op to be the trolling. I apologize again if I have ever insulted anybody here, I didn't mean that and I'm just looking for some helpful tips.

"So it is not really about chess but rather the ego of the programmer"
Yes, it's not really about chess, BUT it's not about my ego either(It could've been so if I did already post the source code of such a program in brainfuck). One of the main inner motivasions to start this project was to make it a COMMUNITY project. Originally I've posted the idea to right a chess program in brainfuck at reddit's brainfuck community. It has been hanging there for a while and then some people desired to join others - just to follow the project. So I want to learn to work in a team. I have some experience in maintaining one-person projects but I don't want this bf chess to be one of them, I want the collaboration instead and you might argue that the idea for this project is not best fits the purpose of learning to work in team, but my original idea was to invent the project which stays the most far from the realife/business projects in order to not being disturbed by the common problems there. Well may be I'm wrong. Hope it's a bit more clear now, Mike, I just didn't want to post these of my thoughts here because they doesn't relate to chess programming, so question was about the "implementation details", so as far as I've been consulted by brainfuck programmers, now it's time to consult from chess programmers, hence I'm here.

"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."

And this is probably the most useful REAL reply to my op, even though it replies to HGM... And for this part I'd like to thank you, Mike, for providing reasonable information along with your decent thoughts is much more helpful compare to the "April fool's day"

I don't know if I should apologise or say your welcome. Do I feel insulted? Maybe at some level that might be the case. My focus has always been on speed of execution. BF is insulting not to me but rather to the goals of any serious programmer which is to write smaller faster code within the limits that good programming style permits. BF to programming is like the AC is to Christianity. And to me that is not an exaggeration. I too wrote an assembly language move generator for a look up style generator like in GNU Chess 4. So we have that in common! On my system that is about half as fast as an i9-9900k my assembler move generator does bench 6 at 75 million+ nodes per second while making and unmaking all generated moves and doing no cache counting. Here is the code that generates and records the white queen moves and captures.

Code: Select all

; white move generator - gets the first piece in the list of pieces and jumps to that piece
wmg:          push        ebp
                  push        edi
                  push        esi
                  mov         ebp,[ply]
                  mov         eax,[first+ebp*4]
                  mov         [lis+ebp*4],eax
                  mov         edi,[nxt]
                  jmp         [ptmf+edi*4]
                  
;white next piece
wnxtp:       mov         edi,[nxt+edi*4]
                 jmp         [ptmf+edi*4]
        
;white queen move - looks up the first to-square in a table and jumps through another table
wqm:        mov         ecx,[ps+edi*4]
                mov         esi,[qol+ecx*4]
                movsx      ebx,[qns+esi+ecx]
                mov         edx,[brd+ebx*4]
                jmp         [wqmf+edx*4]
        
;white queen move record move        
wqmrm:   mov         [tree.fsq+eax*8],cl
               mov         [tree.tsq+eax*8],bl
               mov         [tree.typ+eax*8],QMOV
               inc           eax
               movsx      ebx,[qns+esi+ebx]
               mov         edx,[brd+ebx*4]
               jmp         [wqmf+edx*4]
              
;white queen move record capture              
wqmrc:   mov          [tree.fsq+eax*8],cl
              mov          [tree.tsq+eax*8],dl
              mov          [tree.typ+eax*8],QCAP
              inc            eax
 
;white queen move next direction            
wqmnd:  movsx      ebx,[qnd+esi+ebx]
              mov         edx,[brd+ebx*4]
              jmp         [wqmf+edx*4]

The data table wqmf (white queen move function) directs the jump to record a move, a capture or get the first to-square of the next direction. All the program flow is controlled in this way. And that includes the make move and unmake move routines as well.

Yes this somewhat involves my ego. I do not deny that. However, it is also a quest for the fastest possible code. Now, if this is what your project was all about I'd be in 100%!

[maksimKorzh]

Hi Mike, it seems like you feel insulted. I didn't really mean to insult you and the reason for your first posts were left without answer is because first: I had some internet connection troubles for a couple of days and second: your posts didn't contain any questions. But still you make me feel a bit guilty. The op wasn't ever meant to be a trolling. I can't consider myself as a chess programmer even though accomplished 3 chess programs in my life(all very poor from the strength perspective, involving only the very basic beginner's techniques for search and evaluation(my original aim was always minimalism in terms of design parts as well as code size)) but this doesn't mean that "he is sitting back and watching the machinations his unrealistic proposal would cause". I just thought that writing a few real chess programs(I've been posting about and had numerous discussions here that helped me a lot especially in implementing the quiescence search(thanks to HGM and Marco Belli)) did make me the part of this great community and gave me the right to share my project idea with the community, so I have no idea why do you consider my op to be the trolling. I apologize again if I have ever insulted anybody here, I didn't mean that and I'm just looking for some helpful tips.

"So it is not really about chess but rather the ego of the programmer"
Yes, it's not really about chess, BUT it's not about my ego either(It could've been so if I did already post the source code of such a program in brainfuck). One of the main inner motivasions to start this project was to make it a COMMUNITY project. Originally I've posted the idea to right a chess program in brainfuck at reddit's brainfuck community. It has been hanging there for a while and then some people desired to join others - just to follow the project. So I want to learn to work in a team. I have some experience in maintaining one-person projects but I don't want this bf chess to be one of them, I want the collaboration instead and you might argue that the idea for this project is not best fits the purpose of learning to work in team, but my original idea was to invent the project which stays the most far from the realife/business projects in order to not being disturbed by the common problems there. Well may be I'm wrong. Hope it's a bit more clear now, Mike, I just didn't want to post these of my thoughts here because they doesn't relate to chess programming, so question was about the "implementation details", so as far as I've been consulted by brainfuck programmers, now it's time to consult from chess programmers, hence I'm here.

"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."

And this is probably the most useful REAL reply to my op, even though it replies to HGM... And for this part I'd like to thank you, Mike, for providing reasonable information along with your decent thoughts is much more helpful compare to the "April fool's day"

I don't know if I should apologise or say your welcome. Do I feel insulted? Maybe at some level that might be the case. My focus has always been on speed of execution. BF is insulting not to me but rather to the goals of any serious programmer which is to write smaller faster code within the limits that good programming style permits. BF to programming is like the AC is to Christianity. And to me that is not an exaggeration. I too wrote an assembly language move generator for a look up style generator like in GNU Chess 4. So we have that in common! On my system that is about half as fast as an i9-9900k my assembler move generator does bench 6 at 75 million+ nodes per second while making and unmaking all generated moves and doing no cache counting. Here is the code that generates and records the white queen moves and captures.

Code: Select all

; white move generator - gets the first piece in the list of pieces and jumps to that piece
wmg:          push        ebp
                  push        edi
                  push        esi
                  mov         ebp,[ply]
                  mov         eax,[first+ebp*4]
                  mov         [lis+ebp*4],eax
                  mov         edi,[nxt]
                  jmp         [ptmf+edi*4]
                  
;white next piece
wnxtp:       mov         edi,[nxt+edi*4]
                 jmp         [ptmf+edi*4]
        
;white queen move - looks up the first to-square in a table and jumps through another table
wqm:        mov         ecx,[ps+edi*4]
                mov         esi,[qol+ecx*4]
                movsx      ebx,[qns+esi+ecx]
                mov         edx,[brd+ebx*4]
                jmp         [wqmf+edx*4]
        
;white queen move record move        
wqmrm:   mov         [tree.fsq+eax*8],cl
               mov         [tree.tsq+eax*8],bl
               mov         [tree.typ+eax*8],QMOV
               inc           eax
               movsx      ebx,[qns+esi+ebx]
               mov         edx,[brd+ebx*4]
               jmp         [wqmf+edx*4]
              
;white queen move record capture              
wqmrc:   mov          [tree.fsq+eax*8],cl
              mov          [tree.tsq+eax*8],dl
              mov          [tree.typ+eax*8],QCAP
              inc            eax
 
;white queen move next direction            
wqmnd:  movsx      ebx,[qnd+esi+ebx]
              mov         edx,[brd+ebx*4]
              jmp         [wqmf+edx*4]

The data table wqmf (white queen move function) directs the jump to record a move, a capture or get the first to-square of the next direction. All the program flow is controlled in this way. And that includes the make move and unmake move routines as well.

Yes this somewhat involves my ego. I do not deny that. However, it is also a quest for the fastest possible code. Now, if this is what your project was all about I'd be in 100%!

Thanks for sharing your assembly snippet. Your nps speed is really amazing especially bearing in mind that no hashing has been involved.

I got your chess programming path, Mike, and now I can realize that the poor bf performance is an insult itself to the speedwise approach. I knew that this forum mostly consists of very solid programmers who is not going to be interested in my project, but on the other hand this thread already has quite a few useful tips and ideas. I was also hoping to get some feedback from HGM which is very important for me due to his great skills in optimising code sizewise.

Thank's for diving into explanations of my previous post, for your attention and tips.

[odomobo]

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.

So imagine that you have a globals section of 100 cells, and each stack frame for your recursive function is 10 cells. For practical reason, you'd want your stack to start at cell 100 and grow to the right. The first cell of the stack frame would be a sentinel value -- every stack frame would have a 1, and the value before the first stack frame would have a 0, and there would similarly be a 0 after the last stack frame. This would allow you to know once you're finished recursing, and it will also give a mechanism to access globals from the recursive function.

Next, you need a way to explicitly encode function state on the stack. This is similar to the way you can implement coroutines in c:

Code: Select all

int coroutine(int nextState)
{
    switch(nextState){
    case 0:
        if (foo()) {
            bar();
            return 1;
    case 1:
            baz();
        } else {
            quz();
            return 2;
    case 2:
            qux();
        }
        zzz();
    }
}

So, you'd end up doing something like this, but in brainfuck:

Code: Select all

struct frame {
    int sentinel;
    int state;
    // other data
};

void recursion(frame *f)
{
    while (f->sentinel)
    {
        if (f->state == 0)
        {
            // logic before calling self recursively
            
            if (recurse)
            {
                f->state = 1;
                f++; // same as shifting to the next stack frame
                f->sentinel = 1;
                f->state = 0;
            }
            if (!recurse)
            {
                f->state = 1;
            }
        }
        if (f->state == 1)
        {
            // logic after calling self recursively
            
            f->sentinel = 0;
            f--; // the previous stack frame already has its state set up
        }
    }
}

Note that you will need additional states for boundaries around while loops which are bisected by recursion.

I.e.

Code: Select all

while (additional moves)
{
    recurse();
}

This is because at the end of the while loop, you have to explicitly jump to the start, by setting a state. You can think of setting states as explicitly enumerating gotos.

If you have troubles with this, I'd recommend writing some c code in this manner to become familiar with it.

How to go from the current stack frame to the globals, and back?

Code: Select all

// in current stack frame
while (f->sentinel) f--;
// now in globals
f++;
while (f->sentinel) f++;
f--;
// now in current stack frame

[maksimKorzh]

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.

So imagine that you have a globals section of 100 cells, and each stack frame for your recursive function is 10 cells. For practical reason, you'd want your stack to start at cell 100 and grow to the right. The first cell of the stack frame would be a sentinel value -- every stack frame would have a 1, and the value before the first stack frame would have a 0, and there would similarly be a 0 after the last stack frame. This would allow you to know once you're finished recursing, and it will also give a mechanism to access globals from the recursive function.

Next, you need a way to explicitly encode function state on the stack. This is similar to the way you can implement coroutines in c:

Code: Select all

int coroutine(int nextState)
{
    switch(nextState){
    case 0:
        if (foo()) {
            bar();
            return 1;
    case 1:
            baz();
        } else {
            quz();
            return 2;
    case 2:
            qux();
        }
        zzz();
    }
}

So, you'd end up doing something like this, but in brainfuck:

Code: Select all

struct frame {
    int sentinel;
    int state;
    // other data
};

void recursion(frame *f)
{
    while (f->sentinel)
    {
        if (f->state == 0)
        {
            // logic before calling self recursively
            
            if (recurse)
            {
                f->state = 1;
                f++; // same as shifting to the next stack frame
                f->sentinel = 1;
                f->state = 0;
            }
            if (!recurse)
            {
                f->state = 1;
            }
        }
        if (f->state == 1)
        {
            // logic after calling self recursively
            
            f->sentinel = 0;
            f--; // the previous stack frame already has its state set up
        }
    }
}

Note that you will need additional states for boundaries around while loops which are bisected by recursion.

I.e.

Code: Select all

while (additional moves)
{
    recurse();
}

This is because at the end of the while loop, you have to explicitly jump to the start, by setting a state. You can think of setting states as explicitly enumerating gotos.

If you have troubles with this, I'd recommend writing some c code in this manner to become familiar with it.

How to go from the current stack frame to the globals, and back?

Code: Select all

// in current stack frame
while (f->sentinel) f--;
// now in globals
f++;
while (f->sentinel) f++;
f--;
// now in current stack frame

Thanks for such a detailed and clear explanations, odomobo, your idea is just brilliant.

[dmc75287]

That's just crazy enough to be amazing! Amazingly wonderful! I am totally on board.

[dmc75287]

We program in brainfuck because it is difficult and a challenge. There is a way to do it, it may take decades but we're not in a hurry.

[flok]

any news?