Proper Chess Engine with networked CPUs & LAN play

User projects written in or related to FreeBASIC.
Stonemonkey
Posts: 587
Joined: Jun 09, 2005 0:08

Re: Proper Chess Engine with networked CPUs & LAN play

Postby Stonemonkey » Dec 02, 2012 22:56

From the code I posted, I'm doing this. All information for en passant and castling is stored in the board.

Code: Select all

'piece bits
'
'0-2 -> piece (pawn=1,rook=2,knight=3,bishop=4,queen=5,king=6)
'3   -> colour (0=black,8=white)
'4   -> piece moved (0=moved,16=not moved)
'5   -> pawn moved 2 places in last move(en passant)
board_data:'board startup position
'black (17=pawn->22=king)
data 18,19,20,21,22,20,19,18
data 17,17,17,17,17,17,17,17
data 00,00,00,00,00,00,00,00
data 00,00,00,00,00,00,00,00
data 00,00,00,00,00,00,00,00
data 00,00,00,00,00,00,00,00
data 25,25,25,25,25,25,25,25
data 26,27,28,29,30,28,27,26
'white(25=pawn->30=king)
'
'When a piece is moved, bits 4 and 5(=16 and 32) are set to 0.
'Exception - if a pawn is moved forward by 2 places on it's
'first move bit 5 is set to 1
'
TESLACOIL
Posts: 1769
Joined: Jun 20, 2010 16:04
Location: UK
Contact:

Re: Proper Chess Engine with networked CPUs & LAN play

Postby TESLACOIL » Dec 03, 2012 1:18

I was thinking along those lines too

For tracking 3 fold repetition, which by definition requires two or more 'complete' board states to be = , i was thinking of putting the information into a string. If String A = any previous string then you are one step closer to 3fold repetition. If string A <> any previous string then add it to the list of all previous strings.

knowing if you are 1 or 2 steps away from 3fold repetition will profoundly effect the valuations of the effected positions

any half decent chess engine will need that value at all times, as its creating the move tree AND when its deciding which branches to prune

Chess games are typically 30 to 70 moves long but you can cull the 3fold list every time certain events occur so the length of the list you need to check will most often range between 1 and 10. Though it may exceed 50 in certain end games but then you have a whole heap less to calculate as most of the pieces are off the board by then....The computation problem arises when you need to compute it along side the many thousands or millions of board positions you generate each and every move. Im not sure what % CPU burden this will cause, perhaps insignificant in the overall scheme of things.

I have played several games where sacking a piece has enabled me to escape defeat as by that action i exposed the enemy king and got a draw through repetition...Its for reasons like this that its wise to include 3fold evaluation at every stage and not just an after thought.



Board representation
http://en.wikipedia.org/wiki/Board_repr ... 28chess%29

Chess piece relative value.
http://en.wikipedia.org/wiki/Chess_piece_relative_value





Im also considering embedding all important information in the board representation. The value of the pieces, live en passant, the check status of the king. The data size might double but it might make evaluation of the board and legality checking a much swifter process.

An eloquent board representation might well reduce the amount of fudge code/computation required for 100% legal move generation and at the same time yield 'ball park figures' for evaluations.

example in decimal for clarity

eg a king might be 9000 its piece value, +/- smaller numbers which define its board position, value at that position, check status, castling potential, freedoms of movement etc

The key problem for 100% legal move generation is having to wade through miles & miles of unimportant data in search of the snippets of important data. If some or perhaps even all of those golden nuggets can be encoded in the board representation then you don't have to go looking to far for them.
Last edited by TESLACOIL on Dec 03, 2012 1:55, 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 03, 2012 1:55

eg a king might be 9000 +/- smaller numbers which define its board position, check status, castling potential, freedoms of movement


It's easier to use the bits rather than fiddling around with values like that.

what the piece is could be found with:
piece=square(x,y) AND 7

1=pawn
2=rook
3=knight
etc.

the colour of the piece(although it might be easier to use 2 bits, 01 for black,10 for white or something)
colour=square(x,y) AND 8

whether or not the piece has been moved since the start of the game (this bit is set to 1 for each piece when game starts)
move=square(x,y) AND 16

if the piece can be taken by en passant
passant=square(x,y) AND 32

when a piece is moved, using
square(new_x,new_y)=square(old_x,old_y) AND &hef
square(old_x,old_y)=0
the bit to say if the piece has been moved is set to 0 by the 'AND &hef'
TESLACOIL
Posts: 1769
Joined: Jun 20, 2010 16:04
Location: UK
Contact:

Re: Proper Chess Engine with networked CPUs & LAN play

Postby TESLACOIL » Dec 03, 2012 2:07

ref It's easier to use the bits rather than fiddling around with values like that.

yup, agreed it is fiddly

I was stealing the idea/schema from the evaluation side of things where fiddly stuff like that is actually used. Eg the value of a bishop is reduced if its not part of a pair of bishops and it is increased if it sits on a good bishop square and likewise its decreased if its sat in a corner or has not moved. Positions are evaluated in centi pawns, 1/100ths of a pawn. The king usually higher in value than all pieces combined.

King 9999
queen 900
rook 500
bishop 330
knight 300
pawn 100

Im sure it possible to combine elements of both schema( binary flags, dynamic values) but it would be tricky to get it right.
TESLACOIL
Posts: 1769
Joined: Jun 20, 2010 16:04
Location: UK
Contact:

Re: Proper Chess Engine with networked CPUs & LAN play

Postby TESLACOIL » Dec 03, 2012 2:23

Perpetual check is a rather nebulous condition one also has to test and evaluate

Perpetual check
http://en.wikipedia.org/wiki/Perpetual_check
Last edited by TESLACOIL on Dec 03, 2012 2:25, 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 03, 2012 2:25

An integer value can be assigned in the same way using higher bits, so far I've only used 6 so still plenty for something like that.
For example you could use 8 bits to store a base value for the piece and another 8 bits for a variable value.

Another way that's been mentioned is to use UDTs, that way you don't need to worry about shifting the bits up and down and it might make the code a bit more understandable.
TESLACOIL
Posts: 1769
Joined: Jun 20, 2010 16:04
Location: UK
Contact:

Re: Proper Chess Engine with networked CPUs & LAN play

Postby TESLACOIL » Dec 03, 2012 2:26

I think the idea of using lots of fields ( flags ) is a good way to go. It Keeps it tidy and if its in an array its easy to compare.

some boards are 12x12 this allows the king to use a fixed pattern detector for detecting night checks rather then a seek routine which alters depending on the kings position.


Generating Legal King moves

It might be worth hard coding detection of king in check. Casting outwards from the king as i mentioned earlier.

You cant castle if you are in check OR if the king passes through a line of check OR if the destination square is threatened

The other way is just to brute force all 'physical' and not just 'legal' moves for the other side. If ANY of the outcomes sees your value drop by 9999 then you know the king got the chop and thus that move is illegal.

*during castling it does not matter if the rook is threatened or passes through attack lines ONLY threats to the king count
Last edited by TESLACOIL on Dec 03, 2012 2:48, edited 2 times in total.
Stonemonkey
Posts: 587
Joined: Jun 09, 2005 0:08

Re: Proper Chess Engine with networked CPUs & LAN play

Postby Stonemonkey » Dec 03, 2012 2:38

I wouldn't be too bothered by perpetual check, it won't be part of the move checking and could be done with storing the board with each move and comparing back a number of moves to make sure the game isn't going round in circles.
TESLACOIL
Posts: 1769
Joined: Jun 20, 2010 16:04
Location: UK
Contact:

Re: Proper Chess Engine with networked CPUs & LAN play

Postby TESLACOIL » Dec 03, 2012 2:41

ref perpetual check

yeah, its nebulous and very important evaluation wise but not technically critical....a simple tally of 'check density' and or 'checks in a row' would prolly suffice. Lines with high check counts need to be investigated anyway, that's just common sense.

Set of metrics of 100% legal move generation

Set of metrics for evaluation ( Perpetual check could go here )



Q Stonemonkey , you play chess yourself ? I used to played for a club a while back
Stonemonkey
Posts: 587
Joined: Jun 09, 2005 0:08

Re: Proper Chess Engine with networked CPUs & LAN play

Postby Stonemonkey » Dec 03, 2012 2:57

I'm going to give this a go too, maybe get them to play off against each other if they get finished.
Stonemonkey
Posts: 587
Joined: Jun 09, 2005 0:08

Re: Proper Chess Engine with networked CPUs & LAN play

Postby Stonemonkey » Dec 03, 2012 3:04

A. I've played from time to time against friends and my dad but that's about it.
TESLACOIL
Posts: 1769
Joined: Jun 20, 2010 16:04
Location: UK
Contact:

Re: Proper Chess Engine with networked CPUs & LAN play

Postby TESLACOIL » Dec 03, 2012 3:14

Im probably a much more experienced player, but your coding skills are far ahead of mine.

I am good at design & problem solving though. If i wasn't good at design id run a mile from writing a chess engine lol especially with my nooby code skills.

Engine match would be fun. Just got to get over the '100% legal move generation' and then the evaluation battles can begin.



* i have a dozen or so fast computers and all the top chess engines at my disposal so i can help tweak any evaluation engines we build. Its winter in the UK and busy CPU's keep the frost at bay, that's my excuses anyway.
TESLACOIL
Posts: 1769
Joined: Jun 20, 2010 16:04
Location: UK
Contact:

Re: Proper Chess Engine with networked CPUs & LAN play

Postby TESLACOIL » Dec 03, 2012 3:59

Castling

Castling is tricky as you have to find threats to every square the king passes through as generating pseudo moves for the other side in order to detect check either wont work if you just rely on the testing the landing square. You have to let the king move 1 and 2 squares, checking both locations are safe.

Kings traveling through lines of check are illegal and its a typical bug many programmers miss or forget.


http://en.wikipedia.org/wiki/Castling
Stonemonkey
Posts: 587
Joined: Jun 09, 2005 0:08

Re: Proper Chess Engine with networked CPUs & LAN play

Postby Stonemonkey » Dec 03, 2012 4:06

Yep, I've just finished working on that and I think it's all working, en passant too, and it won't allow any move that puts it in check or any move that doesn't get out of check.

It doesn't detect check mate or stale mate yet but that shouldn't be too much of a problem.

I don't know how to deal with the promotion to different pieces atm though.
TESLACOIL
Posts: 1769
Joined: Jun 20, 2010 16:04
Location: UK
Contact:

Re: Proper Chess Engine with networked CPUs & LAN play

Postby TESLACOIL » Dec 03, 2012 4:20

Castling a speedy solution !

If you check a kings normal move positions first then you will already know if it can move that transient 1 square left or 1 square right. Just look up the appropriate board. Or whenever king left = valid set a flag and check for that flag prior to testing for castling that side....this falls under code optimization

Code: Select all


If castling = possible AND normal king left = legal then proceed with next phase of  the castling test ELSE cant castle this way

etc

Last edited by TESLACOIL on Dec 03, 2012 4:29, edited 4 times in total.

Return to “Projects”

Who is online

Users browsing this forum: No registered users and 2 guests