About Me

I'm just someone struggling against my own inertia to be creative. My current favorite book is "Oh the places you'll go" by Dr. Seuss

Saturday, March 15, 2008

Funny obsessive ideas

Video game AI constructed from an adapting Stochastic Matrix. The matrix would encode N states- however many situations one wants the AI to be aware of, and M state transitions- The actions that the AI would take given that situation. A random state transition is chosen weighted according to the stochastic matrix probabilities. If the state transition results in success, then the weight for that transition's weight is incremented. If it results in failure, all other transitions are incremented instead. it may be possible to trace back a decision path several steps, and increment several of the transitions leading up to the success or failure.

It may also be possible to do that by stating that several previous conditions constitute a single "state".

The player's behavior can be observed to produce a stochastic matrix as well, and AI behavior could be an average between the computer's own learning, and observing the player.

I'd like a program that analyzes a body of text, and highlights words and letters depending on their relative probability. This would help spot errors in esoteric texts.

I would also like to use stochastic matrices for compression of text. If a run of text conforms to the predictions of a stochastic matrix, then one can specify a character of text by the rank of its prediction. That is, if presented with the digraph Th, the matrix would predict "e" as the most likely letter to occur, and thus encode e as "1", a as the second most likely choice, would be encoded as "2" etc. I haven't tried it, but my hope is that this would produce encodings along the lines of "111111111211121113211111111211132111111311112" Not only can encodings like this be very efficiently run length encoded, but if the predictions stay below low powers of 2, each character needs significantly less than 8 bits to encode it!

1 comment:

szityu said...

Hi Breton,

Seems like you're talking about reinforcement learning! :-)

You might find interesing the paper of Spronck et al., where they use this principle in Neverwinter Nights... and learn to beat the built-in AI in 30 games.

Similar ideas are also used in text compression (which proves that it is a good idea :-)

Istvan Szita