1
2 /* "Species" - a CoreWars evolver. Copyright (C) 2003 'Varfar'
3 *
4 * This program is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License as published by the Free
6 * Software Foundation; either version 1, or (at your option) any later
7 * version.
8 *
9 * This program is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
12 * more details.
13 *
14 * You should have received a copy of the GNU General Public License along
15 * with this program; if not, write to the Free Software Foundation, Inc.,
16 * 675 Mass Ave, Cambridge, MA 02139, USA.
17 */
18
19 #include "species.hpp"
20 #include "inst_gen_weighted_random.hpp"
21 #include "rand.hpp"
22 #include "opcode_branch_lookup.hpp"
23 using namespace std;
24
25 /***** CInstGeneratorWeightedRandom class implementation *********************/
26
CInstGeneratorWeightedRandom()27 CInstGeneratorWeightedRandom::CInstGeneratorWeightedRandom() {
28 _type = WEIGHTED_RANDOM; // very important line!
29 // init the freq_hint table to default values
30 _freq_hint_sum = 0.0F;
31 for(int i=0; i<OPCODE_LAST; ++i) {
32 _freq_hint[(OPCODE)i] = OPCODE_FREQ_HINT_DEFAULT;
33 _freq_hint_sum += _freq_hint[(OPCODE)i];
34 }
35 _branch_bias = false;
36 _branch_pivot = BRANCH_PIVOT_DEFAULT;
37 }
38
get_freq_hint(const OPCODE opcode)39 float CInstGeneratorWeightedRandom::get_freq_hint(const OPCODE opcode) {
40 if(!(0 <= opcode < OPCODE_LAST))
41 PANIC(BAD_OPCODE,"request for invalid opcode in freq_hint",NULL);
42 return _freq_hint[opcode];
43 }
44
set_freq_hint(const OPCODE opcode,const float val)45 void CInstGeneratorWeightedRandom::set_freq_hint(const OPCODE opcode,const float val) {
46 if(!(0 <= opcode < OPCODE_LAST))
47 PANIC(BAD_OPCODE,"attempt to set invalid opcode in freq_hint",NULL);
48 if(0.0F > val)
49 PANIC(NEG_OPCODEFREQ_HINT,"attempt to set negative freq_hint",NULL);
50 _freq_hint_sum -= _freq_hint[opcode];
51 _freq_hint[opcode] = val;
52 _freq_hint_sum += _freq_hint[opcode];
53 if(0.0F == _freq_hint_sum)
54 PANIC(ZERO_OPCODEFREQ_HINT_SUM,"total freq_hints have zero sum",NULL);
55 }
56
suggest_instruction(insn_t & instruction,const MODE)57 void CInstGeneratorWeightedRandom::suggest_instruction(insn_t &instruction,const MODE /*mode*/) {
58 // NOTE: might be more fair to maintain a _branch_hint_sum and scale the roulette to a single pass
59
60 // generate a random number between 0.0F and freq_hint_sum
61 const float x = CRand::frand(_freq_hint_sum); // the target value
62 float y = 0.0F, // an iterator through all buckets
63 bucket, // an intermediary for weighing branch instructions
64 branch_weight = 1.0F; // a scale relative to the pivot
65 int i;
66 // need to weigh branches?
67 if(_branch_bias) {
68 // seek back to find a branch
69 for(i=index()-1; i>0; --i) {
70 if(OPCODE_IS_BRANCH[chromosome()->code(i).opcode()]) { // found?
71 // calculate weight based on distance to pivot
72 branch_weight = ((index()-i) / _branch_pivot);
73 break; // stop searching then
74 }
75 }
76 }
77 // rolette-wheel to the choosen instruction
78 do {
79 for(i=0; i<OPCODE_LAST; ++i) {
80 bucket = _freq_hint[(OPCODE)i];
81 if(_branch_bias && OPCODE_IS_BRANCH[(OPCODE)i]) {
82 bucket *= branch_weight;
83 }
84 y += bucket;
85 if(y > x) { // found?
86 generate_completely_random(instruction);
87 instruction.set_opcode((OPCODE)i);
88 return;
89 }
90 }
91 if(!_branch_bias)
92 cerr << "WARNING: roulette past end of freq_hint range" << endl;
93 } while(true);
94 }
95
read_ini_impl(INIFile & ini)96 void CInstGeneratorWeightedRandom::read_ini_impl(INIFile &ini) {
97 // load the freq_hints
98 int i;
99 KeyValuePair *kvp;
100 // opcodes
101 for(i=0; i<OPCODE_LAST; ++i) {
102 // get it
103 kvp = ini.get(MNEMONIC_OPCODE((OPCODE)i));
104 if(0 == kvp) // not set?
105 set_freq_hint((OPCODE)i,OPCODE_FREQ_HINT_DEFAULT);
106 else
107 set_freq_hint((OPCODE)i,kvp->getValueAsFloat(OPCODE_FREQ_HINT_DEFAULT));
108 }
109 // branch pivot?
110 kvp = ini.get("branch_bias");
111 if(0 != kvp) { // set
112 _branch_bias = kvp->getValueAsBool(_branch_bias);
113 if(_branch_bias) {
114 kvp = ini.get("branch_pivot");
115 if(0 != kvp) {
116 _branch_pivot = kvp->getValueAsInt(_branch_pivot);
117 if(1 > _branch_pivot) { // avoid a divzero further down the line!
118 PANIC(NEG_OPCODEFREQ_HINT,"branch_pivot cannot be less than 1",NULL);
119 }
120 }
121 }
122 }
123 }
124
read_override_ini_impl(INIFile & ini)125 CInstGenerator *CInstGeneratorWeightedRandom::read_override_ini_impl(INIFile &ini) {
126 CInstGeneratorWeightedRandom *ret = this;
127 int i, pivot;
128 bool bias;
129 KeyValuePair *kvp;
130 // load the freq_hints
131 for(i=0; i<OPCODE_LAST; ++i) {
132 // get it
133 kvp = ini.get(MNEMONIC_OPCODE((OPCODE)i));
134 if(0 != kvp) { // set?
135 if(this == ret) { // first opccode to be overridden?
136 ret = new CInstGeneratorWeightedRandom(*this); // create a copy
137 }
138 ret->set_freq_hint((OPCODE)i,kvp->getValueAsFloat(OPCODE_FREQ_HINT_DEFAULT));
139 }
140 }
141 // bias?
142 kvp = ini.get("branch_bias");
143 if(0 != kvp) { // set?
144 bias = kvp->getValueAsBool(ret->_branch_bias);
145 if(bias != ret->_branch_bias) { // overriden?
146 if(this == ret) { // first thing to be overriden?
147 ret = new CInstGeneratorWeightedRandom(*this); // create a copy
148 }
149 ret->_branch_bias = bias;
150 }
151 kvp = ini.get("branch_pivot");
152 }
153 // pivot? We'll ignore in the case when bias isn't set to keep things clean
154 if(ret->_branch_bias) {
155 kvp = ini.get("branch_pivot");
156 if(0 != kvp) { // set?
157 pivot = kvp->getValueAsInt(ret->_branch_pivot);
158 if(1 > pivot) { // avoid a divzero further down the line!
159 PANIC(NEG_OPCODEFREQ_HINT,"branch_pivot cannot be less than 1",NULL);
160 }
161 if(pivot != ret->_branch_pivot) {
162 if(this == ret) { // first thing to be overriden?
163 ret = new CInstGeneratorWeightedRandom(*this); // create a copy
164 }
165 ret->_branch_pivot = pivot;
166 }
167 }
168 }
169 // done
170 return ret;
171 }
172
write_ini(ostream & os)173 void CInstGeneratorWeightedRandom::write_ini(ostream &os) {
174 int i;
175 // list freq_hints
176 for(i=0; i<OPCODE_LAST; ++i)
177 if(OPCODE_FREQ_HINT_DEFAULT != _freq_hint[(OPCODE)i]) // not default value?
178 os << MNEMONIC_OPCODE((OPCODE)i) << '=' << _freq_hint[(OPCODE)i] << endl;
179 // list pivot stuff
180 if(_branch_bias) {
181 os << "branch_bias=" << _branch_bias << endl;
182 if(BRANCH_PIVOT_DEFAULT != _branch_pivot) {
183 os << "branch_pivot=" << _branch_pivot << endl;
184 }
185 }
186 }
187
write_override_ini(ostream & os,const CInstGenerator * parent)188 void CInstGeneratorWeightedRandom::write_override_ini(ostream &os,const CInstGenerator *parent) {
189 if(this == parent) // no override at all?
190 return;
191 if(same_type(parent,this)) { // not same concrete type?
192 write_ini(os);
193 return;
194 }
195 int i;
196 // list freq_hints
197 for(i=0; i<OPCODE_LAST; ++i)
198 if(((CInstGeneratorWeightedRandom*)parent)->_freq_hint[(OPCODE)i] != _freq_hint[(OPCODE)i]) // overriden?
199 os << MNEMONIC_OPCODE((OPCODE)i) << '=' << _freq_hint[(OPCODE)i] << endl;
200 // branch pivot stuff
201 if(_branch_bias != ((CInstGeneratorWeightedRandom*)parent)->_branch_bias) {
202 os << "branch_bias=" << _branch_bias << endl;
203 }
204 if(_branch_bias && (_branch_pivot != ((CInstGeneratorWeightedRandom*)parent)->_branch_pivot)) {
205 os << "branch_pivot=" << _branch_pivot << endl;
206 }
207 }
208