ASCII chess game

[tyama501]

I found ASCII chess game.

ASCII-Chess
https://github.com/Parigyan/ASCII-Chess

Forked and enhancement
https://github.com/matthew1796/ASCII-Chess

It uses unicode like
printf("\u2588\u2588\u2588\u2588\u2588\u2588\u2588");
for chess grid.

Currently our console cannot display unicodes,
but it may work if we replace with some other ascii codes
and using OpenWatcom?

[ghaerr]

Currently our console cannot display unicodes,
but it may work if we replace with some other ascii codes
and using OpenWatcom?

Can you get a screenshot of either of these programs running on Linux or FreeBSD?

It uses unicode like
printf("\u2588\u2588\u2588\u2588\u2588\u2588\u2588");
for chess grid.

Yes this should be easily converted - depending on the glyphs used. If the actual unicode glyphs exist on either PC-98 or IBM PC, then we should somewhat easily be able to handle converting 16-bit unicode to CP 437 (or PC-98's charset). If the glyphs do not exist, then the only option might be to draw the characters using Nano-X from a unicode font, which would be a lot of work.

[tyama501]

I have forked the matthew1796 fork and removed tests when ELKS is defined.

[tyama501]

Also I have noticed we need to shrink the board to fit it into 80x25 console...

[ghaerr]

Unfortunately it gets
SBLK OUT OF HEAP SPACE error

Make sure you have specified max heap with -maout-heap=0xffff in the link line?

[ghaerr]

Oh, I see from chmem you have already done that. I don't see when it gets the error, does that happen only during chess play, or at start?

[ghaerr]

Maybe I will try OpenWatcom later.

You should look at chess source and understand when it is doing malloc or realloc and for how much. If moving to OWC, you may still need special memory management outside of default heap like we're doing in 8086 toolchain. But it is important to know how much memory is being used and where. This can be turned on for the default malloc allocator by setting VERBOSE=1 in libc/malloc/Makefile and then running "sysctl malloc.debug=1" in shell script to see results on console.

[toncho11]

@tyama501 Maybe it will be fun to try compiling this chess game with the new enhanced toolchain from: https://github.com/ghaerr/8086-toolchain

[ghaerr]

@toncho11, yes that would be fun to try, as it uses multi-dimensional arrays and things like that that the C86 compiler could be tested with, but unfortunately (see below) there is little possibility this will run on C86 since it seems that it is a true memory hog and will need to be compiled large model and require multi-arena heap support. I would try playing around with this chess and C86, but since it won't run, probably no sense in doing so.

However, more ideas for chess games or other C programs to try with C86 are welcome! :)

[ghaerr]

@tyama501,

I quickly compiled up your chess game with max heap and ran it on ELKS, pulling in the debug malloc using the following extra source file added to the compilation:

/* stub to force inclusion of debug malloc (v7) */
#include <stdlib.h>

void *malloc(size_t size)
{
    return __dmalloc(size);
}

void free(void *ptr)
{
    __dfree(ptr);
}

void *realloc(void *ptr, size_t size)
{
    return __drealloc(ptr, size);
}

Unfortunately it gets
SBLK OUT OF HEAP SPACE error

I then ran it on the console after setting sysctl to turn on malloc debugging, and it comes up and runs, with the unicode output being interpreted by my macOS Terminal:

# sysctl malloc.debug=2
# ./a.out

                              PLAYER                             
           1      2      3      4      5      6      7      8    
       ----------------------------------------------------------
       |       ███████       ███████       ███████       ███████|
     A |   5   ██▌2▐██   4   ██▌7▐██   9   ██▌4▐██   2   ██▌5▐██| A
       |       ███████       ███████       ███████       ███████|
       |███████       ███████       ███████       ███████       |
     B |██▌1▐██   1   ██▌1▐██   1   ██▌1▐██   1   ██▌1▐██   1   | B
       |███████       ███████       ███████       ███████       |
       |       ███████       ███████       ███████       ███████|
     C |       ███████       ███████       ███████       ███████| C
       |       ███████       ███████       ███████       ███████|
       |███████       ███████       ███████       ███████       |
     D |███████       ███████       ███████       ███████       | D
       |███████       ███████       ███████       ███████       |
       |       ███████       ███████       ███████       ███████|
     E |       ███████       ███████       ███████       ███████| E
       |       ███████       ███████       ███████       ███████|
       |███████       ███████       ███████       ███████       |
     F |███████       ███████       ███████       ███████       | F
       |███████       ███████       ███████       ███████       |
       |       ███████       ███████       ███████       ███████|
     G |   1   ██▌1▐██   1   ██▌1▐██   1   ██▌1▐██   1   ██▌1▐██| G
       |       ███████       ███████       ███████       ███████|
       |███████       ███████       ███████       ███████       |
     H |██▌5▐██   2   ██▌4▐██   7   ██▌9▐██   4   ██▌2▐██   5   | H
       |███████       ███████       ███████       ███████       |
       ----------------------------------------------------------
           1      2      3      4      5      6      7      8    
                             COMPUTER                            

       '1'=>PAWN        '2'=>KNIGHT          '4'=>BISHOP
       '5'=>ROOK        '7'=>QUEEN           '9'=>KING

PLAYER 1 TYPE IN YOUR MOVE: 1 b1 c1

After that, the computer runs and I see from the output that the program does hundreds of mallocs (here is short list):

(11)malloc(  212) alloc   216, free     0, arena   216/  216
(11)malloc(   12) alloc   232, free    20, arena   232/  252
(11)malloc(  212) alloc   446, free    22, arena   446/  468
(11)malloc(   12) alloc   462, free     6, arena   462/  468
(11)malloc(  212) alloc   676, free     8, arena   676/  684
(11)malloc(   12) alloc   692, free    28, arena   692/  720
(11)malloc(  212) alloc   906, free    30, arena   906/  936
(11)malloc(   12) alloc   922, free    14, arena   922/  936
(11)malloc(  212) alloc  1136, free    16, arena  1136/ 1152
(11)malloc(   12) alloc  1152, free     0, arena  1152/ 1152
(11)malloc(  212) alloc  1366, free     2, arena  1366/ 1368
(11)malloc(   12) alloc  1382, free    22, arena  1382/ 1404
(11)malloc(  212) alloc  1596, free    24, arena  1596/ 1620
(11)malloc(   12) alloc  1612, free     8, arena  1612/ 1620
(11)malloc(  212) alloc  1826, free    10, arena  1826/ 1836
(11)malloc(   12) alloc  1842, free    30, arena  1842/ 1872
(11)malloc(  212) alloc  2056, free    32, arena  2056/ 2088
(11)malloc(   12) alloc  2072, free    16, arena  2072/ 2088
(11)malloc(  212) alloc  2286, free    18, arena  2286/ 2304
(11)malloc(   12) alloc  2302, free     2, arena  2302/ 2304
(11)malloc(  212) alloc  2516, free     4, arena  2516/ 2520
(11)malloc(   12) alloc  2532, free    24, arena  2532/ 2556
(11)malloc(  212) alloc  2746, free    26, arena  2746/ 2772
...
...
(11)malloc(  212) alloc 54036, free    36, arena 54036/54072
(11)malloc(   12) alloc 54052, free    20, arena 54052/54072
(11)malloc(  212) alloc 54266, free    22, arena 54266/54288
(11)malloc(   12) alloc 54282, free     6, arena 54282/54288
(11)malloc(  212) alloc 54496, free     8, arena 54496/54504
(11)malloc(   12) alloc 54512, free    28, arena 54512/54540
(11)malloc(  212) alloc 54726, free    30, arena 54726/54756
(11)malloc(   12) alloc 54742, free    14, arena 54742/54756
(11)malloc(  212) alloc 54956, free    16, arena 54956/54972
(11)malloc(   12) alloc 54972, free     0, arena 54972/54972
(11)malloc(  212) (11)SBRK 216 FAIL, OUT OF HEAP SPACE
 (no more mem) = NULL
alloc 54972, free     0, arena 54972/54972
(11)malloc(   12) alloc 54988, free    20, arena 54988/55008
(11)malloc(  212) (11)SBRK 216 FAIL, OUT OF HEAP SPACE
 (no more mem) = NULL
alloc 54988, free    20, arena 54988/55008
(11)malloc(   12) alloc 55004, free     4, arena 55004/55008
(11)malloc(  212) (11)SBRK 216 FAIL, OUT OF HEAP SPACE
 (no more mem) = NULL

Etc etc.

So it is very apparent that the program allocates way more than 55K of heap, which then causes it to run out of memory. The good news is that we now have our malloc/free under control so the program does not crash.

However, compiling this in large model under Watcom won't solve this problem - as the program needs more than 64k heap. Even moving to the current "arena malloc" code isn't going to immediately solve this problem because arena malloc, while working in large model with an external data segment heap, only allows for a single 64k heap, which will likely be used up by this program.

So the solution is 1) I need to extend the arena malloc to allow for multiple 64k arenas of memory to be allocated, and 2) the program will need to be compiled in large model using OWC. And even then we hope that the "AI.h" part of the program doesn't end up using way more memory than is available on real mode ELKS.

This will be a very good test program to get the multi-arena heap working :)

[tyama501]

Wow, nice to see the unicode on your macOS terminal.

Yes, the heap error occurs on the computer turn.

I thought I need to use far memory allocation, but nice to hear the arenas memory allocation idea.

Thank you!

[ghaerr]

Yes, it will need both far memory allocation as well the arena allocator that allows for automatic multiple heaps to be both simultaneously allocated and possibly released. I don't know as to how fast I can get to writing that enhancement, but now have it on my list. Until this is done I don't think we will be able to move forward on this particular chess game.

Also a nice enhancement might be trying to automatically convert unicode output to CP 437 (or PC-98 charset) to ELKS console. That could be messy and affect other programs, so we'd need a switch to turn it on and off. That enhancement should probably come after getting arena malloc working, unless you'd like to jump into it (amongst your nano-X and other ELKS projects :)

[tyama501]

8 x 8 chess board uses at least 24 lines if each box height is 3 lines,
so it is hard to fit it in the 25 line console with additional information and command line.
First, I will think about how playable screen can be.
(We might not need unicode at all)

Thank you.

[ghaerr]

8 x 8 chess board uses at least 24 lines if each box height is 3 lines,

Yes, I see what you mean. Probably not yet worth redoing though until we know that we can actually make the computer player side work - we don't know how much memory it needs/how deep the calculation tree goes for planning the next move. It is possible that it uses more memory than will ever be available. We could probably find that out by adding a total += size counter in the stub malloc routine and display that. I'll probably do that before attempting the multi-heap arena, since it's possibly a lot of work to add multiple heaps.

[toncho11]

I see that in Ai.h there are several loops:

for(z; z<=99; z++)

Maybe if you can put 99 as a variable for all of these and then reduce it to 10? Honestly there are not many comments and variable names are short and not very descriptive ...

[toncho11]

Or maybe here:

typedef struct node {
    struct node *head;
    list_elm* elist;
    struct node* array[100];

100 can be reduced?

[ghaerr]

Agreed the code is complex, I haven't studied it. I'm running with the debug malloc output and can see directly what the program is allocating, that's all.

What's happening is that the first move uses 22k, the next move uses way more - and runs out of memory. I am guessing that the algorithm likely uses more and more memory as it sees deeper into the possible next moves - in other words, a likely exponential increase in requirements as the game gets more complex. I'm no chess expert, but it would seem that the middle of chess game would be quite a bit more complicated to figure out than the first few turns. My quick conclusion is that, even with the forward look reduced from 100 to 10, the program runs out of 64K in the 2nd move. With a multi-heap arena, we might get 8 more of those 64k heaps to use (~480k perhaps?). I'm concluding that the program likely uses way more memory than that.

It is fun playing with it though and interesting to see the malloc debug output on a program that uses lots of memory, especially after spending lots of time writing the allocator :)

[ghaerr]

Oh and yes, the program appears to be calling free() after the first move and starting anew each time.

[ghaerr]

Ok @toncho11, I decreased the lookahead yet again in chess, from 10 to 3. I was able to play chess for 10-12 moves, kind of cool, before it ran out of memory again around 55k. At first it only used ~22k or so each move, but then that gradually started increasing, probably because the board was more complicated. So it still won't work, but it was kind of fun waiting for it to "think" through its next move, which even on my fast laptop and QEMU, took a couple seconds. It might be interesting nonetheless to have this program available just to see how slow it is on an 8088. I suspect it will be found to be quite slow!

I suppose it is possible that with very little lookahead this program could be made to not run out of memory with a multi-heap arena. It would be bad though if someone were in the middle of an intense game though and the computer crapped out!! So far it isn't crashing though, likely just picking the wrong move, since the NULL pointer dereference isn't (yet) happening to overwrite anything else important. The IA16 compiler usually puts constant string data (e.g, "quoted stings") in lower addresses of the data section. If this program were converted to large model (required for multi-heap), it would become dangerous, as then it could be found scribbling all over far memory on an unchecked NULL pointer (it never checks for NULL error return). The workaround for that case would be to exit on allocation error, but that's no fun in the middle of an exciting chess game!

[tyama501]

Hello all,

Thank you for doing so much work for this.

As it is written in README this game does not do so much look ahead.
The wait is just inserted by sleep to pretending thinking.

This game seems to be used as student study and it has been some bugs I have already fixed some of them and created issue(but I don't think it is maintained now)

I will look again it can be enhanced more when I have time.

[ghaerr]

The wait is just inserted by sleep to pretending thinking.

Oh my gosh I see it now, sleep(2)!!! LOL!!! So that is what I get for thinking it's thinking - when its actually sleeping.

[ghaerr]

@toncho11 was wondering whether this ASCII chess game might be able to be compiled and run using the new toolchain, so I tried it.

With a few hacks, our toolchain preprocessed, compiled, assembled and linked successfully. I didn't try running it because of the few problems, but they could be worked around with a little more work. Of course, the results will be very similar to the IA16 version: the program will quickly run out of memory.

Here were the hacked changes:

Gregs-MacBook-Pro1:8086-toolchain greg$ diff AI.*
89c89
<        int moves[8]; //XXX ={i+1,j,i+2,j,i+1,j+1,i+1,j-1};
---
>        int moves[8]={i+1,j,i+2,j,i+1,j+1,i+1,j-1};
123c123
<        int moves[8]; //XXX = {i-1,j,i-2,j,i-1,j+1,i-1,j-1};
---
>        int moves[8] = {i-1,j,i-2,j,i-1,j+1,i-1,j-1};
158c158
<     int moves[16]; //XXX = {i+2,j-1,i+2,j+1,i-2,j-1,i-2,j+1,i+1,j+2,i+1,j-2,i-1,j+2,i-1,j-2};
---
>     int moves[16] = {i+2,j-1,i+2,j+1,i-2,j-1,i-2,j+1,i+1,j+2,i+1,j-2,i-1,j+2,i-1,j-2};
336c336
<     int moves[16]; //XXX = {i+1,j,i+1,j+1,i+1,j-1,i,j-1,i,j+1,i-1,j,i-1,j-1,i-1,j+1};
---
>     int moves[16] = {i+1,j,i+1,j+1,i+1,j-1,i,j-1,i,j+1,i-1,j,i-1,j-1,i-1,j+1};
556,557c556,557
<     //if(maxim_val >= 0)
<        //XXXmaxim_val = 0.3*maxim_val;
---
>     if(maxim_val >= 0)
>        maxim_val = 0.3*maxim_val;
559c559
<     //XXXelse
---
>     else

and then produced the following warnings (which are fine):

"AI.h", line 678: warning [4]: definition of 'subshell' hides an earlier definition
"AI.h", line 694: warning [4]: definition of 'c' hides an earlier definition
"AI.h", line 713: warning [4]: definition of 'shell' hides an earlier definition
"AI.h", line 714: warning [4]: definition of 'c' hides an earlier definition
"AI.h", line 828: warning [2]: size of parameter 1 changed by prototype on function srand
"chess2.c", line 296: warning [4]: 'if' statement has no effect
"chess2.c", line 1152: warning [3]: escape ignored in sequence '\u'
"chess2.c", line 1152: warning [3]: escape ignored in sequence '\u'
"chess2.c", line 1152: warning [3]: escape ignored in sequence '\u'

Basically, C86 doesn't support:

• Initialization of variables from non-constant expressions. Workaround by initializing each element explicitly with statements. This might be a C99 feature, not sure. Otherwise its a GCC extension.
• Floating point. The program uses one multiply by float 0.3 and then converts back to int. Workaround by dividing by 3. C86 does support floating point but we've not turned it on because it requires hardware 8087+ FPU and possibly other issues.
• Unicode string constants using \u in string. No workaround, requires C86 compiler enhancement or recoding w/o unicode.

Overall, I'm pleasantly surprised that our toolchain got this far, and produced an executable!