aiphighhope.h

aiParts is a set of C++ classes that can be used to develop artificial intelligence for multi-decisi

//**********************************************************************
//  aipHighHope.h  -   Problem Solving using the High-Hope Technique
//
//  Provides: aipHHProblem  aipHHDecision  aipHHOption
//              aipHHImportance  aipHHDecisionItr  aipHHOptionItr
//
//  An aipHHProblem problem is assembled with aipHHDecision and
//  aipHHOption objects.  
//
//  Calling aipHHProblem::solve() attempts to solve the problem
//  using the High-Hope technique.
//
//  An aipHHProblem problem has aipHHDecision decisions and 
//  aipHHOption options.  
//
//  Copyright (c)  2005, 2008  Brian Marshall
//
//  See the license at end of this file.
//
//  Developers/Contributers:
//    [BRM] Brian Marshall - Calgary - [e-mail]
//
//
//  08/06/16  [BRM] added decision is_decided(), 
//                  removed decision groups, modified deciding,
//                  new next_decision(), added aipHHImportance,
//                  decisions may be decided multiple times,
//                  removed dcsn.m_opt_prev; small changes
//  05/11/18  [BRM] a failed try that got further than the previous
//                     try is, optionally, an improvement
//                  worst decision has extra affect on further tries
//                  modified constant Curiosity_Starting
//  05/11/18  [BRM] added aipHHDcsnGrp and support in decisions
//  05/11/12  [BRM] added aipHHHope and aspect classes
//                  moved logic from aipHHProblem to hope aspects
//                  added aipHHSolveStat, try_to_find_solution()
//                  removed redundant rand() function
//  05/11/07  [BRM] moved random_num() to class aipBase
//  05/11/01  [BRM] count tries to get to best try
//  05/10/24  [BRM] added decision, option: any_fear(), any_greed()
//                  added HH_Try_Is_A_Best
//  05/10/21  [BRM] added aipHHOption::dump_hope_to_ptr()
//  05/10/02  [BRM] Split out from non-HH problem, decision
//  05/09/20  [BRM] Development begins.
//
//----------------------------------------------------------------------
//  The High-Hope Technique
//
//  In the High-Hope technique, decisions and options have an aipHHHope
//  member which models hope as fear + greed + curiosity... 
//       Fear: the desire to avoid known bad things
//       Greed: the desire to take advantage of known good things
//       Curiosity: the desire to try new things
//
//  Solving a problem involves trying many times.  The tries affect 
//  the hopes and the hopes affect the subsequent tries.
//
//  The High-Hope technique: 
//    - for a specified number of tries...
//      - attempt to find a solution:
//        - while the solution is not complete...
//          - pick a decision in an application-specific way
//          - for the decision: choose an option:
//              the one with the highest g_opt(): the sum of: 
//                - the sum of:
//                    - the option-hope-goodness
//                  possibly plus:
//                    - (normalized) constant-goodness
//                    - application-specific non-constant goodness
//      - if this solution is the best-so-far: remember it
//
//  One try differs from the next as a result of changes in the hope
//  of decisions and options. (For example, once an option has been
//  tried, the curiosity associated with that option goes down.)
//
//  If a decision has multiple options that are the best, one is
//  chosen at random. (The random-number generator will always return
//  the same series of random numbers.)
//
//  In a try, the next decision to decide is the one with the
//  highest importance.  This may be overridden by subclasses of
//  aipHHProblem.
//
//  Fear, Greed and Curiosity are handled differently after each try
//  (for each decision and option):
//    Fear
//       Starts at aipNeutral; when a try fails, fear becomes 
//       stronger; when a solution is found, fear becomes weaker.
//    Greed 
//       Starts at aipNeutral, and when a complete solution is found,
//       it is set to one of:  
//         New-Best, Best, Improved, Changed, Complete.
//    Curiosity
//       Starts high, drops as decisions and options are tried;
//
//  After a series of tries that result in the same solution, the
//  hope will be raised to an identical high value for all decisions 
//  and options that are not in the solution.
//  
//  After many tries that do not result in a new-best or improved
//  solution, fear is weakened and all curiosities are reset to an 
//  identical high value.
//    
//  The HighHope software does not use the hope of decisions;
//  applications may use it.  Applications in which an option
//  determines the next decision (such as finding a path through
//  a network of nodes) will presumably use decision hope.
//  
//----------------------------------------------------------------------

#ifndef aipHighHope_h_guard
#define aipHighHope_h_guard

#include "aipImportance.h"
#include "aipProblem.h"

//----------------------------------------------------------------------
//  Constants

static const aipG Curiosity_Starting = aipVeryGood + aipGood;

static const aipG Greed_For_New_Best = aipGood;
static const aipG Greed_For_Best     = aipQuiteGood;
static const aipG Greed_For_Was_Best = aipPrettyGood;
static const aipG Greed_For_Improved = aipPrettyGood;
static const aipG Greed_For_Changed  = aipFairlyGood;
static const aipG Greed_For_Complete = aipSomewhatGood;;

//  Note:  High-Hope technique uses:  11000 to 11999

    // aipMsg typ values: 
static const short HH_Starting_Solve         = 11001;
static const short HH_Solve_Has_Ended        = 11002;
static const short HH_Starting_New_Try       = 11003;
static const short HH_Try_Has_Ended          = 11004;
static const short HH_This_Is_Best_So_Far    = 11005;
static const short HH_No_Recent_Improve      = 11006;
static const short HH_No_Recent_Change       = 11007;
static const short HH_No_Recent_Best_So_Far  = 11008;

  // Try-status after a try has ended
static const short HH_Try_Has_Failed     = 11101;
static const short HH_Try_Is_New_Best    = 11102;
static const short HH_Try_Is_A_Best      = 11103;
static const short HH_Try_Is_Improved    = 11104;
static const short HH_Try_Is_Changed     = 11105;
static const short HH_Try_Is_Complete    = 11106;

//----------------------------------------------------------------------
//  Classes.  Sub-classing is shown by indentation.

//  class  aipG  is a typedef for  aipGoodness

//  aipHope is a compound emotion: Fear + Greed + Curiosity

// class aipBase;                       ( in aipBase.h )
     class aipHHImportance;       // Importance for choosing decisions
//   class aipDemon;                    ( in aipPandemonium.h )
//     class aipAspect;                 ( in aipEmotion.h)
//       class aipEmotion;              ( in aipEmotion.h)
//         class aipCompEmotion;        ( in aipEmotion.h)
//           class aipHope;             ( in aipEmotion.h)
               class aipHHHope;   // hope with High-Hope aspects
         class aipHHFearAspect;   // how messages affect fear in hope
         class aipHHGreedAspect;  // how msgs affect greed in hope
         class aipHHCuriosityAspect; // msgs affect curiosity in hope
//     class aipProblem;                ( in aipProblem.h )
         class aipHHProblem;      // problem with aipDecision    
//     class aipDecision;               ( in aipDecision.h )
         class aipHHDecision;     // Decision in aipHHProblem
//     class aipOption;                 ( in aipDecision.h )
         class aipHHOption;       // Option in aipHHDecision
// class aipDemonItr;                    ( in aipPandemonium.h )
     class aipHHDecisionItr;      // aipHHDecision iterator
     class aipHHOptionItr;        // aipHHOption iterator
   class aipHHSolveStat;          // solve() status and statistics
// class aipMsg;                         ( in aipBase.h )
     class aipHHMsg;              // High-Hope problem-solving message


//======================================================================
//  aipHHImportance  -  Importance for choosing decisions

class aipHHImportance : public aipImportance {

  long      m_been_prob;  // has been a problem aspect

public:

  aipHHImportance () { m_been_prob = 0; }
  virtual ~aipHHImportance () {}

  virtual long val () const { 
    return aipImportance::val() + m_been_prob; 
  }

  virtual void take_msg (aipMsg *m);

};

//======================================================================
//  aipHHHope  -  Hope with High-Hope aspects


class aipHHHope : public aipHope {

public:

  aipHHHope ();
  virtual ~aipHHHope () {}

};


//======================================================================
//  aipHHFearAspect  -  how messages affect fear in hope

class aipHHFearAspect : public aipAspect {

protected:

aipFear * fear () const { return (aipFear *)emotion(); }

public:

  aipHHFearAspect() {}
  virtual ~aipHHFearAspect() {}

  virtual void take_msg (aipMsg *m);

};


//======================================================================
//  aipHHGreedAspect  -  how msgs affect greed in hope

class aipHHGreedAspect : public aipAspect {

protected:

  aipGreed  * greed () const { return (aipGreed *)emotion(); }

public:

  aipHHGreedAspect() {}
  virtual ~aipHHGreedAspect() {}

  virtual void take_msg (aipMsg *m);

};


//======================================================================
//  aipHHCuriosityAspect  -  how msgs affect curiosity in hope

class aipHHCuriosityAspect : public aipAspect {

protected:

  aipCuriosity * curiosity() const { return (aipCuriosity*)emotion(); }

public:

  aipHHCuriosityAspect() {}
  virtual ~aipHHCuriosityAspect() {}

  virtual void take_msg (aipMsg *m);

};


//======================================================================
//  aipHHProblem  -  Problem with solve() that uses High-Hope technique.
//
//  m_g_cmp_cur, m_g_cmp_prev, m_g_cmp_bsf are goodnesses 
//  of solutions - the sum of the goodness of each decision.  These 
//  values are meaningful when compared to each other; they may or
//  may not be meaningful when compared to standard goodness constants
//  like aipQuiteGood and aipVeryBad.  They may not be actual goodness
//  values at all - in a shortest-path problem, they might be the
//  solution-distance, in metres or kilometres, multiplied by -1.
//
//  For problems in which option-goodness should affect which option
//  is chosen by a decision...
//  normalize_option_goodnesses() should be called before solve() 
//  if options do get goodnesses that are not really goodness values
//  (ex: they are kilometers or dollars), and there are values
//  that would be inappropriate goodness values - for example, a nice
//  low cost of $1200, stored in a goodness as -1200, interpreted as
//  a goodness would be very-very-bad.  normalize_option_goodnesses()
//  will force the values into a range of roughly -17 to +17.
//
//  Subclasses that require option-goodness normalization can:
//    - use normalize_option_goodnesses(), or,
//    - override normalize_option_goodnesses(), or,
//    - normalize the values before they are used to make options
//
//  solve() tries to find a maximum; if the best solution is a minimum, 
//  appropriate user-meaningful goodness values must be multiplied by 
//  -1.  If this sort of thing is going on, a subclass should override
//  the virtual function bsf_goodness_for_user().
//
//  bsf_goodness_for_user() returns the goodness value that is to
//  be reported to the user for the best-so-far solution found.
//
//  If m_dcsn_is_progress is:
//     1: each decision is a step closer to completing solution 
//     0: different solutions can have different number of decisions
//
//  If m_worst_is_extra_bad is true, the goodess of the worst decision
//  will be added to the solution-goodness, for purposes of comparing 
//  to other solutions, an extra couple of times.

class aipHHProblem : public aipProblem {

  long      m_num_try;              // times solve() will try
  int       m_dcsn_is_progress;     // 0 = no
  int       m_worst_is_extra_bad;   // 0 = no
  int       m_should_log_tries;     // 0 = no

  aipHHSolveStat  * m_solve_stat;   // status and statistics

protected:

  virtual void try_to_find_solution ();

  virtual aipHHDecision * next_decision ();

  virtual int solution_is_complete () const;

  virtual void log_this_try () {}

    //  threshold values used in solve()

  virtual long many_tries_since_change() const {
    return (5 + m_num_try/400);
  }

  virtual long many_tries_since_improve() const {
    return (20 + m_num_try/200);
  }

  virtual long many_tries_since_bsf() const {
    return (40 + m_num_try/50);
  }

  virtual aipG too_bad_to_go_on() const { 
    return aipForbidden;  // subclasses can override
  }

    //  used in some types of problems...
  virtual void normalize_option_goodnesses();  // sample 

public:

  aipHHProblem ();
  virtual ~aipHHProblem ();

      // setting up the problem

  void set_num_try (long x) { m_num_try = x; }

  void set_dcsn_is_progress   (int x) { m_dcsn_is_progress = x;   }
  void set_worst_is_extra_bad (int x) { m_worst_is_extra_bad = x; }

  void add_decision (aipDecision *x) {}      // use add_hh_decsion
  void add_hh_decision (aipHHDecision *x);

  void enable_log_tries  () { m_should_log_tries = 1; }
  void disable_log_tries () { m_should_log_tries = 0; }

  int should_log_tries () const { return m_should_log_tries; }

      // about the problem

  long  num_try () const { return m_num_try; }

  long num_decisions() const;

  int  dcsn_is_progress   () const { return m_dcsn_is_progress;   }
  int  worst_is_extra_bad () const { return m_worst_is_extra_bad; }

  aipHHDecisionItr hh_decision_iterator() const;

  aipHHSolveStat * solve_stat () const { return m_solve_stat; }

  virtual aipG g();

  virtual void take_msg (aipMsg *m) { aipProblem::take_msg(m); }
  virtual void note_decide (aipHHDecision *d, aipHHOption *o) {}

  virtual aipG solve();   // returns goodness for user

};


//======================================================================
//  aipHHDecision  -  Decision used in an High-Hope aipHHProblem
//
//  A set of decisions may share a set of options.  An option may be
//  added to more than one decision, but, for destruction purposes,
//  only one decision will own the option.
//