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.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.
Code: Select all
#include <iostream>
struct Action
{
int val;
};
struct State
{
int val_;
State& make(Action const& a) { val_ += a.val; return *this; }
State& undo(Action const& a) { val_ -= a.val; return *this; }
int val() const { return val_; }
};
void traverse(State& s, int d) // state by non-const ref
{
std::cout << "depth = " << d << ", value = " << s.val() << "\n";
if (d == 0) return;
Action const a[1] = { Action{1} }; // "move generation"
for (int i = 0; i < 1; ++i) {
s.make(a[i]);
traverse(s, d - 1); // wrap recursive call with make/undo that modify state
s.undo(a[i]);
}
}
int main()
{
State s{0}; // globally modifiable state
traverse(s, 3);
}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.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.
Code: Select all
#include <iostream>
struct Action
{
int val;
};
struct State
{
int val_;
State& make(Action const& a) { val_ += a.val; return *this; }
};
State result(State const& s, Action const& a)
{
State nrv{s}; nrv.make(a); return nrv;
}
struct Node
{
State state;
Node const* parent = nullptr;
Action const* action = nullptr;
Node(Node const& n, Action const& a)
:
state{result(n.state, a)}, parent{&n}, action{&a}
{}
Node(State const& s) : state{s} {}
int val() const { return state.val_; }
};
Node result(Node const& n, Action const& a)
{
return Node{n, a};
}
void traverse(Node const& n, int d) // take state by const reference
{
std::cout << "depth = " << d << ", value = " << n.val() << "\n";
if (d == 0) return;
Action const a[1] = { Action{1} }; // "move generation"
for (int i = 0; i < 1; ++i)
traverse(result(n, a[i]), d - 1); // copy-make the successor from result(n, a[i])
}
int main()
{
State const s{0}; // local, const state
Node const n{s};
traverse(n, 3);
}
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.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".
Code: Select all
#include <iostream>
struct Action
{
int val;
};
struct State
{
int val_;
State& make(Action const& a) { val_ += a.val; return *this; }
State& undo(Action const& a) { val_ -= a.val; return *this; }
};
struct Node
{
State & state; // hold state by non-const reference
Node const* parent = nullptr;
Action const* action = nullptr;
~Node()
{
if (action)
state.undo(*action);
}
Node(Node const& n, Action const& a)
:
state{n.state}, parent{&n}, action{&a}
{
state.make(*action);
}
Node(State& s)
:
state{s}
{}
int val() const { return state.val_; }
};
Node result(Node const& n, Action const& a)
{
return Node{n, a};
}
void traverse(Node const& n, int d) // take argument by const reference
{
std::cout << "depth = " << d << ", value = " << n.val() << "\n";
if (d == 0) return;
Action const a[1] = { Action{1} }; // "move generation"
for (int i = 0; i < 1; ++i)
traverse(result(n, a[i]), d - 1); // constructor/destructor of automatically call make/undo
}
int main()
{
State s{0}; // globally modifiable state...
Node const n{s}; // ...wrapped by local const node
traverse(n, 3);
}
Code: Select all
template<class Node>
void traverse(Node const& n, int d) // take argument by const reference
{
std::cout << "depth = " << d << ", value = " << n.val() << "\n";
if (d == 0) return;
Action const a[1] = { Action{1} }; // "move generation"
for (int i = 0; i < 1; ++i)
traverse(result(n, a[i]), d - 1); // copy-make or make/undo depending on the type of Node class that is being passed
}
