Scan

Discussion about development of draughts in the time of computer and Internet.
Post Reply
Rein Halbersma
Posts: 1628
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Scan

Post by Rein Halbersma » Wed Jul 12, 2017 09:16

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.

Sidiki
Posts: 112
Joined: Thu Jan 15, 2015 16:28
Real name: Coulibaly Sidiki

Re: Scan

Post by Sidiki » Wed Jul 12, 2017 12:11

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.

Fabien Letouzey
Posts: 285
Joined: Tue Jul 07, 2015 07:48
Real name: Fabien Letouzey

Re: Scan

Post by Fabien Letouzey » Wed Jul 12, 2017 12:39

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/Breakth ... oard_game)

Krzysztof Grzelak
Posts: 716
Joined: Thu Jun 20, 2013 17:16
Real name: Krzysztof Grzelak

Re: Scan

Post by Krzysztof Grzelak » Wed Jul 12, 2017 14:37

Thank you Fabien. So far after 2 hours I have not run Scan 3.0.

Rein Halbersma
Posts: 1628
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Scan

Post by Rein Halbersma » Sun Jul 23, 2017 10:22

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).

Fabien Letouzey
Posts: 285
Joined: Tue Jul 07, 2015 07:48
Real name: Fabien Letouzey

Re: Scan

Post by Fabien Letouzey » Sun Jul 23, 2017 12:54

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.

Rein Halbersma
Posts: 1628
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Scan

Post by Rein Halbersma » Sun Jul 23, 2017 16:43

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.
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).
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 :)

Rein Halbersma
Posts: 1628
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Scan

Post by Rein Halbersma » Sun Jul 23, 2017 17:01

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.

Fabien Letouzey
Posts: 285
Joined: Tue Jul 07, 2015 07:48
Real name: Fabien Letouzey

Re: Scan

Post by Fabien Letouzey » Sun Jul 23, 2017 19:38

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?
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.

Fabien Letouzey
Posts: 285
Joined: Tue Jul 07, 2015 07:48
Real name: Fabien Letouzey

Re: Scan

Post by Fabien Letouzey » Sun Jul 23, 2017 19:44

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.

Rein Halbersma
Posts: 1628
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Scan

Post by Rein Halbersma » Sun Jul 23, 2017 19:58

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.
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[]).

Rein Halbersma
Posts: 1628
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Scan

Post by Rein Halbersma » Sun Jul 23, 2017 20:12

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.
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.

Fabien Letouzey
Posts: 285
Joined: Tue Jul 07, 2015 07:48
Real name: Fabien Letouzey

Re: Scan

Post by Fabien Letouzey » Sat Jul 06, 2019 15:08

Hi all,

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

The main addition in this version are two new variants: Frisian draughts and losing draughts (aka antidraughts/giveaway/suicide). This completes the set of variants discussed here:
viewtopic.php?f=53&t=4013&start=690

There are also a few changes that make it worthwhile to upgrade for most. Sometimes in the most unexpected place: for ildjarn (if he uses Scan at all), Scan will allow positions with more than 20 pieces per side (at his own peril).

---

You will need to copy the endgame tables from Scan 3.0 (directory data/bb) or download them separately. Don't forget to set "bb-size" accordingly in scan.ini

You can also move the new executable to your favourite directory (after renaming the old one for safety), but make sure to also use the new evaluation files in the "data" directory. While Scan's evaluation function is the same as before, the file format has changed.

Enjoy Scan!

Fabien.

Krzysztof Grzelak
Posts: 716
Joined: Thu Jun 20, 2013 17:16
Real name: Krzysztof Grzelak

Re: Scan

Post by Krzysztof Grzelak » Sun Jul 07, 2019 09:40

Thank you very much Fabien.

hendrikv
Posts: 81
Joined: Sun Jul 17, 2005 09:04
Real name: Hendrik Veenstra
Location: Oerterp
Contact:

Re: Scan

Post by hendrikv » Mon Jul 22, 2019 22:17

Nice blog post about the new version of Scan and the integration in Lidraughts.
https://lidraughts.org/blog/XQlZORAAACE ... tidraughts

Post Reply