Jump to content
BrainDen.com - Brain Teasers

Question

Here's the challenge: write a little code snippet in java or just generic pseudocode or even just describe your algorithm (you don't even have to know programming, I can just convert your algorithm for you!) that plays ROCK PAPER SCISSORS against an enemy... that enemy is another algorithm!

THE GAME

We all know the game rock paper scissors could use a little strategy... sure there is some psychological merit to it, but most of it is luck. Well, that's about to change.... you will create a deterministic algorithm that will battle against other algorithms for the ultimate title of ROCK PAPER SCISSORS CHAMPION!!! There will be no randomness functions, no chance, no luck. It's about skill. Is your algorithm a simple numerical ninja? Or is it a complex meta-algorithm that attempts to counterguess the enemy's strategy? MAY THE BEST ALGORITHM WIN!!!!!

TECHNICAL SPECS

Your algorithm has access to three different inputs: it has an array of all the moves its used previously. This array is called a. There is another array, b, that contains the moves used by the enemy in this match. You also have a variable, i, that denotes the round number (i=0 is the first round, i=1 is the next round, then i=2, etc).

Right now I have the global var numRounds set to 50. Ie, there will be 50 rounds before we see whose won more games. Let me know if you think that number should be something else.

0 = ROCK

1 = PAPER

2 = SCISSORS

[rock beats scissors, scissors beats paper, paper beats rock]

the arrays a & b are of the datatype int and hold zeroes, ones and twos up to a or b. a and all values after that in the array is NULL, same with b. So the array is only defined from a[0] to a[i-1] or equivalent for b.

For the very first round, i=0, there will be nothing in the arrays. So if your algorithm uses previous data to make future decisions, you'll need to have some primer value for i=0

For anyone interested, here is my java code that runs all this:



// ROCK PAPER SCISSORS CONTEST FOR BRAINDEN

//  BY UNREALITY

//    ENJOY

import java.util.Scanner;

public class ropasc

{

    public static int numGames = 50;

// rock: 0

// paper: 1

// scissors: 2


    private int[] myTurns; private String myName;



    public ropasc(String name)

    {

        myName = name;

        myTurns = new int[numGames];

    }


    public int[] get()

    {

        return myTurns;

    }


    public String getName()

    {

        return myName;

    }


    public int next(int[] enemy, int i)

    {

        int x=0;

        if (myName=="Test1") x = test1(myTurns, enemy, i);

        if (myName=="Test2") x = test2(myTurns, enemy, i);

        if (myName=="Test3") x = test3(myTurns, enemy, i);

        // etc. Could use "java.lang.reflect.*" to do this more elegantly but this way is simpler

        myTurns[i] = x;

        return x;

    }


    public int test1(int[] a, int[] b, int i)

    {

        if (i==0) return 2;

        return b[i-1];

    }


    public int test2(int[] a, int[] b, int i)

    {

        return i % 3;

    }


    public int test3(int[] a, int[] b, int i)

    {

        int sum = 0;

        for (int z=0; z<i; z++)

        {

            sum += (a[z] + b[z]);

        }

        sum %= 3;

        return sum;

    }


    public static String conv(int k)

    {

            if (k==0) return "ROCK";

            if (k==1) return "PAPER";

            if (k==2) return "SCISSORS";

            return "";

    }


    public static void main(String[] args)

    {


        String na = "", nb = "";

     /*   String na = "Test1"; // these two lines

        String nb = "Test2"; // will be the only ones changed to switch who is fighting whom */

        // how about, instead get user input?

        Scanner inp = new Scanner(System.in);

        System.out.print("\n\nFirst Algorithm: ");

        na = inp.next();

        System.out.print("\nSecond Algorithm: ");

        nb = inp.next();


        System.out.print(na + " vs " + nb + "\n\n");

        ropasc rps1 = new ropasc(na);

        ropasc rps2 = new ropasc(nb);

        int res1 = 0, res2 = 0, win1 = 0, win2 = 0, result = 2;

        for (int i=0; i< numGames; i++)

        {

            res1 = rps1.next(rps2.get(), i);

            res2 = rps2.next(rps1.get(), i);

            result = (2+res1+res2) % 3;

            if (result==1) win2++;

            if (result==0) win1++;

            System.out.println(conv(res1) + " vs " + conv(res2));

        }

        String zprint ="";

        if (win1>win2) zprint = rps1.getName() + " wins " + win1 + " games to " + win2 + "!!!\n";

        if (win1<win2) zprint = rps2.getName() + " wins " + win2 + " games to " + win1 + "!!!\n";

        if (win1==win2) { zprint = "Both players won " + win1 + " games! The match was a tie\n"; } else { zprint += "There were " + (numGames - win1 - win2) + " ties\n"; }

        System.out.print(zprint);

    }

}

New entrants will be like this:

public int nameOfAlgorithmint[] a, int[] b, int i)

{

// body here

}

and will be inserted into the program after the algorithm method for test3

All algorithms must return one of these three integers: 0 (ROCK), 1 (PAPER), 2 (SCISSORS)!!!

good luck and post here with remarks, questions, etc.... let's get a signup list?

1) Unreality

2) ...

should we shoot for eight people?

REMEMBER YOU DONT NEED TO KNOW PROGRAMMING... you just need to make a killer algorithm that's a whiz at R/P/S :) I can write the actual code for it for you if you want!

Link to post
Share on other sites
  • Answers 257
  • Created
  • Last Reply

Top Posters For This Question

Recommended Posts

  • 0

yeah it's not hard... I'd recommend posting here to sign up but you don't others to design their algorithms against yours, so you can just PM them to me. I've already made mine (I'll post it here openly in a second) so don't worry about me cheating :P


public int hawk(int[] a, int[] b, int i)

    {

        if (i==0) return (int)Math.pow(2,21) % 3;

        int[] num = new int[3];

        for (int z=0; z<i; z++) { num[b[z]]++; }

        int x=0;

        if (num[0] > num[1]) { x = 0 ; } else if (num[1] > num[0]) { x = 1 ; } else { x = num[x] % 2 ; }

        if (num[2] > num[x]) x = 2;

        return (x+1)%3;

    }

all algorithms will start with public int hawk(int[] a, int[] b, int i) { //// BODY HERE } remember, a is an array of the moves YOU'VE made, b is an array of the moves THE ENEMY's made. i is what round # it is. 0 means first round, then 1, then 2, 3, 4, etc. You don't need to know programming!!! I will make it for you based on your description! For example, to produce 'hawk', you could've done this for your algorithm: * if it's the first round, just do something pseudorandom (i did (2^21) mod 3, albeit not very random but it works as long as I don't check what that result is haha) * for all other rounds, find out what the opponent has used most, then use the move that beats that move that's what 'hawk' is. The only other extra thing needed would be how ties are handled and other minute things [for example, in hawk, if the enemy does rock and paper equally, which one 'hawk' picks to defeat is pretty much random based on the local environment. Then if all three tie, that same random result is used. If rock and scissors tie, or if paper and scissors tie, it will go with the rock or the paper to beat, not scissors.] for those test programs I put above, here is the code and beneath that, an algorithm description that would show me how to make said code for you:

~~~~~~~

what is this "%3"?

The % stands for modulus and means remainder-after-division.

Any number 'mod 3' will produce an integer less than three - ie, 0, 1, or 2 (ROCK/PAPER/SCISSORS)

0 mod 3 = 0

1 mod 3 = 1

2 mod 3 = 2

3 mod 3 = 0

4 mod 3 = 1

5 mod 3 = 2

6 mod 3 = 0

7 mod 3 = 1

8 mod 3 = 2

9 mod 3 = 0

10 mod 3 = 1

11 mod 3 = 2

12 mod 3 = 0

13 mod 3 = 1

14 mod 3 = 2

15 mod 3 = 0

16 mod 3 = 1

17 mod 3 = 2

[etc.]

That can be a helpful tool :thumbsup: Beware of some tricky behavior when negative numbers are involved (http://mindprod.com/jgloss/modulus.html#SIGNRULES) but if you're describing to me how you want your algorithm to work I'll take care of that stuff for you :)

public int test1(int[] a, int[] b, int i)

    {

        if (i==0) return 2;

        return b[i-1];

    }
* test1 * if first round, use scissors * for subsequent rounds, use whatever the opponent used last round (essentially the molehill-for-tat strategy)
  public int test2(int[] a, int[] b, int i)

    {

        return i % 3;

    }
* test2 * very simple. Plays in a cyclic order = rock paper scissors rock paper scissors rock paper scissors etc. etc.
 public int test3(int[] a, int[] b, int i)

    {

        int sum = 0;

        for (int z=0; z<i; z++)

        {

            sum += (a[z] + b[z]);

        }

        sum %= 3;

        return sum;

    }

* test3

* uses rock as 0, paper as 1, scissors as 2; adds up all previous moves by both players into a single sum. Then modulo 3 to get either 0 (rock), 1 (paper) or 2 (scissors) to play. You could say that this one attempts no strategy or meta-algorithm-ness or anything, it just tries to be pseudorandom.

Link to post
Share on other sites
  • 0

you really can't do any better than random, so, no algorithm will be particularly better than another.

for example i might be able to write an algorithm that counters hawk, but then,

it would most likely be very bad at taking on any other algorithm.

it just comes down to how random is random.

none the less, this kinda sounds fun.

Link to post
Share on other sites
  • 0

you really can't do any better than random, so, no algorithm will be particularly better than another.

for example i might be able to write an algorithm that counters hawk, but then,

it would most likely be very bad at taking on any other algorithm.

it just comes down to how random is random.

none the less, this kinda sounds fun.

I think that what you said (about randomness being optimal) is only correct for humans (and non-tournament-serious humans at that), but part of this exercise is finding out, eh? Furthermore, a random game will only get you to win 1/3 of the time (the other thirds are losing and tying). Surely that can be further optimized. Also, when ALL the players are deterministic non-random algorithms, there's something to be said for strategy :)

At the very least it will be interesting to see what people come up with ;D

Link to post
Share on other sites
  • 0

Thanks for participating Phillip, your algorithm looks great :D (I converted your description to java and sent it back to you, let me know how you like it ;D). I think it will hold up its own pretty well

Also I'm thinking we should have a Round-Robin tournament style, where everyone plays everyone once. numGames = 50 I think is still a good number

Link to post
Share on other sites
  • 0

I'm trying to recall the algorithm I designed in my dream earlier.. so I'll get back to you on this, but count me in. (Sick people have wacky dreams, I'm evidence of this. If anyone wants to hear a story about gladiators, love and betrayal, running, a six year old freshman, and bizarre methods of breaking into Universal, hit me up. My dreams are... weird.)

Link to post
Share on other sites
  • 0

izzy submitted what appears to be a very clever algorithm... it was a bit of a challenge to program, but fun :D She also suggested that I write a completely random program to see how it matches up, so I did... [programs we make are not allowed to be random, of course]

1) Unreality

2) phillip1882

3) Izzy

4) Random Opponent

5) ...

let's see who else we get. I know a few other people that are interested ;D PM your friends/BD friends and get them over here!

Link to post
Share on other sites
  • 0

Hmm.. You know, I'm sort of convinced that the random program will win this. To be known implies that it can be beaten. I can easily (have Unreality) program an algorithm that beats Unreality's Hawk, (1: random 2-all: use whatever beats the thing that beats the thing I've used most), this can be done for my algorithm, and really any other one that can be created - unless it's can't be predicted - random. Once we have are battle, and all program are known, programming one that beats all the ones we have so far shouldn't be *that* hard. Realistically speaking, what we're creating can be used in tournaments. But random, for it's 1/3 success rate, just can't be beaten.

edit: Unless you always know who you're facing beforehand. Then you could use some sort of clone function (50%) victory, or just do the opposite of what they'll do (100%).

Hmm. Unless we can trick other programs into doing what we want them to do? (Which is sort of like the beginning of mine..)

Edited by Izzy
Link to post
Share on other sites
  • 0

yeah it lies in how the algorithm uses and interprets all the information it receives through both arrays and the 'i' variable. That makes algorithm vs. algorithm interesting, but not algorithm vs. random, which is why originally I had not used that, I don't know why I caved in :D

1) Unreality

2) phillip1882

3) Izzy

4) ...

It's only interesting when all algorithms have the same restriction, because it's about how well they use the data given to them to pre-empt the opponent's next move.

Granted you could make a program that has a random array 0,1,1,0,2,1,0,etc and then use the i variable to sample the next number from it, but that would be the same as random and thus cheating (unless there was some pattern to the numbers that could be calculated from 'i' without needing the array)

Link to post
Share on other sites
  • 0

yeah it lies in how the algorithm uses and interprets all the information it receives through both arrays and the 'i' variable. That makes algorithm vs. algorithm interesting, but not algorithm vs. random, which is why originally I had not used that, I don't know why I caved in :D

1) Unreality

2) phillip1882

3) Izzy

4) ...

It's only interesting when all algorithms have the same restriction, because it's about how well they use the data given to them to pre-empt the opponent's next move.

Granted you could make a program that has a random array 0,1,1,0,2,1,0,etc and then use the i variable to sample the next number from it, but that would be the same as random and thus cheating (unless there was some pattern to the numbers that could be calculated from 'i' without needing the array)

1) Unreality

2) phillip1882

3) Izzy

4) dawh

I guess you can pencil me in. I have a few questions (and a few suggestions) that I sent you in a PM. Not sure exactly when I'll have time for this, but I'll try to come up with something soon. Though it might not be good to "play" against a random competitor, it might still be interesting to see how the algorithms compare against it as some sort of "control" test. Chances are it would completely ruin people's methods for winning, but it might show something very interesting when it's all said and done.

Link to post
Share on other sites
  • 0

alright I think we should see if we can get at least one or two more people... I know there are more people out there interested, PM your buddies on here and see who we can come up with? :thumbsup:

1) Unreality

2) phillip1882

3) Izzy

4) dawh

also dawh has helped me find a few bugs in my coding, thanks man! :) And i've made other changes too, though I think I'm going to rewrite it all just as an exercise (and to make sure they give the same results :wacko: haha). I'll keep everyone's functions that they submitted (or that I wrote according to their algorithm specifications) the same, don't worry

Link to post
Share on other sites
  • 0

This is frustrating... not only are the spoilers not working, but spaces aren't kept!

int fib1 = 0;

int fib2 = 1;

int roll = 0;

while(rounds)

{

____if ((i+1)%fib2 == 0)

____{

________fib2 = fib2 + fib1;

________fib1 = fib2 - fib1;

________roll = roll%3 + 1;

____}

____if (i%2 == 0)

________return roll;

____else

________return ((roll + b)%3);

}

Btw, I also think Random will win this

Edited by rookie1ja
spoiler code corrected, spaces can be done in code tags
Link to post
Share on other sites
  • 0

i rewrote the code and made it way better, check it out:


import java.util.Scanner;

public class rps

{


public static final int ROCK = 0;

public static final int PAPER = 1;

public static final int SCISSORS = 2;

public static final int ROUNDS = 50;


   public static int rpsgo(int algoNum, int i, int[] a, int[] b)

   {

        if (algoNum==0) // hawk

        {

            if (i==0) return (int)Math.pow(2,21) % 3;

            int[] num = new int[3];

            for (int z=0; z<i; z++) { num[b[z]]++; }

            int x=0;

            if (num[0] > num[1]) { x = 0 ; } else if (num[1] > num[0]) { x = 1 ; } else { x = num[x] % 2 ; }

            if (num[2] > num[x]) x = 2;

            return (x+1)%3;

        }

        else if (algoNum==1) // test1

        {

            if (i==0) return SCISSORS;

            return b[i-1];

        }

        else if (algoNum==2) // test2

        {

            return i % 3;

        }

        else if (algoNum==3) // test3

        {

            int sum = 0;

            for (int z=0; z<i; z++)

            {

                sum += (a[z] + b[z]);

            }

            sum %= 3;

            return sum;

        }

        /*else if (algoNum==4) // izzy

        {


        }

        else if (algoNum==5) // phil

        {



        }

        else if (algoNum==6) // backatyou

        {


        }

        else if (algoNum==7) // dnoob

        {


        }*/


        else return ROCK;

    }


    public static String conv(int yeah)

    {

        if (yeah==ROCK) return "rock";

        if (yeah==PAPER) return "paper";

        if (yeah==SCISSORS) return "scissors";

        return "you've got a problem";

    }


   public static void main(String[] args)

   {

           Scanner inp = new Scanner(System.in);

           String[] names = { "hawk", "test1", "test2", "test3", "izzy", "phil", "backatyou", "dnoob" };

           System.out.println("Welcome to R/P/S!");

           for (int j=0; j<names.length; j++) { System.out.println(j + " (" + names[j] + ")");}

           System.out.print("First Algorithm: ");

           int algo1 = inp.nextInt();

           System.out.print("Second Algorithm: ");

           int algo2 = inp.nextInt();


           System.out.print("\n\n"+names[algo1]+" vs "+names[algo2]+"\n\n");


           int[] ar1 = new int[ROUNDS];

           int[] ar2 = new int[ROUNDS];


           int[] wins = new int[ROUNDS];


           for (int k=0; k<ROUNDS; k++)

           {

                   ar1[k] = rpsgo(algo1, k, ar1, ar2);

                   ar2[k] = rpsgo(algo2, k, ar2, ar1);

                   wins[k] = ( 3 + ar1[k] - ar2[k] ) % 3;

                   // 0 -> tie

                   // 1 -> one wins

                   // 2 -> two wins

           }


           int oneWins=0; int twoWins=0;

           for (int l=0; l<ROUNDS; l++)

           {

               System.out.println(conv(ar1[l]) + " vs " + conv(ar2[l]));

               if (wins[l]==1) { oneWins++; }

               if (wins[l]==2) { twoWins++; }

            }

            int ties = ROUNDS - oneWins - twoWins; String msg;

            if (oneWins > twoWins) msg = names[algo1]+" wins!!!";

            else if (twoWins > oneWins) msg = names[algo2]+" wins!!!";

            else msg = "It was a tie!!!";

            System.out.println("\n"+names[algo1]+" won "+oneWins+" games and "+names[algo2]+" won " +twoWins+ " ~ there were " + ties + " ties");

            System.out.println(msg);

        }

}

darth noob is this what you mean with "while(rounds)"?

else if (algoNum==7) // dnoob

        {

int fib1 = 0;

int fib2 = 1;

int roll = 0;

for(int z=0; z<i; z++)

{

if ((i+1)%fib2 == 0)

{

fib2 = fib2 + fib1;

fib1 = fib2 - fib1;

roll = roll%3 + 1;

}

if (i%2 == 0) return roll; 

else return ((roll + b[i])%3);

}

        }

I think that code has the potential to return 3, we'll see what it does if you confirm that's what you want :)

1) Unreality

2) phillip1882

3) Izzy

4) dawh

5) darthnoob

I dont have time now but later I'll copy over the rest of the programs and put dawh's in,etc

Link to post
Share on other sites
  • 0

darth noob is this what you mean with "while(rounds)"?


else if (algoNum==7) // dnoob

        {

int fib1 = 0;

int fib2 = 1;

int roll = 0;

for(int z=0; z<i; z++)

{

if ((i+1)%fib2 == 0)

{

fib2 = fib2 + fib1;

fib1 = fib2 - fib1;

roll = roll%3 + 1;

}

if (i%2 == 0) return roll; 

else return ((roll + b[i])%3);

}

        }

I think that code has the potential to return 3, we'll see what it does if you confirm that's what you want :)

1) Unreality

2) phillip1882

3) Izzy

4) dawh

5) darthnoob

I dont have time now but later I'll copy over the rest of the programs and put dawh's in,etc

I figured you already had a way to loop the rounds. While(round) is just me saying "this is what you loop for every round" and to make sure the scope of the int variables I declared were out side of the looping

Link to post
Share on other sites
  • 0

dathnoob: you have it like this:


            int fib1 = 0;

            int fib2 = 1;

            int roll = 0;

            for(int z=0; z<i; z++)

            {

                if ((i+1)%fib2 == 0)

                {

                    fib2 = fib2 + fib1;

                    fib1 = fib2 - fib1;

                    roll = roll%3 + 1;

                }

                if (i%2 == 0) return roll; 

                else return ((roll + b[i])%3);

            }

with the while(rounds) thing encapsulating your whole code. Thus the program will return something after only the very first iteration. Did you mean this:

           int fib1 = 0;

            int fib2 = 1;

            int roll = 0;

            for(int z=0; z<i; z++)

            {

                if ((i+1)%fib2 == 0)

                {

                    fib2 = fib2 + fib1;

                    fib1 = fib2 - fib1;

                    roll = roll%3 + 1;

                }

            }

            if (i%2 == 0) return roll; 

            else return ((roll + b[i])%3);

?

And I just have to put dawh's code in and it will be ready for some tournament-ing

Link to post
Share on other sites
  • 0

the problem is that you can't have variables like that that continue over multiple rounds - your only data each iteration is from the moves you've done so far, the moves the other person has done so far, and the round number (i). This is why it's easiest for people to just tell me what they want their algorithm to do and I'll write the necessary code :)

Link to post
Share on other sites
  • 0

I just realized my b should probably be b[i-1]

EDIT: then declare some data fields!!! pleeease!

public int dnoobFib1 and so on!

EDIT2: but if you don't want to I can rewrite it so that it'll be the same algorithm

Edited by DarthNoob
Link to post
Share on other sites
  • 0

actually... I don't think I feel like programming that. So here's what I want my algorithm to be:

I do rock once

I do paper once

I do scissors twice

I do rock 3x

I do paper 5x

I do scissors 8x

I do rock 13x

I do paper 21x

I do scissors 34x

and so on

(I realize that's more than 50 rounds)

Get the pattern? Fibonacci sequence.

However, there's a twist thrown in: every other round you add the enemy's last roll to my current one. So say I'm in the spot I'm supposed to do scissors 8x, but it's an odd number round, and the enemy did scissors last round.

2 + 2 = 4

4%3 = 1

Instead of doing scissors, I do paper.

Now that I think on it, though, I might prefer this: instead of adding the enemy's last roll, add the enemy's mode, i.e. the enemy's most common roll up to that point

EDIT: just saw your post, ha. Wonder if I shoulda pm'd

Edited by DarthNoob
Link to post
Share on other sites
  • 0

the problem is that you can't have variables like that that continue over multiple rounds - your only data each iteration is from the moves you've done so far, the moves the other person has done so far, and the round number (i). This is why it's easiest for people to just tell me what they want their algorithm to do and I'll write the necessary code :)

I doubt it would have been easier for you to code my algorithm... :ph34r: (Largely because explaining it effectively would have been a pain. :rolleyes: )

I just realized my b should probably be b[i-1]

EDIT: then declare some data fields!!! pleeease!

public int dnoobFib1 and so on!

EDIT2: but if you don't want to I can rewrite it so that it'll be the same algorithm

I definitely see that you would want b[i-1]. Data fields would solve your problem, but I'm not sure you need them. Your algorithm might work with unreality's modification. Since there's no state data being stored the way it is now, by going through the loop, you would always get to the next iteration that you would have been at if you had stored the values in fields. It just recalculates the data each round instead of storing it. Not the most efficient way, but since these aren't the most intensive problems, it shouldn't be a big issue.

If you've got a place to run unreality's program code on your computer, you could run your algorithm against one (or more) of the test programs and PM unreality your results. Then he can see if his modified version is getting the same answers.

If unreality adds the fields, then I don't see any reason for that loop to exist. You are only going to do it once, so the loop is just confusing. The loop is only necessary if you have to recalculate the values from the beginning each time.

Hmm, it seems some of this may be moot now, but in case it's still useful to someone, here it is! :wacko:

Link to post
Share on other sites
  • 0

starting on it now... I have an idea of how to use a few mathematical tricks to make the code pretty light

but just to clarify, the pattern stays rigid, just every other round it gets distorted and the other set of rounds in between that is normal and fixed according to the pattern?

Edited by unreality
Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    No registered users viewing this page.


×
×
  • Create New...