Unifying make/undo and copy-make

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Rein Halbersma
Posts: 689
Joined: Tue May 22, 2007 9:13 am

Unifying make/undo and copy-make

Post by Rein Halbersma » Mon Dec 21, 2015 3:00 pm

Every great magic trick consists of three parts or acts. The first part is called "The Pledge". The magician shows you something ordinary: a deck of cards, a bird or a man. He shows you this object. Perhaps he asks you to inspect it to see if it is indeed real, unaltered, normal. But of course...it probably isn't.
Consider the following skeleton for a recursive tree traversal (using the Action/State vocabulary of the Russell & Norvig AI textbook) based on a very simple game that has a single integer as its state. Let's assume there's only one legal move at each depth. See here for an online example.

Code: Select all

#include <iostream>

struct Action
&#123;
    int val;
&#125;;

struct State
&#123;    
    int val_;
    State& make&#40;Action const& a&#41; &#123; val_ += a.val; return *this; &#125;
    State& undo&#40;Action const& a&#41; &#123; val_ -= a.val; return *this; &#125;
    int val&#40;) const &#123; return val_; &#125;
&#125;;

void traverse&#40;State& s, int d&#41; // state by non-const ref
&#123;
    std&#58;&#58;cout << "depth = " << d << ", value = " << s.val&#40;) << "\n";
    if &#40;d == 0&#41; return;
    Action const a&#91;1&#93; = &#123; Action&#123;1&#125; &#125;;  // "move generation" 
    for &#40;int i = 0; i < 1; ++i&#41; &#123;
        s.make&#40;a&#91;i&#93;);
        traverse&#40;s, d - 1&#41;; // wrap recursive call with make/undo that modify state
        s.undo&#40;a&#91;i&#93;);
    &#125;
&#125;

int main&#40;)
&#123;
    State s&#123;0&#125;; // globally modifiable state
    traverse&#40;s, 3&#41;;
&#125;
Isn't it annoying that the state is passed by non-const reference to the traversal algorithm that -when all is said and done- leaves the state in its original position? And the manual make/undo wrapping of the recursive call is also not exception-safe. So you can't mimic e.g. the practice popularized by the Boost.Graph library and throw an exception when the search has found a match, when the GUI demands a response, or when the allocated time is up.
The second act is called "The Turn". The magician takes the ordinary something and makes it do something extraordinary. Now you're looking for the secret... but you won't find it, because of course you're not really looking. You don't really want to know. You want to be fooled.
So let's try and fix it and do the good old copy-make, and for good measure, let's wrap the state inside a node with parent and action pointers to be able to walk up and down the search tree. See here for an online example.

Code: Select all

#include <iostream>

struct Action
&#123;
    int val;
&#125;;

struct State
&#123;    
    int val_;
    State& make&#40;Action const& a&#41; &#123; val_ += a.val; return *this; &#125;
&#125;;

State result&#40;State const& s, Action const& a&#41;
&#123;
    State nrv&#123;s&#125;; nrv.make&#40;a&#41;; return nrv;
&#125;

struct Node
&#123;
    State         state;
    Node   const* parent = nullptr;
    Action const* action = nullptr;
    
    Node&#40;Node const& n, Action const& a&#41;
    &#58;
        state&#123;result&#40;n.state, a&#41;&#125;, parent&#123;&n&#125;, action&#123;&a&#125;
    &#123;&#125;
    
    Node&#40;State const& s&#41; &#58; state&#123;s&#125; &#123;&#125;    
    int val&#40;) const &#123; return state.val_; &#125;
&#125;;

Node result&#40;Node const& n, Action const& a&#41;
&#123;
    return Node&#123;n, a&#125;;    
&#125;

void traverse&#40;Node const& n, int d&#41; // take state by const reference
&#123;
    std&#58;&#58;cout << "depth = " << d << ", value = " << n.val&#40;) << "\n";
    if &#40;d == 0&#41; return;
    Action const a&#91;1&#93; = &#123; Action&#123;1&#125; &#125;;  // "move generation"
    for &#40;int i = 0; i < 1; ++i&#41;
        traverse&#40;result&#40;n, a&#91;i&#93;), d - 1&#41;;   // copy-make the successor from result&#40;n, a&#91;i&#93;)
&#125;

int main&#40;)
&#123;
    State const s&#123;0&#125;; // local, const state
    Node const n&#123;s&#125;;
    traverse&#40;n, 3&#41;;
&#125;
This traversal algorithm has the correct const-reference signature and is also exception-safe. What's not to like? Answer: the cost of copying the state between different levels of the tree traversal. For small games, this might not be a big issue, but realistic game engines have several kB of state and copy-make will eventually have a big speed penalty.
But you wouldn't clap yet. Because making something disappear isn't enough; you have to bring it back. That's why every magic trick has a third act, the hardest part, the part we call "The Prestige".
So let's see if we can combine the best of both worlds here: const-reference arguments, exception-safety and no copy-penalties. Just push the make/undo logic to the constructor and destructor of the Node class (destructors are automatically called even in the face of exceptions). This also requires holding a non-const reference to the global state inside that Node class, and that solves the copy-penalty as a bonus. And since const is shallow in C++, we can pass this node by const-reference to the search algorithm.

Code: Select all

#include <iostream>

struct Action
&#123;
    int val;
&#125;;

struct State
&#123;    
    int val_;
    State& make&#40;Action const& a&#41; &#123; val_ += a.val; return *this; &#125;
    State& undo&#40;Action const& a&#41; &#123; val_ -= a.val; return *this; &#125;
&#125;;

struct Node
&#123;
    State       & state;   // hold state by non-const reference
    Node   const* parent = nullptr;
    Action const* action = nullptr; 
    
    ~Node&#40;)
    &#123;
        if &#40;action&#41;
            state.undo&#40;*action&#41;;     
    &#125;

    Node&#40;Node const& n, Action const& a&#41;
    &#58;
        state&#123;n.state&#125;, parent&#123;&n&#125;, action&#123;&a&#125;
    &#123;
        state.make&#40;*action&#41;;
    &#125;

    Node&#40;State& s&#41;
    &#58;
        state&#123;s&#125;
    &#123;&#125;    
    
    int val&#40;) const &#123; return state.val_; &#125;
&#125;;

Node result&#40;Node const& n, Action const& a&#41;
&#123;
    return Node&#123;n, a&#125;;    
&#125;

void traverse&#40;Node const& n, int d&#41;    // take argument by const reference
&#123;
    std&#58;&#58;cout << "depth = " << d << ", value = " << n.val&#40;) << "\n";
    if &#40;d == 0&#41; return;
    Action const a&#91;1&#93; = &#123; Action&#123;1&#125; &#125;;  // "move generation" 
    for &#40;int i = 0; i < 1; ++i&#41;
        traverse&#40;result&#40;n, a&#91;i&#93;), d - 1&#41;;   // constructor/destructor of automatically call make/undo
&#125;

int main&#40;)
&#123;
    State s&#123;0&#125;;         // globally modifiable state...
    Node const n&#123;s&#125;;    // ...wrapped by local const node 
    traverse&#40;n, 3&#41;;
&#125;
And there you have it: an algorithm with copy-make syntax and safety but with make/undo performance. Try for yourself online. As a bonus, because the final traverse() algorithm (with the make/undo wrapped inside a Node class) is syntactically identical to the earlier copy-make version, one can even make a single function template that truly unifies the source code:

Code: Select all

template<class Node>
void traverse&#40;Node const& n, int d&#41;    // take argument by const reference
&#123;
    std&#58;&#58;cout << "depth = " << d << ", value = " << n.val&#40;) << "\n";
    if &#40;d == 0&#41; return;
    Action const a&#91;1&#93; = &#123; Action&#123;1&#125; &#125;;  // "move generation" 
    for &#40;int i = 0; i < 1; ++i&#41;
        traverse&#40;result&#40;n, a&#91;i&#93;), d - 1&#41;;   // copy-make or make/undo depending on the type of Node class that is being passed
&#125;
One can pass any Node class to this traverse() template, as long as there is a suitable result() function that computes the successor node, either in-place or as a copy.

mar
Posts: 2195
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Unifying make/undo and copy-make

Post by mar » Mon Dec 21, 2015 7:46 pm

The idea of undoing moves in destructor is certainly nice, yet I don't see anything magical here. Objects are naturally destroyed as soon as they leave scope, so why the dramma? :)
So you can't mimic e.g. the practice popularized by the Boost.Graph library and throw an exception when the search has found a match, when the GUI demands a response, or when the allocated time is up.
This might be considered exception abuse by some people and it shows that exceptions can act as a super-goto across several stack frames, cleaning up along the way.
My opinion is anyone is free to use/not use specific language features and shouldn't care much about what others think => if it works for you, good for you.

Rein Halbersma
Posts: 689
Joined: Tue May 22, 2007 9:13 am

Re: Unifying make/undo and copy-make

Post by Rein Halbersma » Mon Dec 21, 2015 9:01 pm

mar wrote:The idea of undoing moves in destructor is certainly nice, yet I don't see anything magical here. Objects are naturally destroyed as soon as they leave scope, so why the dramma? :)
Ah well, you are not easily fooled by magicians :) The destructor trick is indeed just a simple example of a scope guard. I got the idea from a C++ talk of CppCon (can't remember the title) where all manual file open/close were wrapped in little objects to guarantee exception safety. That in itself is not that important in search, as you say, it can even be considered bad style to throw exceptions to terminate a recursive search.

What I like about this style of programming is that one can write a single search routine in copy-make style and pretty easily switch to make/undo by passing different Node types, without having to adapt the algorithm itself.

jdart
Posts: 4014
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Unifying make/undo and copy-make

Post by jdart » Mon Dec 21, 2015 11:19 pm

I don't know of any strong program that uses copy-make.

--Jon

Rein Halbersma
Posts: 689
Joined: Tue May 22, 2007 9:13 am

Re: Unifying make/undo and copy-make

Post by Rein Halbersma » Mon Dec 21, 2015 11:26 pm

jdart wrote:I don't know of any strong program that uses copy-make.

--Jon
If I am not mistaken, Komodo does.

User avatar
lucasart
Posts: 3141
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Unifying make/undo and copy-make

Post by lucasart » Tue Dec 22, 2015 10:34 am

Rein Halbersma wrote: based on a very simple game that has a single integer as its state. Let's assume there's only one legal move at each depth.
What kind of game is that ? Single integer as state ? Only one move possible, so nothing to decide, what's the point of the game ? Any relevance to chess, or just theoretical masturbation ?
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

Rein Halbersma
Posts: 689
Joined: Tue May 22, 2007 9:13 am

Re: Unifying make/undo and copy-make

Post by Rein Halbersma » Tue Dec 22, 2015 11:39 am

lucasart wrote:
Rein Halbersma wrote: based on a very simple game that has a single integer as its state. Let's assume there's only one legal move at each depth.
What kind of game is that ? Single integer as state ? Only one move possible, so nothing to decide, what's the point of the game ? Any relevance to chess, or just theoretical masturbation ?
Hi Lucas, nice to see you again, with your usual happy mood :roll:

Of course, this simple game is just a toy example to quickly code up something that compiles. It's very easy to extend the code to a real game of course. I use the idea to wrap make/undo in a node class in my draughts engine.

The relevance to chess is that there have been past discussions here (by Don Dailey e.g.) on testing copy-make vs make/undo, and that turned out to require quite a bit of rewriting. My point is that you don't have to rewrite the search algorithm to switch between different types of state manipulation.

kbhearn
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: Unifying make/undo and copy-make

Post by kbhearn » Tue Dec 22, 2015 1:08 pm

Rein Halbersma wrote:
lucasart wrote:
Rein Halbersma wrote: based on a very simple game that has a single integer as its state. Let's assume there's only one legal move at each depth.
What kind of game is that ? Single integer as state ? Only one move possible, so nothing to decide, what's the point of the game ? Any relevance to chess, or just theoretical masturbation ?
Hi Lucas, nice to see you again, with your usual happy mood :roll:

Of course, this simple game is just a toy example to quickly code up something that compiles. It's very easy to extend the code to a real game of course. I use the idea to wrap make/undo in a node class in my draughts engine.

The relevance to chess is that there have been past discussions here (by Don Dailey e.g.) on testing copy-make vs make/undo, and that turned out to require quite a bit of rewriting. My point is that you don't have to rewrite the search algorithm to switch between different types of state manipulation.
While i do like your Node class and think it's a nice approach to take i suspect it doesn't address the difficulties in comparing copy-make and make-unmake. it's simple enough to turn unmake into a null function and have the compiler whisk it away to neverland to achieve the same result in a less clever manner.

I think the problem is how the underlying state is designed might be completely different as copy-make might prefer an efficient structure with little redundancy(would need to be tested though, i thought i remembered an old discussion where don claimed the board state could be surprisingly large without a gamebreaking impact on speed under copy-make) where make-unmake might be much less averse to redundantly represented information that makes life easier as long as not too much of it has to be updated very frequently. And these differences in design choices of the state may then reflect in how you design your eval, or your move ordering, or other parts i'm not thinking of. While i'm sure it's technically possible to abstract out everything it's considerably more of a rewrite than a little bit of stack variable destructor magic.

Rein Halbersma
Posts: 689
Joined: Tue May 22, 2007 9:13 am

Re: Unifying make/undo and copy-make

Post by Rein Halbersma » Tue Dec 22, 2015 4:24 pm

kbhearn wrote: While i do like your Node class and think it's a nice approach to take i suspect it doesn't address the difficulties in comparing copy-make and make-unmake. it's simple enough to turn unmake into a null function and have the compiler whisk it away to neverland to achieve the same result in a less clever manner.
I don't think you can simply define undo() to be empty and use the make/undo code for a copy-make algorithm, because the "undo" with copy-make is popping from the call stack. You really need to make a copy for that, not just write an empty undo().
I think the problem is how the underlying state is designed might be completely different as copy-make might prefer an efficient structure with little redundancy(would need to be tested though, i thought i remembered an old discussion where don claimed the board state could be surprisingly large without a gamebreaking impact on speed under copy-make) where make-unmake might be much less averse to redundantly represented information that makes life easier as long as not too much of it has to be updated very frequently. And these differences in design choices of the state may then reflect in how you design your eval, or your move ordering, or other parts i'm not thinking of. While i'm sure it's technically possible to abstract out everything it's considerably more of a rewrite than a little bit of stack variable destructor magic.
Yes, in practice there are quite few details to think about. E.g., in pure copy-make, the Node class extends the State class by only adding the hash (which is still incrementally updated when a successor node is created, of course), the half move and full move counters as extra bookkeeping information. Even the ep and castling rights can be stored in the State.

But in make/undo, the ep and castling rights, are typically not reversible if one has a very compact move representation (i.e. state.make(move) depends on info in state to update ep / castling). So then one would have a hybrid approach by keeping the big reversible state by reference, and the (typically much smaller) irreversible state by value, e.g. like this

Code: Select all

class Node
&#123;
    ReversibleState & revstate;
    IrreversibleState irrstate;
    // hash code, parent/move pointers, move counters etc.
&#125;;
So effectively, the irreversible parts of the State are distributed on the stack at the various tree levels, and are discarded after each pop of the call stack. This means that one does not have to keep an explicit stack.

But again, the tree traversal can be written as a generic algorithm in terms of the Node class as a thin wrapper that abstracts away from the underlying memory/CPU tradeoffs that the designer of the state class chooses to make. I use as rule of thumb to keep the Node class not bigger than a single cache line.

User avatar
Bloodbane
Posts: 154
Joined: Thu Oct 03, 2013 2:17 pm

Re: Unifying make/undo and copy-make

Post by Bloodbane » Tue Dec 22, 2015 5:13 pm

jdart wrote:I don't know of any strong program that uses copy-make.

--Jon
The only engine I know that uses copy-make and is even near the top engines is Hakkapeliitta. According to my notes copy-make was actually slightly faster than make-unmake.
Functional programming combines the flexibility and power of abstract mathematics with the intuitive clarity of abstract mathematics.
https://github.com/mAarnos

Post Reply