NADYA2.0 engine progress

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
BlueStar
Posts: 16
Joined: Fri Apr 10, 2020 12:41 am
Full name: Craig Hoibakk

NADYA2.0 engine progress

Post by BlueStar » Fri Jun 19, 2020 1:39 am

Just wanted to give a quick update on my engine NADYA2.0. My engine is dedicated to my daughter, and while I've dabbled in dozens of programming languages my career, I've been coding in "C/C++" primarily (and professionally), since 1987. So I wanted to pick something new, challenging, and fun for my COVID-19 home chess project, and choose PROLOG (which wow, has come a long ways in 35 years). I choose Visual Prolog by PDC, because I was impressed with the compiler's speed, wanted to take advantage of the automatic backtracking, stricter type rules, and eventually dabble into chess machine learning to try and help make up for performance. I have decided, when I am ready, to release it under some sort of open permissive license. I have also decided to create NADYA chess completely on my own for a first playable version, and releasing the source will show it is 100% new. I have not reviewed anyone else's source code, however I have been doing extensive research on various algorithms, and am adopting the "lingo" as I slowly learn it (i.e. PERFT, bit-boards, etc). I implemented my own bit-board system before I even found out what bit-boards were. Then found out about "magic bit-boards" (I'm still working on/debugging my own magic generator and am so close (somehow my math is skipping spaces every so often which is not so good for sliding pieces, lol)--so in the interim I am using the "Copyright (C) 2007 Pradyumna Kannan" C++ implementation as a temporary drop-in replacement, and knowing my implementation will be much slower when I am finished debugging my own magic number generator, I set the #pragma settings such that it runs at its slowest possible configuration--although 64-bit). Until I have my own *original* implementation, I will be crediting "Pradyumna Kannan" for use of that code in my copyright, startup, and source, and the source will remain untouched. Luckily when I decided on bit-board representation, I chose LSB order, so was able to comment two lines of my own code, and replace with two lines of code to call the external DLL, and the whole code (prolog/and magics) worked perfect together the very first time.

NADYA2.0 supports castling, en-passant, 50 move limit, etc, so should be a fully legal chess engine when working (notice I don't use the word "completed" lol).

Some confusing and interesting facts about PROLOG that I believe gives me a reliability advantage and actually helps to greatly eliminate bugs and debugging time. In Prolog, a variable is considered either "bound" or "unbound". While there are ways in some implementations to get around this, once a variable is "bound" (i.e. assigned a value), it cannot be changed (i.e. no MAKE/UNMAKE move). Cant unmake something that is read-only. To help eliminate bugs and embrace the AI concepts(I use that extremely loosely, as I think that term is mostly misused) and language constructs like backtracking, etc. My compiler has the incredibly cool feature to also have the ability to have "delayed assignment to a constant" (i.e. calculated only when it is first referenced). I try to use this to my advantage when I can. Even in my prolog classes (which can have modifiable variables), I choose to only use them as constants once assigned. The one exception so far, is in my PERFT function (of which I'll post to this thread) with my "counter" class that counts moves, checks, checkmates, capture counts, etc.

I am just starting my PERFT testing, but I'm not posting any NPS counts counts after reading the earlier PERFT topic and realizing just how much slower my engine is (HINT: I have not yet reached even 1-million NPS). Fortunately, when I started NADYA2.0, I asked my daughter, "since it shares your namesake, do you want it to be based on speed or elegance?", she didn't hesitate and said elegance, so as I mention on the title screen, "She said elegance, so that will forever be it's goal." So I'm using that as my excuse for slower performance :P. HOWEVER, I'm not even going to attempt any but the simplest performance increases until I can pass all of my perft testing perfectly. Even the tiniest of changes in this critical code can introduce frustrating problems.

I have had to write a single external "C" DLL unfortunately, as my PROLOG compiler throws exceptions on all math overflows (which doesn't allow for calculating things like De Bruijn sequences, or magic bit-board keys). However, rather than write the whole De Bruijn code in "C", I only write the required functions (keeping the De Bruijn sequence in Prolog) as in:

UINT64 APIENTRY Mult_no_overflow(UINT64 A, UINT64 B)
{
return A * B;
}

I have also created a handful of conversion routines in my DLL, as type conversion (especially between different types, or sizes), it is pure torture, and found myself spending as much time trying to learn how to convert various types as writing the actual code. for instance converting a 64-bit integer to a 32-bit integer, or converting between a string/number. (This is probably my ignorance of the compiler I am using, so I'm not trying to fault the compiler). So most all my code is from scratch--and with the additional overhead of a massive PROLOG learning curve. It has now taken me longer to write just my move generator for NADYA2.0 than it took to write all of NADYA1.0 (which I now consider an ignorant learning excercise--that taught me just how exacting (i.e. PERFECT) a chess engine has to be). So I started from scratch (re-using my NADYA1.0 text GUI interface), and am building all of NADYA2.0 on top of a custom diagnostic framework (I'm SO glad I did!). Another reason it is slow--and it is hard to turn off my diagnostic code with the prolog compiler and my design implementation, so I might have to spend some time to "disconnect" my diagnostic framework somewhat, so I can compile with or w/o it, but again not worried about that until the the move generator passes perft testing.

Once I have a working engine, I will be enlisting additional help to start the forever project of improving it (especially in the area of board evaluation).

I will attach some sample source, and a few screen shots to this thread to give you a sample preview. However, if your like me when I first started prolog again, it might not make a lot of sense--but maybe give an example of me trying write for elegance. However, for you all, I believe the actual logic itself will make perfect sense. Sometimes, I feel like I'm writing in "steam-punk" (my description), because I'll have some beautiful pure prolog logic, and then a whole swath of bit-wise math that follows. The mixing of high level/low-level makes it look to me like what I call "steam-punk" code.

I will post an update and examples now again, and I know I will have a ton of questions. I don't anticipate a first playable version of NADYA2.0 for at least a few months at an absolute minimum however.

Cheers
C. Hoibakk.

BlueStar
Posts: 16
Joined: Fri Apr 10, 2020 12:41 am
Full name: Craig Hoibakk

Re: NADYA2.0 engine progress

Post by BlueStar » Fri Jun 19, 2020 1:57 am

My code uses my own variable naming convention I have memorized, and them listed in a comment section I will post later.

My PERFT predicates:

Code: Select all

clauses
    perft(Depth) = Counter :-
        Counter = counter::new(),
        perft(Depth, Counter).

clauses
    perft(0, Counter) :-
        Counter:inc(), !.

    perft(Depth, Counter) :-
        Move = for_each_move(),
        Board = make_move(Move),
        Counter:count_stats(Board, Move),
        Board:perft(Depth-1, Counter),
        fail.

    perft(_,_).
And some castle detection code:

Code: Select all

clauses
    %    this calculates the possible castle position based on the passed in color and board state
    castle_bits(C) = BB :-
        hasDomain(c_bb, KSMask), hasDomain(c_bb, QSMask),
        (C=white, KSMask=0x70, QSMask=0x1C, KPos=k_pos_w, ! ; C=black, KSMask=0x7000000000000000, QSMask=0x1C00000000000000, KPos=k_pos_b, !),
        if state():castle_mask(C, KS, QS) then
            (KS=true,
                get_tl(chess::flip_color(C))**KSMask = 0,
                get_pos_bits(0+KPos)**KSMask = 0, % removing the king pos should be zero or pieces are in the way
                KSV=KSMask, !
                ;
                KSV = 0),
            BB1 = KSV,
            (QS=true,
                get_tl(chess::flip_color(C))**QSMask = 0,
                get_pos_bits(0+KPos)**QSMask = 0, % removing the king pos should be zero or pieces are in the way
                QSV=QSMask, !
                ;
                QSV = 0),
            BB2 = QSV
        else
            BB1 = 0, BB2 = 0
        end if,
        BB = BB1++BB2.
Retrieving a move bit-board:

Code: Select all

clauses
    %   returns a bit_board object with all the possible moves for the passed in piece
    %   whatever returns from here HAS to include the en-passant moves for pawns!!!
    move_bb(Piece) = BBObj :-
        (Piece:color()=white, BBList=move_bbs_w, ! ; BBList=move_bbs_b),
        %  find the matching bit-board for the passed in piece/position
        TempBB = list::getMember_nd(BBList), TempBB:piece():pos()=Piece:pos(), % PERFORMANCE:  using backtracking is abysmally slow here, see TODO list.
        if Piece:type()=king then
            hasDomain(c_bb, V),
            %  XOR out any king move bits that -O-verlap the enemy TL, then add the possible castle bits
            O = TempBB:bits()**get_tl(flip_color(Piece:color())),
            V = (TempBB:bits()^^O) ++ castle_bits(Piece:color()),
            BBObj = bit_board::new(V)
        elseif Piece:type()=pawn then
            %  get the bit-board for a pawn including en-passant destination
            hasDomain(c_bb, DestBit),
            (DestBit = 1 << b_state:en_passant_capture_dest(), ! ; DestBit = 0),
            BBObj = bit_board::new(TempBB:bits() ++ DestBit)
        else
            BBObj = TempBB
        end if, !.
P.S. I'm FAR from being a prolog master, so take that into account when you read my rookie code. Also, I use the % PERFORMANCE comment to flag areas that need to be changed when the code is running accurately--and of course then be retested all over again, lol.

BlueStar
Posts: 16
Joined: Fri Apr 10, 2020 12:41 am
Full name: Craig Hoibakk

Re: NADYA2.0 engine progress

Post by BlueStar » Fri Jun 19, 2020 2:46 am

A startup / perft 3 screenshot:

Image

BlueStar
Posts: 16
Joined: Fri Apr 10, 2020 12:41 am
Full name: Craig Hoibakk

Re: NADYA2.0 engine progress

Post by BlueStar » Fri Jun 19, 2020 3:16 am

I like visual debugging, so NADYA2.0 supports individual move queries (including castling/en-passant moves), displays threat-lists, moves by color, captures, etc.

A move query with an en-passant board I use for testing (last move A7-A5):

Image

MOBMAT
Posts: 267
Joined: Sat Feb 04, 2017 10:57 pm
Location: USA

Re: NADYA2.0 engine progress

Post by MOBMAT » Fri Jun 19, 2020 5:09 am

Does your Prolog have the ability to allow you to create a UCI compatible engine?
i7-6700K @ 4.00Ghz (using 6 threads), EGTBs on PCI SSD
Benchmark: Stockfish 11 64 bmi2 (nps): 2067669

User avatar
mvanthoor
Posts: 241
Joined: Wed Jul 03, 2019 2:42 pm
Full name: Marcel Vanthoor

Re: NADYA2.0 engine progress

Post by mvanthoor » Fri Jun 19, 2020 6:52 pm

This is beautiful :)

I love seeing engines being written in any language that isn't C or C++. Not that I dislike those languages; I've used C extensively in the past, and if Rust hadn't existed, there would have been a great chance of me using C for my engine. It's just... plain old, same old, engine nr. 752 in C/C++.

You are doing EXACTLY the same thing as I've been doing in Rust...
- Learning a new language (I wrote and rewrote parts of my engine several times as I learned more about Rust).
- Building your own diagnostics/development framework (in my case called "extra", but I think I'll rename it "diag" or "dev")
- You have a text user interface very similar to that in my engine (but yours is in color)
- You're in about the same state of development.

The only drawback I'm seeing is speed... If your engine runs at 1 million leaves per second in Perft, it's going to be at a huge disadvantage against any other engine. Every doubling in speed, be it by using a faster CPU or faster code, gains about 50 ELO (if I remember correctly; just assume for the sake of argument it's correct).

An engine that runs at 40 million leaves/sec is 40x faster, and thus will have more than five speed doublings (1->2->4->8->16->32), so if the implementations are EXACTLY the same, the faster engine will be at least 250 or 300 ELO stronger.

Is Prolog interpreted? (Even if it compiles into an executable, it can still be interpreted... with the code and the interpreter in one EXE.)

Personally, I can't use slow programming languages. I've worked in embedded software engineering, writing tiny but very powerful and fast programs in C, that could be completely static and standalone in one executable. I couldn't use anything slower than C, or a language such as C# .NET Core that creates an executable which needs you to distribute a huge framework along with it, consisting of a lot of files.

I'll have to take a look at Prolog. I'm curious now... and you're sure that you can't write a multiplier with overflow? Rust has specialized functions for specifically this case.

BlueStar
Posts: 16
Joined: Fri Apr 10, 2020 12:41 am
Full name: Craig Hoibakk

Re: NADYA2.0 engine progress

Post by BlueStar » Fri Jun 19, 2020 8:53 pm

MOBMAT wrote:
Fri Jun 19, 2020 5:09 am
Does your Prolog have the ability to allow you to create a UCI compatible engine?
I don't see why not. After taking a cursory review of the UCI specifications, I see nothing that would prohibit me from building a UCI interface. I've always considered my text GUI kind of a "throw-away". I'll never get rid of it, but I will probably just make it part of my diagnostic system, useful mostly for debugging.

Cheers,
C Hoibakk.

BlueStar
Posts: 16
Joined: Fri Apr 10, 2020 12:41 am
Full name: Craig Hoibakk

Re: NADYA2.0 engine progress

Post by BlueStar » Fri Jun 19, 2020 9:37 pm

mvanthoor wrote:
Fri Jun 19, 2020 6:52 pm
You are doing EXACTLY the same thing as I've been doing in Rust...
Yes, I've been following your posts regarding rustic! So cool. You are one of the bloke's that made me decide not to yet publish my perft timings :lol: since as you say we are close in development progress!
mvanthoor wrote:
Fri Jun 19, 2020 6:52 pm
The only drawback I'm seeing is speed...
Yes, I have an uphill battle, however, I still have many areas I've identified that will greatly improve my performance. Plus I have not yet started any profile testing. I'm stubborn and sticking with "get it right, then get it fast". Of course it will never reach the raw speed of pure "C" (partly do to the the backtracking mechanics and overhead of predicate horn logic in Prolog). However, some of those language features will eventually give me some small advantages when it comes to maintainability, and I'm hoping I will eventually make up for some speed with machine learning and pattern recognition. There are also some major advancements starting to be implemented in some advanced Prolog compilers (i.e. "boxing", better parallel processing [we'll see], etc).

Also, I'm not trying to build a program to beat Stockfish, Lc0, Crafty, etc. I want to play them for sure, and hopefully let my program eventually "learn" from playing them. But even if I were to use all my career skills to build an engine completely in Assembly (Can't wait to look at the new Sargon!), it would still be years before I would have an adequate understanding of "computer" chess mechanics to build anything with a smart enough board evaluator. We'll see :)
mvanthoor wrote:
Fri Jun 19, 2020 6:52 pm
Is Prolog interpreted? (Even if it compiles into an executable, it can still be interpreted... with the code and the interpreter in one EXE.)
Visual Prolog is definately a true compiler (how optimized, I'm not sure). It is one of the reasons, Visual Prolog ends up being so strongly typed as opposed to other Prolog interpreters. Oh, also, it can directly link to static lib files created by Visual Studio C++ (un-managed code), so If I wanted to write more of the procedural code in "C", I could.
mvanthoor wrote:
Fri Jun 19, 2020 6:52 pm
I'll have to take a look at Prolog. I'm curious now... and you're sure that you can't write a multiplier with overflow? Rust has specialized functions for specifically this case.
Yes. I've interacted with the lead developer at PDC who helped explain the limitations.

As I mentioned, I've been eyeing your progress on TalkChess, and enjoy seeing the progress you are making with Rustic. Can't wait to play you eventually. If even if Rustic ends up being 20 times faster. :)

Cheers,
C Hoibakk.

BlueStar
Posts: 16
Joined: Fri Apr 10, 2020 12:41 am
Full name: Craig Hoibakk

Re: NADYA2.0 engine progress

Post by BlueStar » Thu Jul 16, 2020 12:46 am

I didn't realize how much of an obsession this would become. The move generator in NADYA2.0 now appears to be accurate. Start 7, kiwipete 5, etc..

I regret adding "bulk counting" to my perft/divide predicate -- in my case it complicated the elegance/simplicity of the original code (due to my method of counting extra stats) for a very small increase in speed. I'm planning on pulling it back out.

My "perft/divide" collects (counts) all of the statistics shown here (https://www.chessprogramming.org/Perft_ ... l_Position). However, I gather additional statistics/counts. One of the other reasons I'm gathering as much possible statistical data as possible (or rather the ability to detect as many important statistical facts as possible), is that, when I add a simple NLP module the move generator will in essence become a really cool chess query database. This is easily done in Prolog. For instance, something like a purely fictional query like: "for fen("INSERT FENSTRING HERE") show pawn promotion with capture to Knight with checkmate maxdepth(8)". [long wait... then outputs every move path to fulfill the goal].

I did some research on WinBoard as someone suggested, and realized the simplicity of the interface will make it super easy to support based on my console text IO. I already have my engine loading in WinBoard (receiving the "xboard" command).

Next:

1. perform some cleanup / code readability / elegance.
2. move the super-simple NADYA1 brute-force board evaluator into the NADYA2.0 evaluator interface.
3. test start to end-game, with manual entry of machine move recommendations
4. implement "xboard" commands / and non-prompt entry mode.
5. ...

Tony P.
Posts: 119
Joined: Sun Jan 22, 2017 7:30 pm
Location: Russia

Re: NADYA2.0 engine progress

Post by Tony P. » Thu Jul 16, 2020 4:42 am

Wow, I'd never consider writing a whole chess engine in a logic programming language :o There are, however, important chess tasks that this approach would excel at, such as the verification of either side's ability to secure at least a draw, which would increase the accuracy of evals in training sets; and the procedural generation of positions with forced wins, draws or tactics giving an almost decisive advantage (e.g. over +2.0) at any game stage, allowing both to create a puzzle generator with more diverse and personalized output than the existing puzzle DBs, and to speed up the reinforcement learning of a full chess engine.

The test-time speed is what's stopping me and probably many others from considering Prolog as a language to write or fork a complete engine in. Out of curiosity, what other languages did you consider, and why did you reject them?

In particular, have you looked into Nim? I haven't written in it yet, but I've done some search about it on the interwebs :lol:

Statically typed. Compiles to C, C++, Obj-C and/or JS.

Speed: competitive, especially because procedures that are too slow and critical to performance can be rewritten in C(/C++) and called relatively easily.

Machine learning: Arraymancer, Nimtorch.
Multithreading: Weave.

Memory management: GC :( with many strategies to choose from, of which, Automatic Reference Counting introduced in v1.2 is deterministic and looks promising.

Existing chess engines (for those who don't like to greenfield): Chrysaora is in active development but GPLed :P Donna-Nim is MIT-licensed, but it was last updated 5 years ago. The Go version of Donna is rated ~2600 on CCRL 40/15 (on 1 core), so there's a lot of room for improvement. There's also an engine with its own GUI.

Someone, please discourage me :lol:
P.S. I'm excited about Rust too.

Post Reply