API tools faq
paste
DjSapsan

CPU generations

DjSapsan
Feb 21st, 2019 (edited)
236
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Lua 15.44 KB | None | 0 0
raw download clone embed print report
  1. --if arg[#arg] == "-debug" then require("mobdebug").start() end
  2. --require("mobdebug").on()
  3.  
  4. local class = require "middleclass"
  5. local CPU = class("CPUClass")
  6. math.randomseed(os.time())
  7.  
  8. local file outputFile = io.open("programs.txt","w")
  9. local outstr = ""
  10.  
  11. conf = {
  12.   bits = 8,                   -- битность процессора
  13.   ticksPerStep = 100,         -- тиков на решение задачи
  14.   errorRate = 9,              -- 1 error per 10 generations
  15.   maxPop = 50,                -- макс. популяция
  16.   cloneBest = 10,             -- клонировать тех, кто входит в указанный топ
  17.   initialEnergy = 100,        -- начальная энергия
  18.   takeFinalProgramStr = false  --
  19.  
  20. }
  21. conf.maxNumber = 2^conf.bits
  22.  
  23. input = {}      -- вход на каждый проц
  24. check = {}      -- ожидаемый выход
  25. CPUlist = {}    -- список всех процов
  26. bestList = {}   -- сортированный список лучших
  27.  
  28. function CPU:initialize()
  29.   self.ID = getNewID()
  30.   CPUlist[self.ID]=self
  31.  
  32.   self.energy = conf.initialEnergy
  33.  
  34.   self.a = 0
  35.   self.b = 0
  36.   self.RAM = {}
  37.   self.pointer = 0
  38.   self.flag = false
  39.   self.overflow = false
  40.  
  41.   self.outR = 0
  42.   self.inR = 0
  43.   self.ioPointer = 1
  44.  
  45.   self.steps = 0
  46.   self.output = {}
  47.   self.finalProgramStr = ""
  48. end
  49.  
  50. function getNewID()
  51.   return #CPUlist + 1
  52. end
  53.  
  54. function CPU:getString()
  55.   programm = ""
  56.   return "My ID:"..self.ID..", E:"..self.energy.."\n"
  57. end
  58.  
  59. function CPU:kill()
  60.   CPUlist[self.ID] = nil
  61.   self = nil
  62. end
  63.  
  64. function CPU:resetState()
  65.   self.a = 0
  66.   self.b = 0
  67.   self.pointer = 0
  68.   self.flag = false
  69.   self.overflow = false
  70.   self.steps = 0
  71.   --self.finalProgramStr = ""
  72. end
  73.  
  74. function CPU:run()
  75.   while (self.steps <= conf.ticksPerStep) do
  76.     value = self:fetch()
  77.    
  78.     if self.steps == 0 and conf.takeFinalProgramStr then
  79.       self.finalProgramStr = self.finalProgramStr .. self:getOperationStr()
  80.     end
  81.    
  82.     self:runOperation(value)
  83.    
  84.     if self.steps ~= 0 and conf.takeFinalProgramStr then
  85.       self.finalProgramStr = self.finalProgramStr .. self:getOperationStr()
  86.     end
  87.    
  88.     if self.markToKill then break end
  89.   end
  90.  
  91.   self.steps = 0
  92.   if self.markToKill then self:kill() end
  93. end
  94.  
  95. function CPU:incPointer()
  96.   self.pointer = self.pointer + 1
  97.   if self.pointer >= conf.maxNumber then self.pointer = 0 end
  98. end
  99.  
  100. function CPU:fetch()
  101.   return self.RAM[self.pointer] or 0
  102. end
  103.  
  104. function CPU:fixA()
  105.   if tostring(self.a) == 'nan' or  tostring(self.a) == 'nil' then self.a = 0
  106.   elseif self.a >= conf.maxNumber then self.a = self.a % conf.maxNumber self.overflow = true
  107.   elseif self.a < 0 then self.a = conf.maxNumber + self.a
  108.   else self.a = math.floor(self.a) end
  109. end
  110.  
  111. function CPU:fixB()
  112.     if tostring(self.b) == 'nan' or  tostring(self.b) == 'nil' then self.b = 0
  113.   elseif self.b >= conf.maxNumber then self.b = self.b % conf.maxNumber
  114.   elseif self.b < 0 then self.b = conf.maxNumber + self.b
  115.   else self.b = math.floor(self.b) end
  116. end
  117.  
  118. function CPU:getRAM(addr)
  119.   return self.RAM[addr] or 0
  120. end
  121.  
  122. function CPU:exception()
  123.   self.markToKill = true
  124. end
  125.  
  126. function CPU:runOperation(op)
  127.   op = op % (#operations + 1)
  128.   if op == 0 then self.steps = conf.ticksPerStep elseif
  129.   op == 1 then self:incPointer(); addr = self:fetch(); self.a = self:getRAM(addr); elseif
  130.   op == 2 then self:incPointer(); val  = self:fetch(); self.a = val; elseif
  131.   op == 3 then self:incPointer(); addr = self:fetch(); self.RAM[addr] = self.a;  elseif
  132.   op == 4 then self.a, self.b = self.b, self.a elseif
  133.   op == 5 then self:incPointer(); addr = self:fetch(); self.a = self.a + self:getRAM(addr); self.overflow = false elseif
  134.   op == 6 then self:incPointer(); val = self:fetch(); self.a = self.a + val; self.overflow = false elseif
  135.   op == 7 then self:incPointer(); addr = self:fetch(); self.a = self.a - self:getRAM(addr); elseif
  136.   op == 8 then self:incPointer(); val = self:fetch(); self.a = self.a - val; elseif
  137.   op == 9 then self:incPointer(); addr = self:fetch(); self.a = self.a * self:getRAM(addr); self.overflow = false elseif
  138.   op == 10 then self:incPointer(); val = self:fetch(); self.a = self.a * val; self.overflow = false elseif
  139.   op == 11 then self:incPointer(); addr = self:fetch(); if (self:getRAM(addr)==0) then self:exception(); return end
  140.     self.b =(self.a%self:getRAM(addr)); self.a=math.floor(self.a/self:getRAM(addr)); self.steps=self.steps+5 elseif
  141.   op == 12 then self:incPointer(); val = self:fetch(); if (val==0) then self:exception(); return end
  142.     self.b = (self.a % val); self.a = math.floor(self.a / val); self.steps = self.steps + 5 elseif
  143.   op == 13 then self.a = self.a + 1; self.overflow = false elseif
  144.   op == 14 then self.a = self.a - 1; self.overflow = false elseif
  145.   op == 15 then self.flag = self.overflow elseif
  146.   op == 16 then self.flag = self.a == 0 elseif
  147.   op == 17 then self:incPointer(); addr = self:fetch(); self.flag = self.a > self:getRAM(addr) elseif
  148.   op == 18 then self:incPointer(); val = self:fetch(); self.flag = self.a > val elseif
  149.   op == 19 then self:incPointer(); addr = self:fetch(); self.flag = self.a < self:getRAM(addr) elseif
  150.   op == 20 then self:incPointer(); val = self:fetch(); self.flag = self.a < val elseif
  151.   op == 21 then self:incPointer(); addr = self:fetch(); self.flag = self.a == self:getRAM(addr) elseif
  152.   op == 22 then self:incPointer(); val = self:fetch(); self.flag = self.a == val elseif
  153.   op == 23 then self.flag = not self.flag elseif
  154.   op == 24 then self:incPointer(); addr = self:fetch(); self.pointer = self:getRAM(addr) elseif
  155.   op == 25 then self:incPointer(); addr = self:fetch(); self.pointer = addr elseif
  156.   op == 26 then self.pointer = self.a elseif
  157.   op == 27 then self:incPointer(); if (self.flag) then addr = self:fetch(); self.pointer = self:getRAM(addr) end elseif
  158.   op == 28 then self:incPointer(); if (self.flag) then addr = self:fetch(); self.pointer = addr end elseif
  159.   op == 29 then self:incPointer(); if (self.flag) then addr = self:fetch(); self.pointer = self.a end elseif
  160.   op == 30 then self.output[self.ioPointer] = self.a; self.steps = conf.ticksPerStep elseif
  161.   op == 31 then self.a = input[self.ioPointer];  end
  162.  
  163.   self:fixA()
  164.  
  165.   self.steps = self.steps + 1
  166.   self:incPointer();
  167. end
  168.  
  169. function CPU:validateOutput()
  170.   self.energy = self.energy - self:fitnessTables(self.output, check) - self.steps--*2
  171. end
  172.  
  173. function CPU:fitnessTables(t1,t2)
  174.   mistake = 0
  175.   for i = 1, #t2 do
  176.     if tostring(t1[i]) == 'nil' then t1[i] = 0 end
  177.     diff = t1[i] - t2[i]
  178.     mistake = mistake + diff*diff
  179.   end
  180.  
  181.   if mistake > 0 and mistake < 5 then  conf.takeFinalProgramStr = true
  182.     --printPopulation()
  183.     print ("------------")
  184.     print (table.tostring(self.output))
  185.     print (self.finalProgramStr)
  186.   end
  187.  
  188.   if mistake == 0 then
  189.     print("CPU has found right answer!") print(table.unpack(t1)) print("RAM:") print(table.tostring(self.RAM)) os.exit() end
  190.   return mistake*4
  191. end
  192.  
  193. function CPU:printRAM()
  194.   RAMstr = ""
  195. end
  196.  
  197. function CPU:clone()
  198.   temp = CPU:new()
  199.   temp.RAM = tableCopy(self.RAM)
  200.  
  201.   isMutate = math.random(1,10)<=conf.errorRate
  202.   if (isMutate) then temp:mutate() end
  203. end
  204.  
  205. function CPU:mutate()
  206.   where = math.random(0,conf.maxNumber)
  207.   what = math.random(0,conf.maxNumber)
  208.   self.RAM[where] = what
  209. end
  210.  
  211. function table.val_to_str ( v )
  212.   if "string" == type( v ) then
  213.     v = string.gsub( v, "\n", "\\n" )
  214.     if string.match( string.gsub(v,"[^'\"]",""), '^"+$' ) then
  215.       return "'" .. v .. "'"
  216.     end
  217.     return '"' .. string.gsub(v,'"', '\\"' ) .. '"'
  218.   else
  219.     return "table" == type( v ) and table.tostring( v ) or
  220.       tostring( v )
  221.   end
  222. end
  223.  
  224. function table.key_to_str ( k )
  225.   if "string" == type( k ) and string.match( k, "^[_%a][_%a%d]*$" ) then
  226.     return k
  227.   else
  228.     return "[" .. table.val_to_str( k ) .. "]"
  229.   end
  230. end
  231.  
  232. function table.tostring( tbl )
  233.   local result, done = {}, {}
  234.   for k, v in ipairs( tbl ) do
  235.     table.insert( result, table.val_to_str( v ) )
  236.     done[ k ] = true
  237.   end
  238.   for k, v in pairs( tbl ) do
  239.     if not done[ k ] then
  240.       table.insert( result,
  241.         table.key_to_str( k ) .. "=" .. table.val_to_str( v ) )
  242.     end
  243.   end
  244.   return "{" .. table.concat( result, "," ) .. "}"
  245. end
  246.  
  247. function tableCopy(t)
  248.   local t2 = {}
  249.   for k,v in pairs(t) do
  250.     t2[k] = v
  251.   end
  252.   return t2
  253. end
  254.  
  255.  
  256.  
  257. function CPU:getOperationStr()
  258.   val = self:fetch()
  259.   val = val % (#operations + 1)
  260.   str = operations[val]
  261.   if string.sub(str, -1)=="@" then
  262.     p = self.pointer + 1
  263.     if p>=conf.maxNumber then p = 0 end
  264.     str = str..tostring(self.RAM[p]).." at ["..p.."]"
  265.   elseif string.sub(str, -1)=="*" then
  266.     p = self.pointer + 1
  267.     if p>=conf.maxNumber then p = 0 end
  268.     str = str..tostring(self.RAM[p])
  269.   elseif string.sub(str, -1)=="." then
  270.     str = str.." (a="..tostring(self.a)..")"
  271.   elseif string.sub(str, -1)=="?" then
  272.     str = str.." (f="..tostring(self.flag)..")"
  273.   end
  274.   return str.." | "
  275. end
  276.  
  277. operations = {
  278.   [0] = "end",
  279.   [1] = "load@",
  280.   [2] = "loadC*",
  281.   [3] = "store*",
  282.   [4] = "switch.",
  283.   [5] = "add@",
  284.   [6] = "addC*",
  285.   [7] = "sub@",
  286.   [8] = "subC*",
  287.   [9] = "mult@",
  288.   [10] = "multC*",
  289.   [11] = "div@",
  290.   [12] = "divC*",
  291.   [13] = "inc.",
  292.   [14] = "dec.",
  293.   [15] = "overflow?",
  294.   [16] = "a == 0?",
  295.   [17] = "a > RAM?",
  296.   [18] = "a > const?",
  297.   [19] = "a < RAM?",
  298.   [20] = "a < const?",
  299.   [21] = "a == RAM?",
  300.   [22] = "a == const?",
  301.   [23] = "not?",
  302.   [24] = "jump [RAM]@",
  303.   [25] = "jump [const]*",
  304.   [26] = "jump [a].",
  305.   [27] = "jump to RAM if F@",
  306.   [28] = "jump to const if F*",
  307.   [29] = "jump to a if F.",
  308.   [30] = "out.",
  309.   [31] = "in"
  310. }
  311.  
  312. function getBestList()
  313.   --i = 1
  314.   bestList = {}
  315.   for _,c in pairs(CPUlist) do
  316.     table.insert(bestList,#bestList+1,c)
  317.   end
  318.  
  319.   if (#bestList>1) then table.sort(bestList,function(a,b) return a.energy > b.energy end) end  -- сортируем по оценке
  320. end
  321.  
  322. function runTest(testC)
  323.   if testC == nil then
  324.    
  325.     for _,c in pairs(CPUlist) do
  326.       for i = 1,#input do
  327.         c:resetState()
  328.         c.ioPointer = i            -- смотрим на следующих инпут
  329.         c:run()                    -- запускаем процессор
  330.       end
  331.       c:validateOutput()         -- оцениваем его работу
  332.     end else
  333.    
  334.     for i = 1,#input do
  335.       testC:resetState()
  336.       testC.ioPointer = i            -- смотрим на следующих инпут
  337.       testC:run()                    -- запускаем процессор
  338.     end
  339.   end
  340. end
  341.  
  342. function printPopulation()
  343.   for _,c in ipairs(bestList) do
  344.     print("ID:".. c.ID..", E:".. c.energy) print(table.unpack(c.output))
  345.   end
  346.   print("-----------------------------")
  347. end
  348.  
  349. function runEcosystem(t)
  350.   getBestList()
  351.   --printPopulation()
  352.   last = #bestList
  353.   for i = 1,last do
  354.     if (#CPUlist<conf.maxPop and i<= conf.cloneBest) then bestList[i]:clone() end                          -- размножаем первых
  355.     while(#CPUlist<conf.maxPop and bestList[1].energy>0) do bestList[1]:clone() end                        -- размножаем первого до максимального населения
  356.     if (i>conf.cloneBest) then bestList[i]:kill() end                                                      -- умирают слабые
  357.     if (i>1 and bestList[i].energy<=0) then bestList[i]:kill() end                                         -- умирают слабые
  358.   end
  359.    
  360. end
  361.  
  362. function runGeneration(times)  
  363.   for i=1,times do
  364.     runTest()                     -- запуск программ
  365.     runEcosystem(i)                -- кормежка, размножение и смерть
  366.   end
  367.  
  368.   print("END")
  369.   print(table.unpack(bestList[1].output))
  370.   print(table.unpack(bestList[1].RAM))
  371.   print("Process is halted - max number of tries was reached")
  372. end
  373.  
  374. function testCPU()
  375.   testC = CPU:new()
  376.   testC.RAM = {58,255,3,231,176,170,29,88,47,169,186,119,211,14,15,162,150,46,149,250,251,181,92,237,0,183,161,247,137,47,102,88,188,184,167,109,253,225,113,36,73,38,103,15,255,61,245,2,161,198,167,205,4,249,154,17,197,77,137,199,238,91,119,245,47,99,166,150,5,54,141,106,231,187,147,115,156,71,103,24,9,14,174,137,204,13,155,244,53,12,61,134,140,95,69,31,14,78,94,116,75,178,75,21,256,236,202,137,158,133,135,91,16,211,189,134,18,46,222,55,1,106,84,60,150,8,118,65,38,171,151,108,223,104,167,196,142,116,47,48,68,176,226,68,217,148,216,131,194,31,16,159,197,252,129,206,95,24,142,169,153,101,154,223,98,128,52,39,21,152,37,67,181,109,242,41,72,89,110,218,171,209,68,101,90,165,171,72,251,36,95,55,15,92,60,23,177,71,165,176,35,11,42,134,204,60,124,59,40,130,68,233,134,175,100,241,218,154,230,42,75,67,214,33,6,85,159,99,233,10,12,158,12,8,33,256,237,207,12,50,62,31,114,106,169,183,206,110,214,252,207,105,128,208,194,245,[0]=220}
  377.   -- squares {58,255,3,231,176,170,29,88,47,169,186,119,211,14,15,162,150,46,149,250,251,181,92,237,0,183,161,247,137,47,102,88,188,184,167,109,253,225,113,36,73,38,103,15,255,61,245,2,161,198,167,205,4,249,154,17,197,77,137,199,238,91,119,245,47,99,166,150,5,54,141,106,231,187,147,115,156,71,103,24,9,14,174,137,204,13,155,244,53,12,61,134,140,95,69,31,14,78,94,116,75,178,75,21,256,236,202,137,158,133,135,91,16,211,189,134,18,46,222,55,1,106,84,60,150,8,118,65,38,171,151,108,223,104,167,196,142,116,47,48,68,176,226,68,217,148,216,131,194,31,16,159,197,252,129,206,95,24,142,169,153,101,154,223,98,128,52,39,21,152,37,67,181,109,242,41,72,89,110,218,171,209,68,101,90,165,171,72,251,36,95,55,15,92,60,23,177,71,165,176,35,11,42,134,204,60,124,59,40,130,68,233,134,175,100,241,218,154,230,42,75,67,214,33,6,85,159,99,233,10,12,158,12,8,33,256,237,207,12,50,62,31,114,106,169,183,206,110,214,252,207,105,128,208,194,245,[0]=220}
  378.   -- fibb {129,231,80,155,68,203,147,220,50,95,50,228,170,17,80,177,233,61,205,111,86,236,15,175,95,89,49,87,145,229,8,80,125,228,199,10,82,74,37,70,158,174,221,10,11,101,40,255,210,19,187,184,76,232,98,127,196,190,62,27,157,73,46,77,176,72,185,130,79,125,218,210,69,244,64,131,36,227,225,153,223,3,201,51,89,242,173,167,160,150,76,141,0,230,178,236,127,246,69,212,98,202,60,170,186,29,73,194,233,143,218,148,153,13,94,76,69,254,106,182,96,158,185,118,159,146,76,152,154,150,137,123,62,12,40,229,123,186,211,173,218,103,202,48,64,140,62,155,179,13,232,1,69,167,53,95,178,116,124,102,7,231,98,27,135,42,21,61,191,174,39,117,67,196,141,62,47,89,74,104,184,210,229,243,67,152,125,112,102,218,114,205,20,97,117,120,182,203,86,1,138,33,157,198,217,185,253,135,95,55,25,66,251,184,64,40,103,193,170,248,250,3,117,170,10,222,25,14,252,104,248,237,177,193,172,13,192,44,254,135,191,126,109,83,171,188,176,18,126,166,180,169,160,1,107,211,[0]=92}
  379.  
  380.   runTest(testC)
  381.   print("RAM:")
  382.   print(table.unpack(testC.output))
  383.   print(CPUlist[1].finalProgramStr)
  384. end
  385.  
  386. function stopAll()
  387.   print("----------------- END -----------------")
  388.   print("Best ID:".. bestList[1].ID..", E:".. bestList[1].energy) print(table.unpack(bestList[1].output))
  389.   print("RAM:")
  390.   print(table.unpack(bestList[1].RAM))
  391.   print()
  392.   os.exit()
  393. end
  394. --------------------------------------------- BEGIN -------------------------------
  395. --input = {1,2,3,4,5,6,7,8,9,10}
  396. --check = {1,4,9,16,25,36,49,64,81,100} {1,1,2,3,5,8,13,21,34,55} {2,3,4,5,6,7,8,9,10,11}
  397.  
  398. input = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}
  399. check = {1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0}
  400.  
  401. CPU:new()
  402. CPUlist[1].RAM = {[0]=30,0}
  403.  
  404. print("running...")
  405. runGeneration(1000000)
  406. --testCPU()
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!