RoShamBo and Linux MM

[Cesar Eduardo Barros <cesarb@nitnet.com.br>]

I'm not a MM developer, and I don't understand much of the subject; I'm sending
this so you can tell me where I'm wrong =)

The RoShamBo Programming Competition is a contest of the popular
Rock-Paper-Scissors game, in which a program has to guess what the other
program will chose, and then play the right option to beat the opponent. The
opponent, of course, will try to do the same. Its page is
http://www.cs.ualberta.ca/~darse/rsbpc.html

The "ideal" strategy in a game theory sense is to do all your choices randomly,
so you will have an equal chance of winning or losing.

However, your opponents are not all random. To make things more interesting,
some of your opponents will be bots designed to use simple strategies, like a
constant 0-1-2-0-1-2-0-1-2, a distribution based on the digits of pi, or in the
contest announcement text. Other bots do simple things like playing the last
move of the opponent.

So, how does that relate to VM? Imagine you have a set of n pages, and you have
to chose one to swap out:

        0-1-2-3-4-5-6-7-8-...-n

You also have an history of accesses to the pages:

time
   0    0-1-2-3-4-5-a-7-8-...-n
   1    0-a-2-3-4-5-6-7-8-...-n
   2    0-1-a-3-4-5-6-7-8-...-n
   .
   .
   .
   t    0-1-2-3-a-5-6-7-8-...-n

You are now at time t+1.

This is like the RoShamBo game, but with n choices instead of 3, and with your
objective being to find the page with the least likelihood of being accessed
sooner. Notice that I'm not removing the swapped-out pages from the statistics.

A predictor would have to do some kinds of prediction that the contestants on
that contest had to do. Basically, in the RoShamBo contest, you had to find a
pattern in the opponent's behavior; in the VM problem, you have to find a
pattern in the memory accesses. You have the advantage of the "opponent" not
trying to outsmart you, tough.

So, I think that by looking at the players in that contest, we might gain some
insight in how to design a swap-out algorithm.

Comments?

-- 
Cesar Eduardo Barros
cesarb@nitnet.com.br
cesarb@dcc.ufrj.br
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/