The task was to write a LUA AI that beats the computer in Rock-paper-scissors. The computer had three different strategies, each of them depended on a random seed. The submitted AI had to figure out which strategy it's playing against then somehow recover its inner state and then win at least 90000 out of 100000 times.
The three strategies worked like this python code:
class Slime(object):
def __init__(self, seed):
self.state = seed
def play(self, last):
self.state = (self.state+1)%3
return self.state
class Alpaca(object):
def __init__(self, seed):
self.state = seed
def play(self, last):
self.state = (self.state+last-1640531527)%(2**32)
return self.state%3
class Nozomi(object):
def __init__(self, seed):
self.state = seed
def play(self, last):
self.state = (self.state*48271)%(2**31-1)
return self.state%3To recognize the Slime strategy, my AI counted how many times the computer's choice was equal to 1 + the computer's previous choice. If that happened at least 80% then it simply returned the computer's last choice which would beat its next one.
To recognize the Nozomi strategy, my AI pre-calculated hashes of 100 consecutive choices at different seed positions. As 48271 is a primitive root modulo 2**31-1, I could start with seed=1, calculate the hash of the 100 next choices then skip 9800 choices (it's easy to skip multiple values from an LCG with no additive term), then calculate the hash of the next 100 and so on. These hashes were stored in a LUA table. Then during playing it always calculated the current hash value, and if it found it in the table then it started to simulate the LCG from there.
The Alpaca strategy was recognized as not being the previous two. My AI calculated intervals the current state could be in. At start it could be anywhere in the [0,2**32-1] interval. After a move it could be figured out whether the current state is below or above 1640531527 because that number is not divisible by 3 so it acted differently if there was an underflow. After each move the intervals were rotated (and thus possible split into 2 smaller intervals) with this number, and then the intervals were decreased according to the presence of underflow. When only one possible state was left, it started to play against that.
I have never written more than one line long LUA codes before so I wanted to keep this tradition. My final solution was:
echo "local e=0 local f=0 local g=0 local h=4294967296 local i=1640531527 local j=h-i local k=0 local l local m local n local o=nil local p={}local q=1000000000039 local r=196603639867 local s={}local t=1 local u=0 for v=1,219130 do u=0 for w=1,100 do u=(u*3+(t%3))%q t=(t*48271)%2147483647 end s[u]=t t=(t*70566312)%2147483647 end function play(v)if v==-1 then e=e+1 f=1 n=1 o=nil u=0 b=-1 c=0 return 1 else f=f+1 if v==(b+1)%3 then c=c+1 end b=v if o==nil then p[f-1]=v u=(u*3+v)%q if f>101 then u=(u-(p[f-101]*r)+q)%q end o=s[u]end if o~=nil then n=(o+2)%3 o=(o*48271)%2147483647 return n end if 5*c>4*f then return v else if f==2 then l={}l[1]=0 m={}m[1]=h-1 k=1 n=1 g=v else local w=0 local x={}local y={}local z=0 local A=0 for B=1,k do local C=l[B]local D=m[B]if g==v then if D>=j then D=j-1 end else if C<j then C=j end end if C<=D then w=w+1 x[w]=C y[w]=D if D<=i then z=z+D-C+1 else if C>i then A=A+D-C+1 else z=z+i-C+1 A=A+D-i end end end end g=(v+n+2)%3 if z>A then d=(g+1)%3 else d=(g)%3 end n=(d+2)%3 k=0 l={}m={}for B=1,w do local C=x[B]local D=y[B]C=(C+j+n)%h D=(D+j+n)%h if C<=D then k=k+1 l[k]=C m[k]=D else k=k+1 l[k]=0 m[k]=D k=k+1 l[k]=C m[k]=h-1 end end end return n end end end-- EOF" |nc 13.113.99.240 50216(No, I didn't really write this code by hand, it was produced by a minifier because my original code was longer than the 2048 bytes limit, but my original version was almost as unreadable as this one.)
It gave me the flags:
You are luaky! hitcon{Hey Lu4ky AI, I am Alpaca... MEH!}
Wow... You are VERY LUAKY!! hitcon{Got AC by r4nd() % 3! Nozomi p0wer chuunyuuuuu~ <3}