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.
4Can you make a copy of your server available for entrants to test against? – Peter Taylor – 2014-04-13T12:55:43.523
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? – Hasturkun – 2014-04-13T13:30:50.3701@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? ;) – sadakatsu – 2014-04-13T18:19:57.890
@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. – sadakatsu – 2014-04-13T18:24:22.040
@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 – 2014-04-13T18:27:27.230
@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. – sadakatsu – 2014-04-13T18:32:37.740
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. – Peter Taylor – 2014-04-13T21:26:13.450
Race conditions are a good reason to change the requirements. I will change the specifications accordingly. – sadakatsu – 2014-04-13T21:40:38.663
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. – intx13 – 2014-04-14T02:32:49.687
1The 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. – sadakatsu – 2014-04-14T03:29:44.087
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. – SirDarius – 2014-04-15T14:36:40.890
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 toRandomPlayer.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. – Peter Taylor – 2014-04-17T12:59:23.863@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. – sadakatsu – 2014-04-17T15:51:54.407
@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 newProcess, and theProcessdocumentations 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 addSystem.out.flush()calls? – sadakatsu – 2014-04-17T15:56:09.443@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. – sadakatsu – 2014-04-17T16:05:23.150The 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
– Peter Taylor – 2014-04-17T16:07:11.323disproveserver->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. – sadakatsu – 2014-04-17T16:14:03.350let us continue this discussion in chat
– sadakatsu – 2014-04-18T04:04:02.623Can two different players make the same suggestion? – Gaelan – 2014-04-20T18:54:27.967
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. – sadakatsu – 2014-04-20T19:12:55.350
Do we have response time limit ? – Ray – 2014-04-23T12:23:04.090
@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?). – sadakatsu – 2014-04-23T12:40:29.077
I think 2~5 seconds per turn will be a proper limit. – Ray – 2014-04-23T13:03:32.197
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. – sadakatsu – 2014-04-23T13:47:31.390
@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 – 2014-04-24T12:17:15.517@Ray, what's wrong with using the BSD socket
– sadakatsu – 2014-04-24T13:23:58.787socket.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. – Ray – 2014-04-24T13:35:49.593You 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. – sadakatsu – 2014-04-24T13:40:43.263
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 – 2014-04-24T14:02:08.943
@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
cmdstrangles the socket (which makes no sense). If I run it separately,recv()andsendallseem 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'sstdoutconsumption is the problem, but I have no answers... – sadakatsu – 2014-04-24T17:37:29.843This 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? – sadakatsu – 2014-04-24T17:40:44.340
@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. – sadakatsu – 2014-04-24T20:20:42.253
@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. – Ray – 2014-04-27T04:54:38.693
@gamecoder: It looks like an AI never knows if a
suggestis made and someone elsedisproveit (or even if the AI implicitly disproves it by having only one of the cards). This is important information when playing Clue. – Ben Jackson – 2014-04-27T22:54:09.053... have you read the
suggestionprotocol? – sadakatsu – 2014-04-27T22:55:21.720@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. – AJMansfield – 2014-05-16T22:33:18.210
Anyone want to try writing an AI that will collude with other instances of itself in the same game? – AJMansfield – 2014-05-16T23:33:22.853
Did AI01 of the #14 pull request still crash ? – Ray – 2014-05-17T13:20:39.360
@Ray, Unfortunately, yes. I tried the tournament first with #13 and then with #14. The results I mention above are for #14. – sadakatsu – 2014-05-17T19:53:42.500