text:
Prisoner's Dilemma v.2 - Battle Royale
In this question, a game was devised in which players would face each other off pair by pair in the Prisoner's Dilemma, to determine which iterative strategy scored the highest against others.
In this question, I devised a way for multiple people to play the Prisoners' Dilemma against each other all at the same time. In this variation, the payoff matrix is unnecessary, with each outcome between each pair of two players being the sum of two functionally independent decisions.
Your task is to build an AI to play this symmetric, generalized version of the multiplayer Prisoner's Dilemma that will achieve the highest score possible.

Rules of the Game
In each round of this multiplayer, multi-round Prisoner's Dilemma, a player A can decide to "take 1" from some other player B. In this circumstance, A's score increases by 1, while B's score decreases by 2. This decision is allowed to happen between each ordered pair of players.
This is the only decision made for each player – either to "take 1" or not to "take 1" from each other player, which are homologous to defection and cooperation respectively. The effective payoff matrix between two players P1 and P2 looks as follows:
  P1/P2     P1 Take1   P1 Don't
P2 Take1     -1/-1      -2/+1
P2 Don't     +1/-2       0/ 0

Tournament Procedure
The game will consist of P * 25 rounds, where P is the number of participating players. All players start with a score of 0. Each round will consist of the following procedure:
At the beginning of a round, each program will be given a history of the previous rounds from standard input, in the following format:

One line containing 3 numbers, P, D, and N.

P is the total number of players in the game. Each player is randomly assigned an ID number from 1 to P at the beginning of the game.
D is the ID of the current player.
N is the number of rounds that have been played.

N lines, each line representing the outcomes of a round. On line k of N, there will be some number n_k of ordered pairs (a, b), separated by spaces, which represent that the player with ID a "took 1" from the player with ID b in that round.
A uniformly random number R from 0 to 18446744073709551615 (264 - 1), to act as a pseudorandom seed. These numbers will be read from a pre-generated file, which will be released at the end of the tournament so that people can verify the results for themselves.
One extra line that represents some form of state to be read into your program, if your program produced such an output in the previous round. At the beginning of the game, this line will always be empty. This line will not be modified by either the scoring code or other programs.

Each program will then use its strategy to produce the following to standard output:

A list of K numbers, which are the IDs of the programs it will "take 1" from this round. An empty output means it will do nothing.
Optionally, one extra line representing some form of state to pass on to later rounds. This exact line will be fed back to the program in the next round.

Below is an example input for the beginning of the game for a player of ID 3 in a 4-player game:
4 3 0
4696634734863777023

Below is an example input for the same game with a few rounds already played:
4 3 2
(1, 2) (1, 3) (1, 4) (4, 2)
(1, 3) (2, 1) (2, 4) (3, 1) (4, 1)
4675881156406346380

Each program will be fed exactly the same input for a round except for the ID number D which is unique to each program.
Below is an example output in which player 3 takes 1 from everybody else:
1 2 4

At the end of all the required rounds, the player with the highest final score will be the winner.

Timeline
The coding for this tournament will last for a total of 7 days. The deadline for submissions is 2014-05-09 00:00 UTC.
Do not post actual programs before this date – post the SHA256 hash of the source code of your program as a commitment. You may change this hash any time before the deadline, but commitments posted after the deadline will not be accepted for judgment. (Please use base 64 notation for your hashes, as my verification program spits out base 64 and it's a more compact notation.)
After the deadline is over, you will have 1 day (until 2014-05-10 00:00 UTC) to post the actual source code of your program for your submission. If the SHA256 hash of your posted source code does not match any hash that you posted before the deadline, your code will not be accepted into the tournament.
After this, I will download all the submissions onto my own computer, and run all the tournament entries in this battle royale, hopefully posting the results within 2 days from then, by 2014-05-12 00:00 UTC.
I will accept the answer with the highest score, and award a bounty of +100 to that answer if its final score is greater than 0.
After the tournament is over, I will post the random seed file used to run the competition, and people may start posting other solutions trying to top the ones used in the tournament. However, they will not count for acceptance or the bounty.
The Host Machine
I will be running these solutions on a virtual machine on my computer. This virtual machine will run Ubuntu Linux 14.04, with 2 gigabytes of RAM. My base machine has an Intel i7-2600K processor running at 3.40 GHz.
Requirements
Your program must be written in a language for which a compiler or interpreter that will compile your program exists and is readily available for the latest version of Ubuntu Linux, so that I can run all the submissions and judge them in a virtual machine.
Your program must not take more than 2.000 seconds to run each round. If your program runs out of time or produces an error, its output will be considered empty for that round.
Your program must be deterministic; that is, it must always return the same output for the same input. Pseudorandom solutions are allowed; however, their randomness must depend on the random seed given to it as input and nothing else. The seed file was generated using Python's os.urandom. It contains a total of 500 lines (more will be generated if necessary), and its SHA256 hash is K+ics+sFq82lgiLanEnL/PABQKnn7rDAGmO48oiYxZk=. It will be uploaded here once the tournament is over.

Plants
To kick things off, there will be four "plants", representing initial naïve strategies. These will be playing in the tournament along with your submissions. However, in the unlikely case that one of them wins, the highest score obtained by a player other than a plant will be considered the winner.
To calculate the hash of each plant's file, replace every group of 4 spaces with a tab, since the formatter here doesn't seem to like tab characters.
The Lazy — never does anything.
n1bnYdeb/bNDBKASWGywTRa0Ne9hMAkal3AuVZJgovI=
pass

The Greedy — always takes 1 from everybody else.
+k0L8NF27b8+Xf50quRaZFFuflZhZuTCQOR5t5b0nMI=
import sys

line1 = sys.stdin.readline()
n = [int(i) for i in line1.split()]
for i in range(n[0]):
    if i+1 != n[1]:
        print i+1,
print

The Wrathful — takes 1 from everybody else on the first round, and takes 1 from everybody who took 1 from it the previous round afterwards.
Ya2dIv8TCh0zWzRfzUIdFKWj1DF9GXWhbq/uN7+CzrY=
import sys
import re

line1 = [int(i) for i in sys.stdin.readline().split()]

players = line1[0]
pid = line1[1]
rounds = line1[2]

lines = []

if rounds == 0:
    for i in range(players):
        if i+1 != pid:
            print i+1,
    print
else:
    for i in range(rounds):
        lines.append(sys.stdin.readline())
    lastline = lines[-1]
    takes = re.findall(r'\([0-9]+, [0-9]+\)', lastline)
    for take in takes:
        sides = [int(i) for i in re.findall(r'[0-9]+', take)]
        if sides[1] == pid:
            print sides[0],
    print

The Envious — takes 1 from the 50% of players with the current highest score excluding itself, rounding down.
YhLgqrz1Cm2pEcFlsiIL4b4MX9QiTxuIOBJF+wvukNk=
import sys
import re

line1 = [int(i) for i in sys.stdin.readline().split()]

players = line1[0]
pid = line1[1]
rounds = line1[2]

lines = []
scores = [0] * players

if rounds == 0:
    for i in range(players):
        if i+1 != pid:
            print i+1,
    print
else:
    for i in range(rounds):
        takes = re.findall(r'\([0-9]+, [0-9]+\)', sys.stdin.readline())
        for take in takes:
            sides = [int(i) for i in re.findall(r'[0-9]+', take)]
            scores[sides[0] - 1] += 1
            scores[sides[1] - 1] -= 2
    score_pairs = [(i+1, scores[i]) for i in range(players)]
    score_pairs.sort(key=lambda x:(x[1], x[0]))
    score_pairs.reverse()
    taken = 0
    j = 0
    while taken < (players) / 2:
        if score_pairs[j][0] != pid:
            print score_pairs[j][0],
            taken += 1
        j += 1

In a tournament of 100 rounds just amongst these four, they receive scores of:
Lazy: -204
Greedy: -100
Wrathful: -199
Envious: -199

Judging Program
I've posted the judge program I'll be using at Github. Download it and test it out. (And maybe fix a bug or two if you find one. :P)
It doesn't have compilation options for anything other than Python at the moment. I'll be including those later - if people could contribute compilation or interpretation scripts for other languages, I'd be much obliged.

Phase 2: Source Code Submission
I've posted a new branch tournament to the Github repository for the contest, containing the pd_rand file and other plant entries. You can either post your source code here or submit it to that branch as a pull request.
The order of the contestants will be as follows:
'begrudger'
'regular'
'patient'
'lazy'
'backstab'
'bully'
'lunatic'
'envious'
'titfortat'
'greedy'
'wrathful'
'judge'
'onepercent'

Final Scores
The output of my testing program:
Final scores:
begrudger -2862
regular -204
patient -994
lazy -2886
backstab -1311
bully -1393
lunatic -1539
envious -2448
titfortat -985
greedy -724
wrathful -1478
judge -365
onepercent -1921

Rankings:
 1. regular      -204
 2. judge        -365
 3. greedy       -724
 4. titfortat    -985
 5. patient      -994
 6. backstab    -1311
 7. bully       -1393
 8. wrathful    -1478
 9. lunatic     -1539
10. onepercent  -1921
11. envious     -2448
12. begrudger   -2862
13. lazy        -2886

So it turns out that the winner is indeed a player - it's The Regular, with -204 points!
Unfortunately, its score wasn't positive, but we can hardly expect that in a simulation of the Iterated Prisoner's Dilemma where everybody's playing to win.
Some surprising results (at least that I thought were surprising):

The Greedy scored more than Tit for Tat, and in fact, generally higher than most scorers at all.
The Judge, which was meant to be a sort of "morality enforcer" character (it basically took 1 from whoever had taken 1 from anybody an above-average number of times) ended up scoring rather high, while in simulation testing, it would actually get a rather low score.

And others that (I thought) weren't so surprising:

The Patient scored a full 484 points more than The Wrathful. It really pays to cooperate that first time.
One Percent very quickly had almost nobody to kick while they were down. Seems that the 1% is only able to stay that way because they have more players in the game.

Anyway, now that the tournament is over, feel free to post as many extra players as you'd like, and test around with them using the judge program.

I've named all the plants after vices, since I expect that this competition will be more vicious than the previous one, and I thought I'd theme the plants' names to reflect that.

Would posting the source to the control program and/or plants hurt anything? We know what they do anyway, and I'd prefer to be able to test against something without writing five extra programs.

I suppose not. Lemme edit them in right now.

Can we have a little more time to submit the actual code? If I'll be busy for those twenty-four hours, am I disqualified?

Should the output be terminated with \n, \0, something else, nothing, or does it matter?

@ypnypn: When you submit your code, email your source code to me and I'll edit it into your answer for you during the code-submission period.

@Geobits: The terminated output doesn't matter, as long as it's a list of numbers separated by spaces.

May I only enter a single program? 2) Will my program get the same value of R in each round? 3) Is the official scorer's code available, or do I have to write my own for testing? 4) Does "some other player B" mean I cannot take 1 from myself?

@PleaseStand 1) To prevent collusion between solutions by the same user, each contestant may only enter one program for the actual tournament. However, in the after-tournament stage, feel free to post as many alternate solutions as you want, as long as they are distinct strategies.  2) Your program will get a different random value of R each round, but each program will get the same value of R for that round.  3) I haven't written the official scorer's code yet, so you'll have to write your own until I get that done.

If you take 1 from yourself, the only result is that your own score decreases by 1, so I'm not sure why you'd want to do that. But the answer is no, you cannot take 1 from yourself.

So because R changes each round, if my program were to choose one of several strategies at random, it would have to "forget" which one it picked, instead having to infer that from the history?

I've edited in something that allows you to pass one line of data onto the next round. Does that solve your problem?

There are going to be a lot of upvotes for answers once the deadline passes, aren't there?

Devil's advocate question: suppose I write a solution which seeds it's PRNG from R during the first round but passes the state of the PRNG forward from round to round (rather than re-seeding with the new R). Still "deterministic" under the rules?

@dmckee: Yes, that is valid, as it will still always return the same output for the same input. The person who suggested that rule suggested it for exactly the concern you mentioned, so it is definitely allowed.

@Kevin: Yeah, most likely.

I don't understand. Is there some sort of penalty for everyone taking 1 all the time? Wouldn't it be the most advantageous to always take 1?

@ZoveGames It would be, but then everybody would use that strategy and no points would ever be gained.

How would we test our programs (say, against the plants)?

I'm writing a judge program for that right now. Sit tight.

@JoeZ. Kk. Working on my answer now.

When will player ID assignments (which could potentially affect program behavior) be posted? At 2014-05-09 00:00 UTC (the beginning of the source code posting window)?

@PleaseStand Yes. If I do it before then, the number of entrants might change. (And if I do it after then, I might accidentally run the tests more than once and bias myself toward a certain result.)

My concern is then with "If the SHA256 hash of your posted source code does not match any hash that you posted before the deadline [...]". The hash should match the last one posted before the deadline so the player who posts his or her source code last cannot choose which program to post based on the player ID assignments (e.g. one that assumes Tit-for-tat has ID 1).

I did the "any hash" thing so that people who discover errors in their latest revision could revert to an earlier one.

Also, remember that all edits are logged, and they need to be in order to count. If a person posts 30 edits within 5 minutes of each other in order to have a choice in IDs, 1) they won't all show up in the edit history because of the grace period, and 2) it would definitely be very suspicious and I'd probably ask them about what those 30 edits in a row were all about.

@JoeZ. Is it okay to have multiple entries here?

@Trimsty No.

@JoeZ. Oh, okay, sorry, didn't see that comment for some reason.

It's alright. You can post all the alternate entries you want after the tournament is over, by the way.

@JoeZ. Cool. Thanks.

I don't understand. How can The Greedy lose under the game rules?

@justhalf The Greedy doesn't maximize damage to the opponent, or try to mess with other AIs. For instance, a game with only Greedy bots can never gain points.

How can greedy not maximizing damage? If we take from other player, the other player can only get -1 or -2, while if we don't take, the other player can get 1 or 0. Obviously taking 1 from other player will maximize the damage. And so Greedy will never lose. And it will almost always win, unless all the opponent are also Greedy, like you said.

@justhalf A critical part of this competition is that you're not actually allowed to submit a Greedy. You have to find something else that works.

@Trimsty It doesn't look like anyone did submit one, but I don't see that in the rules. I thought about doing it myself, but went with something else out of curiosity's sake. I agree that being Greedy is probably the best overall strategy if your goal is to look out for yourself. We don't care about the overall point total for this challenge.

@Geobits I don't see how people submitting duplicates would be allowed, the goal is to make an ai, not choose one :P

@Trimsty When the challenge first went up, the code for the plants was not shown. Through the entire coding phase, we could not see other answers. Dupes could have happened purely by accident by choosing the very obvious greedy strategy.

Will my "Sort the set of victims and remove duplicates" change to the scorer be used in the tournament?

Actually I don't understand this challenge as a challenge. It's more like a playground to me  where people can submit answers to play. Because there is absolutely no dilemma here, according to the rules. Each time you "take 1", overall point will decrease by 1 and your point increase by 1. If you don't, overall point will stay the same. So if you want to maximize your points, always take 1. If you want to maximize overall points, never take 1. It's as simple as that. Unless you can come up with some interesting winning criteria, I don't see anything interesting in this challenge.

@justhalf If you've actually read any resarch on strategies in the iterated prisoner's dilemma, you'd know what you're saying is false. The Wikipedia article is a good place to start.

" If the game is played exactly N times and both players know this, then it is always game theoretically optimal to defect in all rounds.". So it proofs my assertion?

That is the Nash equilibrium. The optimal strategy in practice is different.

The Regular
The version of this entry I have chosen for the tournament (SHA-256: ggeo+G2psAnLAevepmUlGIX6uqD0MbD1aQxkcys64oc=) uses Joey's "Random sucker" strategy (albeit with a minor and likely insignificant change), which came in second place in the last contest. Unfortunately, a newer, more effective version submitted just 3 minutes 25 seconds before the deadline has a serious bug, so it could not be used. Nevertheless, this version still fares relatively well.
<?php

$secretKey = '95CFE71F76CF4CD2';
$hashOutput = '';
$hashSeq = 0;
$hashIndex = 64;

function psRand($min = null, $max = null) {
    global $secretKey, $state, $hashOutput, $hashSeq, $hashIndex;
    if ($hashIndex > 56) {
        $hashOutput = hash_hmac('sha256', ++$hashSeq . ' ' . $state['rand'], $secretKey);
        $hashIndex = 0;
    }

    $num = (int)(hexdec(substr($hashOutput, $hashIndex, 8)) / 2);
    $hashIndex += 8;

    return $min === null ? $num : (int)($min + $num * ($max - $min + 1) / 2147483648);
}

$line = fgets(STDIN);
sscanf($line, "%d %d %d", $numPlayers, $myPlayerId, $roundsPlayed);
$roundsCount = 25 * $numPlayers;
$roundsRemaining = $roundsCount - $roundsPlayed - 1;

$betrayalCount = array_fill(1, $numPlayers, 0);
for ($round = 0; $round < $roundsPlayed; ++$round) {
    $line = fgets(STDIN);
    preg_match_all('/\((\d+), (\d+)\)/', $line, $matches, PREG_SET_ORDER);
    foreach ($matches as $m) {
        $defector = (int)$m[1];
        $victim = (int)$m[2];
        if ($victim === $myPlayerId) {
            ++$betrayalCount[$defector];
        }
    }
}

$hashOutput = rtrim(fgets(STDIN), "\n");
$state = unserialize(rtrim(fgets(STDIN), "\n"));
if (!$state) {
    $state = ['rand' => ''];
}

$state['rand'] = hash_hmac('sha256', $state['rand'] . $line, $secretKey);
$victims = [];

if ($roundsPlayed > 1) {
    for ($other = 1; $other <= $numPlayers; ++$other) {
        if ( $other === $myPlayerId) {
            continue;
        }

        if ($betrayalCount[$other] > 7 || psRand() % 1024 < 32 || !$roundsRemaining ) {
            $victims[] = $other;
        }
    }
}

echo implode(' ', $victims), "\n", serialize($state), "\n";

The buggy version has an SHA-256 hash of 2hNVloFt9W7/uA5aQXg+naG9o6WNmrZzRf9VsQNTMwo=:
<?php

$secretKey = '95CFE71F76CF4CD2';
$hashOutput = '';
$hashSeq = 0;
$hashIndex = 64;

function psRand($min = null, $max = null) {
    global $secretKey, $state, $hashOutput, $hashSeq, $hashIndex;
    if ($hashIndex > 56) {
        $hashOutput = hash_hmac('sha256', ++$hashSeq . ' ' . $state['rand'], $secretKey);
        $hashIndex = 0;
    }

    $num = (int)(hexdec(substr($hashOutput, $hashIndex, 8)) / 2);
    $hashIndex += 8;

    return $min === null ? $num : (int)($min + $num * ($max - $min + 1) / 2147483648);
}

$line = fgets(STDIN);
sscanf($line, "%d %d %d", $numPlayers, $myPlayerId, $roundsPlayed);
$roundsCount = 25 * $numPlayers;
$roundsRemaining = $roundsCount - $roundsPlayed - 1;

$betrayalCount = array_fill(1, $numPlayers, 0);
$scoreWindow = array_fill(1, $numPlayers, array_fill(1, $numPlayers, 0));
$lastMove = array_fill(1, $numPlayers, array_fill(1, $numPlayers, false));
for ($round = 0; $round < $roundsPlayed; ++$round) {
    $line = fgets(STDIN);
    preg_match_all('/\((\d+), (\d+)\)/', $line, $matches, PREG_SET_ORDER);
    foreach ($matches as $m) {
        $defector = (int)$m[1];
        $victim = (int)$m[2];
        if ($victim === $myPlayerId) {
            ++$betrayalCount[$defector];
        }
TAB>TAB>if ($round >= $roundsPlayed - 10) {
TAB>TAB>TAB>$scoreWindow[$defector][$victim] -= 2;
TAB>TAB>TAB>$scoreWindow[$victim][$defector] += 1;
TAB>TAB>}
TAB>TAB>if ($round === $roundsPlayed - 1) {
TAB>TAB>TAB>$lastMove[$defector][$victim] = true;
TAB>TAB>}
    }
}

$line .= fgets(STDIN);
$state = unserialize(rtrim(fgets(STDIN), "\n"));
if (!$state) {
    $state = ['rand' => '', 'copying' => array_fill(1, $numPlayers, 0)];
}

$state['rand'] = hash_hmac('sha256', $state['rand'] . $line, $secretKey);
$victims = [];

if ($roundsPlayed > 1) {
    for ($other = 1; $other <= $numPlayers; ++$other) {
        if ($other === $myPlayerId) {
            continue;
        }

TAB>TAB>if ($roundsPlayed >= 10) {
TAB>TAB>TAB>$myScore = $scoreWindow[$other][$myPlayerId];
TAB>TAB>TAB>foreach ($scoreWindow[$other] as $betterPlayer => $betterScore) {
TAB>TAB>TAB>TAB>if ($betterScore >= 0.5 * $myScore && !psRand(0, $betterPlayer)) {
TAB>TAB>TAB>TAB>TAB>$state['copying'][$other] = $betterPlayer;
TAB>TAB>TAB>TAB>}
TAB>TAB>TAB>}
TAB>TAB>}

TAB>TAB>if ($state['copying'][$other]) {
TAB>TAB>TAB>if ($lastMove[$state['copying'][$other]][$other]) {
TAB>TAB>TAB>TAB>$victims[] = $other;
TAB>TAB>TAB>}
        } elseif ($betrayalCount[$other] > 7 || psRand() % 1024 < 32 || !$roundsRemaining ) {
            $victims[] = $other;
        }
    }
}

echo implode(' ', $victims), "\n", serialize($state), "\n";

To fix it, make these replacements:

Replace $hashOutput = rtrim(fgets(STDIN), "\n"); with $line .= fgets(STDIN); (not that that really matters).
Replace if ($betterScore >= 3 * $myScore) { with if ($betterScore >= 0.5 * $myScore && !psRand(0, $betterPlayer)) { (this is what killed it).

3 minutes and 25 seconds before the deadline. I'm impressed.

Just a friendly reminder: the coding phase is over; you've got a day to post your source code. (Procedure is at the bottom of the question.)

Regardless of whether I use your old version or your new version, your program still comes out first. Congratulations!

One Percent
b61189399ae9494b333df8a71e36039f64f1d2932b838d354c688593d8f09477

Looks down on those prisoners he considers beneath him.

Simply takes from everyone that has points less than or equal to himself. The assumption is that those prisoners are less likely to take in return (or they'd have more). I don't know how good of an assumption that is, but that's what he's operating on.
Also takes from everyone on the last round. There is literally no downside to this, since nobody can revenge-steal after that.
If you have problems getting the hash because of tab/spaces from pasted code, here's a link to the file itself.
import java.io.BufferedReader;
import java.io.InputStreamReader;

class OnePercent {

    static int numPlayers;
    static int me;
    static int turn;
    static int[] values;

    public static void main(String[] args) {
        if(!readInput())
            return;
        String out = "";
        for(int i=1;i<values.length;i++){
            if(i != me && (values[i] <= values[me] || turn > (numPlayers*25-2)))
                out += i + " ";
        }
        out.trim();
        System.out.print(out);
    }

    static boolean readInput(){
        try {
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            String line = reader.readLine();
            if(line == null)
                return false;
            String[] tokens = line.split(" ");
            if(tokens.length < 3)
                return false;
            numPlayers = Integer.valueOf(tokens[0]);
            me = Integer.valueOf(tokens[1]);
            turn = Integer.valueOf(tokens[2]);
            values = new int[numPlayers+1];
            for(int i=0;i<values.length;i++)
                values[i]=0;

            for(int i=0;i<turn;i++){
                line = reader.readLine();
                line = line.replaceAll("[)]",",");
                line = line.replaceAll("[( ]", "");
                tokens = line.split(",");
                for(int j=0;j<tokens.length-1;j+=2){
                    int thief = Integer.valueOf(tokens[j]);
                    int poor = Integer.valueOf(tokens[j+1]);
                    if(thief<1||poor<1||thief>numPlayers||poor>numPlayers)
                        continue;
                    values[thief]++;
                    values[poor] -= 2;
                }
            }
            reader.close();
        } catch(Exception e) {
            return false;
        }
        return true;
    }

}

Remember you guys can continue making improvements to your solutions up until the 05-09 00:00 deadline.

Yep. If I think of something else, I will. I have a hard time believing anyone's going to claim that bounty, though. Going positive in this game would be... unusual.

Yeah, I don't expect anyone to actually reach that bounty. It would really be quite a game-theory-defying accomplishment, probably worth real money in research possibilities (A solution that works better than two people always cooperating! Imagine that!) instead of just a measly 100 reputation on Stack Exchange.

BTW, base64 version of your hash (since my verification program uses base64 notation): thGJOZrpSUszPfinHjYDn2Tx0pMrg401TGiFk9jwlHc=

Now, that being said, I've actually had a few AIs get positive scores while running my tests.

@JoeZ. With the knowledge of what the others would do, sure ;) Against unknown entries, I can't see a very reliable strategy. Outliers will be outliers, I guess.

Actually, it turns out that two of the plants got bugged. I'll have to fix them :S

Just a friendly reminder: the coding phase is over; you've got a day to post your source code. (Procedure is at the bottom of the question.)

For some reason, I get XtvwsEmk+vpmox1+t9QMjQP+rbbqOgw+DxdhseS7Fl4= when I download your file and run it through verify.py.

@JoeZ. That's weird, I'm getting a different sum for my local file now also, despite the fact that the file shows a 'modified date' of May 1. WTF. Where do we go from here? My source was the first put up, so it's not like I changed it after seeing another entry, but I understand if you feel you have to disqualify me.

Is it the same checksum I'm getting, first of all?

According to this site, yes. I don't have a handy local base64 hash tool, and was using a simple sha256sum.

I think I'll still accept it this time around, since your code's strategy doesn't appear to be anything malicious and there are too few entrants for it to matter anyway.

Tit-for-tat
9GkjtTDD2jrnMYg/LSs2osiVWxDDoSOgLCpWvuqVmSM=

Similar to Wrathful, with a few (hopefully) performance-enhancing changes.
import sys
import re

line1 = [int(i) for i in sys.stdin.readline().split()]

players = line1[0]
pid = line1[1]
rounds = line1[2]

lines = []

if rounds == 0:
    print
elif rounds == 25 * players - 1:
    for i in range(players):
        if i+1 != pid:
            print i+1,
    print
else:
    for i in range(rounds):
        lines.append(sys.stdin.readline())
    lastline = lines[-1]
    takes = re.findall(r'\([0-9]+, [0-9]+\)', lastline)
    for take in takes:
        sides = [int(i) for i in re.findall(r'[0-9]+', take)]
        if sides[1] == pid:
            print sides[0],
    print

Did you get my email address?

@Joe; yes; thanks. (I'm not certain I'll need it, but thanks for being accommodating.)

Alright, I just wanted to know so I could delete it.

Uh... Where's the program?

@luserdroog People are posting hashes of their program's source code instead of the program itself. Once the 7 days to write code are up, people will reveal their actual programs for testing.

Oh. Ok. I did finally read that in the question (after posting the comment). But there should, perhaps, be a little more text. This answer showed up in the "low quality" review queue.

Yeah, that's true. A submission should probably have a title and at least a tagline like Geobits' one up there.

BTW, base64 version of your hash (since my verification program uses base64 notation): UJzAZbQ3EASIfUs9mAwf18Pl0qoTIK01vboKGmmtO5M=

It's generally not a good idea to paste a string into a web converter as some tabs and newlines get replaced with other things. I'm personally going to use the verify.py in the pdc2014 github.

@JoeZ. Okay, I posted the results from your verify.py.

Just a friendly reminder: the coding phase is over; you've got a day to post your source code. (Procedure is at the bottom of the question.)

I can't get your hash to match. What sort of line endings and tabs did you use?

Default for newlines in Notepad++; four spaces (no tabs). Here's a link on Pastebin

Here are a few more plants that will be participating in the game. These ones are more advanced, and their source code will not be revealed until the end of the coding phase.
Just like the four plants in the question, if they manage to score higher than all other players, only the highest score achieved by an actual contestant will be considered a winner.

The Bully
29AGVpvJmDEDI5Efe/afmMJRLaJ+TpjwVcz1GkxgYZs=
Picks on people.

The Judge
yjdCQ3uQ4YKe7xAKxdTFLF4d72fD4ACYpDLwkbzdISI=
Punishes wrongdoers.

The Lunatic
m3FsRPocekCcK6GDswgnobV2CYOxX8LquChnKxrx1Wo=
Has no idea what it's doing.

The Patient
nd7Pt3bVpFnuvDVeHQ5T9EPTq7KjNraVzp/KGtI73Vo=
Never makes the first move.

If these are only plants, I see no reason to not allow them. If they are contestants that can win, I think it's only fair that you get only one entry per the comments above.

I briefly considered having my own entry, then decided that that's an unfair proposition altogether even if I only entered one more, since too many other elements of the game are under my control. So any entries I place here will all just be plants.

The reason I thought people might not have wanted them even as plants is because it represents a rather radical change in the base players that are available (and thus base strategies) that wasn't available at the beginning of the game. But if we're going by the assumption that solutions should be coded to be optimal regardless of the players inserted as plants, then I suppose I could enter them as well.

Well, entries should be coded to "optimal" (if that exists here) regardless of the players involved simply because we can't see the other answers anyway. It makes no difference if these were plants or other answers to the program, except that these can't "win". Assuming that the winner is defined as the non-plant with the highest score, I don't see how it will matter much. I say let them in.

The Begrudger
g1TXBu2EfVz/uM/RS24VeJuYMKLOaRatLxsA+DN1Mto=

Code
I will admit that I did not spend much time on this...
import sys
p, d, n, o = input().split(' ') + ['']
p, d, n = int(p), int(d), int(n)
for i in range(n):
    r = input()
    r = r[1:len(r)-1].split(') (')
    for a in r:
        if int(a.split(', ')[1]) == d and not a.split(', ')[0] in o:
            o += a.split(', ')[0] + " "

input()
print(o)

Just a friendly reminder: the coding phase is over; you've got a day to post your source code. (Procedure is at the bottom of the question.)

I tried to run this and ran into the following bug: o += a.split(', ')[0] doesn't leave space between the numbers.

@PleaseStand I have fixed that, but I think that the tested version will end up with the bug because the competition is over.

Yeah, your code produced a bug whenever I ran it, and I couldn't figure out how to fix it. It did slightly better than The Lazy, though.

Backstab
Python 3
Despite the name, this bot is actually quite gracious. But don't tick it off.
import sys, math

inp = [int(i) for i in sys.stdin.readline().split()]
inp.append([])
for i in range(inp[2]):
    inp[3].append(
        [eval(i+')') for i in sys.stdin.readline().split(')')[:-1]]
    )
inp += sys.stdin.readline()

# inp is [P, D, N, [M1, M2...], R]

dat = [[], inp[2] % 2] # average runlength take and don't per player, parity of round

lastatk = []

for i in range(inp[0]):
    dat[0].append([])
    lastatk.append(0)

for i,r in enumerate(inp[3]): # each round
    for m in r: # each move
        if m[1] == inp[1]:
            dat[0][m[0]-1].append(i) # round num they attacked
            lastatk[m[0]-1] = i # keep track of last attack

# now that we know who attacked me when, i can do some stats

nav = []
rl = []

for i in range(inp[0]):
    nav.append([[0], False])
    rl.append([[], []]) # attack, don't

for i in range(inp[2]): # each round
    for p in range(1, inp[0]+1): # each player
        if p != inp[1]: # let's not judge ourselves
            if i in dat[0][p-1]: # p attacked me in round i
                if nav[p-1][1]: # attack chain?
                    nav[p-1][0][-1] += 1
                else: # start attack chain!
                    rl[p-1][1] += [nav[p-1][0][-1]] # copy peace chain
                    nav[p-1][0].append(1)
                    nav[p-1][1] = True
            else: # peace!
                if not nav[p-1][1]: # peace chain?
                    nav[p-1][0][-1] += 1
                else: # peace to all!
                    rl[p-1][0] += [nav[p-1][0][-1]] # copy atk chain
                    nav[p-1][0].append(1)
                    nav[p-1][1] = False

print(nav)

print(inp[3])

# now, rl has runlengths for each player.

print(rl)

rl = [[sum(i[0])/len(i[0]+[0]), sum(i[1])/len(i[1]+[0])] for i in rl]

# rl now contains the averages w/ added zero.

# So, now we have average runtime and last attack. Let's quickly make some descisions.

out = []

for p in range(1, inp[0]+1): # each player
    if p != inp[1]: # again, let's not judge ourselves
        if lastatk[p-1] == inp[0]-1: # they attacked us!
            out.append(p)
        else: # whew, we can recover
            if inp[0] - lastatk[p-1] > rl[p-1][0]: # they're due to defend!
                out.append(p)
            elif int(__import__('binascii').b2a_hex(inp[-1].encode()), 16) % 4 == 0: # 1 in 4 chance of doing this
                out.append(p) # backstab!!1!!1one!!!1!!

print(*out)

EDIT 2: Posted source. Yay.
EDIT: After some testing I fixed some flaws I found. They aren't algorithmic, just some issues reading the input.

Just a friendly reminder: the coding phase is over; you've got a day to post your source code. (Procedure is at the bottom of the question.)

@JoeZ. Posted. I hope I'm in time. :P

P, D, N, R sounds like the drives a car can shift into.

@JoeZ. xD They're from your post, so ;3

Oh, my bad. Sorry :S

@JoeZ. Oh no, I left my logging code in and didn't notice. :S Can I remove it or am I dq'd? :P

@JoeZ. Also, I seem to be on par with Wrathful when fighting against just the simple plants.

Eh, go ahead and remove it. At this point if I disqualified people for mistakes like that, I'd have no entrants left.


text:
Collatz Attack!
This challenge is based on some new findings related to the Collatz conjecture and designed somewhat in the spirit of a collaborative polymath project. Solving the full conjecture is regarded as extremely difficult or maybe impossible by math/number theory experts, but this simpler task is quite doable and there is many examples of sample code. In a best case scenario, new theoretical insights might be obtained into the problem based on contestants entries/ ingenuity/ creativity.
The new finding is as follows: Imagine a contiguous series of integers [ n1 ... n2 ] say m total.  Assign these integers to a list structure. Now a generalized version of the Collatz conjecture can proceed as follows. Iterate one of the m (or fewer) integers in the list next based on some selection criteria/algorithm. Remove that integer from the list if it reaches 1. Clearly the Collatz conjecture is equivalent to determining whether this process always succeeds for all choices of n1, n2.
Here is the twist, an additional constraint. At each step, add the m current iterates in the list together. Then consider the function f(i) where i is the iteration number and f(i) is the sum of current iterates in the list. Look for f(i) with a particular "nice" property.
The whole/ overall concept is better/ more thoroughly documented here (with many examples in ruby). The finding is that fairly simple strategies/ heuristics/ algorithms leading to "roughly monotonically decreasing" f(i) exist and many examples are given on that page. Here is one example of the graphical output (plotted via gnuplot):

So here is the challenge: Use varations on the existing examples or entirely new ideas to build a selection algorithm resulting in a f(i) "as close to monotonically decreasing as possible". Entrants should include a graph of f(i) in their submission. Voters can vote based on that graph & the algorithmic ideas in the code.
The contest will be based on n1 = 200 / n2 = 400 parameters only! (the same on the sample page.) But hopefully the contestants will explore other regions and also attempt to generalize their algorithms.
Note, one tactic that might be very useful here are gradient descent type algorithms, or genetic algorithms.
Can discuss this all further in chat for interested participants.
For some ref, another codegolf Collatz challenge: Collatz Conjecture (by Doorknob)

Capitalization please!

Why are people voting to close? It's nice to have non-stereotypical questions! I the problem too much thinking/reading involved in understanding the question?!

"Iterate one of the m (or fewer) integers in the list" How does one "iterate" an integer? Did you mean "increment" or "decrement"?

iterate here means "advance to next 'iterate' in the Collatz sequence for that integer"

It looks like the example you've posted will be hard to beat... :)

@anorton thx for interest/compliment, the above code does reflect quite a bit of analysis/experimenting :) however, hint: a brute force analysis of the problem and an algorithm that merely runs thru a table encoding an optimum previously found is still an algorithm... while the code given is surprisingly simple, there is no credit for small code, the emphasis is on the function smoothness/monotonicity.

@vzn I can't promise a submission anytime soon, as I'm headed on vacation this weekend after school ends, and things are kinda hectic right now.  However, I will certainly experiment with this--after all, this is a novel approach to a problem I find very intriguing.  :)

@anorton the collatz problem is indeed maybe like an iceberg, amazingly simple on the surface and yet quite amazingly theoretically deep underneath that, and probably hundreds of papers have been written on the subj and many mathematicians/experts have studied it over many decades ... it connects to many diverse aspects of theory etc. but alas paradoxically few ppl seem to be studying it at any given moment...

What do you mean by "as close to monotonically decreasing as possible"? No matter what order you iterate the values in the list, the graph will still increase and decrease the same amount.

hi @KSFT try rereading carefully or experimenting with the collatz conjecture iterates or read the links to see the idea(s) behind the writing. can teach/ walk thru the basics in number theory chat room for anyone interested

Ah, I didn't realize that you can iterate multiple values at once.

followup/ reveal to some conjecture/ this challenge (was hoping participants would discover this on their own), there is a sense that this problem is solvable in a very smooth way, considering the concept of "local" vs "global" algorithms. algorithms that precompute entire trajectories can guarantee very high smoothness. the open problem is if an algorithm exists looking only at "local" info. proving one exists is nearly equivalent to solving the conjecture. more on this, see eg ML + ATP + collatz = ? (via weka) / TMachine blog

I wrote some code in Python 2 to run algorithms for this challenge:
import matplotlib.pyplot as plt

def iterate(n):
    return n*3+1 if n%2 else n/2
def g(a):
    ##CODE GOES HERE
    return [True]*len(a)
n1=input()
n2=input()
a=range(n1,n2+1)
x=[]
y=[]
i=0
while any(j>1 for j in a):
    y.append(sum(a))
    x.append(i)
    i+=1
    b=g(a)
    for j in range(len(a)):
        if b[j]:
            a[j]=iterate(a[j])
plt.plot(x,y)
plt.show()

g(x) takes the list of values and returns a list of bools for whether each one should be changed.
That includes the first thing I tried, as the line right after the comment, which was iterating all of the values in the list. I got this:

It doesn't look close to monotonic, so I tried iterating only values that would decrease the sum, if there are any, iterating the ones that would increase it least otherwise:
l=len(a)
n=[iterate(i) for i in a]
less=[n[i]<a[i] for i in range(l)]
if any(less):
    return less
m=[n[i]-a[i] for i in range(l)]
return [m[i]==min(m) for i in range(l)]

Unfortunately, that doesn't terminate (at least for n1=200, n2=400). I tried keeping track of values I'd seen before by initializing c=set():
l=len(a)
n=[iterate(i) for i in a]
less=[n[i]<a[i] for i in range(l)]
if any(less):
    return less
m={i:n[i]-a[i] for i in range(l)}
r=[i for i in m if m[i]==min(m.values())]
while all([a[i] in c for i in r]) and m != {}:
    m={i:m[i] for i in m if a[i] not in c}
    r+=[i for i in m.keys() if m[i]==min(m.values())]
for i in r:
    c.add(a[i])
return [i in r for i in range(l)]

That doesn't terminate either, though.
I haven't tried anything else yet, but if I have new ideas, I'll post them here.

+1 thx for your interest & reviving the challenge. this is not very good for performance but you get the acceptance anyway, my small gesture of thx :) ... also others interested plz feel free to chat about it or invite me into chat to further discuss

Python 3
My main idea was to add each numbers Collatz sequence to the f(i) function individually in a way that it minimizes the total increasing of f(i). The resulting function isn't strictly decreasing but it has a nice structure (in my opinion :)). The second graph was created with longer interval for f(i) and slightly different punishment function. Code on Gist.

When using the (3*n+1)/2 rule instead the 3*n+1 one the algorithm produces a completely monotonic f(i)! I'm sure this modification could make vzn's graphs a lot smoother too. The second graph was created with longer interval for f(i). Code on Gist.

Both results are similar for bigger [n,2*n] ranges.

2nd two are novel/ great, best outside entries so far! a completely monotonic decrease is something like a breakthrough! if you can show it works on increasingly larger starting iterates in "similar way", that is a actual proof strategy candidate...!

@vzn With some modification strictly monotonic f seems to be achievable. Even if my current algorithm fails there is considerable space for improvement. I will let it run and see if it fails for some n (over 200). Strict monotony is stronger the the Collatz conjecture so I might pass on that for now. :) Do your functions work well with the (3n+1)/2 rule? Why don't you use that?

@vzn So many ideas... The main holdback is the relevant xkcd :). The  monotonic decrease seems to hold. A [1,n] range might be more interesting because there we could also ask (if the monotony holds) whether we can create an [1,n+1] by not modifying the [1,n] one and adding the n+1 sequence to it.

so nice to see some shared inspiration! a proof strategy could work either way, eg in constant-sized "blocks". from experiments on the cited pg, various strategies tend to "break" for larger n. more detailed description of your algorithm in words would be great.

fyi ported this to ruby & did some basic experiments, graphed results here. the code seems to have some small dependence on nondeterminism in the sort but maybe not for larger n.

@vzn Since then I worked on it and I'm fairly sure that for any 0<e<1 the f function with [e*n,n] range can be strictly monotonic. I didn't have the time/motivation to write it all out with all the data and supportive arguments. Anyway I modified my program to give you proof/data to work with. http://ideone.com/cUq0oa In each line there are the chosen (starting) numbers for that iteration. If you have questions I'm at the codegolf.se chat sometimes.

@vzn And I'm planning to submit a Collatz related golf question soon. http://meta.codegolf.stackexchange.com/a/4832/7311

as explained in my blog your claim wrt "strictly monotonic" decrease in the "aggregate trajectory sum" for any [e*n,n] range is nearly equivalent to the collatz conjecture itself! so while it is so far supported empirically for smaller ranges (verified/ replicated in my blog just cited), unf it is highly unlikely to be able to fully characterize with a proof... but this correspondence was also the original motivation for the aggregate reformulation & would be very interested to further discuss/ dissect that claim in [chat]

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Find the next subpermutation of base-64 digits
Permutations of a set have a natural order called lexicographic order in which two permutations are compared by comparing the first position at which they differ. For the purposes of this question we're working with base 64 and the order of the digits is
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

Note that this is not the same order as their ASCII values.
This ordering can be extended naturally to handle subpermutations of a given length.
Task
Write a program, function or named verb which takes as input (via stdin in the case of a program or as an argument otherwise) a 12-character subpermutation of the base-64 alphabet given above, and which produces (respectively to stdout or as the return value) the lexicographically next 12-character subpermutation. If working with typed input you may use strings or character arrays holding the ASCII values of the digits listed above.
Your solution should be relatively efficient; and in particular, it is forbidden to loop through base-64 numbers testing them until you find one which doesn't repeat any digits.
It is only required that your program handle 12-character subpermutations, but you do not need to verify that the input is 12 characters in length; if it handles other lengths too you may wish to mention that in your answer.
If the input is the lexicographically greatest subpermutation, the output should wrap round to the lexicographically smallest subpermutation.
Test cases
Input           Output
ABCDEFGHIJKL    ABCDEFGHIJKM
ABCDEFGHIJK+    ABCDEFGHIJK/
ABCDEFGHIJK/    ABCDEFGHIJLK
ABCDEFGHIJLK    ABCDEFGHIJLM
ABCD/9876542    ABCD/9876543
ABCD/9876543    ABCD/987654+
ABCD/987654+    ABCD/98765+E
ABCD/98765+E    ABCD/98765+F
ABCDEF+/9875    ABCDEF+/9876
ABCDEF+/9876    ABCDEF/GHIJK
ABCDEF/GHIJK    ABCDEF/GHIJL
ABCDEF/GHIJL    ABCDEF/GHIJM
ABCDEFG+/987    ABCDEFG/HIJK
A+/987654321    A/BCDEFGHIJK
/+9876543210    ABCDEFGHIJKL

Anyone who wants to submit their code samples can go ahead via a fork & pull request on github

You write named verb. You don't write named function, so as written anonymous functions are OK but anonymous verbs are not. Is that an oversight or do you just not like J?

All of those test cases are correct.  But the last one starts with the highest possible adaptation.  Why do you start back at the beginning?

It's okay, it's just my sample code wasn't made to handle that edge case.

@marinus I'm not sure what you're referring to.  This question has been rewritten by Peter.  If you'd like to see the original post you can here http://6ftdan.com/2014/05/03/golf-challenge-unique-base-64-incrementor/

Updated link to original challenge: http://6ftdan.com/danielpclark/2014/05/03/golf-challenge-unique-base-64-incrementor/

GolfScript, 115 characters
:I,,0\{26,{65+.32+}%$10,{`}%'+/'++:A,1$-@*\)I<)A@-?+}/1I,,{A,\-*}/\)1$%\I,,{A,\-/\.2$%\2$/@\}%*>A\{1$=\[1$]-\}%\0<+

It passes all the test cases and works also for subpermutations of size other than 12 and for full permutations as well.
Online tester
Annotated Code:
:I                        # save input to variable I

### get the numerical index of the (sub)permutation
,,0\                      # push 0 (accumulator) and [0 .. <Length I>-1]
{                         # loop over

  ### construct the alphabet A
  26,{65+.32+}%$          # A-Z and a-z
  10,{`}%                 # 0-9
  '+/'++                  # append '+/'
  :A                      # save to variable A

  ,1$-                    # length of alphabet (i.e. 64) minus loop variable
                          # i.e. 64 -> 63 -> 62 -> 61 -> ...
                          # (this is the number of possible characters at
                          # the current position)
  @*                      # multiply the accumulator by this value
  \)I<                    # get anything from the input up to the current character
  )                       # extract the current character of input
  A@-                     # remove anything from the alphabet which was in the rest,
                          # i.e. the already processed chars cannot be used any more
  ?                       # find the index of the current input character
  +                       # add to the accumulator
}/

### calculate the total number of (sub)permutations
1                         # push 1 (accumulator)
I,,{                      # loop for i = 0 .. <Length I>-1
  A,\-                    # length of alphabet minus loop variable
  *                       # multiply to accumulator
}/

### at this point the stack is <Index of input (sub)permutation>
###   <Total number of (sub)permutations>
\)                        # increment the index (i.e. next (sub)permutation)
1$%                       # warp around for the last possible (sub)permutation
\                         # swap back order

### backwards transformation into the (sub)permutation space
I,,{                      # map for each index [0 .. <Length I>-1]
  A,\-/                   # divide the weight factor by length of alphabet minus
                          # loop variable
  \.2$%                   # take index % new weight factor
  \2$/                    # and index / new weight factor (result for the map operation)
  @\                      # re-order stack
}%
*>                        # get rid of 0 1 on the stack

### back to the alphabet
A\                        # push the full alphabet under the index array
{                         # map on the index array
  1$=                     # take the i-th element of the alphabet
  \[1$]-\                 # and reduce the alphabet by this characters
}%

\0<                       # transforms the remaining alphabet into an empty string
+                         # make string from array by joining with the empty string

GolfScript, 77 70 characters
Another more direct approach in GolfScript which happens to work in the general case also.
:I{)26,{65+.32+}%$10,{`}%'+/'++:^2$-:S\?).S,<{S[=]+0}*1$!!*}do^1$-+I,<

Also this solution can be tested online.

Ruby: Whittled down to 658 Characters
class B;def initialize(g)@l=12;@b=(("A".."Z").to_a+("a".."z").to_a+("0".."9").to_a+["+","/"]
).each_with_index.map{|x,i|{x=>i}}.inject(:update);@g=g;@i=@b.invert;@m=@l.times.map{|i|
@i[@b.length-i-1]}.join;end;def n;c(@g)?@g:r;end;def c(s);@b[s[-1]]==@b.length-1?(return false
):s==@m?r: f(s,s[-1]) ?s[-1]=f(s,s[-1]):f(s,s[-2])?r: (s[-1]=f(s);f(s,s[-2])?s[-2]=f(s,s[-2]):r)
true;end;def h(s)v=s.split("").map{|x|@b[x]};v.index(v.compact.max)end;def r;@g==@m?@g=@l.times.map{
|j| @i[j]}.join: (v=@g[0..h(@g)-1];c(v);u=@g[h(@g)..-1].length;u.times{v+=f(v)};@g=v);end
def f(s,a=@i[0])(@b[a]..@b.length-1).each{|p|unless !!s[@i[p]];return @i[p]end};false;end;end

Running test cases:
puts "      IN   *******   OUT"
["ABCDEFGHIJKL","ABCDEFGHIJK+","ABCDEFGHIJK/","ABCDEFGHIJLK","ABCD/9876542",
"ABCD/9876543","ABCD/987654+","ABCD/98765+E","ABCDEF+/9875","ABCDEF+/9876",
"ABCDEF/GHIJK","ABCDEF/GHIJL","ABCDEFG+/987","A+/987654321","/+9876543210"
    ].each do |v|
    t = B.new(v.dup)
    puts " #{v}   #{t.n}"
end

Outputs:
      IN   *******   OUT
 ABCDEFGHIJKL   ABCDEFGHIJKM
 ABCDEFGHIJK+   ABCDEFGHIJK/
 ABCDEFGHIJK/   ABCDEFGHIJLK
 ABCDEFGHIJLK   ABCDEFGHIJLM
 ABCD/9876542   ABCD/9876543
 ABCD/9876543   ABCD/987654+
 ABCD/987654+   ABCD/98765+E
 ABCD/98765+E   ABCD/98765+F
 ABCDEF+/9875   ABCDEF+/9876
 ABCDEF+/9876   ABCDEF/GHIJK
 ABCDEF/GHIJK   ABCDEF/GHIJL
 ABCDEF/GHIJL   ABCDEF/GHIJM
 ABCDEFG+/987   ABCDEFG/HIJK
 A+/987654321   A/BCDEFGHIJK
 /+9876543210   ABCDEFGHIJKL

For the long understandable version of this code see my github post https://github.com/danielpclark/b64challenge
This code was tested with Ruby version 1.9.3.  I can only vouch for is version.

I could have saved a BUNCH of characters if I didn't have to pass that last test case.

Also I didn't use any Regex.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Determine if a move exists in a Bejeweled/match 3 game
Background
In Bejeweled and similar games, the player must swap any two adjacent gems (no diagonals) in an 8x8 grid of gems in order to match three of the same color in a row. The gems can be matched horizontally or vertically. Gameplay continues until there no move exists that can be made resulting in three in a row, at which point the game is over.
Task
The goal is to write a program that determines whether a game of Bejeweled is not over yet. In other words, it must check to see if there is a possible move that makes at least three in a row. There can be more than three gems in a row and it is still a valid move.
Input
Your program must accept via standard input an 8x8 representation of a Bejeweled grid. Each of the seven gem colors will be represented by a digit from 1 to 7. Each line will contain one row, and 8 lines, each consisting of 8 digits, will be input. See the examples. You can assume that the input will always follow this format, and will never already contain three in a row.
Output
The program must then output (to standard output) yes or no depending on whether or not at least one valid move exists that would result in three or more gems in a row. Your program must not output anything other than a single instance of either yes or no.
Rules
Your program must not use any external files or resources, command-line arguments, or require a certain file name. The program with the least number of bytes in its source code wins.
Examples
Input:
12314131
13224145
54762673
61716653
61341144
23453774
27645426
75575656

Output: yes
Input:
35261546
76421754
15743271
62135642
35617653
64565476
54427254
15635465

Output: no
See MT0's answer below for additional test cases.

Is it just rows, or columns too.

@TheDoctor Columns too. When I use the phrase "three in a row" I mean that they must be lined up in a horizontal or vertical direction.

@bdr9 you might want to edit that in

@JanDvorak Done.

Also might want to edit in if 4+ in a row is allowed.

Will the input ever contain 3 in a row, and if so should we immediately return true?

@Quincunx Thanks. It is allowed. I have updated the question.

@ali0sha You can assume the input will never already contain 3 in a row. I have updated the question.

I'm kind of confused as to how one would go about doing this without code golf.

Original Solution: JavaScript - 261 255 228 227 179 153 Characters
/(\d)(\1(\d|.{6}|.{9})|(\d|.{6}|.{9})\1|.{7}\1(.|.{9})|(.|.{9})\1.{7}|(.{7,9}|.{17})\1.{8}|.{8}\1(.{7,9}|.{17}))\1/.test(s.replace(/\n/g,'A'))?'yes':'no'

Assuming that the string to test is in the variable s (to make it a function f then add f=s=> to the beginning of the code or, otherwise, to take input from a prompt then replace s with prompt()).
Outputs is to the console.
3rd Solution: JavaScript (ECMAScript 6) - 178 Characters
p=x=>parseInt(x,36);for(t="2313ab1b8a2a78188h9haj9j8iaiir9r",i=v=0;s[i];i++)for(j=0;t[j];v|=s[i]==s[i+a]&s[i]==s[i+b]&i%9<8&(b>3|(i+b-a)%9<8))a=p(t[j++]),b=p(t[j++]);v?'yes':'no'

I took the 2nd solution, below, (which uses regular expressions to check for characters in certain configurations) and reworked it to just check the string for identical characters in the same configurations without using regular expressions.
The Base-36 string "2313ab1b8a2a78188h9haj9j8iaiir9r" gives pairs of offsets to check - i.e. the pair 23 results in the check if ith character is identical to the (i+2)th character and the (i+3)th character (the equivalent of the regular expression (.).\1\1 - with some additional checks to ensure that the non-identical character is not a newline).
2nd Solution: JavaScript (ECMAScript 6) - 204 Characters
p=x=>parseInt(x,18);g=a=>a?a>1?"(.|\\n){"+a+"}":".":"";f=(x,a,b)=>RegExp("(.)"+g(a)+"\\1"+g(b)+"\\1").test(x);for(t="10907160789879h8",i=v=0;t[i];v|=f(s,x,y)||f(s,y,x))x=p(t[i++]),y=p(t[i++]);v?'yes':'no'

Builds multiple regular expressions (see below for more details) using pairs of values taken from the  Base-18 string 10907160789879h8 and takes the OR of all the tests. To reduce it further you can note that the regular expressions come in pairs where one is the "reverse" of the other (ignoring the Regular Expressions for 3-in-a-row horizontally and vertically as the OP states they will never be present - if you want to add those tests back in the append 0088 to the Base-18 string).
Explanation
Start with 16 regular expressions covering all the possible configurations of valid moves:
REs=[
    /(\d)\1\1/,                 // 3-in-a-row horizontally
    /(\d).\1\1/,                // 3-in-a-row horizontally after left-most shifts right
    /(\d)\1.\1/,                // 3-in-a-row horizontally after right-most shifts left
    /(\d)(?:.|\n){9}\1\1/,  // 3-in-a-row horizontally after left-most shifts down
    /(\d)(?:.|\n){7}\1.\1/, // 3-in-a-row horizontally after middle shifts down
    /(\d)(?:.|\n){6}\1\1/,  // 3-in-a-row horizontally after right-most shifts down
    /(\d)\1(?:.|\n){6}\1/,  // 3-in-a-row horizontally after left-most shifts up
    /(\d).\1(?:.|\n){7}\1/, // 3-in-a-row horizontally after middle shifts up
    /(\d)\1(?:.|\n){9}\1/,  // 3-in-a-row horizontally after right-most shifts up
    /(\d)(?:.|\n){7,9}\1(?:.|\n){8}\1/, // 3-in-a-row vertically (with optional top shifting left or right)
    /(\d)(?:.|\n){7}\1(?:.|\n){9}\1/,   // 3-in-a-row vertically after middle shifts right
    /(\d)(?:.|\n){9}\1(?:.|\n){7}\1/,   // 3-in-a-row vertically after middle shifts left
    /(\d)(?:.|\n){8}\1(?:.|\n){7}\1/,   // 3-in-a-row vertically after bottom shifts right
    /(\d)(?:.|\n){8}\1(?:.|\n){9}\1/,   // 3-in-a-row vertically after bottom shifts left
    /(\d)(?:.|\n){17}\1(?:.|\n){8}\1/,  // 3-in-a-row vertically after top shifts down
    /(\d)(?:.|\n){8}\1(?:.|\n){17}\1/,  // 3-in-a-row vertically after bottom shifts up
];

(Note: the regexs for 3-in-a-row horizontally (0th) and vertically (part of the 9th) are irrelevant as the OP states that inputs matching these will never be present.)
Testing each of those against the input will determine if a valid move of that configuration can be found.
However, the regular expressions can be combined to give these 6:
/(\d)(?:.|(?:.|\n){9}|(?:.|\n){6})?\1\1/            // Tests 0,1,3,5
/(\d)\1(?:.|(?:.|\n){9}|(?:.|\n){6})?\1/            // Tests 0,2,6,8
/(\d)(?:.|\n){7}\1(?:.|(?:.|\n){9})\1/              // Tests 4,10
/(\d)(?:.|(?:.|\n){9})\1(?:.|\n){7}\1/              // Tests 7,11
/(\d)(?:(?:.|\n){7,9}|(?:.|\n){17})\1(?:.|\n){8}\1/ // Tests 9,14
/(\d)(?:.|\n){8}\1(?:(?:.|\n){7,9}|(?:.|\n){17})\1/ // Tests 9a,12,13,15

These can then be combined into a single regular expression:
/(\d)(?:.|(?:.|\n){9}|(?:.|\n){6})?\1\1|(\d)\2(?:.|(?:.|\n){9}|(?:.|\n){6})?\2|(\d)(?:.|\n){7}\3(?:.|(?:.|\n){9})\3|(\d)(?:.|(?:.|\n){9})\4(?:.|\n){7}\4|(\d)(?:(?:.|\n){7,9}|(?:.|\n){17})\5(?:.|\n){8}\5|(\d)(?:.|\n){8}\6(?:(?:.|\n){7,9}|(?:.|\n){17})\6/

Which just needs to be tested against the input.
Test Cases
Some test cases which other people might find useful (doesn't comply with the input format of using only digits 1-7 but that's easily corrected and is only an 8x4 grid - since that is the minimum required for a test of all the valid inputs).
In the format of a map from input string to which of the 16 regular expressions above it matches.
Tests={
    "12345678\n34567812\n56781234\n78123456": -1, // No Match
    "12345678\n34969912\n56781234\n78123456": 1,    // 3-in-a-row horizontally after left-most shifts right
    "12345678\n34567812\n59989234\n78123456": 2,    // 3-in-a-row horizontally after right-most shifts left
    "12345978\n34567899\n56781234\n78123456": 3,    // 3-in-a-row horizontally after left-most shifts down
    "12345978\n34569892\n56781234\n78123456": 4,    // 3-in-a-row horizontally after middle shifts down
    "12345678\n34967812\n99781234\n78123456": 5,    // 3-in-a-row horizontally after right-most shifts down
    "12399678\n34967812\n56781234\n78123456": 6,    // 3-in-a-row horizontally after left-most shifts up
    "12345678\n34597912\n56789234\n78123456": 7,    // 3-in-a-row horizontally after middle shifts up
    "12345998\n34567819\n56781234\n78123456": 8,    // 3-in-a-row horizontally after right-most shifts up
    "12945678\n34597812\n56791234\n78123456": 9,    // 3-in-a-row vertically after top shifts right
    "12349678\n34597812\n56791234\n78123456": 9,    // 3-in-a-row vertically after top shifts left
    "12345978\n34569812\n56781934\n78123456": 10,   // 3-in-a-row vertically after middle shifts right
    "92345678\n39567812\n96781234\n78123456": 11,   // 3-in-a-row vertically after middle shifts left
    "12945678\n34967812\n59781234\n78123456": 12,   // 3-in-a-row vertically after bottom shifts right
    "12349678\n34569812\n56781934\n78123456": 13,   // 3-in-a-row vertically after bottom shifts left
    "12395678\n34567812\n56791234\n78193456": 14,   // 3-in-a-row vertically after top shifts down
    "12345698\n34567892\n56781234\n78123496": 15,   // 3-in-a-row vertically after bottom shifts up
    "12345678\n34567899\n96781234\n78123456": -1,   // No match - Matches (.)\1.\1 but not 3 in a row
    "12345679\n99567812\n56781234\n78123456": -1,   // No match - Matches (.).\1\1 but not 3 in a row
};

Edit 1
Replace \ds with . - saves 6 characters.
Edit 2
Replace (?:.|\n) with [\s\S] and removed extra non-capturing groups and updated back references (as suggested by m-buettner) and added in yes/no output.
Edit 3

Added ECMAScript 6 solution to build the individual Regular Expressions from a Base-18 string.
Removed the tests for 3-in-a-row horizontally (as suggested by m-buettner).

Edit 4
Added another (shorter) solution and two more non-matching tests cases.
Edit 5

Shortened original solution by replacing newlines with a non-numeric character (as suggested by VadimR).

Edit 6

Shortened original solution by combining bits of the regular expression (as suggested by VadimR).

Nice solution! I wouldn't have thought that regex could work. Please include the ?'yes':'no' in your character count for fairness, because it is in the requirements and everyone else is using it.

Thanks for the additional test cases, I added a link to your answer so other people can see them.

Whoa. +1 for regex

H-mm, no modifier in JS for . to match any character including newline? With Perl, combined regexp is mere 129 bytes string (which, being lazy, I compiled with Regexp::Assemble), so the whole Perl program is about 150 bytes.

But even so, replacing newline with e.g. A before testing gives much shorter solution than 227.

Having . match a newline (or a newline replaced with a non-digit) brings its own issues - (.).\1\1 should fail in the case of 1\n11.

Nice, I was hoping somebody would do this in regex. That would have been my first method to try.

Could this be modified using node.js to actually read from stdin per spec?

As I stated - if you want to read input from the user then use prompt() - or if you want to use the SpiderMonkey JavaScript engine then use readline().

MT0, take a look at this regexp: (\d)(.{8}\1(.{17}|.{7}|.{9})|.{7}\1(.{8}|.{9}|.)|.{9}\1(.{7}|.{8})?|\1(.{6}|.{9}|\d)|(.{6}|\d)\1|.{17}\1.{8}|.\1.{7})\1, generated by the module I mentioned.

@VadimR Thanks but you can go even further replacing .{8}|.{9} with .{8,9} and .{7}|.{8} with .{7,8}

Python 383
Just a single* line of Python!
a=[list(l)for l in raw_input().split('\n')];z=any;e=enumerate;c=lambda b:z(all(p==b[y+v][x+u]for(u,v)in o)for y,r in e(b[:-2])for x,p in e(r[:-2])for o in [[(0,1),(0,2)],[(1,0),(2,0)]]);print z(c([[q if(i,j)==(m,n)else a[m][n]if(i,j)==(y+1,x+1)else p for j,p in e(r)]for i,r in e(a)])for y,t in e(a[1:-1])for x,q in e(t[1:-1])for n,m in((x+u,y+v)for u,v in[(1,0),(1,2),(0,1),(2,1)]))

*Well, with semicolons, but that's still non-trivial in python (python one-liners are fun!)

Upvoted for incomprehensible comprehensions :)

APL (Dyalog Unicode), 71 bytes
'no' 'yes'⊃⍨{∨/∊{((3≤1⊥⊃=⊢)¨4,/⍵)({∨⌿∧⌿∨⌿⍵∘.=⊣/⍵}⌺2 3⊢⍵)}¨⍵(⍉⍵)}↑{⍞}¨⍳8

Try it online!
Nice challenge to show off some extreme array-processing capabilities of APL.
Without the I/O restriction, it is 55 52 bytes as a function taking a 8-by-8 matrix of chars and returning a boolean (therefore without 7-bytes pre-processing ↑{⍞}¨⍳8 and 12-bytes post-processing 'no' 'yes'⊃⍨):
{∨/∊{((3≤1⊥⊃=⊢)¨4,/⍵)({∨⌿∧⌿∨⌿⍵∘.=⊣/⍵}⌺2 3⊢⍵)}¨⍵(⍉⍵)}

Try it online!
The basic idea is that we can test for 1x4 and 2x3 sub-boxes if each sub-box has a valid Bejeweled move:
(1x4 box)
OxOO    OOxO

(2x3 box)
OOx     OxO     xOO
xxO     xOx     Oxx

Oxx     xOx     xxO
xOO     OxO     OOx

For 1x4 boxes, we can check if the first item appears at least 3 times. For 2x3 boxes, we can check if at least one item in the first column appears in every column. For 4x1 and 3x2 boxes, we can check for 1x4 and 2x3 on the board transposed.
How it works: the code
'no' 'yes'⊃⍨{∨/∊{((3≤1⊥⊃=⊢)¨4,/⍵)({∨⌿∧⌿∨⌿⍵∘.=⊣/⍵}⌺2 3⊢⍵)}¨⍵(⍉⍵)}↑{⍞}¨⍳8

↑{⍞}¨⍳8  ⍝ Take 8 lines of input and form a 8x8 matrix
     ⍳8  ⍝ A dummy length-8 vector
 {⍞}¨    ⍝ Map "take a line of input" over the dummy vector
↑        ⍝ Promote a vector of vectors to a matrix (M)

{∨/∊{...}¨⍵(⍉⍵)}  ⍝ Pass the matrix onto the inline function
          ⍵(⍉⍵)   ⍝ M and transpose of M
    {...}¨        ⍝ Test over M and transposed M for Bejeweled moves
                  ⍝ (explained below)
 ∨/∊              ⍝ Enlist all booleans and check if any is true

{((3≤1⊥⊃=⊢)¨4,/⍵)({∨⌿∧⌿∨⌿⍵∘.=⊣/⍵}⌺2 3⊢⍵)}  ⍝ Test over all possible sub-boxes
((3≤1⊥⊃=⊢)¨4,/⍵)  ⍝ Test over 1x4 boxes
           4,/⍵   ⍝ Extract 1x4 boxes
 (    ⊃=⊢)¨       ⍝ For each box, test if each item equals first item
  3≤1⊥            ⍝ Is the count at least 3?
({∨⌿∧⌿∨⌿⍵∘.=⊣/⍵}⌺2 3⊢⍵)  ⍝ Test over 2x3 boxes
 {             }⌺2 3⊢⍵   ⍝ Ditto
        ⍵∘.=⊣/⍵          ⍝ Compare each item with the first column
  ∨⌿                     ⍝ Does there exist an item from the first column
    ∧⌿                   ⍝ that appears on every column
      ∨⌿                 ⍝ at least once?

'no' 'yes'⊃⍨  ⍝ Map 0/1 to no/yes respectively

Perl, 114 96 95 93 92 87 86 85 bytes
Includes + for -a0p
Run with the input on STDIN:
bejeweled.pl
12314131
13224145
54762673
61716653
61341144
23453774
27645426
75575656
^D

bejeweled.pl:
#!/usr/bin/perl -a0p
$i/s%.%chop$F[$i++&7]%eg>3|/(.)((.|\H{6}|\H{9})\1|\H{7}\1.)\1/||redo;$_=$1?yes:n.o

This combines a single direction horizontal regex solution with rotations
Explanation:
In this solution I will repeatedly rotate and do the following 4 tests:
/(.).\1\1/,      // 3-in-a-row horizontally after left-most shifts right
/(.)\C{9}\1\1/,  // 3-in-a-row horizontally after left-most shifts down
/(.)\C{7}\1.\1/, // 3-in-a-row horizontally after middle shifts down
/(.)\C{6}\1\1/,  // 3-in-a-row horizontally after right-most shifts down

Where \C is "any character" (unlike . this includes newline). Except that \C is deprecated and leads to warnings, so I use \H (non-horizontal space) instead which is good enough to capture all digits and newline.
After 4 rotation this will have done all 16 tests that are needed
-p                            Read lines from STDIN, print $_ at the end
-0                            No line ending => slurp ALL of STDIN
-a                            Split $_ into @F. Since there are no spaces
                              on the rows this means each element of @F is
                              1 row

    s%.%chop$F[$i++&7]%eg     Replace each row by the removed last column
                              This is therefore a left rotation. Very short
                              but at the cost of using @F. To make sure that
                              @F gets refilled from $_ each time I won't be
                              able to use while, until, eval or do$0 for the
                              loops but have to use redo. That costs a few
                              bytes but less than having to do my own split
$i/                      >3   The previous regex replacement always
                              returns 64 and each time through the loop $i is
                              increased by 64. So if this division reaches
                              4 all rotations have been done

/(.)((.|\H{6}|\H{9})\1|\H{7}\1.)\1/ This is the 4 regexes mentioned above
  ||redo                      Stop the loop if the regex matches or we
                              rotated 4 times
$_=$1?yes:n.o                If the regex matched $1 will be one of the
                              color digits (which cannot be 0) and this will
                              assign "yes" to $_. If the regex didn't match
                              in 4 times $1 will get its value from the last
                              succesful regex in scope which will be the one
                              from the rotation, but that one doesn't have
                              any () so $1 will be unset. So in case there
                              is no move $_ will be set to "no" (which needs
                              to be constructed because "no" is a keyword)

Node.js - Naive solution - 905 bytes
Well, no answers yet so I'll post a really naive solution in Node.js
It goes through every possible move and then tests the resulting board to see if there's 3 in a row.
Golfed (with google closure compiler) (some hacky stuff in there like !0 and !1; I'm not even sure what it did with my XOR swap)
Array.prototype.a=function(){for(var f=[],d=0;d<this.length;d++)f[d]=this[d].a?this[d].a():this[d];return f};for(var a=[],b=0;8>b;b++)a[b]=[];for(b=2;b<process.argv.length;b++)for(var c=process.argv[b].split(""),e=0;e<c.length;e++)a[b-2][e]=parseInt(c[e],10);function h(){for(var d=l,f=0;f<d.length-2;f++)for(var g=0;g<d[f].length-2;g++){var k=d[f][g];if(k==d[f+1][g]&&k==d[f+2][g]||k==d[f][g+1]&&k==d[f][g+2])return!0}return!1}function m(){console.log("yes");process.exit()}for(b=0;b<a.length;b++)for(e=0;e<a[b].length;e++){var l=a.a();0!=b&&(l[b-1][e]^=l[b][e],l[b][e]^=l[b-1][e],l[b-1][e]^=l[b][e],h()&&m(),l=a.a());b!=a.length-1&&(l[b+1][e]^=l[b][e],l[b][e]^=l[b+1][e],l[b+1][e]^=l[b][e],h()&&m(),l=a.a());0!=e&&(l[b][e-1]^=l[b][e],l[b][e]^=l[b][e-1],l[b][e-1]^=l[b][e],h()&&m(),l=a.a());e!=a[b].length-1&&(l[b][e+1]^=l[b][e],l[b][e]^=l[b][e+1],l[b][e+1]^=l[b][e],h()&&m(),l=a.a())}console.log("no");

Note that I wrote this all on my mobile and don't have time to test it or anything. Comment if you see any bugs, I'll check it myself later.
The pre-golfed human readable version
// set it up
Array.prototype.clone = function() {
    var arr = [];
    for( var i = 0; i < this.length; i++ ) {
        if( this[i].clone ) {
             arr[i] = this[i].clone();
        } else {
             arr[i] = this[i];
        }
    }
};
var board=[];
for(var i=0;i<8;i++)board[i]=[];
for(var i=2;i<process.argv.length;i++){
    var row=process.argv[i].split("");
    for(var j=0;j<row.length;j++)board[i-2][j]=parseInt(row[j], 10);
}
// function to test
function testBoard(arr){
    for(var i=0;i<arr.length-2;i++){
        for(var j=0;j<arr[i].length-2;j++){
            var val=arr[i][j];
            if(val==arr[i+1][j] && val==arr[i+2][j])return true;
            if(val==arr[i][j+1] && val==arr[i][j+2])return true;
        }
    }
    return false;
}
// functions to exit
function yay(){console.log("yes");process.exit();}
function nay(){console.log("no");}
// super slow naive solution time
for(var i=0;i<board.length;i++){
    for(var j=0;j<board[i].length;j++){
        var newboard=board.clone();
        if(i!=0){
            newboard[i-1][j]=newboard[i-1][j]^newboard[i][j];// whoa, it's a
            newboard[i][j]=newboard[i-1][j]^newboard[i][j];  // cool algorithm
            newboard[i-1][j]=newboard[i-1][j]^newboard[i][j];// at least this
                                                             // isn't all naive
            if(testBoard(newboard))yay();
            newboard=board.clone();
        }
        if(i!=board.length-1){
            newboard[i+1][j]=newboard[i+1][j]^newboard[i][j];
            newboard[i][j]=newboard[i+1][j]^newboard[i][j];
            newboard[i+1][j]=newboard[i+1][j]^newboard[i][j];
            if(testBoard(newboard))yay();
            newboard=board.clone();
        }
        if(j!=0){
            newboard[i][j-1]=newboard[i][j-1]^newboard[i][j];
            newboard[i][j]=newboard[i][j-1]^newboard[i][j];
            newboard[i][j-1]=newboard[i][j-1]^newboard[i][j];
            if(testBoard(newboard))yay();
            newboard=board.clone();
        }
        if(j!=board[i].length-1){
            newboard[i][j+1]=newboard[i][j+1]^newboard[i][j];
            newboard[i][j]=newboard[i][j+1]^newboard[i][j];
            newboard[i][j+1]=newboard[i][j+1]^newboard[i][j];
            if(testBoard(newboard))yay();
            newboard=board.clone();
        }
    }
}
nay();

Hah I actually missed the first post by 10 minutes. I kinda like this though...

Ah, exact same method I used (naive but small code!). +1 for being much more descriptive than me

I wonder if there's a more efficient algorithm...

05AB1E, 51 bytes
„€¸…Ü#|€S2FÐ€ü3ø€ü2s€ü4«sø}\«€`ʒÐg;iøćδåøPàë¢3å]gĀè

Port of the approach used by @Bubbler in his APL answer, so make sure to upvote him!!
Try it online.
Explanation:
„€¸…Ü                 # Push dictionary string "no yes"
     #                # Split it on spaces: ["no","yes"]
|                     # Push all input-lines as list
 €S                   # Convert each line to a list of digits
   2F                 # Loop 2 times:
     Ð                #  Triplicate the matrix
      €               #  For each row:
       ü3             #   Create overlapping triplets
         ø            #  Zip/transpose; swapping rows/columns
          €           #  For each overlapping 3-sized column:
           ü2         #   Create overlapping pairs
     s                #  Swap to get the initial matrix again
      €               #  For each row:
       ü4             #   Create overlapping quadruplets
         «            #  Merge this list of 4x1 blocks to the list of 2x3 blocks
     s                #  Swap again to get the initial matrix
      ø               #  Zip/transpose; swapping rows/columns
    }\                # After the loop: discard the top item
      «               # Merge the two lists together
       €`             # Flatten it one level down
         ʒ            # Filter this list of 4x1 and 2x3 blocks by:
          Ð           #  Triplicate the block
           g          #  Get its length (either 4 or 2)
            ;i        #  If this length is 2:
              ø       #   Zip/transpose; swapping rows/columns,
                      #   to make the 2x3 block a 3x2 block
               ć      #   Extract head; pop and push the remainder 2x2 columns and
                      #   first 2x1 column separated to the stack
                δ     #   Apply double-vectorized:
                 å    #    Check if the value is in the list
                  ø   #   Zip/transpose; swapping rows/columns,
                      #   so the checks per value are in the same inner list
                   P  #   Check for both lists whether all checks were truthy
                    à #   And check if either of the two checks is truthy
             ë        #  Else (the length is 4 instead):
              ¢       #   Count how many times each value occurs in the 4x1 block
               3å     #   And check if the counts contain a 3
         ]            # Close both the if-else statement and filter
          g           # Get the amount of remaining blocks
           Ā          # Check that at least one block is remaining
                      # (1 if truthy; 0 if falsey)
            è         # And use that to index into the ["no","yes"] list
                      # (after which the result is output implicitly)

See this 05AB1E tip of mine (section How to use the dictionary?) to understand why „€¸…Ü is "no yes".

Python3, 314B
import itertools as T,copy
r=[]
K=range(8)
J=[list(input())for w in K]
P=T.product
f=lambda A:["yes"for b in[A[m][n:]for m,n in P(K,K[:6])]if b[0]==b[1]==b[2]]
for i,j,x in P(K,K,[0,1]):
 t=j+1-x
 if i+x<8and t<8:B=copy.deepcopy(J);B[i][j],B[i+x][t]=B[i+x][t],B[i][j];r+=f(B)+f(list(zip(*B)))
r+=["no"]
print(r[0])

Change the 8, the 5 on line 6, and the 8s on line 9 to handle arbitrarily large input sizes; also doesn't care what each value is, so you can feed it:
absdefgh
sdkljahs
lsdfjasd
fjdhsdas
dkjhfasd
sdfhaskd
sdkfhkas
weriuwqe

and it will return yes.
Annotations
import itertools as T,copy
            # itertools.product is going to save us lots of for loops
r=[]        # result
K=range(8)  # we can use range(8) everywhere, so this saves more than the usual R=range
J=[list(input())for w in K]
            # input handling: keep everything as a length-1 string to avoid map(int,input())
P=T.product
f=lambda A:["yes"for b in[A[m][n:]for m,n in P(K,K[:6])]if b[0]==b[1]==b[2]]
            # check the condition horiontally only. K[:6] is the same as range(5)
            # A[m][n:n+3] would be neater, but not actually needed
for i,j,x in P(K,K,[0,1]):
            # <3 itertools.product! 3 for-loops without it.
            # NB we're only going right and downwards
 t=j+1-x
 if i+x<8and t<8:
            # don't want out-of-bounds errors at the edges
  B=copy.deepcopy(J)
            # preserve the reference array
  B[i][j],B[i+x][t]=B[i+x][t],B[i][j]
            # do the switch
  r+=f(B)+f(list(zip(*B)))
            # do the test. you could end up with lots of 'yes's in r.
            # zip(*B) takes the transpose, so that f checks the columns too
r+=["no"]   # happens to ensure that r is nonempty
print(r[0]) # only prints no if r was empty before the last line

GNU sed 255+2 = 257B
I thought this wasn't going to be as good as python but it is now :-/ I've been without internet access today so I occupied myself with solving this in sed :). Needs to be called with the -r flag, i.e. sed -rf command.sed < input so I added 2 to my score.
:a
$!N
s/\n/ /g
ta
:b
/^((\w)(\w\2\2|\2\w\2|\w\2\w* \w\2|\2\w* \w\w\2|\w* (\2\w* \w* \2|\w* \2\w* \2|\w\2\2|\w\2\w* \2|\2\w* \w\2|\w\2\w* \w\2))|\w((\w)(\w* \6\w\6|\6\w* \6|\w* (\6\w \w\6|\w\6\w* \6|\6\w* \6))|\w(\w)\w* \9\9))/c\yes
s/\w(\w*)/\1/g
tb
c\no

How it works:

Read the grid into a single line of space-separated characters
Use the motherload regex to find out whether there's a match in the first column* - if yes, swap the entire line for 'yes' (ending the program)
Strip the first character from each column and goto 2 if we did
If we didn't (the line is empty) replace the whole line with 'no'

Ruby, 201 bytes
I was disappointed not to see any solutions to this great challenge that don't use a regex or brute force (although those are great), so I wrote one. It takes input on STDIN.
The core bitwise arithmetic algorithm is derived from this fantastic answer on Game Development Stack Exchange by @leander.
s=$<.read
$><<(?1..?9).any?{|n|a=[0]*19
s.scan(n){i=$`.size
a[i/9+1]+=2**(i%9)
a[i%9+10]+=2**(i/9)}
a.each_cons(3).any?{|x,y,z|q=y&y<<1
l=q<<1
q>>=2
y&(l<<1|q>>1)|(q|l|(y&y<<2)>>1)&(x|z)>0}}?"yes":"no"

Ruby lambda, 181 bytes
Here it is as a lambda that takes a string and returns true or false:
->s{(?1..?9).any?{|n|a=[0]*19
s.scan(n){i=$`.size
a[i/9+1]+=2**(i%9)
a[i%9+10]+=2**(i/9)}
a.each_cons(3).any?{|x,y,z|q=y&y<<1
l=q<<1
q>>=2
y&(l<<1|q>>1)|(q|l|(y&y<<2)>>1)&(x|z)>0}}}

See it on repl.it: https://repl.it/ColJ/2
Ungolfed & explanation
->s{
  (?1..?9).any? {|n|
    a = [0] * 19

    s.scan(n) {
      i = $`.size
      a[i/9+1] += 2**(i%9)
      a[i%9+10] += 2**(i/9)
    }

    a.each_cons(3).any? {|x,y,z|
      q = y & y << 1
      l = q << 1
      q >>= 2
      y & (l << 1 | q >> 1) |
        (q | l | (y & y << 2) >> 1) &
        (x | z) > 0
    }
  }
}

The code iterates over the digits "1" to "9." Each iteration has two discrete steps:
The first step is board transformation, which you can see in the s.scan(n) block in the ungolfed code. It transforms the board into an array of 8 integers, one for each row, by treating matching digits as 1s and all others as 0s in a binary string. For example, take the row 12231123. In the first iteration, this will become the binary string 10001100 (all 1s become—er, stay—1s and all other digits become 0s), which is the decimal number 140. In the second iteration the same row becomes 01100010 (all 2s become 2s and all other digits become 0s), or decimal 98.
It simultaneously performs a second transformation, which is the same as the first but with the board rotated 90 degrees. This lets us use the same logic for making horizontal matches as vertical ones. For simplicity, it concatenates the two boards into a single long one with a zero at the beginning, middle (to separate the two boards), and end for padding.
The second step is searching for possible matches, which you can see in the each_cons(3).any? block. The transformed rows (which are now 8-bit integers) are checked in (overlapping) groups of three rows (x, y, z) using bitwise arithmetic. Each group is checked to see if a match can be made in row y, either by shifting a piece in row y or by shifting a piece into y from x or z. Since there is a zero "row" before and after both the original and rotated boards' rows, we don't have to check if we're on the first or last row of a board.
If no matches were found, it continues to the next iteration.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Chinese Checkers longest move
In Chinese Checkers, a piece can move by hopping over any other piece, or by making a sequence of such hops. Your task is to find the longest possible sequence of hops.
Input
A sequence of 121 zeroes or ones, each representing a place on a board. A zero means the place is empty; a one means the place is occupied. Positions are listed from left to right; top to bottom. For example, the input of this setup would be
1011110011000001000000000000000000000000100000000001000000000000000000000000000001000000000000000000000001000001100111111

Explanation:

The top-most place is occupied by a green piece, so the first digit in the input is 1. The second row has one empty position and then one occupied position, so 01 comes next. The third row is all occupied, so 111. The fourth row has two empty and two occupied spaces (going left to right), so 0011. Then comes five 0's, a 1, and seven 0's for the next row, and so on.

Like in that setup, there is a corner pointing straight up. There may be any number of pieces on the board (from 1 to 121). Note that pieces of different colors are not represented differently.
Output
The maximum length of a legal hop, using any piece on the board. You may not visit the same place more than once (including the starting and ending positions). However, you may hop over the same piece more than once. If there is no legal hop, output 0. Do not consider whether there exists a legal non-hop move.
For example, the output to the setup described above is 3.
Input and output may be done through stdin and stdout, through command-line arguments, through function calls, or any similar method.
Test Cases
Input:
0100000010000000000000000100000000000000000000000000000001010010000000000000000000000101000000000000000000100000000100001

Output: 0 (no two pieces are next to each other)

Input:
0000000000111100000000011100000000011000000000100000000000000000000000000000000000000000000000000000000000000000000000000

Output: 1 (initial setup for one player in top-left corner)

I play this with my great aunt; we're both reasonably good. This is an interesting challenge.

Maybe you should specify more on how the input is stored/which bits go to where.

Which pieces can you "hop over"? The way my mom and I used to play, you can hop over any single piece in one of the 6 directions any distance away (to the opposite spot of the piece you hopped over) as long as there is no piece in the way of the path for that hop. Others play that you can only hop over adjacent pieces.

@TheDoctor I added a more detailed explanation.

Can you clarify a detail: am I allowed to occupy the same position twice? I assume I can't loop infinitely, but if I can hit a location moving left-right and then later hit it again moving up-left to down-right then it opens up possibilities.

Similarly, can you hop over the same piece twice? Not necessarily from the same starting point; if I am up-left from a piece and hop it, and later I am right of the piece, can I hop it again?

@DevonParsons "You may not visit the same place more than once." However, you may hop over the same piece more than once.

@DevonParsons actually, it is impossible to hop over the same piece twice. The hopping man can only move 2 spaces at a time, which restricts him to a quarter of the cells on the board. This in turn means he can only ever hop over the same piece in one of the three axes of the board. The only choice he has, is that depending on how he approaches it, there may exist paths where he can hop over it forwards and others where he can hop over it backwards.

Perl, 345 322
Edit: golfed, slightly.
More test cases would be nice, but for now it looks like it works. I'll add comments later if necessary. With newlines and indentation for readability:
$_=<>;
$s=2x185;
substr$s,(4,22,unpack'C5(A3)*','(:H[n129148166184202220243262281300')[$i++],0,$_
    for unpack A.join A,1..4,13,12,11,10,9..13,4,3,2,1;
$_=$s;
sub f{
    my(@a,%h)=@_;
    $h{$_}++&&return for@a;
    $-+=$#a>$-;
    $s=~/^.{$a[0]}$_/&&f($+[1],@a)
        for map{("(?=.{$_}1.{$_}(0))","(?<=(0).{$_}1.{$_}.)")}0,17,18
}
f$+[0]while/1/g;
print$-

I added a couple of test cases.

Those work OK, but they are too easy :-).

C,262 260
Golfed code (debugging code and unnecessary whitespace removed. Changed from input via stdin to input via command line, and took advantage of the opportunity to declare variable i there. Latest edit: code moved into brackets of for loops to save two semicolons.)
t[420],j,l,x,y;f(p,d){int z,q,k;for(k=6;k--;t[q]&!t[p+z]?t[q]=0,f(q,d+1),t[q]=1:0)z="AST?-,"[k]-64,q=p+z*2;l=d>l?d:l;}main(int i,char**s){for(i=840;i--;x>3&y>5&x+y<23|x<13&y<15&x+y>13?i>420?t[i-420]=49-s[1][j++]:t[i]||f(i,0):0)x=i%20,y=i/20%21;printf("%d",l);}

Explanation
This relies on a 20x21 board which looks like this, initially filled with zeroes when the program starts (this ASCII art was generated by a modified version of the program, and as the i loop counts downwards, zero is in the bottom right corner):
....................
....................
...............#....
..............##....
.............###....
............####....
.......#############
.......############.
.......###########..
.......##########...
.......#########....
......##########....
.....###########....
....############....
...#############....
.......####.........
.......###..........
.......##...........
.......#............
....................
....................

Loop i runs through this board twice, using x and y to calculate whether a square actually belongs to the checkerboard or not (this requires 6 separate inequalities in x and y.)
If it does, the first time round it fills the squares, putting a 0 (falsy) for a 1 (occupied) and a 1 (truthy) for a 0 (unoccupied). This inversion is important, because all out-of-bounds squares already contain a 0, which means they resemble occupied squares and it is clear they can't be jumped into, without the need for a specific check.
The second time round, if the square is occupied (contains 0) it calls the function f that searches for the moves.
f searches recursively in the 6 possible directions encoded by +/-1 (horizontal), +/-20 (vertical) and +/-19 (diagonal) encoded in the expression "AST?-,"[k]-64. When it finds a hit, it sets that cell to a 0 (occupied) before calling itself recursively, then sets it back to 1 (empty) when the function is returned. The cell value must be changed before the recursive call to prevent hopping into that cell more than once.
Ungolfed code
char s[999];                           //input string.
t[420],i,j,l,x,y;                      //t=board. i=board counter, j=input counter. l=length of longest hop found so far.

f(p,d){                                //p=position, d= recursion depth.
  //printf("%d,%d ",p,d);              //debug code: uncomment to show the nodes visited.
  int k,z,q;                           //k=counter,z=displacement,q=destination
  for(k=6;k--;)                        //for each direction
    z="AST?-,"[k]-64,                  //z=direction
    q=p+z*2,                           //q=destination cell
    t[q]&!t[p+z]?                      //if destination cell is empty (and not out of bounds) and intervening cell is full
      t[q]=0,f(q,d+1),t[q]=1           //mark destination cell as full, recurse, then mark it as empty again.
      :0;
  l=d>l?d:l;                           //if d exceeds the max recorded recursion depth, update l
}

main(){
  gets(s);                             //get input
  for(i=840;i--;)                      //cycle twice through t
    x=i%20,                            //get x
    y=i/20%21,                         //and y coordinates
    x>3&y>5&x+y<23|x<13&y<15&x+y>13?   //if they are in the bounds of the board
      i>420?
        t[i-420]=49-s[j++]             //first time through the array put 0 for a 1 and a 1 for a 0 ('1'=ASCII49)
        :t[i]||f(i,0)                  //second time, if t[i]=0,call f().
       //,puts("")                     //puts() formats debug output to 1 line per in-bounds cell of the board
      :0;
  printf("%d",l);                      //print output
}