text:
King of the Hill: Speed Clue AI
Speed Clue
Cluedo/Clue is a classic board game with a compelling deduction gameplay
component.  Speed Clue is a 3-6 player variant that emphasizes this component by
using only the cards.  The result is that the only difference between standard
Cluedo and Speed Clue is that each player still in the game may make any
suggestion he pleases on his turn instead of waiting to reach a specific room at
the mercy of dice rolls and other players' suggestions.  If you have never
played Cluedo before, or want to be certain of the explicit differences between
the two versions, you may find a complete Speed Clue rule set here.

Goal
Write and submit an AI program to play Speed Clue before 15 May 2014 00:00 GMT.
After that time, I will run a tournament using all the legal entries.  The
entrant whose AI wins the most games in the tournament wins the challenge.

AI Specifications
You can write your AI in pretty much any language you choose, using whatever
techniques you use, so long as it strictly uses the application protocol
over a TCP/IP connection to play games with the server.  A detailed explanation
of all the restrictions can be found here.

How to Play
Start by forking the contest GitHub repository.  Add a directory under the
entries directory named using your StackExchange user name, and develop
your code in that folder.  When you are ready to submit your entry, make a pull
request with your revisions, then follow these instructions for announcing
your entry on this site.
I have provided some code and JARs in the core directory for getting you
started; see my site for a rough guide for the materials.  In addition,
other players are submitting helper code in addition to their entries to help
you get up and running.  Take some time to explore the entries, and don't forget
to test your entry against others' entries before submitting!

Results
Place | User         | AI                 | Result
------+--------------+--------------------+-------------------------------------------------------
    1 | gamecoder    | SpockAI            | 55.75%
    2 | Peter Taylor | InferencePlayer    | 33.06%
    3 | jwg          | CluePaddle         | 20.19%
    4 | Peter Taylor | SimpleCluedoPlayer |  8.34%
    5 | gamecoder    | RandomPlayer       |  1.71%
 ---- | ray          | 01                 | Player "ray-01" [3] sent an invalid accuse message: ""

The results above show the win percentage each qualified AI had of the 25,200 valid matches in which it participated.  There were 30,000 matches in total that counted toward the results, and 6,100 or so that were discounted when 01 was disqualified.
An honorable mention needs to go to ray's 01 AI.  My initial testing showed that it was the strongest, and I expected it to win the competition.  However, it appears to have a very intermittent bug that, as far as I can guess, leads it to eliminate all possible solutions.  The tournament had finished all the three-player matches and had started the four player matches (12,000 games in!) when 01's bug was revealed.  If I just consider the 3-player match standings, the results look like this:
Place | User         | AI                 | Result
------+--------------+--------------------+--------
    1 | ray          | 01                 | 72.10%
    2 | gamecoder    | SpockAI            | 51.28%
    3 | Peter Taylor | InferencePlayer    | 39.97%
    4 | Peter Taylor | SimpleCluedoPlayer | 17.65%
    5 | jwg          | CluePaddle         | 16.92%
    6 | gamecoder    | RandomPlayer       |  2.08%

I had planned on doing some data mining on the results, but I am exhausted.  I had technical difficulties in getting the competition to run all the way through (power failures, system reboots) that necessitated completely rewriting the contest server to save its progress as it proceeded.  I will comment and commit all the changes to the code with all the results files that were generated in case anyone is still interested.  If I decide to do the data mining as well, my results will also be added to the repository.

Thanks for Playing!

Can you make a copy of your server available for entrants to test against?

you must accept two port numbers: the first will be the port to which your program will listen, and the second will be the port to which your program will send., Why two ports?

@PeterTaylor, I will make a copy of the server available as soon as I have written it.  Why do you think I am giving a month?  ;)

@Hasturkun, The architecture I have planned for the server is that it will start your submissions via command line.  It will choose which port each program will use to send it messages so that it can easily identify which program is which (note that the protocol does not include any identifiers).  In addition, each program needs to know to which port to send messages so that the server can actually receive messages.  These are the two ports that each submission must receive as command line arguments.

@gamecoder: You can easily use one TCP/IP connection (i.e. the listener opened by the submission) and send/receive on that. Having two is redundant.

@Hasturkun: You are right, but I think you mistake my meaning.  I don't mean that your program should OPEN two ports.  I mean that your program should open a socket, bind it to the port 127.0.0.1:ARG1, and use that socket to send to the port 127.0.0.1:ARG2.  My server will be able to receive messages using its socket bound to 127.0.0.1:ARG2 and determine from the sender's address whose program sent it.  However, I am new enough to network programming that I am willing to redesign if there is a mistake with this approach.

Hasturkun has a good point. If you supply only the server's port, the client can open a connection to that port without specifying its local port, and the OS will assign it a free one. This simplifies the server programming a bit, because it doesn't have to worry about race conditions between when it checks that a port number is free and when the client opens its connection. You could make the identifier be a command-line argument instead and disqualify any entry which fakes its ID.

Race conditions are a good reason to change the requirements.  I will change the specifications accordingly.

If you're new to network programming, all the clients are running locally, and you've got a simple message/response protocol, why not use UDP instead? It fits with your expectation that the server specifies listen ports for clients too.

The only networking program I have written uses UDP.  I decided to use TCP/IP to (1) get to understand any differences between the two and (2) to use the technology that best supports the lock-step player updates I need for this to work.

If you are running the players locally from the server, why not just use their stdin/stdout to communicate ? I think this would make it much easier for everyone.

Handling external processes with Java is a bit trickier than you might hope. I can't finish a game with 4 RandomPlayers because they block when their stdout buffers fill up. Easy workaround: add a line to RandomPlayer.main: System.setOut(new PrintStream("player"+args[0]+".log"));. Proper fix: make TestServer set a thread going for each process it spawns which reads its stdout.

@SirDarius I looked up how to get programs to use each other's stdin/stdout for communication.  I've never done it before, and I feel a bit embarrassed how easy Java makes it.  I am considering switching to your approach, but currently I don't know how many (any?) want to participate in the contest anyway.  Switching to a stdin/stdout approach is only worth it to me if it will encourage more people to join.

@PeterTaylor I don't understand the issue or your proposed fixes (but that might be because it always works for me :P).  The Java documentation says that Runtime.exec() launches a new Process, and the Process documentations says that it's an encapsulation of a system native process.  There should be no need to further wrap it in a thread.  As for the stdout buffer filling (if that is happening), would it not be sufficient to add System.out.flush() calls?

@PeterTaylor >_< Reading just a little bit further into Process's documentation revealed a warning about child process buffers.  I guess I got lucky by designing my commands to specifically launch in a Windows cmd program.  Mm, humble pie.  I will write a fix for the TestServer and post it on my site later today.

The Process API doc says "failure to promptly write the input stream or read the output stream of the subprocess may cause the subprocess to block, or even deadlock". See e.g. When Runtime.exec() won't for more discussion. On a separate issue, it would be useful if the disprove server->client message included the index of the suggesting player: that simplifies tracking whom I've shown what.

That is a grievous mistake in the protocol.  I will first fix the TestServer and RandomPlayer, then I will modify the rules.  If you want to quickly hack the TestServer so you can get going without waiting on me, the protocol will be disprove player Suspect Weapon Room.

let us continue this discussion in chat

Can two different players make the same suggestion?

One player may not make the same suggestion twice, but other players may make that suggestion if they have not already.  In real Clue, a player making the same suggestion again is legal but a mistake, since nobody will learn anything new.  AIs, however, might decide to use that as a tactic to try to stall other players from learning anything if it thinks another player is closer to winning than it is.  I added this rule to prevent a deadlock situation in which all the players are trying to keep all the other players from learning anything new.

Do we have response time limit ?

@Ray, I will need to add a time limit before the contest ends, but I am hoping to see more entries in different languages before choosing it. If you're thinking of making an approach that brute-forces hand/solution combination analysis or something else time consuming, you should probably make sure that the number of combinations that will be tried is reasonably low (less than 1e9?).

I think 2~5 seconds per turn will be a proper limit.

Before I started this contest, I was working on a Python Clue solver (I was starting to translate it into Java when Peter Taylor put his InferencePlayer up o_q ).  It is really strong, but tends to take a few minutes to decide its first suggestion XD  5 seconds would kick its butt.

@gamecoder, I'm working on a Python solution. I've read the server code and found that you use a 512 buffer to read the socket instead of using in.readLine(). It doesn't make sense for me, and my program always block. Is this some Java convention? Please consider changing to use the normal line by line message exchanging. I've modified both the server and AI code and will fire a pull request.

@Ray, what's wrong with using the BSD socket socket.recv?  Since I had only used Winsock (based on BSD) when I created this protocol, the C implementation of this function is what I had in mind.

@gamecoder, socket.recv(512) may block until it read 512 bytes(not always, I don't know the details). So when the server send a message(20 bytes) to the AI, the AI may continue to wait for more bytes while the server think it should response something.

You can specify non-blocking mode, though that might have to loop.  Please determine for certain that Python cannot work with this protocol before I change it.  I'd rather not set back the people who have already written their network message handling if it can be avoided.

I'm afraid that non-blocking mode won't help here since we don't have an explicit separator between messages. The TCP socket work as duplex data stream, so logically this protocol won't work well. Actually only several lines are modified. I've also adapted Peter's solution to work with the new protocol.

@Ray, I'm working on a Python network interface for the Python Clue solver I had been working on that inspired this contest.  This is probably due to my inexperience, but I have been having a lot of trouble getting Python to work the way I want.  If I try to launch Python in a command window, it seems the cmd strangles the socket (which makes no sense).  If I run it separately, recv() and sendall seem to work fine, but then Python seems to hang in the middle of code that I know works.  I have tried to determine whether Java's stdout consumption is the problem, but I have no answers...

This is a long way to say that I can neither confirm nor deny that the protocol needs to change.  Could you make a pull request on the repo with your Python interface code if it successfully plays through?

@Ray, I got the Python network interface working.  The Python code to use sockets is quite simple and avoids the need to have a terminating character.  I will not change the protocol at this time.  I have closed the issue and pull in the repo without accepting the changes.

@gamecoder I've made a pull request about the python interface. It may attract more people on this site to join(hopefully). Also, I'm going to start a bounty for this interesting problem.

@gamecoder: It looks like an AI never knows if a suggest is made and someone else disprove it (or even if the AI implicitly disproves it by having only one of the cards).  This is important information when playing Clue.

... have you read the suggestion protocol?

@gamecoder There is a better approach to preventing the 'all AIs stalling' problem, which is to add another item to the protocol. If one complete round passes where all players pass, then the server sends a message requesting a suggestion volunteer, waiting for the response, and after a small timeout then randomly selecting one player, and sending a message that they are required to play a valid suggestion.

Anyone want to try writing an AI that will collude with other instances of itself in the same game?

Did AI01 of the #14 pull request still crash ?

@Ray, Unfortunately, yes.  I tried the tournament first with #13 and then with #14.  The results I mention above are for #14.

SpockAI
Identifier: gamecoder-SpockAI
Repo Entry: click here
Selected: Yes
Technology: Java 7 based upon com.sadakatsu.clue.jar
Arguments: {identifier} portNumber [logOutput: true|false]
Description:
SpockAI is a Speed Clue player built upon a class called Knowledge that I wrote.  The Knowledge class represents all the possible states that the game could have given what has happened thus far.  It represents the game's solutions and players' possible hands as sets, and uses iterative deductions to reduce these sets as far as possible every time something is learned.  SpockAI uses this class to determine which suggestions are assured to have the most helpful worst-case results and randomly selects one of those suggestions on its turns.  When it needs to disprove a suggestion, it tries to either show a card it has already shown the suggesting AI or to show it a card from the category for which it has reduced the possibilities the least.  It only makes an accusation when it knows the solution.
The heuristic I used for determining the best suggestion is as follows.  After all information has been learned from a suggestion, the possible solution and possible player hand sets will have been reduced (unless the suggestion reveals no new information).  Theoretically, the best suggestion is the one that most reduces the number of possible solutions.  In the case of a tie, I assume that a suggestion that most reduces the number of possible hands for players is better.  So, for each suggestion, I try every possible outcome that does not lead to a contradiction in knowledge.  Whichever outcome has the least improvement in solution/hand counts is assumed to be the result the suggestion will have.  Then I compare all the suggestions' results, and pick which one has the best result.  In this way, I guarantee optimal worst-case information gain.
I am considering adding a brute force combination analysis of possible solutions and possible player hands to make SpockAI even stronger, but since SpockAI is already the slowest, most resource-intensive entry, I will probably skip that.
Disclaimer:
I had intended to release an AI for this contest weeks ago.  As it stands, I wasn't able to start writing my AI until Friday last week, and I kept finding ridiculous bugs in my code.  Because of this, the only way I was able to get SpockAI to work before the deadline was to use a large thread pool.  The end result is that (currently) SpockAI can hit +90% CPU utilization and 2GB+ memory usage (though I blame the garbage collector for this).  I intend to run SpockAI in the contest, but if others feel that is a violation of the rules, I will award the title of "winner" to second place should SpockAI win.  If you you feel this way, please leave a comment to that effect on this answer.

AI01 - Python 3
I can't find a better name for it yet :-P .
Identifier: ray-ai01
Technology: Python 3
Selected: yes
Arguments: ai01.py identifier port
Description: Work by inference. When the number of cards that the owner is not known is less than a threshold, this AI starts to eliminate all impossible solutions by recursive global inference. Otherwise, it use local inference.
#!/usr/bin/env python
import itertools

from speedclue.playerproxy import Player, main
from speedclue.cards import CARDS
from speedclue.protocol import BufMessager

# import crash_on_ipy

class Card:
    def __init__(self, name, type):
        self.name = name
        self.possible_owners = []
        self.owner = None
        self.in_solution = False
        self.disproved_to = set()
        self.type = type

    def __repr__(self):
        return self.name

    def log(self, *args, **kwargs):
        pass

    def set_owner(self, owner):
        assert self.owner is None
        assert self in owner.may_have
        for player in self.possible_owners:
            player.may_have.remove(self)
        self.possible_owners.clear()
        self.owner = owner
        owner.must_have.add(self)
        self.type.rest_count -= 1

    def set_as_solution(self):
        # import pdb; pdb.set_trace()
        assert self.owner is None
        self.type.solution = self
        self.in_solution = True
        for player in self.possible_owners:
            player.may_have.remove(self)
        self.possible_owners.clear()
        self.type.rest_count -= 1

    def __hash__(self):
        return hash(self.name)

class CardType:
    def __init__(self, type_id):
        self.type_id = type_id
        self.cards = [Card(name, self) for name in CARDS[type_id]]
        self.rest_count = len(self.cards)
        self.solution = None

class PlayerInfo:
    def __init__(self, id):
        self.id = id
        self.must_have = set()
        self.may_have = set()
        self.selection_groups = []
        self.n_cards = None

    def __hash__(self):
        return hash(self.id)

    def set_have_not_card(self, card):
        if card in self.may_have:
            self.may_have.remove(card)
            card.possible_owners.remove(self)

    def log(self, *args, **kwargs):
        pass

    def update(self):
        static = False
        updated = False
        while not static:
            static = True
            if len(self.must_have) == self.n_cards:
                if not self.may_have:
                    break
                for card in self.may_have:
                    card.possible_owners.remove(self)
                self.may_have.clear()
                static = False
                updated = True
            if len(self.must_have) + len(self.may_have) == self.n_cards:
                static = False
                updated = True
                for card in list(self.may_have):
                    card.set_owner(self)

            new_groups = []
            for group in self.selection_groups:
                group1 = []
                for card in group:
                    if card in self.must_have:
                        break
                    if card in self.may_have:
                        group1.append(card)
                else:
                    if len(group1) == 1:
                        group1[0].set_owner(self)
                        updated = True
                        static = False
                    elif group1:
                        new_groups.append(group1)
            self.selection_groups = new_groups

            if len(self.must_have) + 1 == self.n_cards:
                # There is only one card remain to be unknown, so this card must
                # be in all selection groups
                cards = self.may_have.copy()
                for group in self.selection_groups:
                    if self.must_have.isdisjoint(group):
                        cards.intersection_update(group)

                for card in self.may_have - cards:
                    static = False
                    updated = True
                    self.set_have_not_card(card)

        # assert self.must_have.isdisjoint(self.may_have)
        # assert len(self.must_have | self.may_have) >= self.n_cards
        return updated

class Suggestion:
    def __init__(self, player, cards, dplayer, dcard):
        self.player = player
        self.cards = cards
        self.dplayer = dplayer
        self.dcard = dcard
        self.disproved = dplayer is not None

class AI01(Player):
    def prepare(self):
        self.set_verbosity(0)

    def reset(self, player_count, player_id, card_names):
        self.log('reset', 'id=', player_id, card_names)
        self.fail_count = 0
        self.suggest_count = 0
        self.card_types = [CardType(i) for i in range(len(CARDS))]
        self.cards = list(itertools.chain(*(ct.cards for ct in self.card_types)))
        for card in self.cards:
            card.log = self.log
        self.card_map = {card.name: card for card in self.cards}
        self.owned_cards = [self.card_map[name] for name in card_names]
        self.players = [PlayerInfo(i) for i in range(player_count)]
        for player in self.players:
            player.log = self.log
        self.player = self.players[player_id]
        for card in self.cards:
            card.possible_owners = list(self.players)
        n_avail_cards = len(self.cards) - len(CARDS)
        for player in self.players:
            player.may_have = set(self.cards)
            player.n_cards = n_avail_cards // player_count \
                + (player.id < n_avail_cards % player_count)
        for card in self.owned_cards:
            card.set_owner(self.player)
        for card in self.cards:
            if card not in self.owned_cards:
                self.player.set_have_not_card(card)
        self.suggestions = []
        self.avail_suggestions = set(itertools.product(*CARDS))
        self.possible_solutions = {
            tuple(self.get_cards_by_names(cards)): 1
            for cards in self.avail_suggestions
        }
        self.filter_solutions()

    def filter_solutions(self):
        new_solutions = {}
        # assert self.possible_solutions
        join = next(iter(self.possible_solutions))
        for sol in self.possible_solutions:
            for card, type in zip(sol, self.card_types):
                if card.owner or type.solution and card is not type.solution:
                    # This candidate can not be a solution because it has a
                    # card that has owner or this type is solved.
                    break
            else:
                count = self.check_solution(sol)
                if count:
                    new_solutions[sol] = count
                    join = tuple(((x is y) and x) for x, y in zip(join, sol))
        self.possible_solutions = new_solutions
        updated = False
        for card in join:
            if card and not card.in_solution:
                card.set_as_solution()
                updated = True
                self.log('found new target', card, 'in', join)

        # self.dump()
        return updated

    def check_solution(self, solution):
        """
        This must be called after each player is updated.
        """
        players = self.players
        avail_cards = set(card for card in self.cards if card.possible_owners)
        avail_cards -= set(solution)
        if len(avail_cards) >= 10:
            return 1
        count = 0

        def resolve_player(i, avail_cards):
            nonlocal count
            if i == len(players):
                count += 1
                return
            player = players[i]
            n_take = player.n_cards - len(player.must_have)
            cards = avail_cards & player.may_have
            for choice in map(set, itertools.combinations(cards, n_take)):
                player_cards = player.must_have | choice
                for group in player.selection_groups:
                    if player_cards.isdisjoint(group):
                        # Invalid choice
                        break
                else:
                    resolve_player(i + 1, avail_cards - choice)

        resolve_player(0, avail_cards)
        return count

    def suggest1(self):
        choices = []
        for type in self.card_types:
            choices.append([])
            if type.solution:
                choices[-1].extend(self.player.must_have & set(type.cards))
            else:
                choices[-1].extend(sorted(
                    (card for card in type.cards if card.owner is None),
                    key=lambda card: len(card.possible_owners)))

        for sgi in sorted(itertools.product(*map(lambda x:range(len(x)), choices)),
                key=sum):
            sg = tuple(choices[i][j].name for i, j in enumerate(sgi))
            if sg in self.avail_suggestions:
                self.avail_suggestions.remove(sg)
                break
        else:
            sg = self.avail_suggestions.pop()
            self.fail_count += 1
            self.log('fail')
        self.suggest_count += 1
        return sg

    def suggest(self):
        sg = []
        for type in self.card_types:
            card = min((card for card in type.cards if card.owner is None),
                key=lambda card: len(card.possible_owners))
            sg.append(card.name)
        sg = tuple(sg)

        if sg not in self.avail_suggestions:
            sg = self.avail_suggestions.pop()
        else:
            self.avail_suggestions.remove(sg)
        return sg

    def suggestion(self, player_id, cards, disprove_player_id=None, card=None):
        sg = Suggestion(
            self.players[player_id],
            self.get_cards_by_names(cards),
            self.players[disprove_player_id] if disprove_player_id is not None else None,
            self.card_map[card] if card else None,
        )
        self.suggestions.append(sg)
        # Iter through the non-disproving players and update their may_have
        end_id = sg.dplayer.id if sg.disproved else sg.player.id
        for player in self.iter_players(sg.player.id + 1, end_id):
            if player is self.player:
                continue
            for card in sg.cards:
                player.set_have_not_card(card)
        if sg.disproved:
            # The disproving player has sg.dcard
            if sg.dcard:
                if sg.dcard.owner is None:
                    sg.dcard.set_owner(sg.dplayer)
            else:
                # Add a selection group to the disproving player
                sg.dplayer.selection_groups.append(sg.cards)
            self.possible_solutions.pop(tuple(sg.cards), None)

        self.update()

    def update(self):
        static = False
        while not static:
            static = True
            for card in self.cards:
                if card.owner is not None or card.in_solution:
                    continue
                if len(card.possible_owners) == 0 and card.type.solution is None:
                    # In solution
                    card.set_as_solution()
                    static = False

            for type in self.card_types:
                if type.solution is not None:
                    continue
                if type.rest_count == 1:
                    card = next(card for card in type.cards if card.owner is None)
                    card.set_as_solution()
                    static = False

            for player in self.players:
                if player is self.player:
                    continue
                if player.update():
                    static = False

            if self.filter_solutions():
                static = False

    def iter_players(self, start_id, end_id):
        n = len(self.players)
        for i in range(start_id, start_id + n):
            if i % n == end_id:
                break
            yield self.players[i % n]

    def accuse(self):
        if all(type.solution for type in self.card_types):
            return [type.solution.name for type in self.card_types]
        possible_solutions = self.possible_solutions
        if len(possible_solutions) == 1:
            return next(possible_solutions.values())
        # most_possible = max(self.possible_solutions, key=self.possible_solutions.get)
        # total = sum(self.possible_solutions.values())
        # # self.log('rate:', self.possible_solutions[most_possible] / total)
        # if self.possible_solutions[most_possible] > 0.7 * total:
        #     self.log('guess', most_possible)
        #     return [card.name for card in most_possible]
        return None

    def disprove(self, suggest_player_id, cards):
        cards = self.get_cards_by_names(cards)
        sg_player = self.players[suggest_player_id]
        cards = [card for card in cards if card in self.owned_cards]
        for card in cards:
            if sg_player in card.disproved_to:
                return card.name
        return max(cards, key=lambda c: len(c.disproved_to)).name

    def accusation(self, player_id, cards, is_win):
        if not is_win:
            cards = tuple(self.get_cards_by_names(cards))
            self.possible_solutions.pop(cards, None)
            # player = self.players[player_id]
            # for card in cards:
            #     player.set_have_not_card(card)
            # player.update()
        else:
            self.log('fail rate:', self.fail_count / (1e-8 + self.suggest_count))
            self.log('fail count:', self.fail_count, 'suggest count:', self.suggest_count)

    def get_cards_by_names(self, names):
        return [self.card_map[name] for name in names]

    def dump(self):
        self.log()
        for player in self.players:
            self.log('player:', player.id, player.n_cards,
                sorted(player.must_have, key=lambda x: x.name),
                sorted(player.may_have, key=lambda x: x.name),
                '\n    ',
                player.selection_groups)
        self.log('current:', [type.solution for type in self.card_types])
        self.log('possible_solutions:', len(self.possible_solutions))
        for sol, count in self.possible_solutions.items():
            self.log('  ', sol, count)
        self.log('id|', end='')

        def end():
            return ' | ' if card.name in [g[-1] for g in CARDS] else '|'

        for card in self.cards:
            self.log(card.name, end=end())
        self.log()
        for player in self.players:
            self.log(' *'[player.id == self.player.id] + str(player.id), end='|')
            for card in self.cards:
                self.log(
                    ' ' + 'xo'[player in card.possible_owners or player is card.owner],
                    end=end())
            self.log()

if __name__ == '__main__':
    main(AI01, BufMessager)

The AI code can be found here.

Could you make a pull request with your AI?  I'd like to get it into the contest repo.

@gamecoder I've made a stronger AI01 and sent a pull request.

As things currently stand, your 01 is the strongest.  In the trials I run, it consistently wins ~67% of the matches in which it competes.  I'm hoping we'll see some solid entries before the contest ends that can challenge it.

Check out my SpockAI.  It performs pretty well against 01.  I don't know whether it will win the competition, but I'm glad to see your win count reduced  ; )

@gamecoder Actually, I've updated my AI several days ago according to the new rules. I'm glad to see your new entry. It seems to perform well but I didn't test it many times due to it's inefficient. Maybe you can make it faster so that we are easier to test.

Ha ha... this contest has been reminding me of my limitations as a programmer. To make SpockAI more efficient, I'd need a completely different algorithm. I don't have any other ideas. You could try testing my AI on a processor with 12 cores like the one I'll run the contest on? {: )

SimpleCluedoPlayer.java
This class uses AbstractCluedoPlayer, which handles all the I/O and lets the logic work with a simple typed interface. The whole thing is on github.
This beats the random player with high probability (in the worst case it takes 15 suggestions, whereas the random player takes an average of 162), but it will be easily beaten. I offer it to get the ball rolling.
package org.cheddarmonk.cluedoai;

import java.io.IOException;
import java.io.PrintStream;
import java.net.UnknownHostException;
import java.util.*;

/**
 * A simple player which doesn't try to make inferences from partial information.
 * It merely tries to maximise the information gain by always making suggestions involving cards which
 * it does not know to be possessed by a player, and to minimise information leakage by recording who
 * has seen which of its own cards.
 */
public class SimpleCluedoPlayer extends AbstractCluedoPlayer {
    private Map<CardType, Set<Card>> unseenCards;
    private Map<Card, Integer> shownBitmask;
    private Random rnd = new Random();

    public SimpleCluedoPlayer(String identifier, int serverPort) throws UnknownHostException, IOException {
        super(identifier, serverPort);
    }

    @Override
    protected void handleReset() {
        unseenCards = new HashMap<CardType, Set<Card>>();
        for (Map.Entry<CardType, Set<Card>> e : Card.byType.entrySet()) {
            unseenCards.put(e.getKey(), new HashSet<Card>(e.getValue()));
        }

        shownBitmask = new HashMap<Card, Integer>();
        for (Card myCard : myHand()) {
            shownBitmask.put(myCard, 0);
            unseenCards.get(myCard.type).remove(myCard);
        }
    }

    @Override
    protected Suggestion makeSuggestion() {
        return new Suggestion(
            selectRandomUnseen(CardType.SUSPECT),
            selectRandomUnseen(CardType.WEAPON),
            selectRandomUnseen(CardType.ROOM));
    }

    private Card selectRandomUnseen(CardType type) {
        Set<Card> candidates = unseenCards.get(type);
        Iterator<Card> it = candidates.iterator();
        for (int idx = rnd.nextInt(candidates.size()); idx > 0; idx--) {
            it.next();
        }
        return it.next();
    }

    @Override
    protected Card disproveSuggestion(int suggestingPlayerIndex, Suggestion suggestion) {
        Card[] byNumShown = new Card[playerCount()];
        Set<Card> hand = myHand();
        int bit = 1 << suggestingPlayerIndex;
        for (Card candidate : suggestion.cards()) {
            if (!hand.contains(candidate)) continue;

            int bitmask = shownBitmask.get(candidate);
            if ((bitmask & bit) == bit) return candidate;
            byNumShown[Integer.bitCount(bitmask)] = candidate;
        }

        for (int i = byNumShown.length - 1; i >= 0; i--) {
            if (byNumShown[i] != null) return byNumShown[i];
        }

        throw new IllegalStateException("Unreachable");
    }

    @Override
    protected void handleSuggestionResponse(Suggestion suggestion, int disprovingPlayerIndex, Card shown) {
        if (shown != null) unseenCards.get(shown.type).remove(shown);
        else {
            // This player never makes a suggestion with cards from its own hand, so we're ready to accuse.
            unseenCards.put(CardType.SUSPECT, Collections.singleton(suggestion.suspect));
            unseenCards.put(CardType.WEAPON, Collections.singleton(suggestion.weapon));
            unseenCards.put(CardType.ROOM, Collections.singleton(suggestion.room));
        }
    }

    @Override
    protected void recordSuggestionResponse(int suggestingPlayerIndex, Suggestion suggestion, Card shown) {
        shownBitmask.put(shown, shownBitmask.get(shown) | (1 << suggestingPlayerIndex));
    }

    @Override
    protected void recordSuggestionResponse(int suggestingPlayerIndex, Suggestion suggestion, int disprovingPlayerIndex) {
        // Do nothing.
    }

    @Override
    protected Suggestion makeAccusation() {
        Set<Card> suspects = unseenCards.get(CardType.SUSPECT);
        Set<Card> weapons = unseenCards.get(CardType.WEAPON);
        Set<Card> rooms = unseenCards.get(CardType.ROOM);
        if (suspects.size() * weapons.size() * rooms.size()  == 1) {
            return new Suggestion(suspects.iterator().next(), weapons.iterator().next(), rooms.iterator().next());
        }

        return null;
    }

    @Override
    protected void recordAccusation(int accusingPlayer, Suggestion accusation, boolean correct) {
        // Do nothing.
    }

    //*********************** Public Static Interface ************************//
    public static void main(String[] args) throws Exception {
        try {
            System.setOut(new PrintStream("/tmp/speed-cluedo-player" + args[0]+".log"));
            new SimpleCluedoPlayer(args[0], Integer.parseInt(args[1])).run();
        } catch (Throwable th) {
            th.printStackTrace(System.out);
        }
    }
}

Very nice, clean code.  I doubt anyone looking at the test server or random player feel that way.  I also think that you can't have a simpler AI than this  ^_^

InferencePlayer.java
Full code on Github (note: this uses the same AbstractCluedoPlayer as my earlier SimpleCluedoPlayer).
The true core of this player is its PlayerInformation class (here slightly trimmed):
private static class PlayerInformation {
    final PlayerInformation[] context;
    final int playerId;
    final int handSize;
    Set<Integer> clauses = new HashSet<Integer>();
    Set<Card> knownHand = new HashSet<Card>();
    int possibleCards;
    boolean needsUpdate = false;

    public PlayerInformation(PlayerInformation[] context, int playerId, boolean isMe, int handSize, Set<Card> myHand) {
        this.context = context;
        this.playerId = playerId;
        this.handSize = handSize;
        if (isMe) {
            knownHand.addAll(myHand);
            possibleCards = 0;
            for (Card card : knownHand) {
                int cardMask = idsByCard.get(card);
                clauses.add(cardMask);
                possibleCards |= cardMask;
            }
        }
        else {
            possibleCards = allCardsMask;
            for (Card card : myHand) {
                possibleCards &= ~idsByCard.get(card);
            }

            if (playerId == -1) {
                // Not really a player: this represents knowledge about the solution.
                // The solution contains one of each type of card.
                clauses.add(suspectsMask & possibleCards);
                clauses.add(weaponsMask & possibleCards);
                clauses.add(roomsMask & possibleCards);
            }
        }
    }

    public void hasCard(Card card) {
        if (knownHand.add(card)) {
            // This is new information.
            needsUpdate = true;
            clauses.add(idsByCard.get(card));

            // Inform the other PlayerInformation instances that their player doesn't have the card.
            int mask = idsByCard.get(card);
            for (PlayerInformation pi : context) {
                if (pi != this) pi.excludeMask(mask);
            }

            if (knownHand.size() == handSize) {
                possibleCards = mask(knownHand);
            }
        }
    }

    public void excludeMask(int mask) {
        if (knownHand.size() == handSize) return; // We can't benefit from any new information.

        if ((mask & possibleCards) != 0) {
            // The fact that we have none of the cards in the mask contains some new information.
            needsUpdate = true;
            possibleCards &= ~mask;
        }
    }

    public void disprovedSuggestion(Suggestion suggestion) {
        if (knownHand.size() == handSize) return; // We can't benefit from any new information.

        // Exclude cards which we know the player doesn't have.
        needsUpdate = clauses.add(mask(suggestion.cards()) & possibleCards);
    }

    public void passedSuggestion(Suggestion suggestion) {
        if (knownHand.size() == handSize) return; // We can't benefit from any new information.

        excludeMask(mask(suggestion.cards()));
    }

    public boolean update() {
        if (!needsUpdate) return false;

        needsUpdate = false;

        // Minimise the clauses, step 1: exclude cards which the player definitely doesn't have.
        Set<Integer> newClauses = new HashSet<Integer>();
        for (int clause : clauses) {
            newClauses.add(clause & possibleCards);
        }
        clauses = newClauses;

        if (clauses.contains(0)) throw new IllegalStateException();

        // Minimise the clauses, step 2: where one clause is a superset of another, discard the less specific one.
        Set<Integer> toEliminate = new HashSet<Integer>();
        for (int clause1 : clauses) {
            for (int clause2 : clauses) {
                if (clause1 != clause2 && (clause1 & clause2) == clause1) {
                    toEliminate.add(clause2);
                }
            }
        }
        clauses.removeAll(toEliminate);

        // Every single-card clause is a known card: update knownHand if necessary.
        for (int clause : clauses) {
            if (((clause - 1) & clause) == 0) {
                Card singleCard = cardsById.get(clause);
                hasCard(cardsById.get(clause));
            }
        }

        // Every disjoint set of clauses of size equal to handSize excludes all cards not in the union of that set.
        Set<Integer> disjoint = new HashSet<Integer>(clauses);
        for (int n = 2; n <= handSize; n++) {
            Set<Integer> nextDisjoint = new HashSet<Integer>();
            for (int clause : clauses) {
                for (int set : disjoint) {
                    if ((set & clause) == 0) nextDisjoint.add(set | clause);
                }
            }
            disjoint = nextDisjoint;
        }

        for (int set : disjoint) excludeMask(~set);

        return true;
    }
}

It unifies information on suggestions which the player didn't disprove (indicating that they hold none of those cards), suggestions which they did disprove (indicating that they hold at least one of those cards), and cards whose location is certain. Then it iteratively applies some basic rules to compact that information into its essence.
I don't think there's any more deterministic information to be obtained (except from via false accusations, which I'm assuming to be too rare to bother with), although I may have overlooked something. There is potential for a more sophisticated player to estimate probabilities that player X has card Y...
The other area which probably admits significant improvement is in deciding which suggestion to make. I attempt to maximise the information gain using a fairly clunky heavy-force approach, but there's a lot of poorly justified heuristic in evaluating the relative merits of the knowledge gained from different hypothetical disproofs. However, I'm not going to try tuning the heuristics until someone else posts a worthy opponent.

I cannot get either your SimpleCluedoPlayer or your InferencePlayer to run.  I ran ant in the "SpeedClueContest/entries/peter_taylor/" directory and successfully generated the JARs.  I've tried relative and absolute paths to these JARs, passing them "identifier" and "portNumber" in that order, but the TestServer hangs waiting for the "identifier alive" message for each of them.  I looked for and cannot find "/tmp/speed-cluedo-player"+identifier+".log".  Have I messed up the process somehow?

@gamecoder, I probably shouldn't hard-code /tmp. It should be a simple patch; I'll look into it shortly.

Your fix works; I've merged it into the repo.  Now I get to read through InferencePlayer carefully to make sure there are enough differences between it and the LogicalAI I had started working on  >___<

Here comes your opponent :-)

@Ray, excellent. I'll try to dissect your AI and see how it differs from mine at some point: on a cursory glance, it seems to use a similar analysis.

@PeterTaylor, I hope you'll release come improvements before the deadline tonight!  Regardless, I wanted to thank you for your early interest and help that got this competition off the ground.

CluePaddle (ClueStick / ClueBat / ClueByFour) - C#
I have written ClueBot, a C# client for which it is straightforward to implement AIs, and various AIs, including the most serious attempt called CluePaddle. The code is at https://github.com/jwg4/SpeedClueContest/tree/clue_paddle with a pull request started to merge it into upstream.
ClueStick is a proof-of-concept which basically just guesses and ignores most of what happens. ClueBat is another stupid AI, except that it tries to exploit a flaw in ClueStick to force it to do false accusations. ClueByFour is a reasonable AI in that it makes reasonable suggestions and remembers the cards it is shown by others.
CluePaddle is the most intelligent. It tries to figure out who has what based not only on what disproofs have been offered, but also based on which players didn't offer a disproof of a given suggestion. It doesn't take into account how many cards each player has atm but this is to be fixed. It includes a couple of quite long classes so I won't post the whole code here, but the following method gives a flavor.
public void Suggestion(int suggester, MurderSet suggestion, int? disprover, Card disproof)
{
  List<int> nonDisprovers = NonDisprovers(suggester, disprover).ToList();

  foreach (var player in nonDisprovers)
  {
    m_cardTracker.DoesntHaveAnyOf(player, suggestion);
  }

  if (disprover != null && disproof == null)
  {
    // We know who disproved it but not what they showed.
    Debug.Assert(disprover != m_i, "The disprover should see the disproof");
    Debug.Assert(suggester != m_i, "The suggester should see the disproof");
    m_cardTracker.DoesntHaveAllOf(suggester, suggestion);
    m_cardTracker.HasOneOf((int)disprover, suggestion);
  }

  if (disproof != null)
  {
    // We know who disproved it and what they showed.
    Debug.Assert(disprover != null, "disproof is not null but disprover is null");
    m_cardTracker.DoesHave((int)disprover, disproof.Value);
  }
}

If the 4 play against each other, CluePaddle wins by far the most games, with ClueByFour second and the other two nowhere.
Only CluePaddle is a competitive entry (so far). Usage:
CluePaddle.exe identifier port

If anyone else wants to make a C# AI, just create a ConsoleApplication project in the soltution, implement the IClueAI interface in a class, and then make your Program derive from ProgramTemplate and copy what the other projects do for Main(). The only dependency is NUnit for unit testing and you could easily remove all the testing from the code (but don't, just install NUnit).

I have tried to compile your AIs and test them in the ContestServer (soon to be posted).  The CluePaddle project does not compile, claiming that NUnit is not installed even though the other projects do compile.  Those that do compile end up stalling during the testing, and Java reports a connection reset error.  Could you help me determine whether I may have done something wrong?

Correction: ClueStick is the only AI that stalls when I try to start it up.  The other two compete in the trial tournament and eventually get disqualified for the same violations.  ClueByFour gets disqualified for failing to repeat an undisproved suggestion it makes as an accusation when it does not hold any of the cards.  ClueBat gets disqualified for making accusations that has cards it has either been shown or has in its hand.  Please check out the revised AI restrictions to ensure compliance.

@gamecoder Do you have NUnit installed? If you can't install it I can conditionally remove the unit testing code. CluePaddle is my actual entry - I am not too worried about the violations by the other two since they are not really playing to win.

I also have some updates to CluePaddle. I will do a pull request for these later.

I did install NUnit.  I was able to explore its namespaces in MSVS using your other projects' references.  I'll look forward to your pull request.

Your latest pull request did fix CluePaddle; it runs.  However, if you have some time before the deadline, you might want to try improving it.  I find it does not perform very well : /

Thanks for your message @gamecoder. I realize that it can be beaten by all other serious attempts. However, this is my first entry to a CG challenge and I am happy to just participate, and to give something for others to train against.

Thanks for playing!  Every entry has made this content more worth the time I've spent on it.  I hope you had fun and will participate in more challenges.


text:
Maze Generation
I know there is an (old) thread similar to this (here), but I'd like to reboot it with some modifications.
The goal: generate a random-looking maze using an algorithm of your choice, then output the maze graphically (printing counts).

The width and height are determined by you.
There should be at least one path from at least one entrance to at least one exit.
The format of the maze (how you display it, mark entrance(s) or exit(s)) is up to you as well.
The prettier, the better.
Trivial mazes (e.g. blank mazes, lattice mazes, mazes of size 1x1) are discouraged.
Cycles in the maze are allowed and, are encouraged, if the result is reasonable.
Language abuse encouraged.
The maze should look reasonably random (but a completely deterministic (e.g. chaotic) algorithm that generates this is fine too).

Edit: the main focus here is on making the smallest possible implementation.  However, I want to allow some leeway within that constraint to encourage shininess.  I have deliberately left exactly what "features" the maze has open-ended, but as a rough guideline you should try to pack the most amount of bang into the least lexical buck.

What does "random-looking" mean? Can I get away without a single call to the rand()-equivalent of my function as long as the output looks like a mess?

Also "The prettier, the better" seems hardly tangible (or simply irrelevant) to a code-golf challenge. Maybe a popularity contest would be the better choices if you're interested in pretty results.

So is it really code-golf or is it rather popularity-contest?

As another suggestion, if you do want to incentivise both short codes and neat mazes, you could make it a code-challenge and declare that the winner will be selected by some score that is a mixture of code length and upvotes - although it'll be up to you to determine each answers total score, because including the current number of upvotes in the post is a bit useless.

I think each answer should explain what constitute entrances and exits in each maze (as well as, what's a wall and what's a passage), so that we can evaluate the 2nd bullet.

I want this to be a popularity-contest. We'll see more inventive mazes that way.

You should also remove the [code-golf] tag then. I'm not sure it's going to go over so well though, since there are multiple golfed entries already.

@Geobits I wouldn't mind too much, but hence my suggestion to actually make it a code-challenge with combined scoring from code length and votes. That would exactly encourage what the OP wants: short code for interesting mazes.

I wouldn't mind a change of scoring system either, this is supposed to be a bit of fun. However it can't stay as it is now with both code-golf and popularity-contest, those are incompatible and close votes will start because of the ambiguous winning criterion. If you want to consider both, a better way is a formula combining votes and bytes, like this question: http://codegolf.stackexchange.com/questions/23581/eiffel-tower-in-3d

I'm not going to make a troll answer here, but I don't think that anyone is going to beat this (assuming it is a code golf).

Matter of fact, if it uses that algorithm, it should be immediately downvoted (it does not guarantee a start and end point).

Having taken this far too seriously, I've now got 60 lines (2000 characters) of original Spectrum BASIC using a combination of Recursive backtracker and Hunter-Killer algorithms (http://www.astrolog.org/labyrnth/algrithm.htm), so no hope of winning a golf contest, but the mazes sure are purty.

@impinball it DOES guarantee start/endpoint. If you consider the blank area to be the path, any point on the edge of the maze leads trivially without branching to another point on the edge (theoretically all paths on the edge of the maze could be only 2 squares long but the odds of this happening are minuscule, you normally get some nice long random walks.) On the other hand if you consider the printed area as path, fairly large mazes are formed (corollary of the fact that they must be bounded by unprinted areas) and you get interesting mazes, as seen in my answer. The problem is picking one.

C: 265 253 Bytes
#define f(v)for(v=0;v<k;++v)
#define d(q,n)case q:r(c+n,c+2*n);
z[4225],i,j,k=65;r(p,c){if(!z[c]){z[p]=z[c]=1;f(p)switch(rand()%4){d(0,-k)d(1,k)d(2,-1)d(3,1)}}}main(){f(i)z[i]=z[i+4160]=z[i*k]=z[i*k+64]=z[4157]=1;r(67,132);f(i)f(j)putchar(33-z[i*k+j]);}

(Requires 65-character terminal) Generates a relatively random 31x31 maze with one guaranteed path from the entrance to exit.
Example output (with simulated 65-character terminal):
 ! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 !     !       !   !       !     !           !             !   !
 !!!!! !!! !!! ! !!! ! !!! ! !!! !!!!!!! !!! !!!!!!!!! !!! ! ! !
 !   !   !   ! !     ! ! ! ! ! ! !       !   !         !   ! ! !
 ! !!!!! !!! ! !!!!!!! ! ! ! ! ! ! !!!!!!! !!! ! !!!!!!! !!! ! !
 !     !     !         ! !   !   !     !   !   ! !     !   ! ! !
 ! !!! !!!!!!!!!!!!!!!!! !!!!! !!! !!! !!! ! ! !!! !!! !!! !!! !
 !   !         !     !   !     !     !   ! ! ! !     !   !   ! !
 !!!!!!!!!!! ! ! !!! !!! ! !!!!!!!!!!!!! ! !!! ! !!!!!!! !!! ! !
 !           !   !       ! !             !   !     !     !     !
 ! !!!!!!! !!!!!!! !!!!!!! ! !!!!!!!!!!!!!!! !!!!!!! !!!!!!!!!!!
 ! !     ! !   !     !   ! !           !   !       ! !         !
 ! !!! ! ! ! ! !!!!!!! ! ! ! !!!!!!!!! ! ! !!!!!!! ! ! !!!!!!! !
 !   ! !   ! !       ! !   ! !         ! !       ! ! !   !   ! !
 !!! ! !!!!! !!!!!!! ! !!!!!!! !!!!!!!!! !!! !!!!! ! !!! ! !!! !
 !   !   ! ! !       !   !     !   !     ! !           ! !   ! !
 ! !!!!! ! ! ! !!!!!!!!! ! !!!!! !!! !!!!! !!!!!!!!!!! ! ! ! ! !
 ! !       ! !   !   !   ! !       ! !       !   !     ! ! ! ! !
 ! !!!!!!!!! !!! ! ! ! !!! !!!!!!! ! !!!!!!! ! ! !!!!!!! !!! ! !
 !             !   ! !   !       ! !     !   ! !             ! !
 !!!!!!!!!!!!!!!!!!! !!! !!!!!!! ! !!!!! ! !!! !!!!!!!!!!!!!!! !
 !               !   !   !       !         !   !     !   !     !
 ! !!!!!!!!!!!!! ! ! ! !!! !!!!!!! !!!!!!!!! !!! !!! !!! ! !!! !
 ! !   !       !   ! ! ! !     ! ! ! !     !     !   !   !   ! !
 ! ! ! !!!!! !!!!!!! ! ! ! !!! ! ! ! ! !!! !!!!!!! !!! !!!!! !!!
 !   ! !   !       ! ! !     ! !     ! ! !     !   !       !   !
 !!!!! ! ! !!! !!! ! ! !!!!!!! !!!!!!! ! ! !!! ! !!!!!!!!! !!! !
 !     ! !   !   !   !       !       ! ! ! !   !   !         ! !
 ! !!!!! !!! !!! !!!!!!!!!!! !!!!!!! ! ! ! !!!!!!! ! !!!!!!! ! !
 !         ! !           !   !       ! ! !     !   ! !       ! !
 !!!!!!!!!!! !!!!!!!!!!! ! !!! !!!!!!! ! !!!!! ! !!! !!!!!!!!! !
 !         !     !     ! ! !       !   !     ! !     !         !
 ! !!!!!!! !!!!! ! !!! !!! !!!!!!! ! !!!!! ! ! !!!!! ! !!!!!!!!!
 ! !     !     !   ! !   !       ! !       ! !       !         !
 ! ! !!! !!!!! ! !!! !!! !!!!!!! ! !!!!!!!!! !!!!!!!!!!!!!!!!! !
 !     !     ! !   !   ! !     ! !       !   ! !     !         !
 !!!!!!!!!!! ! !!! !!! ! ! ! !!! ! ! !!!!! !!! ! !!! ! !!!!!!! !
 !           ! !       !   ! !   ! !       !   ! ! ! !     !   !
 ! !!!!!!!!!!! !!!!!!!!!!!!! ! !!! !!!!!!!!!!! ! ! ! ! !!! ! !!!
 !       !   !             ! ! ! !   !         ! !   !   ! ! ! !
 !!!!!!! !!! !!!!!!!!!!!!! ! ! ! !!! ! !!!!!!! ! !!! !!!!! ! ! !
 !       !         !     ! ! ! !   !   !     ! !   !       !   !
 ! !!!!!!! !!!!!!! ! !!!!! ! ! !!! !!!!!!! ! ! !!! !!!!!!!!!!!!!
 !   !         ! !   !       ! !           ! !   !             !
 ! ! ! !!!!!!! ! ! !!! !!!!!!! ! !!!!!!!!!!! ! !!!!!!!!!!!!!!! !
 ! ! ! !     ! !   !   ! !     !   !   !     ! !               !
 ! ! !!! !!! ! !!!!! !!! ! !!!!! ! ! ! !!!!!!! ! !!!!!!!!!!!!! !
 ! !   !   ! !   !       !   !   !   !         ! !         !   !
 !!!!! !!! ! !!! ! !!!!!!!!! !!!!!!! !!!!!!!!!!! !!!!! !!!!! !!!
 !     !   !   !   !       !       !       !   !     !       ! !
 ! !!!!! !!!!! !!!!! !!!!! !!!!!!! !!!!!!!!! ! !!!!! !!!!!!! ! !
 !           !     ! !   !   !   !           !   !   !     !   !
 ! !!!!!!!!! !!!!! ! !!! ! !!! ! !!!!!!!!!!!!!!! ! !!! !!! !!! !
 ! !     !       ! !     !     !     !         ! !       !   ! !
 !!! !!! !!!!!!!!! !!!!! !!!!!!!!! ! !!!!!!! !!! ! !!!!!!!!! ! !
 !   !     !   !   !   ! !       ! !         !   ! !         ! !
 ! !!!!!!! ! ! ! ! !!! ! !!!!!!! ! !!!!!!!!! ! !!!!! !!!!!!!!! !
 !       !   !   ! !   !         !   ! !   ! ! !     !       ! !
 ! !!!!! !!!!!!!!! ! !!!!!!!!!!! !!! ! ! ! ! ! ! !!!!! !!!!! ! !
 ! !     !           !         ! ! ! !   !   ! !   !   !     ! !
 ! ! !!!!!!!!!!!!!!!!! !!! !!!!! ! ! !!!!!!!!! !!! ! !!!!!!!!! !
 ! !                     !         !               !           !
 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !

You don't even need int p,int c. p,c is enough...

Mathematica, 144 132 bytes
Since Inception, we all know the most efficient way to draw a maze.
c=0;Graphics@Most[Join@@{Circle[{0,0},i,{a=c-(r=Random[](d=2Pi-1/i)&)[],a+d}],Line[{{i},{i+1}}.{{Cos[c=a+r[]],Sin@c}}]}~Table~{i,9}]

Ungolfed and example output:

Of course, the lines are the walls. You're the minotaur who starts in the centre and needs to get out.

This is pretty, and the code is short, but I would say it's toward the "trivial maze" end of the spectrum.

@LarsH it was non-trivial enough for Dom Cobb :P. you can make it more complicated with one character: turn that last 9 into a 99 :P. But yes that's qualitatively the same thing. I think it does fulfil the specification though. If the OP changes the contest away from pure code-golf I'm willing to come up with something more interesting (e.g. paths that need you to go back inside a ring).

You're right that making it bigger wouldn't change the triviality. The point is that solving this maze is a linear process: at every juncture you can quickly find out whether you've taken the wrong turn, without having to "recurse" into deeper branches. Ian's and aleph's answers, on the other hand, are "real" mazes: they can't be solved in this linear way. Since trivial mazes are discouraged, I'd be tempted to downvote this one, but I don't have enough rep.

@LarsH yep, we agree on that. That's why I said it's the most "efficient" way to draw a maze, not the most "effective" one. ;) Still, it may be simple, but I don't think it falls in a category with the ruled out ones like "blank" or "1x1". Of course, it's at the OP's discretion to disqualify this submission for its simplicity, but as long as he doesn't do that or changes the type of the challenge, I don't see an incentive to make it more complicated/interesting.

@LarsH that being said, I'm not sure if it's due to their algorithms or just a feature of the particular examples they posted, but neither of their answers required backtracking beyond depth "1" more than once. So while they do contain a lot of complexity, it's all in paths that are irrelevant anyway.

OK. I haven't analyzed their mazes in any detail. It's not obvious that they don't require significant backtracking, and that makes a difference; but maybe they're not much further down the continuum away from being trivial.

This maze isn't trivial, in my opinion, even if it's easy (and my circular maze below is even more trivial).  I really just wanted to prevent blank-canvas/size-1/etc. "maze"s.

@IanMallett How is it not trivial? In each ring, you're just looking for the passage in the outer wall to the next outer ring.

-0, your maze isn't impossible like the one from Inception

@NickT there is a possibility that there is another exit behind Cobb's hand ;) (I'd have to rewatch it to be sure).

@m.buettner no, the 3rd ring is impossible to cross. https://www.youtube.com/watch?v=nKI432lCZaU#t=33s

@NickT, oh right, overlooked that. I suppose that would invalidate my answer though :P

C: 364 Bytes
#define I int
m[1600],i=0,r;f(I x,I y,I l){m[80*y+x]|=l;I d[]={x-1,y,2,1,x+1,y,1,2,x,y-1,8,4,x,y+1,4,8},
s[]={5,5,5,5},j=0;for(;j<4;){L:r=rand()%4;for(I k=0;k<4;)if(s[k++]==r)goto L;s[j]=r;I*p=d+
4*s[j++],X=p[0],Y=p[1];if(!(X<0|X>79|Y<0|Y>19|m[80*Y+X])){f(X,Y,p[2]);m[80*y+x]|=p[3];}}}
main(){f(0,0,4);m[9]|=4;for(;i<1600;)putchar("#5FMP<HJR;IK:9LN"[m[i++]]+128);}

Note: in the above, I added newlines to make it fit on the page.  Expected output (on 80-character terminal) (note start and end at top left):

I stared for 10 minutes at it, but I cannot find a start which matches an end? If there is, I'd really like to see the solution to the maze. I tried every entrance, but there were just dead ends…

@bwoebi MSPaint to the rescue! IMAGE

@CeilingGecko Thank you. Effectively missed to look at the very topleft, not realized that could even be an entry

Note that my intention was to have the path be inside the pipes (as here).

@IanMallett I think Ceiling Gecko was aware of that, but flood-filling the left wall with a colour gives you a (non-optimal) path following along the left wall until you find the exit. ;)

I'd be interested in seeing the un-golfed version of this code, if you have time.

While you wrote this you were a-maze-ing coder.

@m.buettner sure; hence my clarification.

@LarsH Regrettably, I don't have the ungolfed version myself.  It works by recursively digging a box into an empty space.  The hardest part is probably the choice of direction, which works by permutation of an array (with, IIRC O(∞) runtime).

Mathematica, 134 130 chars
Graph[Range@273,Reap[Do[c@n/._c:>#0[Sow[#<->n];n],{n,RandomSample@AdjacencyList[g=GridGraph@{13,21},c@#=#]}]&@1][[2,1]],Options@g]

In fact, we can use this algorithm to generate a maze from any (undirected) graph.
For example, generate a maze from the 8*8 knight's tour graph (KnightTourGraph[8,8]):

Graph[Range@64,Reap[Do[c@n/._c:>#0[Sow[#<->n];n],{n,RandomSample@AdjacencyList[g=KnightTourGraph[8,8],c@#=#]}]&@1][[2,1]],Options@g]

Nice maze… but I don't see any entrance which is connected to an exit…?

I believe the idea is to pick a random node (say, upper left) as entrance and another (bottom right) as exit. Mathematica makes sure all nodes are connected with all other nodes, but - especially in the second maze - finding how they are connected is the harder part.

Are the lines (graph edges) supposed to be maze walls, or passages? I thought I knew, but now I'm not sure.

@LarsH They are passages.

In that case, what are the exits and entrances in your first image? Are they all the nodes on the outside edge?

@LarsH The graph is connected, so you can just take two arbitrary nodes, one as entrance, the other as exit.

+1 This is, by far and away, the most interesting maze posted so far.

Bash, 53 50 bytes
w=(╱ ╲);while :;do echo -n ${w[RANDOM%2]};done

Similar idea to the C64 code. Uses Unicode characters as the slashes because they look much nicer in a terminal that supports Unicode. Sample output on OS X Terminal (Menlo font):

I once figured this out: yes 'c=(╱ ╲);printf ${c[RANDOM%2]}'|bash. See this post

This is based on an algorithm that cannot guarantee itself to be solvable, one that is many years old.

JavaScript (ES6), 174
This is the maze builder I used in this other challenge, just golfed.
It's a function with 2 parameters: rows and columns. The maze is totally connected with no loops, so any location can be the starting or ending point.
(r,c,o=2*c+2,i=2*r*o+o,z=[],F=(p,i=Math.random()*4)=>[o,1,-o,-1].map((s,j,d)=>z[s=p+2*d[j+i&3]]>0&&(z[s]=z[(p+s)/2]=' ',F(s))))=>{for(;i--;)z[i]=i%o?8:`\n`;F(o+2);return''+z}

Example
f(7,10)

Output
,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
,8, , , ,8, , , , , ,8, , , , , , , , , ,8,
,8, ,8, ,8,8,8, ,8, ,8,8,8,8,8,8,8, ,8, ,8,
,8, , , ,8, , , ,8, , , ,8, , , , , ,8, ,8,
,8, ,8,8,8, ,8,8,8,8,8, ,8, ,8,8,8,8,8, ,8,
,8, ,8, , , , , ,8, ,8, ,8, ,8, , , , , ,8,
,8, ,8, ,8,8,8, ,8, ,8, ,8, ,8, ,8,8,8,8,8,
,8, ,8, ,8, , , ,8, , , , , ,8, ,8, , , ,8,
,8, ,8, ,8, ,8,8,8,8,8,8,8,8,8, ,8, ,8,8,8,
,8, ,8, ,8, , , , , , , ,8, , , ,8, , , ,8,
,8, ,8, ,8,8,8,8,8,8,8, ,8,8,8, ,8,8,8, ,8,
,8, ,8, , , , , , , ,8, , , ,8, , , , , ,8,
,8, ,8,8,8,8,8,8,8,8,8,8,8, ,8,8,8,8,8, ,8,
,8, , , , , , , , , , , , , ,8, , , , , ,8,
,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8

Test

f=
(r,c,o=2*c+2,i=2*r*o+o,z=[],F=(p,i=Math.random()*4)=>[o,1,-o,-1].map((s,j,d)=>z[s=p+2*d[j+i&3]]>0&&(z[s]=z[(p+s)/2]=' ',F(s))))=>{for(;i--;)z[i]=i%o?8:`\n`;F(o+2);return''+z}

function update() {
  O.textContent='';
  [r,c]=I.value.match(/\d+/g)
  O.textContent=f(r,c)
}

update()
pre { line-height: 0.8em }
Rows,Columns <input id=I oninput='update()' value='8,12'>

I'm not sure ... is the light or the dark area the maze? If the dark, then it has a big loop and one can just stay at the outside when choosing any point as entering/exit point. If the light, then you should add the exit/entry.

@PaŭloEbermann it is the light of course, dark area is the walls. Repeating myself: The maze is totally connected with no loops, so any location can be the starting or ending point

Wow, this is a-mazing! Shaved some bytes and got it down to 133 bytes: https://twitter.com/aemkei/status/889587308894326785
But all credits should go to you!

@aemkei 8 instead of '#', I can't believe I missed that at time

ZX Basic - 54 characters
a$="/\":for i=1 to 24*32:print a$(1+int(rnd*2));:next

Here is the maze showing a route through it (spaces between lines)

and a small snippet from when I first did this (several years ago), and spent a bit of time doing better graphics.

Hm, cheeky. ^^ What's the start and what's the end there? And are the slashes the paths or the walls? And what is the minimum gap size I can pass through?

"There should be at least one path from at least one entrance to at least one exit." I don't see any indication that this criterion is met. Random walls don't necessarily create a maze.

@m.buettner: I'm guessing that the slashes are walls, and that we're supposed to visualize it as though there were zero space between rows, and between columns. So the bottom-left 2x2 characters form a totally closed diamond (square) shape.

@LarsH yeah I thought so. That just makes another point for your case on the OP's question that people should indicate what start and finish are. Also, this scheme doesn't even allow for junctions. You can only have those closed squares or meandering paths (which might also be closed loops).

+1 for the improved graphics and showing the route. I guess given so many potential entrances and exits, the likelihood of having "at least one path from at least one entrance to at least one exit" is pretty high!

@LarsH true, but it also means that from each each entrance there is only a single path you can possibly take it will always lead to an exit. If you considered my mazes trivial, these are even more so. ;)

@LarsH The criterion is met, ALL points on the edge lead to another point somewhere on the edge. But paths are trivial because there's no branches or dead ends. Proof: every square is divided into 2 triangles, each of which is a path fragment with exactly 2 entrances/exits. It's like a tangle of http://en.wikipedia.org/wiki/Rubik's_Snake I like this answer and I'd like to see the paths randomly colored. I'd also like to see a 3d version (in which 2 of the 6 possible orientations cause a block, depending on interpretatation.) The walls form a more challenging maze, with no guarantee of validity

@steveverrill: OK, if you define entrances/exits that way. Tho it's not very natural, e.g. to define the upper left corner as constituting 2 entrances/exits. If you require entrances and exits to be separate from each other (as per the usual understanding of the terms), a strictly alternating lattice of slashes wouldn't have any paths through it.

BBC BASIC, 18 Bytes
An improvement in length on the 23-byte C64 infinite loop version by @nneonneo. VDU sends a single character to the VDU controller: either 2+1*45=ASCII 47 / or 2+2*45=ASCII 92 \
  VDU2+RND(2)*45:RUN

BBC BASIC, 35 Bytes /  107 95 Bytes
35 bytes is just for the last line, which gives a 25 row maze in 40 column layout. MODE1 ensures that no extra space is left between lines. The remainder of the program is optional and improves the formatting. The VDU23 statements redefine the font for characters 47 and 92 (8 bytes forming an 8x8 bitmap.) I include a light pixel in all four corners to stop straight runs from getting pinched off. The side effect of this is that a dot appears in the empty diamonds. 107 bytes total including 2 newlines.
  VDU23,47,131,7,14,28,56,112,224,193
  VDU23,92,193,224,112,56,28,14,7,131
  MODE9FORa=0TO999VDU2+RND(2)*45:NEXT

Edit this program can be shortened to 95 bytes by encoding some of the 8 bit VDU codes into 16 bit small endian values (denoted by a semicolon after them instead of a comma) and representing the MODE statement as a pair of VDU codes, as follows.
VDU23,47,1923;7182;28728;49632;23,92,57537;14448;3612;33543;22,9:FORa=0TO999VDU2+RND(2)*45:NEXT

Output
Using BBC Basic for Windows from bbcbasic.co.uk
Last line only, 35 bytes

Whole program, 107 95 bytes
As I commented on @Brian's answer, the slash splits the square into 2 dark triangles, each of which has exactly 2 entrances/exits. This guarantees a (trivial, unbranched) path from any point on the edge of the maze to some other point on the edge of the maze. Many of these are very short, but there always seem to be a few long ones. Of course, in the middle of the maze there are also some loops.
As other answers have not mentioned it, I'd like to take a good look at the light areas. These are bounded by dark areas, therefore as a corollary to the statement made above, a light area bounded externally by N dark areas touches the edge of the field at N (exactly as many) points. Therefore some fairly large light areas occur, and these form interesting, branched mazes.
In the example below, you can see the raw output (monochrome) from my program. Below that (using Windows Paint) I have coloured the two longest dark areas in blue. Then I coloured the largest light area in yellow, and the two areas bounded by blue in red and green. The yellow, green (and even the red) mazes are quite interesting and nontrivial.

EDIT - Automatic picking of mazes and selection of starts/ends
For one more line (59 characters) the program can automatically pick out up to 6 mazes by choosing squares at random and flood filling in colours red,green,yellow,blue,magenta and cyan. It does not always find a full 6, because if it picks a random square that has already been coloured it does nothing.
The rest of the code below picks out a start for each colour by scanning each column from top to bottom and left to right, and picking the first square it encounters. It picks an end by scanning in the opposite direction.
This produces a set of colourful, intertwined mazes. Sometimes they are so intertwined it looks like the mazes must cross somewhere. But of course, they don't!
Additional code and output 59+187=246 additional characters to be added to the end of the original program (for enhancement beyond question spec.)
  GCOL135FORa=1TO6GCOLa FILLRND(40)*32-16,RND(25)*32+208:NEXT   :REM set background to grey so fill can identify. For each colour 1 to 6, pick a point in the centre of a character and flood fill (characters are logically 32x32 although they are physically only 8x8 pixels.)
  f=126:g=126                                                   :REM flags 1111110 to indicate which starts and ends have not been allocated yet
  FORx=0TO39FORy=0TO24                                          :REM maze is 40x25. There is some blank space at the bottom of the screen (32 rows total)
  p=POINT(x*32+16,1008-y*32)                                    :REM check start point. Text origin is at top of screen, Graphics origin is at bottom, 1280x1024 logical. therefore y offset is 1024-32/2=1008.
  IFf AND2^p f=f-2^p:VDU31,x,y,17,p,79                          :REM if start for colour P has not been allocated yet, allocate it now. VDU31,X,Y go to that square. VDU 17,p select text colour. VDU 79 print an "O"
  p=POINT(1264-x*32,240+y*32)                                   :REM check end point
  IFg AND2^p g=g-2^p:VDU31,39-x,24-y,17,p,79                    :REM if end for colour P has not been allocated yet, allocate it now.
  NEXT:NEXT
  VDU31;26                                                      :REM get the cursor off the board. Move to (0,26). Semicolon used instead of comma here indicating that 31 is a 16 bit small endian value, equivalent to VDU31,0,26 or PRINTTAB(0,26)

C: 235 Bytes
#define P(X,Y)M[(Y+40)*80+X+40]=rand()%49/6;
#define B(X,Y)P(X,Y)P(Y,X)
M[6400],r,i;main(){for(i=0;i<40;i+=2){int x=i,y=0,e=1-x;while(x>=y)
{B(x,y)B(-x,y)B(-x,-y)B(x,-y)++y;e+=e<0?2*y+1:2*(y-x--);}}for(i=0;
i<6400;)putchar(64>>!M[i++]);}

Note: in the above, I added newlines to make it fit on the page. Expected output (on 80-character terminal):
I regret this isn't a very hard maze (in fact, no backtracking to inner rings is required (and you should be able to find a path from the perimeter to the center trivially).  However, it has a nice implementation of Bresenham's circle drawing algorithm at its core.

It's a bit hard to see where you can pass through and where you can't. I have to say, I preferred the pipes ;) (to both this and my circular submission).

@m.buettner: I actually agree.  If you change the i+=2 to i+=3, it might be more clear what's happening.

I helped my kid to do this, to learn a bit of programming: http://jsfiddle.net/fs2000/4KLUC/34/
how do you like it?

If you can fit your code into the post, do that. Also, include a header like #Language(s) - Bytecount. If you only used ASCII characters in your code, you can get a nice bytecount here. A summary of what your code does, any insights you may have had, or any clever things you did might be a nice addition to your post. By the way, Darth Vader makes it very hard to see some of the lines. Finally, Welcome to Code Golf!

You learnt a bit of programming with your children and I learnt a bit of golfing. This is my first golfing and the result is still rather long.
Byte count:
Original: 55+6822=6877.
A bit reorganised: 39+3131=3170
Golfed: 39+1593=1632

Commodore 64 BASIC - 38 bytes
10 PRINT CHR$(205.5+RND(1)); : GOTO 10

This is not my invention, I am simply repeating a very beautiful and short program from days gone past. In fact, there is an entire book named 10 PRINT CHR$(205.5+RND(1)); : GOTO 10 celebrating this piece of code!
You can see the output on this YouTube video; here's a screencap:

Here at this StackOverflow question are more implementations of this maze-generator program. The shortest implementation of the program is the following 23-byte C64 BASIC program posted by that question's author:
1?cH(109.5+rN(1));:gO1

where lowercase letters are entered as-is, and uppercase letters are entered using the Shift key (these have different appearances on an actual C64 screen).

Isn't this exactly the same Brian's submission? (just a bit shorter) And so is your Bash answer? Then the question here is as well, is a maze without junctions still a maze?

nneonneo, +1 for proper and honest attribution of this great idea. @m.buettner The unprinted area produces unbranched labyrinths as you point out. However (and I am surprised no-one else has shown this yet) the printed area forms some interesting, non-trivial, branched mazes (see my answer.) I'm upvoting your maze too as it has the best defined start and end. Defining start and end on these diagonal mazes is not easy.

@m.buettner 1. The x86 binary is only 10 bytes at its smallest. 2. This is a well-honed algorithm, and is not at all original, nor was it intended to create a solvable maze.

Java : 700
Here's a recursive wall adder. The algorithm is outlined on this site:
public class Z{int i,j,u=20,v=u,g[][]=new int[v][u];public static void main(String[]a){new Z().d(0,0,20,20,0).p();}int q(int m){return(int)(Math.random()*m);}<T>void z(T m){System.out.print(m);}void p(){for(i=0;i++<u*2;z("_"));for(i=0;i<v;i++){z("\n|");for(j=0;jv,s=g[i][j]%2>0||b;z(s?"_":" ");z(g[i][j]>1||j+2>u?"|":s&(j+10||b)?"_":" ");}}}Z d(int x,int y,int w,int h,int o){int a=x,b=y,c=a,d=b,e,f;boolean t=o<1;if(t){b+=q(h-2);c+=q(w);}else{a+=q(w-2);d+=q(h);}for(i=t?w:h;i-->0;j=t?a++:b++)if(a!=c&&b!=d)g[b][a]|=t?1:2;e=t?w:a-x+1;f=t?b-y+1:h;if(e>2&&f>2)d(x,y,e,f,e<f?0:1);e=t?w:x+w-a-1;f=t?y+h-b-1:h;if(e>2&&f>2)d(t?x:a+1,t?b+1:y,e,f,e<f?0:1);return this;}}

Basically, it splits each rectangle in two with a wall (and passage), then splits those in two, etc. It generates a "perfect" maze - one with no cycles - that has a path from every point to every other point. Plenty of dead ends, so it's not "trivial" in any sense for larger mazes.
So, the entrance and exit can be decided arbitrarily. If I have to choose one, It'll just say top/left and bottom/right.
It's drawn in double-width ascii, so it's a good idea to pipe output to a file if you're doing one of any size. Here's a 20x20 in console:

And a 100x100 in notepad++ (I had to zoom out to get ti all, so it's somewhat... small):

Code with line breaks:
public class Z{
    int i,j,u=20,v=u,g[][]=new int[v][u];
    public static void main(String[]a){
        new Z().d(0,0,20,20,0).p();
    }

    int q(int m){return(int)(Math.random()*m);}
    <T>void z(T m){System.out.print(m);}

    void p(){
        for(i=0;i++<u*2;z("_"));
        for(i=0;i<v;i++){
            z("\n|");
            for(j=0;jv,s=g[i][j]%2>0||b;
                z(s?"_":" ");
                z(g[i][j]>1||j+2>u?"|":s&(j+10||b)?"_":" ");
            }
        }
    }

    Z d(int x,int y,int w,int h,int o){
        int a=x,b=y,c=a,d=b,e,f;
        boolean t=o<1;
        if(t){
            b+=q(h-2);
            c+=q(w);
            }
        else{
            a+=q(w-2);
            d+=q(h);
        }

        for(i=t?w:h;i-->0;j=t?a++:b++)
            if(a!=c&&b!=d)
                g[b][a]|=t?1:2;

        e=t?w:a-x+1;f=t?b-y+1:h;
        if(e>2&&f>2)d(x,y,e,f,e<f?0:1);
        e=t?w:x+w-a-1;f=t?y+h-b-1:h;
        if(e>2&&f>2)d(t?x:a+1,t?b+1:y,e,f,e<f?0:1);
        return this;
    }
}

ZX Basic - 281 characters
This is more of a "proper" maze, less golfier, but more mazier.
So called Binary maze algorithm, each cell can have an exit going down or right, but not both.
(Now includes marked Start "S" and End "E", to prevent just going straight along one side).
The "::" is ZXB's way of entering Spectrum graphic characters into a text file, equates to a sold block character.
randomize:border 1:paper 1:ink 6:cls
for x=0 to 30 step 2
 for y=0 to 20 step 2
  r=1+int(rnd*2)
  if x=30 and r=1 then
   r=2
  end if
  if y=20 and r=2 then
   r=1
  end if
  print at y,x;"\::"
  print at y+(r=2),x+(r=1);"\::"
 next
next
print inverse 1;at 0,0;"S";at 20,31;"E"

No I actually meant that you should swap the start and the end (start bottom right, end top left). As it stands its trivial, because due to the rules you just have to go down and right all the time to reach the end.

Even if the start and end are reversed, the maze has the (perhaps interesting) property that the correct path will only move up and left. The maze isn't trivial anymore, though, because there are many points at which you can go one of two ways.

C- 244
#include <unistd.h>
#include <windows.h>
int main(i,j,rv,rs){srand( time(0));for (i = 0; i < 80; i++)for (j = 0; j <50 ; j++){rv = rand() %10;rs = rand() %100;if(rs < 10 || rs  > 90)continue;if(rv<4){gotoxy(i,j);printf("%c", '#');}}return 0;}

Here is how it looks like:

Note: this solution is inspired by the untrusted game level 8:into the woods.

source: Stack Exchange

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

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

sort: votes


text:
Remove Duplicates From One List
Task:
Remove all duplicates from one list of integers. A list is simply a sequence of connected values that allows the same values to be stored at different positions in this sequence.
If an item was found to be the same value as another item in this list, keep the first occurence of the item and remove the second (third and so on...) occurence of the item.
Input/Output
You may write a function or full program that takes a list of integers as an input and returns a list without duplicates as an output.
Rules:

This is a code-golf challenge, so shortest answer wins!

Please state what you mean by a "list", and how the program will interact with this list (i.e. input/output)

I would have preferred leaving this question closed and creating a new one, since it is old and the edit invalidates almost all of the existing answers

@JoKing same here. I have no idea why/who reopened, but I thought it was best to clean it up if it was being reopened

APL (1)
∪

∪ takes a list and returns the unique elements  in a list, i.e.:

    ∪ 1 2 3 2 3 4 5
1 2 3 4 5

if you need I/O it's 2:
∪⎕

Since it's not specified, default counting for code-golf is in bytes (according to the tag wiki), which would make ∪ 2 (UTF-16) or 3 (UTF-8) bytes. Together with I/O, that's 4 or 6.

GolfScript (2 bytes)
.&

Takes input on stack, leaves output on stack.

GolfScript beats all!as usual...

Red, 8 bytes
unique s

assuming list is in word 's

Python 2: 12 bytes
print set(l)

No input spec, so I'm assuming the list is held in a variable called l.

Python - 12 bytes
list(set(l))

Assuming the list is given in the variable l.

Mathematica, 7 bytes or 3 characters
Assumes input in variable x
Union@x

If we're counting in Mathematica characters, I can do 3 (the second input line):

Ruby, 3 characters
a|a

Assumes the list is stored in variable a. Also works with & instead of |.
If the original list has to be altered (instead of keeping the original the same and creating a new list with duplicates removed), then 4 characters:
a|=a

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

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