[TynesideLUG] Dumping the internal tables of a machine learning penny matching game
Morten Bojsen-Hansen
morten at alas.dk
Mon Jul 1 17:10:19 UTC 2024
If you paste the code into Compiler Explorer (https://godbolt.org/z/G3WsTod7E) you can even run it. :-)
Best,
--
Morten Bojsen-Hansen
morten at alas.dk
On Mon, Jul 1, 2024, at 17:50, Ian Bruntlett wrote:
> Hi,
>
> In a FB discussion I mentioned patching a machine learning algorithm in an
> attempt to learn how the machine learned things.
>
> This code is from the book "Learn C++ by Example", published by Manning.
>
> If you've got an up to date C++ compiler installed, you can compile the
> code below (assuming you put it in a file called "bonus_main.cpp" using
> this command in a single line:
>
> g++ -g -Wall -Wshadow -Wconversion -std=c++23 -Wl,-Map=bonus_main.map
> bonus_main.cpp -o bonus_main
>
> The code starts below:
> #include <cassert>
> #include <concepts>
> #include <coroutine>
> #include <iostream>
> #include <optional>
> #include <functional>
> #include <map>
> #include <memory>
> #include <random>
> #include <string>
> #include <tuple>
> #include <unordered_map>
> #include <utility>
>
>
> // Listing 8.1 Read an optional zero or one
> std::optional<int> read_number(std::istream& in)
> {
> std::string line;
> std::getline(in, line);
> if (line == "0") {
> return { 0 };
> }
> else if (line == "1") {
> return { 1 };
> }
> return {};
> }
>
> // Listing 8.2 A pennies game
> void pennies_game()
> {
> int player_wins = 0;
> int turns = 0;
> std::mt19937 gen{ std::random_device{}() };
> std::uniform_int_distribution dist(0, 1);
>
> std::cout << "Select 0 or 1 at random and press enter.\n";
> std::cout << "If the computer predicts your guess it wins.\n";
> while (true)
> {
> const int prediction = dist(gen);
>
> auto input = read_number(std::cin);
> if (!input)
> {
> break;
> }
> const int player_choice = input.value();
>
> ++turns;
> std::cout << "You pressed " << player_choice << ", I guessed " <<
> prediction << '\n';
>
> if (player_choice != prediction)
> {
> ++player_wins;
> }
> }
> std::cout << "you win " << player_wins << '\n'
> << "I win " << turns - player_wins << '\n';
> }
>
> // Listing 8.3 Three possible choices and outcomes
> enum class Choice
> {
> Same,
> Change,
> Shrug,
> };
>
> // Code by Ian
> std::ostream &operator <<(std::ostream &os,const Choice c)
> {
> switch (c)
> {
> case Choice::Same: return os << "Same";
> case Choice::Change: return os << "Change";
> case Choice::Shrug: return os << "Shrug";
> default:
> return os << "!!";
> }
> }
>
>
> enum class Outcome
> {
> Lose,
> Win,
> Unset,
> };
>
> // Code by Ian
> std::ostream &operator <<(std::ostream &os,const Outcome o)
> {
> switch (o)
> {
> case Outcome::Lose: return os << "Lose";
> case Outcome::Win: return os << "Win";
> case Outcome::Unset: return os << "Unset";
> default:
> return os << "!!";
> }
> }
> using state_t = std::tuple<Outcome, Choice, Outcome>;
> using last_choices_t = std::pair<Choice, Choice>;
>
> // Code by Ian
> std::ostream &operator <<(std::ostream &os,const state_t &st)
> {
> os << "( ";
> os << std::get<0>(st) << "," << std::get<1>(st) << "," << std::get<2>(st);
> os << ") ";
>
> return os;
> }
>
> std::ostream &operator <<(std::ostream &os,const last_choices_t &lc)
> {
> return os << "(" << lc.first << "," << lc.second << ")";
> }
>
> // Listing 8.5 Specializing std::hash for our state tuple
> template<>
> struct std::hash<state_t>
> {
> std::size_t operator()(state_t const& state) const noexcept
> {
> std::size_t h1 = std::hash<Outcome>{}(std::get<0>(state));
> std::size_t h2 = std::hash<Choice>{}(std::get<1>(state));
> std::size_t h3 = std::hash<Outcome>{}(std::get<2>(state));
> return h1 + (h2 << 1) + (h3 << 2);
> }
> };
>
> // Listing 8.6 An initial state table
> std::unordered_map<state_t, last_choices_t> initial_state()
> {
> const auto unset = std::pair<Choice, Choice>{ Choice::Shrug,
> Choice::Shrug };
> return {
> { {Outcome::Lose, Choice::Same, Outcome::Lose}, unset },
> { {Outcome::Lose, Choice::Same, Outcome::Win}, unset },
> { {Outcome::Lose, Choice::Change, Outcome::Lose}, unset },
> { {Outcome::Lose, Choice::Change, Outcome::Win}, unset },
> { {Outcome::Win, Choice::Same, Outcome::Lose}, unset },
> { {Outcome::Win, Choice::Same, Outcome::Win}, unset },
> { {Outcome::Win, Choice::Change, Outcome::Lose}, unset },
> { {Outcome::Win, Choice::Change, Outcome::Win}, unset },
> };
> }
>
> // Listing 8.7 Class to track the game's state
> class State
> {
> std::unordered_map<state_t, last_choices_t> state_lookup =
> initial_state();
> public:
> friend std::ostream& operator<< (std::ostream &s, const State &rState);
> // Listing 8.8 Find the choices or return two shrugs
> last_choices_t choices(const state_t& key) const
> {
> if (auto it = state_lookup.find(key); it!=state_lookup.end())
> {
> return it->second;
> }
> else
> {
> return { Choice::Shrug, Choice::Shrug };
> }
> }
> // Listing 8.9 Update choices for valid keys
> void update(const state_t& key, const Choice& turn_changed)
> {
> if (auto it = state_lookup.find(key); it != state_lookup.end())
> {
> const auto [prev2, prev1] = it->second;
> last_choices_t value{ prev1, turn_changed };
> it->second = value;
> }
> }
> };
>
> // Code by Ian.
> std::ostream& operator<< (std::ostream &s, const State &rState)
> {
> s << "State table\n";
> for ( const auto& it : rState.state_lookup ) // we're a friend function,
> state is an unordered_map <state_t, last_choices_t>
> {
> s << it.first << " -> "; // state_t is a tuple
> s << it.second; // last_choices_t is a pair
> s << std::endl;
> }
> return s;
> }
>
>
> // Listing 8.10 Choice from state
> Choice prediction_method(const last_choices_t& choices)
> {
> if (choices.first == choices.second)
> {
> return choices.first;
> }
> else
> {
> return Choice::Shrug;
> }
> }
>
> // Listing 8.11 A mind-reading class
> template <std::invocable<> T, typename U>
> class MindReader {
> State state_table;
>
> T generator;
> U distribution;
>
> int prediction = flip();
>
> state_t state{Outcome::Unset, Choice::Shrug, Outcome::Unset};
> int previous_go = -1;
>
> // Listing 8.12 Update the prediction
> bool update_prediction(int player_choice)
> {
> bool guessing = false;
> Choice option = prediction_method(state_table.choices(state));
> switch (option)
> {
> case Choice::Shrug:
> prediction = flip();
> guessing = true;
> break;
> case Choice::Change:
> prediction = player_choice ^ 1;
> break;
> case Choice::Same:
> prediction = player_choice;
> break;
> }
> return guessing;
> }
>
> int flip()
> {
> return distribution(generator);
> }
>
> public:
> MindReader(T gen, U dis)
> : generator(gen), distribution(dis)
> {
> }
>
> int get_prediction() const
> {
> return prediction;
> }
>
> // Listing 8.13 The mind reader's update method
> bool update(int player_choice)
> {
> const Choice turn_changed = player_choice == previous_go ?
> Choice::Same : Choice::Change;
> state_table.update(state, turn_changed);
>
> previous_go = player_choice;
> state = {std::get<2>(state), turn_changed, (player_choice !=
> prediction) ? Outcome::Win : Outcome::Lose};
>
> return update_prediction(player_choice);
> }
> // code by Ian
> void dump(std::ostream &os)
> {
> os << "MindReader()\n";
> os << "this->prediction = " << this-prediction << ", get_prediction()
> = " << get_prediction() << '\n';
> os << "this->previous_go = " << this->previous_go << '\n';
> os << "this->state = " << this->state << '\n';
> os << state_table << '\n';
> }
> };
>
> // Listing 8.6 Check we have no hash collisions (and more besides)
> void check_properties()
> {
> // No bucket clashes
> std::unordered_map<state_t, last_choices_t> states = initial_state();
> for (size_t bucket = 0; bucket < states.bucket_count(); bucket++)
> {
> auto bucket_size = states.bucket_size(bucket);
> assert(bucket_size <= 1);
> }
>
> {
> MindReader mr([]() { return 0; }, [](auto gen) { return gen(); });
> assert(mr.update(0)); // guesses first
> assert(mr.update(0)); // second is a guess too
> }
>
> assert(prediction_method({ Choice::Shrug, Choice::Shrug }) ==
> Choice::Shrug);
> assert(prediction_method({ Choice::Shrug, Choice::Change }) ==
> Choice::Shrug);
> assert(prediction_method({ Choice::Shrug, Choice::Same }) ==
> Choice::Shrug);
> assert(prediction_method({ Choice::Change, Choice::Shrug }) ==
> Choice::Shrug);
> assert(prediction_method({ Choice::Same, Choice::Shrug }) ==
> Choice::Shrug);
> assert(prediction_method({ Choice::Change, Choice::Change }) ==
> Choice::Change);
> assert(prediction_method({ Choice::Same, Choice::Same }) ==
> Choice::Same);
> assert(prediction_method({ Choice::Change, Choice::Same }) ==
> Choice::Shrug);
> assert(prediction_method({ Choice::Same, Choice::Change }) ==
> Choice::Shrug);
>
> State s;
> auto got1 = s.choices({ Outcome::Unset, Choice::Shrug, Outcome::Unset
> });
> assert(got1.first == Choice::Shrug);
> assert(got1.second == Choice::Shrug);
> auto got2 = s.choices({ Outcome::Lose, Choice::Same, Outcome::Unset });
> assert(got2.first == Choice::Shrug);
> assert(got2.second == Choice::Shrug);
> auto got3 = s.choices({ Outcome::Win, Choice::Change, Outcome::Unset });
> assert(got3.first == Choice::Shrug);
> assert(got3.second == Choice::Shrug);
>
> {
> // Listing 6.12 had a RandomBlob we tested, using a lambda to stub
> out the random function
> // This always returns 0
> MindReader mr([]() { return 0; }, [](auto gen) { return gen(); });
> assert( mr.update(0)); //flip first two goes
> assert( mr.update(0)); //flip first two goes
> // The random generator always returns zero
> // it guesses first
> // state is
> // lose, same, lose
> // but without two matching next choices
> assert( mr.update(0));
> // now
> // lose, same, lose -> -1 ,lose
> // so when we decide 0 it stops guessing
> // now the state is
> // lose, same, lose -> lose ,lose
> // so it will predict a 0 next
> assert(!mr.update(0));
> assert( mr.get_prediction() == 0);
> assert(!mr.update(0));
> assert( mr.get_prediction() == 0);
> assert(!mr.update(0));
> assert( mr.get_prediction() == 0);
> assert(!mr.update(0));
> assert( mr.get_prediction() == 0);
> assert(!mr.update(0));
> assert( mr.get_prediction() == 0);
> }
> }
>
> // Listing 8.14 A mind reading game
> void mind_reader()
> {
> int turns = 0;
> int player_wins = 0;
> int guessing = 0;
>
> std::mt19937 gen{ std::random_device{}() };
> std::uniform_int_distribution dist{ 0, 1 };
> MindReader mr(gen, dist);
>
> std::cout << "Select 0 or 1 at random and press enter.\n";
> std::cout << "If the computer predicts your guess it wins\n";
> std::cout << "and it can now read your mind.\n";
> while (true)
> {
> const int prediction = mr.get_prediction();
>
> // code by Ian
> mr.dump (std::cout);
>
> auto input = read_number(std::cin);
> if (!input)
> {
> break;
> }
> const int player_choice = input.value();
>
> ++turns;
> std::cout << "You pressed " << player_choice
> << ", I guessed " << prediction << '\n';
>
> if (player_choice != prediction)
> {
> ++player_wins;
> }
> if (mr.update(player_choice))
> {
> ++guessing;
> }
> }
> std::cout << "you win " << player_wins << '\n'
> << "machine guessed " << guessing << " times" << '\n'
> << "machine won " << (turns - player_wins) << '\n';
> }
>
> // Listing 8.18 Customer "deleter"
> template<typename Promise>
> struct coro_deleter
> {
> void operator()(Promise* promise) const noexcept
> {
> auto handle =
> std::coroutine_handle<Promise>::from_promise(*promise);
> if (handle)
> handle.destroy();
> }
> };
>
> template<typename T>
> using promise_ptr = std::unique_ptr<T, coro_deleter<T>>;
>
>
> // Listing 8.17, 8.20 and 8.21 The coroutine's Task and promise_type
> struct Task
> {
> // Listing 8.19 Our promise type
> struct promise_type
> {
> std::pair<int, int> choice_and_prediction;
>
> Task get_return_object()
> {
> return Task(this);
> }
> std::suspend_never initial_suspend() noexcept { return {}; }
> std::suspend_always final_suspend() noexcept { return {}; }
> void unhandled_exception() {}
> std::suspend_always yield_value(std::pair<int, int> got)
> {
> choice_and_prediction = got;
> return {};
> }
>
> void return_void() { }
> };
>
> std::pair<int, int> choice_and_prediction() const
> {
> return promise->choice_and_prediction;
> }
> bool done() const
> {
> auto handle =
> std::coroutine_handle<promise_type>::from_promise(*promise);
> return handle.done();
> }
> void next()
> {
> auto handle =
> std::coroutine_handle<promise_type>::from_promise(*promise);
> handle();
> }
> private:
> promise_ptr<promise_type> promise;
> Task(promise_type* p) : promise(p) {}
> };
>
> // Listing 8.16 Our first coroutine
> Task coroutine_game()
> {
> std::mt19937 gen{ std::random_device{}() };
> std::uniform_int_distribution dist{ 0, 1 };
> MindReader mr(gen, dist);
>
> while (true)
> {
> auto input = read_number(std::cin);
> if (!input)
> {
> co_return;
> }
> int player_choice = input.value();
> co_yield{ player_choice , mr.get_prediction() };
> mr.update(player_choice);
> }
> }
>
> // Listing 8.22 A coroutine version of a mind reader
> void coroutine_minder_reader()
> {
> int turns = 0;
> int player_wins = 0;
>
> std::cout << "Select 0 or 1 at random and press enter.\n";
> std::cout << "If the computer predicts your guess it wins\nand it can
> now read your mind.\n";
>
> Task game = coroutine_game();
>
> while (!game.done())
> {
> auto [player_choice, prediction] = game.choice_and_prediction();
> ++turns;
> std::cout << "You pressed " << player_choice << ", I guessed " <<
> prediction << '\n';
>
> if (player_choice != prediction)
> {
> ++player_wins;
> }
> game.next();
> }
> std::cout << "you win " << player_wins << '\n'
> << "machine won " << (turns - player_wins) << '\n';
> }
>
> int main()
> {
> check_properties();
>
> // Commented out by Ian
> // pennies_game();
> // Choose one version of the mind reader (or play both if you want):
> mind_reader();
> //coroutine_minder_reader();
> }
> _______________________________________________
> Tyneside mailing list
> Tyneside at mailman.lug.org.uk
> https://mailman.lug.org.uk/mailman/listinfo/tyneside
More information about the Tyneside
mailing list