Proper Chess Engine with networked CPUs & LAN play

User projects written in or related to FreeBASIC.
TESLACOIL
Posts: 1769
Joined: Jun 20, 2010 16:04
Location: UK
Contact:

Proper Chess Engine with networked CPUs & LAN play

Postby TESLACOIL » Dec 01, 2012 3:15

Proper Chess Engine with networked CPUs & LAN play

Youtube Channel dedicated to chess programs ( play list starting with Alan Turing - The first ever Chess program )
http://www.youtube.com/watch?v=CrLbB4ie ... NmGb7REmpv

Finally getting round to building a proper chess engine. There are some very strong engines out there but essential elements like LAN play and utilizing the processing power of other CPU's on a network are either buggy, an afterthought or just haven't been implemented.

This is for x86 PC's / PC networks running windows and while FreeBASIC is slower than some other languages and no doubt my code will not be the fastest but the ability to add an infinite number of machines will more than make up for any shortfall. Stringing together a couple of clunkers can turn you computer museum into a chess monster.

The main exe will handle all the misc stuff and brute force to 6 ply and then select various lines for further analysis by other local exe's or remote cpu's depending on the filters set by the user. Simple file sharing is all that required combined with elementary message based computing.

*a hobby coder has no chance of writing a truly competitive engine that runs on a single machine, the ability to utilize other machines at least gives you a fighting chance. Most of us have 2 or 3 desktop machines these days & perhaps a laptop or two. Network cables & routers/switches are cheap and chances are you have most of the kit already. Got CPU's ? why not use em !




Q why am i doing this ?
Well i have 3 projects / ambitions and this is the 3rd. Im investing $1000's in a computer network to host my self aware HAL9000 type AI system. ( destined to be the smartest AI on the planet ) The Epic Space game runs on the older parts of the network as i upgrade it and will eventually bring in some revenue, and its my intention that my network Chess Computer be the most powerful dedicated chess computer in the UK if not the world. Playing chess for big prize money, but you have to get in the top 100 if not top 10 to make a living out of it and that is my intention here and that means writing chess software that can run on a network of any size. There is a great deal of crossover between the three projects and having made a lot of headway in one its easy to branch out.

Chess is entering its last phase. By the end of this century it will be mostly strongly solved so the fun will be over by 2100ad. In the near future we are going to see some titanic battles between supercomputers with millions of cores and i just want to be part of that fun. That and contribute to the knowledge of mankind.

Ive included some links to useful information as writing a proper bug free chess program is a lot more complicated than it appears at first glance. So forgive the link spam.


Tips for writing a chess program

Many very experienced coders come unstuck as chess is full of weird and wonderful exceptions to the rule. Pressures to optimize the code for speed, cope with the numerous chess formats or just get the GUI looking sweet all lend their weight. 99% of all code attempts will be riddled with nasty chess bugs because the coder didn't think of all the exceptions they have to handle in advance.

The most important code element is the legal move generator...thats ALL legal moves and not just the ones that spring to mind thank you very much ! lol

A typical chess program will use several internal data formats and will include quite a large amount of spaghetti fudge code in order to handle all those awkward exceptions to the rule which inevitable arise and cannot be dealt with neatly or efficiently.

Draw by repetition is particularly tricky to handle as you not only have to check for this at every single branch but you have to evaluate it too, and sometimes you have to evaluate it retrospectively because if a deeper search indicates you are 'now losing' or 'now winning' then you will want to actively steer away or towards 'draw by repetition'. Worse still draw by repetition often arrives in batches that suddenly multiply exponentially and may well involve a long series of moves which are not necessarily checks. If a chess program cannot handle this well then it falls firmly into the dud-ware category. Its up there with crashing into clouds :-p


Graphics Chess Set Designs & the International Tournament Standard
http://www.youtube.com/watch?v=nO448CufFJw


Chess programming


Writing a chess program in 99 steps
http://www.sluijten.com/winglet/

http://chessprogramming.wikispaces.com/

http://www.frayn.net/beowulf/theory.html

http://tinyurl.com/bpd29ej


ADDED
misc tools
Fritzbench conversion / ELO estimator / CPU architecture comparison

Code: Select all

        'Fritzbench conversion / elo estimator / CPU architecture comparison
       
        dim i as ULONGINT
        dim mem as integer
        dim st as  double
        dim fin as  double
        dim mips as double
        dim q as integer
       
        dim  as integer mpint,cores,fritzb,elo
         
        color 13
        ?
        ?" Fritzbench conversion / elo estimator / CPU architecture comparison"
       
       'goto skip
         
        mem = FRE
        color 12
        ?:?" Free memory:" ;mem  \ (1024 * 1024); " megabytes"
        color 7
        ?:?" starting Free Basic speedtest9.exe....approx 10 seconds":?:sleep 100

        st = TIMER :?" start   "; st , timer

        for i = 1 to 2500000000:next i

        fin = TIMER :?" finish  "; fin , timer

        ?: color 13: ?" time = " ;fin-st;" i = ";i;" how many loops done in total"

        i=i/1000000
        mips = i/ (fin-st)

        ?:?" mips = "; mips; " FreeBASIC for next loop instructions X 1 million"
       

    'skip:

    'mpint = 425
    '* 1.30
    '? 3.9*1.30
    'sleep
    'elo = 0


    screen 19
    mpint = mips

    color 13
    ?
    ?"  Fritz Benchmark Conversion & Comparison Table  including ELO aproximation"
    color 12
    ?
    ?"  Your core speed   ="; mpint ;" mips    using Speedtest9 test as the CPU mark "
    color 7
    ?
    ?"  Applying your single core speed to different architectures & converting to Fritzbenchmark"
    ?
    ?"  No hyper threading       Fritz bench"
    ?
    fritzb = mpint *6*1*.95
    ?"  Single            =     "; fritzb
    fritzb = mpint *6*2*.925
    ?"  Dual              =     "; fritzb
    fritzb = mpint *6*3*.895
    ?"  Triple            =     "; fritzb
    fritzb = mpint *6*4*.867
    ?"  Quad              =     "; fritzb
    fritzb = mpint *6*6*.790
    ?"  Hex               =     "; fritzb
    fritzb = mpint *6*8*.690
    ?"  Octo              =     "; fritzb   
    ?
    ?
    ?"  With hyper threading     Fritz bench"
    ?
    fritzb = mpint *6*1*.99*1.65
    ?"  Single            =     "; fritzb
    fritzb = mpint *6*2*.86*1.45
    ?"  Dual              =     "; fritzb
    fritzb = mpint *6*3*.86*1.35
    ?"  Triple            =     "; fritzb
    fritzb = mpint *6*4*.86*1.31
    ?"  Quad              =     "; fritzb
    fritzb = mpint *6*6*.86*1.30
    ?"  Hex               =     "; fritzb
    fritzb = mpint *6*8*.69*.95
    ?"  Octo              =     "; fritzb   
    ?
    ?"  Notes:"
    ?"  Multi core CPU's suffer performance penalites"
    ?"  Hyper threading cores tend to suffer even more"
    ?"  This means a significant % of perfomance is lost"
    ?"  In general Ghz is king, then cores, then threads"
    ?
    ?"  Calibrated with CPU's 2007 to 2012ad [spread +/- 10%]"
    ?"  * Indvidual cores turboboost higher when tested in isolation"
    ?
    ?"  hit Enter to exit"
    color 6


    locate 8,55:? "Fritz    ELO   HUMAN"
    locate 10,55:? "    1     20   Beginner"
    locate 11,55:? "    5    500   Casual player"
    locate 12,55:? "   50   1200   Weak Club player"
    locate 13,55:? "  500   1900   Strong Club player"
    locate 14,55:? " 5000   2500   Grandmaster"
    locate 15,55:? "10000   2750   World Champion"
    locate 16,55:? "20000   3000   Greatest Human Possible"
    locate 18,55:? "Note: Very rough aproximation"

    sleep: end
    '    ?"  500 Mhz Pent III    =   68"
    '    ?"  Celeron 2600        =  180"
    '    ?"  Sepmron 2600+       =  305"
    '    ?"  Athalon 2000+       =  330"
    '    ?"  Atom N450 2 core    =  235 * task manager cpu usage was showing 50%   "
    '    ?"  Atom N450 2 core    =  335 * running 2 progs at once cpu usage 100% "
    '    ?"  AMD XII 250         =  375"
    '    ?"  AMD FX-8 8350       =  400 * estimated"
    '    ?"  i5 2500k stock      =  475"
    '    ?"  i5 2500k mild OC    =  503"
    '    ?"  i7 3770k mild OC    =  525 * estimated "
    '    ?"  Best CPU 5Ghz OC    =  590 * estimated available in 2012ad"
    '    ?"  6 core 12 thread    = 6250 Total @5ghz OC summing all cores\threads"
    '    ?
    '    ?"  Dual cores total    = 400  to  900 typical"
    '    ?"  Quad cores total    = 1200 to 2000 typical"
    '    ?"  Hex + HT   total    = 1500 to 4500 typical"
    '    ?"  Death Run on L'N    = 5000 to 7000 typical"



Ply calculator a complete opening book or search tree 5 moves deep each side would require 100 terabytes or so of storage

Code: Select all

'ply calculator

dim x as ulongint
x=25
screen 19
?
?" Ply calculator, there are typicaly 25 moves possible "
?
?" a ply refers to one turn taken by one of the chess players."
?
?
?
?" permutations when move options = 25"
?
? " 1  ";x
? " 2  ";x*x
? " 3  ";x*x*x
? " 4  ";x*x*x*x
? " 5  ";x*x*x*x*x
? " 6  ";x*x*x*x*x*x
? " 7  ";x*x*x*x*x*x*x
? " 8  ";x*x*x*x*x*x*x*x
? " 9  ";x*x*x*x*x*x*x*x*x
? " 10 ";x*x*x*x*x*x*x*x*x*x
?
?
?
x=30
?" permutations when move options = 30"
?
? " 1  ";x
? " 2  ";x*x
? " 3  ";x*x*x
? " 4  ";x*x*x*x
? " 5  ";x*x*x*x*x
? " 6  ";x*x*x*x*x*x
? " 7  ";x*x*x*x*x*x*x
? " 8  ";x*x*x*x*x*x*x*x
? " 9  ";x*x*x*x*x*x*x*x*x
? " 10 ";x*x*x*x*x*x*x*x*x*x


sleep : end





Free Memory Calculator memory usage quickly gets out of hand. A few gigs is woefully insufficient so it has to be managed.

Code: Select all

dim mem as ulongint

color 7

mem = FRE

?
?
?
color 10
? "         MB = "; mem  \ (1024 * 1024); " "
color 8
?
?
?
?
? "  Free Memory   "; FRE
?
? "  bytes         "; mem
?
? "  kilobytes        "; mem  \ 1024; " "
?
? "  megabytes           "; mem  \ (1024 * 1024); " "

sleep: end




speed test version 9 with results table for comparison

Code: Select all


    'speed test version 9
   

    dim i as ULONGINT
    dim mem as integer
    dim st as  double
    dim fin as  double
    dim mips as double
    dim q as integer
    color 13
    ?
    ?" Speed test9.exe"
    color 7
    input "...hit enter to start";q
    mem = FRE
    color 12
    ?:?" Free memory:" ;mem  \ (1024 * 1024); " megabytes"
    color 7
    ?:?" starting Free Basic speed test......approx 10 seconds":?:sleep 100

    st = TIMER :?" start   "; st , timer

    for i = 1 to 2500000000:next i

    fin = TIMER :?" finish  "; fin , timer

    ?: color 13: ?" time = " ;fin-st;" i = ";i;" how many loops done in total"

    i=i/1000000
    mips = i/ (fin-st)

    ?:?" mips = "; mips; " FreeBASIC for next loop instructions X 1 million"
   

screen 19
color 13
?
?"  Speed test9.exe    RESULTS TABLE"
color 12
?
?"  Your core speed     ="; mips;" FreeBasic for next loops x 1 million"
    color 7
    ?
    ?"  This just tests a single core / thread"
    ?"  Multiple core/thread efficency is approx = 90%"
    ?"  eg an i5 2500k core = 503 then 4 cores no HT = approx 1850"
    ?
    color 7
    ?"  500 Mhz Pent III    =   68"
    ?"  Celeron 2600        =  180"
    ?"  Sepmron 2600+       =  305"
    ?"  Athalon 2000+       =  330"
    ?"  Atom N450 2 core    =  235 * task manager cpu usage was showing 50%   "
    ?"  Atom N450 2 core    =  335 * running 2 progs at once cpu usage 100% "
    ?"  AMD XII 250         =  375"
    ?"  AMD FX-8 8350       =  400 * estimated"
    ?"  i5 2500k stock      =  475"
    ?"  i5 2500k mild OC    =  503"
    ?"  i7 3770k mild OC    =  525 * estimated "
    ?"  Best CPU 5Ghz OC    =  590 * estimated available in 2012ad"
    ?"  6 core 12 thread    = 6250 Total @5ghz OC summing all cores\threads in theory"
    ?
    ?"  Dual cores total    = 400  to  900 typical"
    ?"  Quad cores total    = 1200 to 2000 typical"
    ?"  Hex + HT   total    = 1500 to 4500 typical"
    ?"  Death Run on L'N    = 4500 to 6500 typical"
    ?
    ?"...hit Enter to exit"
    sleep: end


Link to some earlier work on the KISS chess protocol
viewtopic.php?f=8&t=19565&p=171660&hilit=kiss#p171660

Rules of chess
http://en.wikipedia.org/wiki/Rules_of_chess

The 50 move rule is sometimes lifted for chess computers as many deep wins have been discovered. As chess computers get ever more powerful this rule will probably be abandoned altogether.

Chess Notation

http://en.wikipedia.org/wiki/Chess_notation

http://en.wikipedia.org/wiki/Forsyth%E2 ... s_Notation

http://en.wikipedia.org/wiki/X-FEN

http://en.wikipedia.org/wiki/Portable_Game_Notation

Chess Engines and ratings
http://en.wikipedia.org/wiki/Chess_engine

Online Nalimov Endgame Tablebases
http://www.k4it.de/index.php?topic=egtb&lang=en


>>>> PART ONE <<<< create a file called "startposition.txt" and display that data it in a simple board format

Code: Select all

'creates a file called "startposition.txt"
'fbnetchess1.bas

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

dim title as string
dim special as string
dim notes 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


' intitalize arrays to save start position to file

id(1)= "K" :xx(1)=5:yy(1)=8
id(2)= "Q" :xx(2)=4:yy(2)=8
id(3)= "R" :xx(3)=1:yy(3)=8
id(4)= "R" :xx(4)=8:yy(4)=8
id(5)= "B" :xx(5)=3:yy(5)=8
id(6)= "B" :xx(6)=6:yy(6)=8
id(7)= "N" :xx(7)=2:yy(7)=8
id(8)= "N" :xx(8)=7:yy(8)=8
id(9)= "P" :xx(9)=1:yy(9)=7
id(10)= "P" :xx(10)=2:yy(10)=7
id(11)= "P" :xx(11)=3:yy(11)=7
id(12)= "P" :xx(12)=4:yy(12)=7
id(13)= "P" :xx(13)=5:yy(13)=7
id(14)= "P" :xx(14)=6:yy(14)=7
id(15)= "P" :xx(15)=7:yy(15)=7
id(16)= "P" :xx(16)=8:yy(16)=7

id(17)= "k" :xx(17)=5:yy(17)=1
id(18)= "q" :xx(18)=4:yy(18)=1
id(19)= "r" :xx(19)=1:yy(19)=1
id(20)= "r" :xx(20)=8:yy(20)=1
id(21)= "b" :xx(21)=3:yy(21)=1
id(22)= "b" :xx(22)=6:yy(22)=1
id(23)= "n" :xx(23)=2:yy(23)=1
id(24)= "n" :xx(24)=7:yy(24)=1
id(25)= "p" :xx(25)=1:yy(25)=2
id(26)= "p" :xx(26)=2:yy(26)=2
id(27)= "p" :xx(27)=3:yy(27)=2
id(28)= "p" :xx(28)=4:yy(28)=2
id(29)= "p" :xx(29)=5:yy(29)=2
id(30)= "p" :xx(30)=6:yy(30)=2
id(31)= "p" :xx(31)=7:yy(31)=2
id(32)= "p" :xx(32)=8:yy(32)=2

'? xx(1)
'
'sleep :end


for i = 1 to 32 :mo(i)=99:next i


OPEN "startposition.txt" FOR output AS #1
WRITE #1,"default"
WRITE #1,"specialnull"

for i =1 to 32
WRITE # 1, id(i),xx(i),yy(i),mo(i)
next i

WRITE #1,"notes"
CLOSE #1




OPEN "startposition.txt" FOR input AS #1
input #1,"default"
input #1,"specialnull"

for i =1 to 32
input # 1, id(i),xx(i),yy(i),mo(i)
next i

input #1,"notes"
CLOSE #1



'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


'sleep:end


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

sleep:end



saves the board position to file in the following format

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"






Loading the data back into the main program

Code: Select all

'load position

'fbnetchess1.bas

'using computer notation not chess notation for x,y coordinates to avoid confusion while codeing

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

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



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

'sleep:end



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


sleep:end






Notes

*human chess notation is something that computers know nothing off and so it has to be converted. Trying to debug code with human chess notation is a nightmare as the board can flip, you have to remember whose turn it is and also try and convert A1 to A4 into x,y coordinates which are opposite or inverse to screen x,y. So for the sake of my sanity this is why im just going to forget that human chess notation exists for now and i will just attend to that minor graphical detail once the program is completed.



The Next step

The next step is to flesh out all the flags and switches which will be required for the engine to decipher the board correctly. Eg whose turn is it, what move number are we on, load the previous move history into if any into an array etc.
Last edited by TESLACOIL on Jan 05, 2013 7:19, edited 32 times in total.
BasicCoder2
Posts: 3405
Joined: Jan 01, 2009 7:03

Re: Proper Chess Engine with networked CPUs & LAN play

Postby BasicCoder2 » Dec 01, 2012 11:02

I would suggest you try and modularize your program to make it easier to read and edit. For example you can replace the displayBoard() with a graphical one of the same name without affecting the rest of the program. Here is an example using your program.

Code: Select all


'fbnetchess1.bas

'using computer notation not chess notation for x,y coordinates to avoid confusion while coding

dim shared as string title
dim shared as string special
dim shared as string notes

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

sub intializePieces()
    id(1)= "K" :xx(1)=5:yy(1)=8
    id(2)= "Q" :xx(2)=4:yy(2)=8
    id(3)= "R" :xx(3)=1:yy(3)=8
    id(4)= "R" :xx(4)=8:yy(4)=8
    id(5)= "B" :xx(5)=3:yy(5)=8
    id(6)= "B" :xx(6)=6:yy(6)=8
    id(7)= "N" :xx(7)=2:yy(7)=8
    id(8)= "N" :xx(8)=7:yy(8)=8
    id(9)= "P" :xx(9)=1:yy(9)=7
    id(10)= "P" :xx(10)=2:yy(10)=7
    id(11)= "P" :xx(11)=3:yy(11)=7
    id(12)= "P" :xx(12)=4:yy(12)=7
    id(13)= "P" :xx(13)=5:yy(13)=7
    id(14)= "P" :xx(14)=6:yy(14)=7
    id(15)= "P" :xx(15)=7:yy(15)=7
    id(16)= "P" :xx(16)=8:yy(16)=7

    id(17)= "k" :xx(17)=5:yy(17)=1
    id(18)= "q" :xx(18)=4:yy(18)=1
    id(19)= "r" :xx(19)=1:yy(19)=1
    id(20)= "r" :xx(20)=8:yy(20)=1
    id(21)= "b" :xx(21)=3:yy(21)=1
    id(22)= "b" :xx(22)=6:yy(22)=1
    id(23)= "n" :xx(23)=2:yy(23)=1
    id(24)= "n" :xx(24)=7:yy(24)=1
    id(25)= "p" :xx(25)=1:yy(25)=2
    id(26)= "p" :xx(26)=2:yy(26)=2
    id(27)= "p" :xx(27)=3:yy(27)=2
    id(28)= "p" :xx(28)=4:yy(28)=2
    id(29)= "p" :xx(29)=5:yy(29)=2
    id(30)= "p" :xx(30)=6:yy(30)=2
    id(31)= "p" :xx(31)=7:yy(31)=2
    id(32)= "p" :xx(32)=8:yy(32)=2

    for i as integer = 1 to 32
        mo(i)=99
    next i
       
end sub
   

sub savePiecePositions(cFile as string)
    OPEN cFile FOR output AS #1
    WRITE #1,"default"
    WRITE #1,"specialnull"

    for i as integer = 1 to 32
        WRITE # 1, id(i),xx(i),yy(i),mo(i)
    next i

    WRITE #1,"notes"
    CLOSE #1
end sub

sub loadPiecePositions(cFile as string)
    OPEN cFile FOR input AS #1
    input #1,"default"
    input #1,"specialnull"

    for i as integer = 1 to 32
        input # 1, id(i),xx(i),yy(i),mo(i)
    next i

    input #1,"notes"
    CLOSE #1
end sub

sub displayBoard()
    dim as integer col
    dim as integer c=0
    for i as integer = 1 to 8
        for ii as integer = 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
        next ii
        c=c+1
        if c = 1 then col = 7 : c=c-2 else col = 11
    next i

    col = 31
    for i as integer = 1 to 32
        if i > 16 then col = 0
        draw string ((xx(i)*20)+6,(yy(i)*20)+2),id(i),col
    next i
end sub

screen 19
intializePieces()
savePiecePositions("startposition.txt")
loadPiecePositions("startposition.txt")
displayBoard()
sleep:end


You have chosen to use parallel arrays to represent 32 chess pieces. Another option is the use of a type data structure. One advantage is not having to worry about xx, yy etc being used elsewhere. Here is an example using your code. Notice the main program is identical.

Code: Select all

'fbnetchess1.bas

'using computer notation not chess notation for x,y coordinates to avoid confusion while coding
dim title as string
dim special as string
dim notes as string

type chessPiece
    as string  id    'name
    as integer xx    'position on board
    as integer yy
    as integer mo
end type

dim shared as chessPiece piece(1 to 32)  'create 32 piece types

sub intializePieces()
    for i as integer = 1 to 32
        piece(i).mo = 99
    next i
   
    piece(1).id  = "K" :piece(1).xx = 5: piece(1).yy  =8
    piece(2).id  = "Q" :piece(2).xx = 4: piece(2).yy  =8
    piece(3).id  = "R" :piece(3).xx = 1: piece(3).yy  =8
    piece(4).id  = "R" :piece(4).xx = 8: piece(4).yy  =8
    piece(5).id  = "B" :piece(5).xx = 3: piece(5).yy  =8
    piece(6).id  = "B" :piece(6).xx = 6: piece(6).yy  =8
    piece(7).id  = "N" :piece(7).xx = 2: piece(7).yy  =8
    piece(8).id  = "N" :piece(8).xx = 7: piece(8).yy  =8
    piece(9).id  = "P" :piece(9).xx = 1: piece(9).yy  =7
    piece(10).id = "P" :piece(10).xx =2: piece(10).yy =7
    piece(11).id = "P" :piece(11).xx =3: piece(11).yy =7
    piece(12).id = "P" :piece(12).xx =4: piece(12).yy =7
    piece(13).id = "P" :piece(13).xx =5: piece(13).yy =7
    piece(14).id = "P" :piece(14).xx =6: piece(14).yy =7
    piece(15).id = "P" :piece(15).xx =7: piece(15).yy =7
    piece(16).id = "P" :piece(16).xx =8: piece(16).yy =7

    piece(17).id = "k" :piece(17).xx = 5:piece(17).yy =1
    piece(18).id = "q" :piece(18).xx = 4:piece(18).yy =1
    piece(19).id = "r" :piece(19).xx = 1:piece(19).yy =1
    piece(20).id = "r" :piece(20).xx = 8:piece(20).yy =1
    piece(21).id = "b" :piece(21).xx = 3:piece(21).yy =1
    piece(22).id = "b" :piece(22).xx = 6:piece(22).yy =1
    piece(23).id = "n" :piece(23).xx = 2:piece(23).yy =1
    piece(24).id = "n" :piece(24).xx = 7:piece(24).yy =1
    piece(25).id = "p" :piece(25).xx = 1:piece(25).yy =2
    piece(26).id = "p" :piece(26).xx = 2:piece(26).yy =2
    piece(27).id = "p" :piece(27).xx = 3:piece(27).yy =2
    piece(28).id = "p" :piece(28).xx = 4:piece(28).yy =2
    piece(29).id = "p" :piece(29).xx = 5:piece(29).yy =2
    piece(30).id = "p" :piece(30).xx = 6:piece(30).yy =2
    piece(31).id = "p" :piece(31).xx = 7:piece(31).yy =2
    piece(32).id = "p" :piece(32).xx = 8:piece(32).yy =2
end sub

sub savePiecePositions(cFile as string)
    OPEN cFile FOR output AS #1
    WRITE #1,"default"
    WRITE #1,"specialnull"

    for i as integer = 1 to 32
        WRITE # 1, piece(i).id,piece(i).xx,piece(i).yy,piece(i).mo
    next i

    WRITE #1,"notes"
    CLOSE #1   
end sub

sub loadPiecePositions(cFile as string)
    OPEN cFile FOR input AS #1
    input #1,"default"
    input #1,"specialnull"

    for i as integer = 1 to 32
        input # 1, piece(i).id,piece(i).xx,piece(i).yy,piece(i).mo
    next i

    input #1,"notes"
    CLOSE #1
end sub

sub displayBoard()
    dim as integer col
    dim as integer c=0
    for i as integer = 1 to 8
        for ii as integer = 1 to 8
            c=c+1
            if c = 1 then
                col = 27
                c = c-2
            else
                col = 6
            end if
       
            line (i*20,ii*20)-((i*20)+18,(ii*20)+18),col,bf
        next ii
        c=c+1
        if c = 1 then
            col = 7
            c=c-2
        else
            col = 11
        end if
    next i
    'print piece id on its square
    col = 31
    for i as integer = 1 to 32
        if i > 16 then
            col = 0
        end if
        draw string ((piece(i).xx*20)+6,(piece(i).yy*20)+2),piece(i).id,col
    next i
end sub

screen 19
intializePieces()
savePiecePositions("startposition.txt")
loadPiecePositions("startposition.txt")
displayBoard()
sleep:end


Another way is to represent the data as a single object, the chess board, with states. A move changes the state of the chess board.
TESLACOIL
Posts: 1769
Joined: Jun 20, 2010 16:04
Location: UK
Contact:

Re: Proper Chess Engine with networked CPUs & LAN play

Postby TESLACOIL » Dec 01, 2012 14:32

agreed, but things are a lot more complicated than that so i will be writing lots of individual programs to do highly specific tasks and thoroughly test them before i actually start gluing the code together.

1) I will probably need a dozen internal data formats not just one in order for certain tasks to be carried out with high enough computational efficiency. To get it right is a very laborious process indeed !

2) Brute force to 6 ply (3 moves for both sides) is a default standard as it lays down 'the first road map' for additional analysis. I have to calculate the ram requirements and time constraints for this in advance. The numbers quickly spiral out of control if you are not careful...guaranteeing a total rewrite if you got yer sums wrong lol



The biggest challenge is writing a legal move generator in the first place. Once you have this 100% bug free (and fast) then analyzing 'positions generated' is relatively easy as its a process than can be re optimized time over and over without breaking the core code.

With the legal move generator in place you can then write multiple 'move selection engines' and have them play off against each other.
BasicCoder2
Posts: 3405
Joined: Jan 01, 2009 7:03

Re: Proper Chess Engine with networked CPUs & LAN play

Postby BasicCoder2 » Dec 01, 2012 17:45

.
Last edited by BasicCoder2 on Dec 02, 2012 11:24, edited 1 time in total.
TESLACOIL
Posts: 1769
Joined: Jun 20, 2010 16:04
Location: UK
Contact:

Re: Proper Chess Engine with networked CPUs & LAN play

Postby TESLACOIL » Dec 01, 2012 23:13

Writing a legal chess move generator is not the biggest challenge


you underestimate the task, i take it your not a chess player ? , it is much trickier than you expect, try it and you will find out.

Ill wager you cannot do it without several major rewrites.
Last edited by TESLACOIL on Dec 01, 2012 23:24, edited 1 time in total.
Stonemonkey
Posts: 587
Joined: Jun 09, 2005 0:08

Re: Proper Chess Engine with networked CPUs & LAN play

Postby Stonemonkey » Dec 01, 2012 23:24

It's no big problem, things get tricky when getting the program to decide which of the legal moves to play but wouldn't it be easier just to teach your dinosaur to play chess?
TESLACOIL
Posts: 1769
Joined: Jun 20, 2010 16:04
Location: UK
Contact:

Re: Proper Chess Engine with networked CPUs & LAN play

Postby TESLACOIL » Dec 01, 2012 23:27

@ Stonemonkey , trust me its much harder than it first appears. Legal move generation is a 'known tar pit'. Its the teeth grinder all chess engine builders have to wade through. Its a typical ' yeah its easy....oh no it not" thang

AFAIK no one has built a 100% bug free legal move generator in free basic. If they had id prolly be using it myself !

My dino will take ages to learn to play and it will be crap, crap in mush the same way as humans are generally crap at chess.It will be a good test of its generic learning capability. Chess is full of exceptions to the rule. Its as much of cultural learning experience as a logical one.
Stonemonkey
Posts: 587
Joined: Jun 09, 2005 0:08

Re: Proper Chess Engine with networked CPUs & LAN play

Postby Stonemonkey » Dec 01, 2012 23:39

I found that bit quite fun, getting it to decide which move to make was where things got tricky.
TESLACOIL
Posts: 1769
Joined: Jun 20, 2010 16:04
Location: UK
Contact:

Re: Proper Chess Engine with networked CPUs & LAN play

Postby TESLACOIL » Dec 01, 2012 23:56

ill be glad when i get to that stage ( the network bit i got covered already)

Q so you did all the rules not just some of them ?...sorry i have to ask, lol, ive seen far too many buggy chess engines not too




Q How did you code for 3 fold repetition ?

im sort of stuck on that, i guess you cull saved positions after every pawn move ?

Im also trying to think through possible promotion/castling issues too ref the 3 fold repetition rule but i think ? they should take care of themselves and not throw up any bugs
Stonemonkey
Posts: 587
Joined: Jun 09, 2005 0:08

Re: Proper Chess Engine with networked CPUs & LAN play

Postby Stonemonkey » Dec 02, 2012 0:12

It was quite some time ago but as far as I know it had all moves.

I can't remember exactly what I did but each piece had a an ID to say what it was, say 1=king,2=queen etc ...pawn=6 with bit 4 for black/white. All stored in the board array.

For en passant you could make 7 the ID for a pawn that's moved 2 on it's first move, if it moves again put it back to 6
Something similar could be done for the rooks and kings but you'd have to mess around with the IDs used.

For looking ahead multiple moves I used recursion and temporary boards.
TESLACOIL
Posts: 1769
Joined: Jun 20, 2010 16:04
Location: UK
Contact:

Re: Proper Chess Engine with networked CPUs & LAN play

Postby TESLACOIL » Dec 02, 2012 0:22

Important issues with three fold repetition

Two positions are considered same or equal, if all occupied squares and kind of pieces (not necessarily the same piece) they occupy are the same, the castling rights for both sides did not change, and no en passant capture was possible during the first occurrence, even if obviously not played.



from this

If castling rights change then you can cull/reset the search list

If enpassant rights change then you can *sometimes cull/reset the search list


To clarify >

If enpassant was possible by the opponent it cannot ever be counted as a valid position for the purpose of three fold repetition as enpassant rights only ever last one ply and so by definition cannot exist more than once

If enpassant was not possible then it can be counted as a valid position for the purpose of three fold repetition as 'all the possible opponents moves' can be repeated with out limit as there was no valid enpassant option to expire

* not only do you have to check to see if enpassant was physically possible you also have to check to see if it was legally possible as in taking the pawn the taking side may expose their own king to check from any 10, possible rooks, 10 possible bishops and 9 possible queens < insert gnarly bit of fudge/trick code here , lol >

It is not sufficient to save the position and just add the fact that a pawn has been pushed two squares, you have to save the position with all the opponents newly created legal (but not physical) enpassant rights (if any) so you can compare that specific positions status with all previous saved positions. This means you have to calculate all legal moves for the opponent before you can even start looking to see if a valid position for threefold repetition has been created.

Code: Select all

If a pawn has been pushed two squares AND the opponent could legally take it  enpassant then this position is not valid for three fold repetition

If a pawn has been pushed two squares AND the opponent could physically but not legally take it then this position is valid for three fold repetition

If a pawn has been pushed two squares AND the opponents enpassant rights are unaltered  then this position is valid for three fold repetition





I totally forgot about enpassant rights effecting 3 fold repetition until just now. Glad i checked !
Last edited by TESLACOIL on Dec 02, 2012 1:30, edited 20 times in total.
Stonemonkey
Posts: 587
Joined: Jun 09, 2005 0:08

Re: Proper Chess Engine with networked CPUs & LAN play

Postby Stonemonkey » Dec 02, 2012 0:47

I did it a bit differently, say it's white(cpu) to move, search the board for white pieces, for each white piece found loop through whole board checking for legal move, for each legal move found put the new board position into temporary board and re-call the function passing the new board positions and the colour of piece to play flipped each time and then returning some kind of score.
psuedo code, but it went something like this. I don't know how anyone else does it but that was my solution.

Code: Select all

function make_move(board,colour,depth)
 for y=0 to 7
  for x=0 to 7
   if colour(x,y)=colour then
    for y_dest=0 to 7
     for x_dest=0 to 7
      if test_for_valid_move(x,y,x_dest,y_dest)=1 then
       do some sort of scoring
       if depth<depth_limit then
        copy board to temporary board
        make move from x,y to x_dest,y_dest to temporary board
        make_move(temporary_board,colour xor 1,depth+1)
       end if
      end if
     next
    next
   end if
  next
 next
 return data structure with score and move made
end function
TESLACOIL
Posts: 1769
Joined: Jun 20, 2010 16:04
Location: UK
Contact:

Re: Proper Chess Engine with networked CPUs & LAN play

Postby TESLACOIL » Dec 02, 2012 1:56

Im considering a ray casting principle , or should i say move casting. Knowing how a piece moves (at least start of its turn *promotions ) i cycle through all 16 pieces and look ahead to the destination square to see if it is NOT occupied by one of that sides pieces already.

I think its clear you always have to compute 2 or even 3 ply deep just to encompass checks, three fold repetition etc etc in order to be able to validate the legality of the initial move.

eg the opponents 'physical' but not legal moves have to be examined as you cant place your king in check even though it might be illegal for the opponent to take it. Or you could 'move cast' outward from the king to all potential squares that might be home to a checking piece.
Stonemonkey
Posts: 587
Joined: Jun 09, 2005 0:08

Re: Proper Chess Engine with networked CPUs & LAN play

Postby Stonemonkey » Dec 02, 2012 3:06

Yeah, what I wrote there could be optimised quite a bit, instead of checking every square in the inner loops you'd only need to check the diagonal for bishops, perpendicular lines for rooks, 3*3 squares around king+if castleing is availabe etc. so maybe a select case statement for each type of piece could be used but basically the same method.
TESLACOIL
Posts: 1769
Joined: Jun 20, 2010 16:04
Location: UK
Contact:

Re: Proper Chess Engine with networked CPUs & LAN play

Postby TESLACOIL » Dec 02, 2012 3:23

I think it would be an idea to write a PGN reader

This is a little to simplistic for this job. Its fine for a hobby/ messabout engine but not so hot for a competition engine.
viewtopic.php?f=8&t=19565&p=171610&hilit=chess#p171610

This would be an opportunity to test all the flags/conditions etc and get them right before i indulge in legal move creation and checking. There are quite a few flags and misc data that has to be tagged for a 100% bug free engine. Taking back moves, inserting variations etc and being able to tweak the search parameters in real time would be handy for tuning.

I can add some illegal moves /situations to the PGN file to see if my prog crashes or detects the errors correctly. Its important to be able to setup or import test positions. The more i think about the more i realize its best not to just wade in. You do need a fair amount of extra features to make it all sing together.




Its easy enough to tweak the performance but not so clever if you have a buggy engine you intend on taking part in competition. My current network has a combined fritz bench of approx 250,000kn so even the suckyest algorithms will bite :-D that's about 45billion in speedtest7.exe An overclocked intel 3930k has has a fritz bench of around 20,000kn so i currently have approx 12x that power, this should be sufficient to actually beat any desktop system on the planet. Im planning on slowly upping it to 500,000kn. The 8 core AMD 3250 is a bit crappy but it rocks at chess for the $, another half a dozen of those wont bust the bank

Fritz bench , Speedtest7.exe and CPUid
http://asimov1.wikispaces.com/Download+Benchmarks

Some hot chess PC's 30,000kn achievable with liquid nitrogen cooling
http://www.jens-hartmann.at/Fritzmarks/






Few tweaks and additions , reads in startposition.txt ( see first post ) which now resides in the savegame folder the exe below creates. Reads in data from config.txt which resides in the curdir

Code: Select all

'fbnetchess1.bas

'notes

'using computer notation not chess notation for x,y coordinates to avoid confusion while codeing



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

dim title as string   ' title / header
dim special as string ' data string
dim id(32) as string  ' name of peice
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 ' status of peice
dim notes as string   ' notes



dim as string hpath,spath 'homepath  savepath


dim as integer fnum,plynum 'file number   ply number
dim as string turn

fnum = 999
plynum = 999
turn ="no one"


hpath=curdir
spath=curdir & "\savegame"
 
mkdir "savegame"



OPEN "config.txt" FOR INPUT AS #1
INPUT #1, q
CLOSE #1

?
color 13
?" FBnetchess v1.0   Nov 2012"
color 7
?
?" hpath  "; hpath
?" spath  "; spath
?" q      "; q
?" fnum plynum turn "; fnum; plynum;" "; turn


'sleep:end
sleep






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

chdir spath

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

'sleep:end








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

screen 19


'draw chess board               notes 'Draw String (99, 66), "Origin", 12

locate 2,35 :?"title    = "; title
locate 4,35 :?"special  = "; special
locate 6,35 :?"notes    = "; notes

'sleep

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





sleep:end




Return to “Projects”

Who is online

Users browsing this forum: No registered users and 1 guest