Proper Chess Engine with networked CPUs & LAN play

[frisian]

Numpty is written in freebasic
https://sites.google.com/site/numptyche ... s-versions

The source code as approx 6000 lines long so i cant paste it here. It has some winboard stuff in it to

move format is e2e4 no spaces

I have tried NUMPTY 0.7pr and N O m e g a (N_O_m_e_g_a) the successor of numpty to compile with FB but all attempts with (fblite, qb and deprecated) stop with the message “.... error 122: Too many errors, exiting”

N_O_m_e_g_a is not the best coded or most efficient engine available by any means.
However, my primary objective in releasing N_O_m_e_g_a is to make my experiences and
resources such as they are, available to other novice coders who are keen to
start writing their own programs. With this in mind, my source code which I have
documented as clearly as I can, is also freely available with this release.

N_O_m_e_g_a was written and compiled in FreeBasic, using FBIDE

If someone has managed it to compile with FreeBasic I would like to hear it (just curious).
I had to modify the code to get FB to compile it.

[TESLACOIL]

I cant compile it either but the exe runs ok. I played a handful of moves but that was all

[TESLACOIL]

Key metrics that need tracking

Code: Select all

'positionsetup

dim as integer woo,wooo,boo,booo,mnum,enp,m50rule
dim as string stm,pgn,repx3


woo=1:wooo=1:boo=1:booo=1
stm="white"
mnum=1
enp=0
pgn="no"

if pgn="no" then repx3="no" : m50rule=0


?
?" positionsetup "

? " get/set flags"

?
? " side to move ";stm
? " move number ";mnum
?
? " castling rights"
? " woo  ";woo
? " wooo ";wooo
? " boo  ";boo
? " booo ";booo
?
? " PGN / move history found      =  ";pgn
? " 3 fold Repetition history     =  ";repx3
? " Fifty move rule counter       = ";m50rule
?
? " en passant after pawn push on file number = "; enp


sleep:end

In order to create a good chess engine you either need to be a good programmer with a lot of computing power at your disposal or a good chess player who knows how to tweak the metrics and get the most out of the computational power available.

With a single core you have to play smart, with four or more cores brute force starts to win out. With multiple computers at your disposal you need a multibrained approach in order to compensate for the inherent weaknesses. Large 'vetted' opening books and 'perfect play' endgame tablebases remove a lot of the clunky play associated with weaker computer chess engines.

Powerful Brute force computers get into trouble all the time, but as the trap starts to close they usually manage to wiggle out of danger as the move horizon approaches. As the pieces start to dwindle they can usually see out far enough to detect danger signals, signals that trigger a deeper search. Lazy but effective enough assuming you have enough CPU power and time left on the clock.

Smart engines need to be very crafty, knowing who or what your opponent is, steering the game towards your engines strengths or towards positions in which the opponent is likely to falter. P a4 followed by pawn a5 will get your opponent out of book on move 2, perhaps giving you an advantage in blitz vs a brute force engine. Various anti computer or anti human strategies can be applied. If the opponent is weak enough you can toy with them, pull of an outrageous string of sacrifices, or drive the position into the chess wilderness or weirdness.

[Stonemonkey]

Nice work. What's the state of your project just now?

[TESLACOIL]

Slowly working through the list of metrics needed for 100% legal move generation and also the metrics advanced evaluation.

Im still Defining the architecture. You can see the file structure/debug tools i have in mind if you run this installer.

Code: Select all

'pawnage setup 

'***********************************************************************
'Notes
'**********************************************************************




'***********************************************************************
'variables
'***********************************************************************
dim as string q
dim as integer i 

dim as string hpath


hpath=curdir

?" current dir ";curdir

'***********************************************************************
'installer screen
'***********************************************************************
color 13
?
?" Pawnage 1.1"
color 7
?
?" this program will install the Pawnage 1.0 Chess engine"
?
? " press 'y ' to continue or q to quit"
?

while q="" 
q=inkey
wend


'if q ="y" then ?:?" Installing..." : sleep 1200 else sleep 200:end




'*****************************
'create directories and files
'*****************************

mkdir "misc"

mkdir "graphics"
mkdir "sounds"
mkdir "media"

mkdir "benchmarks"

mkdir "books"
mkdir "engines"
mkdir "tablebases"
mkdir "pgn"
mkdir "network"
mkdir "config"



mkdir "testfiles"

mkdir "testengine1"
mkdir "testengine2"
mkdir "testengine3"
mkdir "testengine4"
mkdir "testengine5"
mkdir "testengine6"
mkdir "testengine7"
mkdir "testengine8"


'mkdir
'mkdir
'mkdir
'mkdir
'mkdir

mkdir "cores"
chdir hpath & "\cores"
for i=1 to 100'1'
mkdir "core" & i
sleep 1 : ? i 
next i

chdir  hpath

?
? " Done"

sleep:end

'***********************

'***********************


sleep 1200
color 15
?
?" um P - E4 "
?:sleep 1200
color 12
?" Pownage 1.0 Resigns "

'**********************
sleep: end
'**********************

As its designed to be multi core multi brained and even multi computer i think i will create a number of micro engines and have them run in parallel. A good way to debug and test code blocks. Eg have a micro engine that only tracks and warns of three fold repetition and does nothing else. Another that evaluates pawn formations and nothing else.

the engines can just be fed PGN longhand, eg e2e4 g8f7 (via .txt files ) so anyone can build a micro engine to test out a specific routine.

movenum1.txt
movenum2.txt

engine1saysthis.txt
engine2saysthis.txt

Something like that. This leaves the coder to focus on any specifics they are trying to nail. They don't have to learn someone elses engine just to insert 20 lines of their code.

[Stonemonkey]

I'll take your word for it, put a cpu in my hand and I'll talk to it in binary but I know little of files and structures so I don't really understand what you're doing.

[TESLACOIL]

Its not rocket science. Just Cpu's and exe's sending each other text messages
http://en.wikipedia.org/wiki/Supercompu ... arallelism

If you want to communicate over a LAN you don't to worry about ip sockets, ports etc

anyold.txt file can be read by anyexecutable.exe anywhere on the LAN


If you want sub 1/10th second ping back times then you need to talk to the hardware. Chess is slow, 1 second plus. So remote communication can be carried out just be reading and writing text files. You can even set up a read only loop so no need to worry about write permissions on remote machines. Feedback via read only .txt files is pretty bullet proof and as simple as it gets.

[Stonemonkey]

Here's an odd situation

say a black rook is shielding the black king from a white rook

It would be an illegal move for the black rook to move away and leave the black king in check so can the white king move onto the path of, or cross the path of the black rook to be castled?

I'm guessing probably not but I'm not sure how my checking will deal with that.

[TESLACOIL]

a king can never be exposed to a 'line of check' that line of check is still good even if the checking piece is itself pinned.

think of it this way....white rook is pinned, but if it moved and took black kings it would be game over.



lets say its whites turn to find all legal moves....white moves just 1 piece THEN black moves in turn every piece it physically can regardless of legalities, if black can take whites king then that white move is by definition illegal.

A) you either cast outwards from whites king to detects all enemy pieces with attack lines

B) or you make 1 move for white, then generate all pseudo moves for black , now eval the board, if whites score drops by 9000 ( the value of whites king ) then it has been possible for black to take it, thus white left its king in check = illegal move for white. Try another white piece.

Perhaps write a simple program that has only a kings and rooks on the board.



you have your brute force generator , have it brute force two ply ( one move for either side) now cull all positions in which the score drops by the value of the first movers king. The king being very very high score, if score drops by 95% or more then whites king is lost. The white move that lead to that position is illegal, or white has been checkmated (lose) if it was already in check, or in zugzwang. ( draw) if it wasn't in check.

[Stonemonkey]

Yeah, that's what I guessed but had to check. Checking again I think my code can deal with it ok, I think when checking for check, it checks for check of the one colour but doesn't check for check of the other colour as a result of the piece that's causing the check.

[TESLACOIL]

Im not sure which approach is faster A or B

especially as you have to brute force a couple of ply anyway.


Link to some earlier work on the KISS chess protocol ( some opening books in longhand PGN making it easy to import )
viewtopic.php?f=8&t=19565&p=171660&hilit=kiss#p171660





If you add lots of metrics / flags to brute force move as you do it generation it will slow it down generation a fair bit but then you have lots of nice graphlines of information you can track which could make future tree pruning more effective.

eg

While you are calculating legal pawn moves you can keep a tally of total pawn freedoms or even individual pawn freedoms. After culling positions for checkmate, enpassent rights, zugzwang etc you just tot up all the counters.

The more plys the smoother the metrics, the values will jump about less so tracking trends or spotting spikes at 6 ply gives the program a set of internal instincts to chew on.


OR

Just examine the metrics at the end of the brute force search horizon. But this might hide trends or event spikes contained within those 6 ply. You could have a separate subroutine that only deeply 're analyzes' the end points.



Castling rights are fairly straight forward if you have a flag for 'original rooks' + has not moved. By testing non castling moves for the king gets you get access to the transient check free left/right squares the king passes through.

Saving all enpasant rights, castling rights into the board position and a log to note if these have changed or not will allow detection of three fold repetition AND also culling of the list of positions to check.

a 16x8 board ( double width ) could do this You could use a 2d array. Note some squares are never effected by enpassant or castling positions so you could use these empty pigeon holes to house other counters.



50 move rule

Counter is reset to zero every time a pawn is moved or a piece taken.
http://en.wikipedia.org/wiki/Fifty-move_rule

Needs to be switched off for very highest level play, ie computer vs computer on long time controls or a mate search will be terminated at the 50 move horizon and a potential win missed.

Mobility a key chess metric, link also lists numerous other chess terms influential for evaluation & pruning
http://en.wikipedia.org/wiki/Mobility_% ... 9#Mobility

[TESLACOIL]

This program should load the data in the second code block below and display the board and numerous stats and flags

Variables required for 100% legal move generation have been included & initialized including 50 move rule and 3 fold repetition

Save game files and saved position need to include these variable ive hard coded them in for now but will append and update the save game file creator at a later date. A PGN file which starts at move can be be reverse engineered to set the '50 move rule' and '3 fold repetition' flags. This feature will be added later.

Currently there are two data structures , a piece list and a simple 8x8 board with 1=white 2= black and 0 = empty
The piece list has an extra field which can be used to signify original and promoted pieces, moved and never moved pieces and other key attributes and metrics.

Code: Select all

'positionsetup

dim as integer i,ii,x,y,c,col
dim as string q,qq

dim as integer sx,sy   'start x , start y 


dim title as string
dim special as string
dim id(32) as string 'name
dim xx(32) as integer ' x cordinate A to H on chessboard as is 
dim yy(32) as integer ' y cordinate 1 to 8 on chessboard displayed inverted
dim mo(32) as integer
dim notes as string


'array to hold the board for legal move detection  1=white 2= black 3 empty
dim bw (8,8) as integer


dim as integer woo,wooo,boo,booo,mnum,enp,m50rule
dim as string stm,pgn,repx3

'zero some arrays

'for i=1 to 32
' id(i) = ""
' xx(i) = 0
' yy(i) = 0
' mo(i) = 0
'next i
    




chdir "testfiles"




OPEN "startposition.txt" FOR input AS #1
input #1, title
? title

input #1,special
? special

for i =1 to 32 
input # 1, id(i),xx(i),yy(i),mo(i) 
? id(i);xx(i);yy(i);mo(i) ; " piece number ";i
next i

input #1,notes
? notes 

CLOSE #1




woo=1:wooo=1:boo=1:booo=1
stm="white"
'stm="black"
mnum=1
enp=0
pgn="no"

if pgn="no" then repx3="no" : m50rule=0


?
?" positionsetup "

? " get/set flags"

?
? " side to move ";stm
? " move number ";mnum
?
? " castling rights"
? " woo  ";woo
? " wooo ";wooo
? " boo  ";boo
? " booo ";booo
?
? " PGN / move history found      =  ";pgn
? " 3 fold Repetition history     =  ";repx3
? " Fifty move rule counter       = ";m50rule
?
? " en passant after pawn push on file number = "; enp


'open saved position and load it into array
'  display the board
screen 19 


'draw chess board               notes 'Draw String (99, 66), "Origin", 12
c=0
for i = 1 to 8
for ii= 1 to 8
c=c+1
if c = 1 then col = 27 : c=c-2 else col = 6
line (i*20,ii*20)-((i*20)+18,(ii*20)+18),col,bf
'sleep 30
next ii
c=c+1
if c = 1 then col = 7 : c=c-2 else col = 11
next i
'sleep:end


col = 31
for i=1 to 32
if i > 16 then col = 0
draw string ((xx(i)*20)+6,(yy(i)*20)+2),id(i),col
'? xx(i),i : sleep
'sleep 150
next i


'cls
'load simplified peices into bw array just as black or white values

color 7 : locate 2,51 :? "peice list, in play > 0"

for i=1 to 16
if  mo(i)>0 then bw (xx(i),yy(i)) =1 else bw (xx(i),yy(i)) = 0 
color 7: locate i+2 ,50: ? i; bw (xx(i),yy(i))
next i

for i=17 to 32
if  mo(i)>0 then bw (xx(i),yy(i)) =2 else bw (xx(i),yy(i)) = 0 
color 8: locate i+2 ,50:? i;bw (xx(i),yy(i))
next i






'PSEUDO MOVE GENERATION **********************************************************************************


'find whos turn it is , should be added to saved position for completness,need to expand the format to encompass this



' find kings normal moves 

'get kings start position 
if stm ="white" then sx = xx(1)  : sy = yy (1)  : color 7
if stm ="black" then sx = xx(17) : sy = yy (17) : color 8

locate 2,24: ? " ";stm;" king at";sx;" sx";sy;" sy"




sleep:end

saved game file , see first post

save the text below as startposition.txt in directory called testfiles ( or just comment out chdir "testfiles" in the code above )

Code: Select all

    "default"
    "specialnull"
    "K",5,8,99
    "Q",4,8,99
    "R",1,8,99
    "R",8,8,99
    "B",3,8,99
    "B",6,8,99
    "N",2,8,99
    "N",7,8,99
    "P",1,7,99
    "P",2,7,99
    "P",3,7,99
    "P",4,7,99
    "P",5,7,99
    "P",6,7,99
    "P",7,7,99
    "P",8,7,99
    "k",5,1,99
    "q",4,1,99
    "r",1,1,99
    "r",8,1,99
    "b",3,1,99
    "b",6,1,99
    "n",2,1,99
    "n",7,1,99
    "p",1,2,99
    "p",2,2,99
    "p",3,2,99
    "p",4,2,99
    "p",5,2,99
    "p",6,2,99
    "p",7,2,99
    "p",8,2,99
    "notes"

[Stonemonkey]

I know that how you code is down to personal preference but I can see you running into all sorts of problems with that. A couple of suggestions, put your board array into a type, make the loading of the board position into a sub routine, that routine should be able to load any board position, remember that the number of pieces on the board can vary.

[Richard]

I would define a UDT structure that held the 8x8 = 64 Ubyte linear array, along with some tags or counters for “who moves next”, “strategy/task” “ply” and “last move was”. That could hold all the necessary information to pass to a tree of multiple threads / processors.

Each piece would be fully represented in a single byte.
An empty square is zero. All black pieces have bit 7 set = +128, plus a piece identification.

As an example, there would be three types of pawn, +1 for those that behave like normal pawns and +2 for those subject to en passant this move, promoted pawns that can travel backwards are possible, so they could be +3. Pieces that have moved could be tagged with bit 6 = +64, that would identify possible castling. Pawn promotion would be a simple overwrite with the new piece identification.

So a piece would change it's exact representation during play, but at any time any processor could evaluate the virtual situation and spawn a selection of next moves for evaluation.

This format would avail itself to fast logical bit tests and 256 element jump tables. No slow string processing would be necessary.

[TESLACOIL]

The first pass is just to get a bug free 100% legal move generator with full metrics. No one has done this as yet in free basic, not even close !

Im not too worried if its a little slow as i have ample computing power at my disposal. There are 101 other minor but important tasks to achieve with the first build so i don't want to get bogged down in the minutia of version 1.0 if you get me.

eg

PGN reader and short hand to long hand PGN convertor

polishing the network / multi cpu aspects of the architecture

UCI interface so you can plug it into fritz GUI and play against the dozens of great engines out there

Opening books

Endgame tablebases


Anyway no matter how tight your code is hobby your engine is gonna get well and truly pulverized by any pro engine already out there if its only running on one core or one machine. This is why im designing 'this system' to be network capable form the off any speed optimizations i make at a later date will be amplified by the number of PC's its running on. Of course it would Ideally all be in ASM or C. The key idea is that each PC or even each core gets its own move generator and a number of different evaluators with different priorities that way you can get depth, breadth and smarts.



Once i have the legal move generator working with an easy to use 'plug n play format' then everyone can have fun writing an evaluation program and playing there engines against everyone else. Sadly there are very few hard core chess players in the community ( its a very small community ) or we would have a swathe a high utility chess tools already.

There are plenty of coders way better than I but they neither have the interest, the inclination or the vision to build a simple but high utility aka easy to use chess engine, so muggins here has to hack n slash his way though it. If i wasn't building a chess supercomputer for competition i wouldn't even attempt this, as i am i thought i may as well share it.

* remember im a designer not a coder, so this is more akin to a working prototype. Once i have the design and architecture sorted i then hand off to artists, engineers, coders whatever and let them do what they are good at. Its all part of the process. What i build and how i why i build it comes from a very different set of motives to a typical hobby coder. In this case the end user happens to me rather than someone else.