Generating Malbolge code using simulated annealing

I've always been fascinated by Malbolge programming language, which is that hard:

Malbolge was so difficult to understand when it arrived that it took two years for the first Malbolge program to appear. Indeed, the author himself has never written a single Malbolge program.[1] The first program was not written by a human being: it was generated by a beam search algorithm designed by Andrew Cooke and implemented in Lisp.[2]

( https://en.wikipedia.org/wiki/Malbolge )

In Russian:

На следующем витке углубления потаенного знания в моду вошла эстетика чистого охренения. На языках той поры писать было невозможно – по определению; они стали крайним проявлением недружелюбности к программисту. Принцип, заявленный еще при разработке INTERCAL'а («чтобы все вас уважали, надо заниматься тем, что никому не понятно») здесь был не просто поставлен во главу угла – возведен в идеал. На переднем крае – язык Malbolge. Такое название для языка программирования (Malebolge, «Злые Щели» (в переводе Державина) – восьмой круг Дантева Ада (Inferno)) его автор Ben Olmstead объясняет безыскусно: «хотелось сделать максимально адский (Infernal) язык из всех возможных». В общем и целом, это вполне удалось: потребовалось всего два года, чтобы создать первую работающую программу на Malbolge (более того, эта программа была не написана собственноручно программистом, а «найдена» специальной исследовательской программой на языке Lisp). Этой первой программой стал классический «Hello world» – вот такой:

 (=<:9876Z4321UT.-Q+*)M&%$H"!~}|Bzy?=|{z]KwZY44Eq0/{mlk**
 hKs_dG5[m_BA{?-Y;;Vb'rR5431M}/.zHGwEDCBA@98\6543W10/.R,+O<

Стоит заметить, что Malbolge взял очень важную планку: эзотерические языки программирования стали объектом исследования. «Как написать работающую программу на Malbolge» – это была задачка, об которую очень и очень стоило поломать голову; золотыми буквами в историю языка вписаны имена Энтони Йонаса, опубликовавшего несколько работающих программ, но не раскрывшего секрета их написания, Лу Шеллера, проведшего криптоанализ (sic!) языка, Томаса Вергзановски, создавшего генератор несложных, но работающих программ... (...которые в несколько раз больше аналогичных программ Энтони Йонаса, по сию пору хранящего свои секреты.)

Подобно Malbolge, «вещью в себе», то есть объектом, а не инструментом изучения, стали: язык Thue, основанный на исчислении Thue, созданном одноименным норвежским математиком; ALPACA – язык клеточных автоматов (игру «Жизнь» помните? – натуральный клеточный автомат); линейка языков Smetana-SMITH-Muriel. Три последних (за авторством уже известного нам Криса Пресси) замечательны тем, что довольно вычурная идея самомодификации кода положена в основу любого действия: единственный способ управления выполнением (вместо всяких там циклов-условий-переходов) – скопировать свой собственный код «вперед», чтобы он выполнился еще раз. Писать такие программы мучительно неприятно; зато для раздвижения границ сознания концепция Сметаны или Туэ – похлеще диэтиламида лизергиновой кислоты. Впрочем, все эти «игрушки» меркнут перед «воплощенной сложностью» в лице Malbolge – и в благодарной памяти потомков он остается единственным вечноживущим языком из категории «чистого охренения». 

( https://rsdn.org/article/philosophy/languages.xml )

More links: https://esolangs.org/wiki/malbolge, http://www.acooke.org/malbolge.html, http://www.lscheffer.com/malbolge.shtml.

My Simulated Annealing (SA) searcher can find a couple of 13-byte program that prints "Hi" (way shorter than the ones that can be generated automatically here):

''B$@"]!<54XE
D=%$$9]76Z:WE

Check with the online interpreter: http://malbolge.doleczek.pl/.

It takes ~10 minutes on my venerable Intel Xeon E3-1220 3.10GHz (remember, this is Python).

What about bruteforce? log2(6^13) = ~33 bits. Still possible.

# requires https://github.com/perrygeo/simanneal library
# Malbolge interpreter has been copypasted from https://github.com/Avantgarde95/pyMalbolge and reworked
# interpreter: http://malbolge.doleczek.pl/

from __future__ import print_function
from __future__ import with_statement
import math
import random
from simanneal import Annealer
import sys

TABLE_CRAZY = (
    (1, 0, 0),
    (1, 0, 2),
    (2, 2, 1)
)

ENCRYPT = map(ord,
              '5z]&gqtyfr$(we4{WP)H-Zn,[%\\3dL+Q;>U!pJS72FhOA1CB'\
              '6v^=I_0/8|jsb9m<.TVac`uY*MK\'X~xDl}REokN:#?G\"i@')

OPS_VALID2 = (4, 5, 23, 39, 40, 62, 68, 81)
OPS_VALID = (4, 5, 39, 40, 62, 68) # without 23 (read), 81 (end)

POW9, POW10 = 3**9, 3**10

# --------------------------------------------------

def rotate(n):
    return POW9*(n%3) + n/3

def crazy(a, b):
    result = 0
    d = 1

    for i in xrange(10):
        result += TABLE_CRAZY[(b/d)%3][(a/d)%3] * d
        d *= 3

    return result

def initialize(source, mem):
    i = 0

    for c in source:
        if c == ' ' or c == '\n':
            continue

        if (ord(c)+i) % 94 not in OPS_VALID2:
            print ('Invalid character in the source file:', ord(c)+i, ' at: ', i)
            sys.exit(1)

        if i == POW10:
            print ('Source file is too long')
            sys.exit(1)

        mem[i] = ord(c)
        i += 1

    while i < POW10:
        mem[i] = crazy(mem[i-1], mem[i-2])
        i += 1

def interpret(mem):
    written=""
    steps=0

    a, c, d = 0, 0, 0

    while 1:
        if mem[c] < 33 or mem[c] > 126:
            return written, steps

        v = (mem[c]+c) % 94

        if v == 4:                        # jmp [d]
            c = mem[d]
        elif v == 5:                      # out a
            #write(chr(a % 256))
            #flush()
            written=written+chr(a % 256)
        #elif v == 23:                     # in a
        #    a = ord(read(1))
        elif v == 39:                     # rotr[d]; mov a, [d]
            a = mem[d] = rotate(mem[d])
        elif v == 40:                     # mov d, [d]
            d = mem[d]
        elif v == 62:                     # crz [d], a; mov a, [d]
            a = mem[d] = crazy(a, mem[d])
        elif v == 68:                   # nop
             pass
        elif v == 81:                     # end
            return written, steps
        else:
            pass

        if mem[c] >= 33 and mem[c] <= 126:
            mem[c] = ENCRYPT[mem[c] - 33]

        c = 0 if c == POW10-1 else c+1
        d = 0 if d == POW10-1 else d+1
        steps=steps+1

    return written, steps

# --------------------------------------------------

def calc_fitness(state):

    mem = [0] * POW10
    if initialize("".join(state), mem)==False:
        return 0

    written, steps = interpret(mem)
    need="Hi"

    # bonus: 10 for each written character
    fitness=len(written)*10

    # bonus: 50 if only 2 characters written
    if len(written)==2:
        fitness=fitness+50

    # bonus: 50 if characters are different
    if len(written)>=2 and written[0]!=written[1]:
        fitness=fitness+50
    if written==need:
        print ("found!")
        print ("".join(state))
        exit(0)

    # bonus: 100 if character is what we need
    if len(written)==1:
        if written[0]==need[0]:
            fitness=fitness+100
    if len(written)==2:
        if written[1]==need[1]:
            fitness=fitness+100
    return -fitness

class TestProblem(Annealer):

    # pass extra data (the distance matrix) into the constructor
    def __init__(self, state):
        super(TestProblem, self).__init__(state)  # important!

    def move(self):
        while True:
            #if (ord(c)+i) % 94 not in OPS_VALID:
            idx = random.randint(0, len(self.state) - 2) # do not touch the last END ins
            a=random.choice(OPS_VALID)
            if a<idx:
                a=a+94
            if a-idx<32:
                continue
            if a-idx>127:
                continue
            t=chr(a-idx)
            if t!=' ' and t!='\n':
                self.state[idx] = t
                return

    def energy(self):
        return calc_fitness(self.state)

if __name__ == '__main__':

    init_state=[]
    pgm_len=13
    # fill with NOPs:
    for i in range(pgm_len):
        init_state.append(chr(68-i))
    # the last ins is END:
    init_state[pgm_len-1]=chr(81-(pgm_len-1))

    test = TestProblem(init_state)
    test.steps = 4000
    # since our state is just a list, slice is the fastest way to copy
    test.copy_strategy = "slice"
    state, e = test.anneal()

    print()
    print("%i energy:" % e)
    pgm="".join(state)
    print (pgm)

    mem = [0] * POW10
    initialize(pgm, mem)
    print (interpret(mem))

( https://github.com/DennisYurichev/yurichev.com/blob/master/blog/malbolge/SA_Malbolge.py )


→ [list of blog posts]

Please drop me email about any bug(s) and suggestion(s): dennis(@)yurichev.com.