fredag, augusti 28, 2009

Markov

Wikipedia:
In mathematics, a Markov chain, named after Andrey Markov, is a stochastic process with the Markov property. Having the Markov property means that future states depend only on the present state, and are independent of past states. In other words, the description of the present state fully captures all the information that could influence the future evolution of the process. Being a stochastic process means that all state transitions are probabilistic (determined by random chance and thus unpredictable in detail, though likely predictable in its statistical properties).


I sommar har jag lekt lite med markov-kedjor. Mest för att testa konceptet och se om jag förstår något utav det. Efter att ha läst om dessa i en bok till kursen Algoritmer och Datastrukturer tänkte jag testa lite själv.

Första implementationen testade jag med en variant av mario, s.k. Infinite Mario som genererar banor slumpmässigt men spelas som vanliga Super Mario. Tydligen så gick det en tävling i att skriva en AI till denna mario. Mer om denna på http://julian.togelius.com/mariocompetition2009/.

Så jag skrev en enkel javaimplementation som sparade spelarens kommandon för att styra gubben, tillsammans med en enkel snapshot över omgivningen vid det givna tillfället. När jag sedan spelat igenom några banor och fått lite data att göra kedjor av så lät jag programmet själv ge kommandon genom en markov-kedja.

Blev ju minst sagt lite blandade resultat, då det var svårt för den att se stora hål i marken, samt att den inte hade någon mekanism för att skilja dåliga händelser från bra. Så hade jag sprungit in i en sköldpadda av misstag så var det OK att göra.

Sen ville jag testa att använda en markov-kedja för ointelligent musikgenerering. Genom att då läsa in en MIDI-fil och hantera varje ton som ett objekt att lagra och generera genom en kedja.

Pythonkod för kedjan:

class Markov:
def __init__(self):
self.chain = {}

def add(self, key, value):
if not self.chain.has_key(key):
self.chain[key] = {value:1}
else:
if not self.chain[key].has_key(value):
self.chain[key][value] = 1
else:
self.chain[key][value] = self.chain[key][value]+1

def get(self, key,count = 3):
largest = (0,0)
while count > 0:
c = random.choice(self.chain[key].keys())
if self.chain[key][c] > largest[1]:
largest = (c, self.chain[key][c])
count -= 1
return largest[0]

def put(self,arr):
old = [(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0)]
for i in arr:
self.add((old[0],old[1],old[2],old[3]),i)
old[0] = old[1]
old[1] = old[2]
old[2] = old[3]
old[3] = i

Detta är då en viktad kedja som föredrar vanligare förekomster framför mindre vanliga.
Nu är put-funktionen hårdkodad för att slänga in 4st tomma tupler som startdata, så till andra implementationer så måste den fixas först.

Till detta så använde jag mig av ett midi-bibliotek för python som jag hittade på http://www.mxm.dk/products/public/pythonmidi/ och midifiler av typen "type 0". Eftersom type 0 bara använder sig av ett spår så fungerade den bättre att använda.