Home Page Downloads Contact Us

Free Open Source Artificial Intelligence C++ Parts

aiParts Open Source Project  

Home Page
Open Source
Contact
Free Downloads
Releases and Credits
Software Status
License
v0.9.3 README File
About rrproj
assigning people and/or equipment to projects
High-Hope Technique
History of the AI
View Source Files
and how they are organized
Making Programs
Development Notes
Using aiParts
Your Application
Support and Services

aiParts Source File

//**********************************************************************
//  samp_a2b.cpp  -  function bodies for samp_a2b.h
//
//  Copyright (c)  1999, 2005, 2007  Brian Marshall
//
//  See the license at end of this file.
//
//  Developers/Contributers:
//    [BRM] Brian Marshall - Calgary - bmarshal@agt.net
//
//  07/11/29  [BRM] changed option logging
//  05/11/10  [BRM] removed call to a2bDecision::set_decision()
//                  modified to log tries using aipHHSolveStat
//  05/10/23  [BRM] added option logging
//  05/10/21  [BRM] improved option debugging logging
//  05/09/27  [BRM] development began
//
//----------------------------------------------------------------------

#include "samp_a2b.h"
#include <string.h>
#include <iostream>
using namespace std;


//======================================================================
//  a2bProblem
//
//----------------------------------------------------------------------
//  Constructor

a2bProblem::a2bProblem () {

  m_node_start = m_node_end = m_node_current = 0;
  m_should_log_options = 0;

}

//----------------------------------------------------------------------
//  Destructor

a2bProblem::~a2bProblem () {}

//----------------------------------------------------------------------
//  add_node

void a2bProblem::add_node (a2bNode *x) { 

  add_hh_decision(x); 

}

//----------------------------------------------------------------------
//  add_link  -  return zero on success, -1 if option new failed
//                                       -2 if from_label not found,
//                                       -3 if to_label not found.
//

int a2bProblem::add_link (const char *from_label, 
                          const char *to_label, long distance) {

  a2bNode *node_from = find_node(from_label);
  if (!node_from) return -2;

  a2bNode *node_to = find_node(to_label);
  if (!node_to) return -3;

  a2bOption *link = new a2bOption(node_to,distance);
  if (!link) return -1;

  node_from->add_a2b_option(link);

  return 0;

}

//----------------------------------------------------------------------
//  node_iterator  -  all the nodes in no particular order

a2bNodeItr a2bProblem::node_iterator() const {

  a2bNodeItr i(decision_pandemonium());

  return i;

}

//----------------------------------------------------------------------
//  solution_iterator  -  nodes in best solution in solution order

a2bSolutionItr a2bProblem::solution_iterator() const { 

  a2bSolutionItr i(this);

  return i;

}

//----------------------------------------------------------------------
//  cur_solution_iterator  -  nodes in current solution in order

a2bCurSolutionItr a2bProblem::cur_solution_iterator() const { 

  a2bCurSolutionItr i(this);

  return i;

}

//----------------------------------------------------------------------
//  next_decision  -  the next decision to do
//
//  In this default function, the next decision is the first unmade
//  decision found by an iterator.

aipHHDecision * a2bProblem::next_decision() {

  if (!m_node_current) return (m_node_current = m_node_start);

  a2bOption *cur_opt = (a2bOption*)m_node_current->opt_cur();

  if (!cur_opt) return (m_node_current = m_node_start);
      // this should not happen if called by solve_a_to_b();

  return (m_node_current = cur_opt->reachable_node());

}

//----------------------------------------------------------------------
//  too_bad_to_go_on

aipG a2bProblem::too_bad_to_go_on() const {

  aipHHSolveStat *ss = solve_stat();

  return ss->g_cmp_bsf().calc_fraction(3,2);

}

//----------------------------------------------------------------------
//  solution_is_complete
//
//  The A-to-B solution is complete when, in the last decision made,
//  the chosen option refers to the ending-node ( == m_node_end).

int a2bProblem::solution_is_complete () const {

  if (m_node_current && m_node_current->a2b_opt_cur() &&
      m_node_current->a2b_opt_cur()->reachable_node() 
                                         == m_node_end) return 1;

  return 0;

}


//----------------------------------------------------------------------
//  log_this_try  - used for debugging or watching the thing work

void a2bProblem::log_this_try () {

  aipHHSolveStat *ss = solve_stat();

  log(ss->i_try()+1); log(": ");

  a2bCurSolutionItr itr = cur_solution_iterator();
  for ( a2bNode * n = itr.first(); n; n = itr.next() ) {
    log("  "); log(n->label());
  }

  log("    ("); log(ss->g_usr_cur().numeric_value()); log (")  ");

  if (ss->try_result() == HH_Try_Has_Failed) {
    if (ss->is_too_bad()) log("quit");
  } else if (ss->try_result() == HH_Try_Is_New_Best) {
    log("New Best");
  } else if (ss->try_result() == HH_Try_Is_A_Best) {
    log("a best");
  } else if (ss->try_result() == HH_Try_Is_Improved) {
    log("improved");
  } else if (ss->try_result() == HH_Try_Is_Changed) {
    log("changed");
  }

  log("\n");

  if (ss->is_many_since_new_best()) {
    log("   ... many tries since new best ...\n");
  }

  if (ss->is_many_since_improve()) {
    log("   ... many tries since improve ...\n");
  }

  if (ss->is_many_since_change()) {
    log("   ... many tries since change ...\n");
  }

}

//----------------------------------------------------------------------
//  take_msg 

void a2bProblem::take_msg (aipMsg *m) {

  if (m->typ() == HH_Starting_New_Try) {
    m_node_current = 0;
  }

  aipHHProblem::take_msg(m);

}

//----------------------------------------------------------------------
//  solve_a_to_b  -  look for shortest path from the starting node 
//                   to the ending node, returning distance, or:
//                     -1  if no solution found
//                     -2  if starting-node not found
//                     -3  if ending-node not found

long a2bProblem::solve_a_to_b (const char *from_label,
                               const char *to_label) {

  if ( should_log_options() ) {
    log("\nOption logging:  option-hope + next-node-hope\n");
    log("  ( hopes are fear+greed+curiosity  ie. (fgc) )\n\n");
  }

  // Note that in this problem, normalize_option_goodnesses()
  // is not used because the constant-option-goodnesses are
  // not used when choosing an option.

  a2bNode *node_start = find_node(from_label);
  if (!node_start) return -2;
  set_start_node(node_start);

  a2bNode *node_end   = find_node(to_label);
  if (!node_end) return -3;
  set_end_node(node_end);
  
  aipG g_solution = solve();                    // high-hope solve

  if (g_solution.is_forbidden()) return -1;

  return g_solution.numeric_value();   // distance of best solution

}

//----------------------------------------------------------------------
//  find_node  -  given the node label

a2bNode * a2bProblem::find_node (const char *label) {

  a2bNodeItr itr = node_iterator();

  for ( a2bNode * n = itr.first(); n; n = itr.next() ) {
    if ( !strcmp(n->label(), label) ) return n;
  }

  return 0;

}

//======================================================================
//  a2bNode
//
//----------------------------------------------------------------------
//  Constructor

a2bNode::a2bNode (const char *label) {

  strncpy (m_label, label, 20);
  m_label[20] = '\0';

}

//----------------------------------------------------------------------
//  Destructor

a2bNode::~a2bNode () {}

//----------------------------------------------------------------------
//  add_a2b_option

void a2bNode::add_a2b_option (a2bOption *x) { 

  add_hh_option(x); 

}


//----------------------------------------------------------------------
//  g_hope

aipG a2bNode::g_hope () const {

  return aipHHDecision::g_hope();

}

//======================================================================
//  a2bOption  -  a path from the owning node to another node
//
//----------------------------------------------------------------------
//  Constructor
//
//  Note that the parent-class is passed the negative distance.
//  The software finds a maximum; we find minimum distance by
//  finding the maximum negative distance.

a2bOption::a2bOption(a2bNode *n, long distance)
                                   : aipHHOption(0-distance) {

  m_reachable_node = n;

}

//----------------------------------------------------------------------
//  Destructor

a2bOption::~a2bOption() {}

//----------------------------------------------------------------------
//  g_opt  -  Goodness for comparing options
//
//  Because we are adding in two hopes (for the option and for the
//  node to which the option points), we divide the sum of the two
//  hopes in half.

aipG a2bOption::g_opt() { 

       // if node is already in the solution...
  if (m_reachable_node->opt_cur()) return aipForbidden;

  aipG g_hope_total = g_hope() + reachable_node()->g_hope();
  aipG g_tot = g_hope_total.calc_fraction(1,2);

     // whether to add a little randomness should be 
     // re-evaluated as the AI is improved.
  g_tot += random_num(-2,2);

  if ( a2b_dcsn() && a2b_dcsn()->a2b_prob() &&
                     a2b_dcsn()->a2b_prob()->should_log_options() ) {
    char  hope_str[31], rhope_str[31];
    dump_hope_to_ptr(hope_str);
    strcat (hope_str, "/2");
    reachable_node()->dump_hope_to_ptr(rhope_str);
    strcat (rhope_str, "/2");
    log("  option - "); log (a2b_dcsn()->label());
    log(" to "); log(m_reachable_node->label());
    log("  = "); log(g_tot.numeric_value());
    log(" = "); log(hope_str); log("   "); log(rhope_str);
    log("\n");
  }  // end of logging goodnesses that control decision-making

  return g_tot;

}

//----------------------------------------------------------------------
//  g_opt_cmp   -  goodness used by solve() to compare solutions

aipG a2bOption::g_opt_cmp() { 

  return g_user_constant(); 

}

//----------------------------------------------------------------------
//  g_opt_usr   -  value reported to user (inside a goodness)

aipG a2bOption::g_opt_usr() { 

  return (aipNeutral - g_user_constant());     // make it positive

}

//======================================================================
//  a2bSolItrBase  -  base class for Solution Iterators
//
//----------------------------------------------------------------------
//  set_itr  -  given an a2bProblem

void a2bSolItrBase::set_itr (const a2bProblem *p) {

  if (p) {
    m_first = p->start_node();
  } else {
    m_first = 0;
  }

  m_current = 0;

}

//----------------------------------------------------------------------
//  set_itr  -  given a reference to a Solution Iterator to copy

void a2bSolItrBase::set_itr (const a2bSolItrBase& i) {

  m_first = i.const_first();
  m_current = 0;

}

//----------------------------------------------------------------------
//  first

a2bNode * a2bSolItrBase::first() {

  return (m_current = m_first);

}

//======================================================================
//  a2bSolutionItr  -  Solution Iterator for Best Solution
//
//----------------------------------------------------------------------
//  next

a2bNode * a2bSolutionItr::next() {

  if (!const_current()) return first();

  a2bOption *link_opt = (a2bOption*)(const_current()->opt_bsf());
  set_cur ( link_opt ? link_opt->reachable_node() : 0 );

  return const_current();

}

//======================================================================
//  a2bCurSolutionItr  -  Solution Iterator for Current Solution
//
//----------------------------------------------------------------------
//  next

a2bNode * a2bCurSolutionItr::next() {

  if (!const_current()) return first();

  a2bOption *link_opt = (a2bOption*)(const_current()->opt_cur());
  set_cur ( link_opt ? link_opt->reachable_node() : 0 );

  return const_current();

}

//======================================================================
//                           License
//
//   Permission is hereby granted, free of charge, to any 
//   person obtaining a copy of this software and associated 
//   documentation files (the "Software"), to deal in the Software 
//   without restriction, including without limitation the rights 
//   to use, copy, modify, merge, publish, distribute, sublicense, 
//   and/or sell copies of the Software, and to permit persons to 
//   whom the Software is furnished to do so, subject to the 
//   following conditions:
//
//   The copyright notice and this license shall be included in all 
//   copies or substantial portions of the Software.
//
//   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
//   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 
//   OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 
//   NON-INFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 
//   HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 
//   WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 
//   FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 
//   OTHER DEALINGS IN THE SOFTWARE.
//
//
//**********************************************************************