World Draughts Forum

It is currently Fri Sep 22, 2017 07:10

All times are UTC+01:00




Post new topic  Reply to topic  [ 162 posts ]  Go to page Previous 17 8 9 10 11
Author Message
 Post subject: Re: Scan
PostPosted: Wed Jul 12, 2017 08:16 
Offline

Joined: Wed Apr 14, 2004 15:04
Posts: 1550
Fabien Letouzey wrote:
Hi all,

Scan 3.0 (and the corresponding Hub 2.0) are now available on Harm Jetten's website:
http://hjetten.home.xs4all.nl/scan/scan.html
Many thanks to him!

It is the version that participated in the Computer Olympiad this year. You will need to copy the endgame tables from Scan 2.0 (directory data/bb) or download them separately. Or you can set "bb-size = 0" in scan.ini for now to deactivate them.

Scan 3.0 also supports Killer and breakthrough (BT) draughts variants. You will need to download the corresponding endgame tables separately and install them into the "data" directory. Note that, for BT, bb-size = 7 instead of the usual 6.

Enjoy Scan!

Fabien.


Hi Fabien,

Great, wonderful! I will upload the files to GitHub later next week.


Top
   
 Post subject: Re: Scan
PostPosted: Wed Jul 12, 2017 11:11 
Offline

Joined: Thu Jan 15, 2015 16:28
Posts: 51
Real name: Coulibaly Sidiki
Rein Halbersma wrote:
Fabien Letouzey wrote:
Hi all,

Scan 3.0 (and the corresponding Hub 2.0) are now available on Harm Jetten's website:
http://hjetten.home.xs4all.nl/scan/scan.html
Many thanks to him!

It is the version that participated in the Computer Olympiad this year. You will need to copy the endgame tables from Scan 2.0 (directory data/bb) or download them separately. Or you can set "bb-size = 0" in scan.ini for now to deactivate them.

Scan 3.0 also supports Killer and breakthrough (BT) draughts variants. You will need to download the corresponding endgame tables separately and install them into the "data" directory. Note that, for BT, bb-size = 7 instead of the usual 6.

Enjoy Scan!

Fabien.


Hi Fabien,

Great, wonderful! I will upload the files to GitHub later next week.



Hi Fabien,

Please, can i Know what is the difference between normal mode and breakthrough?

Thank for this release.


Top
   
 Post subject: Re: Scan
PostPosted: Wed Jul 12, 2017 11:39 
Offline

Joined: Tue Jul 07, 2015 06:48
Posts: 235
Real name: Fabien Letouzey
Sidiki wrote:
Please, can i Know what is the difference between normal mode and breakthrough?

In breakthrough, you win as soon as you make a king. The name comes from this game: https://en.m.wikipedia.org/wiki/Breakthrough_(board_game)


Top
   
 Post subject: Re: Scan
PostPosted: Wed Jul 12, 2017 13:37 
Offline

Joined: Thu Jun 20, 2013 16:16
Posts: 530
Real name: Krzysztof Grzelak
Thank you Fabien. So far after 2 hours I have not run Scan 3.0.


Top
   
 Post subject: Re: Scan
PostPosted: Sun Jul 23, 2017 09:22 
Offline

Joined: Wed Apr 14, 2004 15:04
Posts: 1550
Rein Halbersma wrote:
Fabien Letouzey wrote:
Hi all,

Scan 3.0 (and the corresponding Hub 2.0) are now available on Harm Jetten's website:
http://hjetten.home.xs4all.nl/scan/scan.html
Many thanks to him!

It is the version that participated in the Computer Olympiad this year. You will need to copy the endgame tables from Scan 2.0 (directory data/bb) or download them separately. Or you can set "bb-size = 0" in scan.ini for now to deactivate them.

Scan 3.0 also supports Killer and breakthrough (BT) draughts variants. You will need to download the corresponding endgame tables separately and install them into the "data" directory. Note that, for BT, bb-size = 7 instead of the usual 6.

Enjoy Scan!

Fabien.


Hi Fabien,

Great, wonderful! I will upload the files to GitHub later next week.


For those interested to see what has changed in the source code, I have updated the GitHub repositories for Scan and Hub to reflect the latest releases (Scan 3.0 and Hub 2.0).


Top
   
 Post subject: Re: Scan
PostPosted: Sun Jul 23, 2017 11:54 
Offline

Joined: Tue Jul 07, 2015 06:48
Posts: 235
Real name: Fabien Letouzey
Hi Rein,

Rein Halbersma wrote:
For those interested to see what has changed in the source code, I have updated the GitHub repositories for Scan and Hub to reflect the latest releases (Scan 3.0 and Hub 2.0).

I followed your advice and added a Node class (http://fmjd.org/bb3/viewtopic.php?p=116882#p116882). I don't like the name, but couldn't find a better one ... As I understand, you got the idea from Don?

I'm generally satisfied with this way, and might even use it in games with more piece types. The pain point is due to C++ not managing memory, so it's my responsibility to guarantee that the parent pointer is always valid. It's a piece of cake for recursive functions (search), but not at global level, say to store the game in progress.

I also note that it's not possible to maintain large structures incrementally (like the trit board that I used in Scan 2.0).

Fabien.


Top
   
 Post subject: Re: Scan
PostPosted: Sun Jul 23, 2017 15:43 
Offline

Joined: Wed Apr 14, 2004 15:04
Posts: 1550
Fabien Letouzey wrote:
Hi Rein,

Rein Halbersma wrote:
For those interested to see what has changed in the source code, I have updated the GitHub repositories for Scan and Hub to reflect the latest releases (Scan 3.0 and Hub 2.0).

I followed your advice and added a Node class (http://fmjd.org/bb3/viewtopic.php?p=116882#p116882). I don't like the name, but couldn't find a better one ... As I understand, you got the idea from Don?


Yes, I think Don Dailey was the most prominent champion of Nodes with copy-make semantics. See some of his old Talkchess posts. One reason is that copy-make plays very nice with the Cilk parallelism extensions to C (there is now also Cilk-Plus, owned by Intel, which similarly extends C++). You probably know Don's 2001 article Using Cilk to Write Multiprocessor Chess Programs.

I don't think the source for CilkChess is available. However, MIT students did play quite a bit with Cilk-based game playing code, e.g. in this 1998 hackathon to create another board game engine (Cilk Pousse), see http://people.csail.mit.edu/pousse/ (It's a great read, very fun and interesting story). Unfortunately, this source is no longer available anymore (dead link). But many years later, in a 2010 MIT programming course, I found the following http://courses.csail.mit.edu/6.884/spri ... ha.tar.bz2 that contains an attempt at a C++ port of the CilkPousse code. It has the same copy-make based Node with parent pointers.

Quote:
I'm generally satisfied with this way, and might even use it in games with more piece types. The pain point is due to C++ not managing memory, so it's my responsibility to guarantee that the parent pointer is always valid. It's a piece of cake for recursive functions (search), but not at global level, say to store the game in progress.


Why not store the ongoing game history in a std::list<Node>, so that the pointers remain valid after new moves are being made? (doesn't work with std::vector though, upon reallocation the pointers get invalidated).

Quote:
I also note that it's not possible to maintain large structures incrementally (like the trit board that I used in Scan 2.0).


Yes, the GitHub repo is becoming quite big with all the binaries :)


Top
   
 Post subject: Re: Scan
PostPosted: Sun Jul 23, 2017 16:01 
Offline

Joined: Wed Apr 14, 2004 15:04
Posts: 1550
Fabien Letouzey wrote:
I followed your advice and added a Node class (http://fmjd.org/bb3/viewtopic.php?p=116882#p116882). I don't like the name, but couldn't find a better one ... As I understand, you got the idea from Don?


Another inspiring (for me!) source for using a Node class is the great book Artificial Intelligence: a Modern Approach (AIMA) by Russell and Norvig. They make the distinction between State (in draughts/chess/othello: placement of piece, side to move, other stuff, but excluding history) and the Node (State including history, by using back pointer into the search graph). The graph search algorithms are all using Nodes. It's a very natural class to have. E.g. browse this Python repo for chapter 3 of the book: https://github.com/aimacode/aima-python ... /search.py Note that their algorithms are mostly non-recursive, but using an iterative root driver.


Top
   
 Post subject: Re: Scan
PostPosted: Sun Jul 23, 2017 18:38 
Offline

Joined: Tue Jul 07, 2015 06:48
Posts: 235
Real name: Fabien Letouzey
Rein Halbersma wrote:
Yes, I think Don Dailey was the most prominent champion of Nodes with copy-make semantics. See some of his old Talkchess posts. One reason is that copy-make plays very nice with the Cilk parallelism extensions to C (there is now also Cilk-Plus, owned by Intel, which similarly extends C++). You probably know Don's 2001 article Using Cilk to Write Multiprocessor Chess Programs.

I remember having a look at Cilk a long time ago. The work-stealing part makes it the ideal language for parallel alpha-beta, which I assumed was exactly the point.

And then I read that the technology was acquired by Intel ... How likely is that?

Quote:
Why not store the ongoing game history in a std::list<Node>, so that the pointers remain valid after new moves are being made? (doesn't work with std::vector though, upon reallocation the pointers get invalidated).

I didn't think of it, as I've never had a use case before. Also, for a move list the API really should be that of an array.


Top
   
 Post subject: Re: Scan
PostPosted: Sun Jul 23, 2017 18:44 
Offline

Joined: Tue Jul 07, 2015 06:48
Posts: 235
Real name: Fabien Letouzey
Rein Halbersma wrote:
Fabien Letouzey wrote:
I followed your advice and added a Node class (http://fmjd.org/bb3/viewtopic.php?p=116882#p116882). I don't like the name, but couldn't find a better one ... As I understand, you got the idea from Don?


Another inspiring (for me!) source for using a Node class is the great book Artificial Intelligence: a Modern Approach (AIMA) by Russell and Norvig. They make the distinction between State (in draughts/chess/othello: placement of piece, side to move, other stuff, but excluding history) and the Node (State including history, by using back pointer into the search graph). The graph search algorithms are all using Nodes. It's a very natural class to have. E.g. browse this Python repo for chapter 3 of the book: https://github.com/aimacode/aima-python ... /search.py Note that their algorithms are mostly non-recursive, but using an iterative root driver.


I'm not sure it's natural. As a functional programmer, this "Node" class looks like a list of positions to me and is as such not worthy of a name. For the application to graphs, I guess the abstraction is "path". Disclaimer: I haven't had a look at the Python examples.

But in Scan I mostly use it as a position, except for two places that need repetition detection. I didn't find an appropriate (and short!) name for this.


Top
   
 Post subject: Re: Scan
PostPosted: Sun Jul 23, 2017 18:58 
Offline

Joined: Wed Apr 14, 2004 15:04
Posts: 1550
Fabien Letouzey wrote:
Rein Halbersma wrote:
Yes, I think Don Dailey was the most prominent champion of Nodes with copy-make semantics. See some of his old Talkchess posts. One reason is that copy-make plays very nice with the Cilk parallelism extensions to C (there is now also Cilk-Plus, owned by Intel, which similarly extends C++). You probably know Don's 2001 article Using Cilk to Write Multiprocessor Chess Programs.

I remember having a look at Cilk a long time ago. The work-stealing part makes it the ideal language for parallel alpha-beta, which I assumed was exactly the point.

And then I read that the technology was acquired by Intel ... How likely is that?


There is work underway to get work-stealing technology into the C++ Standard, and Intel is of course very much interested to own tools that enable their multi-core technology for the programmer masses (and MIT professors very much like to be bought out after developing such tools :)). The only thing not quite working with Cilk-Plus is the "abort" feature that its predecessor Cilk had. This makes writing a parallel alpha-beta search still quite tricky. Whenever they gain "abort" like features, it will be a piece of cake.

Quote:
Quote:
Why not store the ongoing game history in a std::list<Node>, so that the pointers remain valid after new moves are being made? (doesn't work with std::vector though, upon reallocation the pointers get invalidated).

I didn't think of it, as I've never had a use case before. Also, for a move list the API really should be that of an array.


Then perhaps std::deque<Node>, which has the same invalidation conditions for pointers to its elements as std::list, but also has array like indexing (using operator[]).


Top
   
 Post subject: Re: Scan
PostPosted: Sun Jul 23, 2017 19:12 
Offline

Joined: Wed Apr 14, 2004 15:04
Posts: 1550
Fabien Letouzey wrote:
I'm not sure it's natural. As a functional programmer, this "Node" class looks like a list of positions to me and is as such not worthy of a name. For the application to graphs, I guess the abstraction is "path". Disclaimer: I haven't had a look at the Python examples.

But in Scan I mostly use it as a position, except for two places that need repetition detection. I didn't find an appropriate (and short!) name for this.


Just so we use the same terminology, the AIMA book has a great section on this.
Quote:
3.3.1 Infrastructure for search algorithms
Search algorithms require a data structure to keep track of the search tree that is being constructed.
For each node n of the tree, we have a structure that contains four components:
• n.STATE: the state in the state space to which the node corresponds;
• n.PARENT: the node in the search tree that generated this node;
• n.ACTION: the action that was applied to the parent to generate the node;
• n.PATH-COST: the cost, traditionally denoted by g(n), of the path from the initial state
to the node, as indicated by the parent pointers.

The node data structure is depicted in Figure 3.10. Notice how the PARENT pointers
string the nodes together into a tree structure. These pointers also allow the solution path to be
extracted when a goal node is found; we use the SOLUTION function to return the sequence
of actions obtained by following parent pointers back to the root.

Up to now, we have not been very careful to distinguish between nodes and states, but in
writing detailed algorithms it’s important to make that distinction. A node is a bookkeeping
data structure used to represent the search tree. A state corresponds to a configuration of the
world. Thus, nodes are on particular paths, as defined by PARENT pointers, whereas states
are not. Furthermore, two different nodes can contain the same world state if that state is
generated via two different search paths.


Applying this to draughts/chess: what the AIMA book calls State is what most people call Position, and what AIMA calls Action is what most people call Move. Also, PATH-COST is just the ply depth from the root.

The Node class + the PARENT pointers together form the search graph, and tracing the pointers gives your path abstraction. Note that the search graph is an implicit graph, and the edges (i.e. moves/actions) between the vertices a.k.a nodes (containing states/positions) are discovered dynamically through the move generator. I agree that Node is not a fundamental abstraction, but it is a natural building block for the graph abstraction.

In my library, I use the AIMA terminology. My State has several components, the side to move, and the piece placements (bitboard collection, I call this Position).

Chapter 3 in AIMA and the Python repo give a nice infrastructure for analyzing game trees. You can write all algorithm in a game independent way, and just plug in your own State, Action and Successor functions.


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 162 posts ]  Go to page Previous 17 8 9 10 11

All times are UTC+01:00


Who is online

Users browsing this forum: No registered users and 2 guests


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 post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Limited