flat assembler
Message board for the users of flat assembler.
 Home   FAQ   Search   Register 
 Profile   Log in to check your private messages   Log in 
flat assembler > Projects and Ideas > chess engine in FASM...

Goto page 1, 2  Next
Author
Thread Post new topic Reply to topic
tthsqe



Joined: 20 May 2009
Posts: 653
chess engine in FASM...
Would anyone like to contribute to a chess engine in FASM? I currently have the basic framework of a bitboard engine and GUI working in FASM.

The engine follows the uci protocol (http://wbec-ridderkerk.nl/html/UCIProtocol.html) and currently plays at about 1800 ELO (http://www.computerchess.org.uk/ccrl/404/). It analyzes ~3 million positions per second with one 2.5GHz laptop core and a simulated PEXT and PDEP. I expect the native PEXT and PDEP of haswell to give good speed boost but haven't tested it on haswell yet.

The engine has LOTS of room for improvement.

If we can make it strong enough (~2500ELO), it could compete in tcec (http://tcec.chessdom.com/).

The engine follows the uci protocol - if you want to use it you can use a well known gui like arena.


Description: updated version - includes several versions for different cpus. might still be some bugs left, but it passed some basic testing. not tested on conroe or nehalem
Download
Filename: fce.zip
Filesize: 113.61 KB
Downloaded: 276 Time(s)



Last edited by tthsqe on 11 Nov 2014, 20:30; edited 5 times in total
Post 16 Jun 2014, 02:25
View user's profile Send private message Reply with quote
r22



Joined: 27 Dec 2004
Posts: 805
How does a chess engine work? Does it find all combinations of X turns ahead and score them based on best/worst outcome to select the next move for the player? Are there lists or databases of terrible moves that are thrown out immediately? Seems like opening moves are pretty well hashed out in the chess world does the engine always use teh same openings or is it more non-deterministic?
Post 16 Jun 2014, 13:52
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 653
r22, It depends on the specific chess engine. Most important is move generation and move make/unmake combined with some search algorithm. Move ordering is important in alpha-beta search. Strong chess programs use better evaluations of the leaf nodes, transposition tables, move ordering heuristics, search tree pruning heuristics,...
Post 16 Jun 2014, 20:46
View user's profile Send private message Reply with quote
r22



Joined: 27 Dec 2004
Posts: 805
So by "bitboard" do you mean storing an empty(0)/occupied(1) board state in a 64bit register 8x8 and then the actual pieces in a dynamic LUT ([0..63] -> piece identifier)? I can see how this would be optimal and why you might want to take advantage of the new PEXT and PDEP opcodes.

If you had a knight at bit position 1 (b1) you could easily check all of it's possible moves with a mask that TESTed bit positions 16 (a3), 18 (c3) and 11 (d2). Cool stuff.

Using this (possibly imaginary) construct you'd have a node structure something like.

Code:

STRUCT moveNode
.board DQ ? ;; 64bit 8x8
.pieces RB 64 ;; [0..64] -> piece ID
.children DQ ? ;; pointer to list of possible child moveNode's
ENDS


Post 17 Jun 2014, 11:55
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 653
r22, I think you get it. My current structures are actually given below. There is great redudancy in the first 64*3 bytes of STATE, but it nice to have a .BOARD that you can look the piece on a given square and bit boards (i.e. .WKNIGHTS), where you can lookup the squares that are occupied by a given piece. For example, BPIECES = BPAWNS | BKNIGHTS | BBISHOPS | BROOKS | BQUEENS | BKING should always hold. Make the opening move e2e4 will involve xoring WPIECES and WPAWNS with (1 shl SQUARE_E2 + 1 shl SQUARE_E4) and making the move on the 64 byte STATE.BOARD. Since making a move (and generating moves) is so quick, I just store a list of pseudolegal moves between [.MOVES_START] and [.MOVES_END]. This way, you only need to store the nodes that are parents of your current node, not the whole tree.

Code:
struct POS
 STATE_PTR       dq ? ;28
 ORG_STATE_PTR   dq ? ;29
 MAIN_RSP        dq ?
                 dq ? ;
 PV              rd MAX_DEPTH*MAX_DEPTH
 PV_LENGTH       rd MAX_DEPTH
 FOLLOW_PV       db ?
ends

struct STATE     ; the first 8*8*3 bytes should be identical for identical positions
;+64*0
 WPIECES     dq ?
 WPAWNS      dq ?
 WKNIGHTS    dq ?
 WBISHOPS    dq ?
 WROOKS      dq ?
 WQUEENS     dq ?
 WKING       dq ?
 EPSQUARE    dq ?
;+64*1
 BPIECES     dq ?
 BPAWNS      dq ?
 BKNIGHTS    dq ?
 BBISHOPS    dq ?
 BROOKS      dq ?
 BQUEENS     dq ?
 BKING       dq ?
 WMSCORE     dw ?
 BMSCORE     dw ?
 SIDE        db ?
 XSIDE       db ?
 CASTLING    db ?
             db ?  ; should be zero
;+64*2
 BOARD       dq ?,?,?,?,?,?,?,?
;+64*3
 HASHKEY     dq ?
 MHASHKEY    dq ?
 PHASHKEY    dq ?
             dq ?

 CHECKERS    dq ?
 ALPHA       dd ?
 BETA        dd ?
 EVAL        dd ?
 DEPTH       dd ?
             dq ?

 MOVES_START dq ?
 MOVES_END   dq ?
 MOVES_PTR   dq ?
 PLY         dd ?
 MATE        db ?
             db ?
             db ?
             db ?

ends                 

Post 17 Jun 2014, 13:21
View user's profile Send private message Reply with quote
r22



Joined: 27 Dec 2004
Posts: 805
Beyond the obvious win/lose checks, how do you score potential moves? Also what are the time/move and memory constraints of these competitive engines? If a memory constraint is imposed you'd want a more compressed state structure.

And... you have a flag for 'castling' but none for 'en passant' Very Happy
Post 17 Jun 2014, 17:36
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 653
For en passant I use a bitboard EPSQUARE since there is a 8 byte hole after the white pieces and nothing to fill it. Now that I think about it, I could put EPSQUARE as a byte in the hole after CASTLING and move the bitboard CHECKERS to the current EPSQUARE location. That should still preserve the identity property for the first 64*3 bytes Smile.


Quote:
how do you score potential moves?


chess evaluation is an art form in itself... At minimum, you should take the difference of the material scores (WMSCORE-BMSCORE), and have a term for mobility. King safety is quite tricky but improves the engine's play.


Quote:
Also what are the time/move and memory constraints of these competitive engines?


The time constraints are determined by the match conditions. Engines should be able to search 3-4 moves deep and produce an adequate move within a milisecond. The best open source program searches to 30-40 moves deep in a couple of minutes. As for the memory constraints, these are generally determined by the size of the hash table. I've seen anthing from 1MB to 16GB for the hash table.


Quote:
If a memory constraint is imposed you'd want a more compressed state structure.


As I said before, the size of the STATE structure does not matter. I do not store the whole search tree in memory - only the list of parents from the root to the current child node is stored. The hash table is what holds information about each node in the search tree, and it is the hash entries should of course be compressed as much as possible. The large STATE strucutre is for fast move making and move generation.

If I get the code cleaned up soon, I'll post an example engine.
Post 17 Jun 2014, 17:57
View user's profile Send private message Reply with quote
r22



Joined: 27 Dec 2004
Posts: 805
Seems the two major factors for an engine are the speed at which you can generate move permutations and the quality of your scoring heuristics.

Move generation can easily be optimized all the way to the opcode level, but choosing the correct move seems like it would take great insight into chess to begin with. Perhaps a genetic algorithm or neural network could be trained to do the best job at that.
Post 17 Jun 2014, 18:46
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 653
yeah - most of the factors that make a chess program strong are algorithmic and not dependent on pedal-to-the-medal opcode optimizations. But it should still be fun anyways
Post 17 Jun 2014, 18:57
View user's profile Send private message Reply with quote
HaHaAnonymous



Joined: 02 Dec 2012
Posts: 1173
Location: Unknown
Stupid post removed.


Last edited by HaHaAnonymous on 28 Feb 2015, 18:12; edited 1 time in total
Post 24 Jun 2014, 22:28
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 653
perpetual development
Post 25 Jun 2014, 04:17
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 653
posted an engine
Post 19 Oct 2014, 09:58
View user's profile Send private message Reply with quote
HaHaAnonymous



Joined: 02 Dec 2012
Posts: 1173
Location: Unknown
Stupid post removed.


Last edited by HaHaAnonymous on 28 Feb 2015, 18:00; edited 1 time in total
Post 01 Feb 2015, 03:38
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 653
Haha, if you want to port something, try my updated version at https://github.com/tthsqe12/asm
If you can make a working linux version ill include it in the master.
Post 01 Feb 2015, 06:55
View user's profile Send private message Reply with quote
m3ntal



Joined: 08 Dec 2013
Posts: 296
Very good code, tthsqe.

Thinking about getting a 64BIT PC soon (ASrock ITX Quad MB+CPU = $75, InWin Developer case = $50, 2G memory = $20). So, I can test your examples.
Post 02 Feb 2015, 04:50
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 653
Haha, I was serious about the linux port. See if you can can translate the functions in Windows.asm on my repo into linux syscalls. It would be really cool if you did. Also, Ill be adding a windows ches gui for uci engines to the repo soon.
Post 02 Feb 2015, 19:48
View user's profile Send private message Reply with quote
HaHaAnonymous



Joined: 02 Dec 2012
Posts: 1173
Location: Unknown
Stupid post removed.


Last edited by HaHaAnonymous on 28 Feb 2015, 17:58; edited 1 time in total
Post 03 Feb 2015, 15:22
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 653
it might be more difficult than i orginally though.
the pthread functions in stockfish are here
https://github.com/official-stockfish/Stockfish/blob/master/src/platform.h#L61
and for example, i found an implementation of one of the functions at
http://fossies.org/dox/glibc-2.20/pthread__mutex__init_8c_source.html
Post 04 Feb 2015, 04:03
View user's profile Send private message Reply with quote
gens



Joined: 18 Feb 2013
Posts: 159
it is futex in the kernel, then most pthread things are built upon that
there are bout man 2 and 7 pages about it and plenty of docs online

PS musl is a much simpler library
http://git.musl-libc.org/cgit/musl/tree/src/thread
Post 04 Feb 2015, 11:18
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 653
m3ntal, kudos to you if you can make an inexpensive windows box. I just added a gui to my repo, so you can play against the engine and other engines as well. Let me know if something doesn't work on your box.
Post 05 Feb 2015, 07:32
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page 1, 2  Next

< Last Thread | Next Thread >

Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Powered by phpBB © 2001-2005 phpBB Group.

Main index   Download   Documentation   Examples   Message board
Copyright © 2004-2016, Tomasz Grysztar.