Contest 43: CyberClue

[Dudi Hatotah]

Jubulani, your bot seems to have all the improvments that I wish my bot had. (I wrote my strategies reply before reading yours!...)
Your bot seems to be close to the ultimate bot...

At any rate, your bot SHOULD be better than mine.

[Darryl]

1. My basic strategy was to create a table of player/card (every player vs. every card) and use it to store all the infomation (for example, when a player DOES NOT respond to a suggestion, I know that he doesn't have all the 3 cards suggested. That makes the cards more suspicious. ...

2. I tried to only ask for 1 card at a time that I needed, the other two would be cards in my hand, that way if it was a no show, I knew that was the card or if it is shown then I elimated a specific card. Only downside to this is that I can never win before the 3rd turn by getting lucky.

I'm sorry, but I believe this would make your bot lose.
I tried this method and it never seemed to work for me. Your bot will advance quite slowly that way.

on the other hand, when no one shows a card on my suggestion and I am holding 2 of them in my hand, your bot will mark the two cards in my hand as more suspicious...


I will advance at same rate or faster. I will either see 1 card (same as asking 3 unknowns) or I will know the guilty card (not possible with 3 unknowns) unless you guessed all 3 correctly.

I did a table like that too and tracked all cards in relation to each player.

I decided against this strategy. My bot askes for the cards it is most likely to be given the info it has currently. I figured getting shown one card was as good as being shown any other card, given you've seen neither of them before.

true but even if one of the 3 suggested cards is the guilty card you won't know till you've elimated the other two. I've already eliminated two in my suggestion. on the other hand....

I have seen my player (VERY rarely) win on the first turn during my testing.

very rarely beats not at all.

But thinking more on this, I could have based my one card I asked on a most likely/suspicious algo, but then again I couldn't figure out a "Most likely Algo"...what did you use that doesn't get corrupted by clueless and info hiding bots like mine. All the algos I tried had my bots chasing after cards in other players hands. Which almost lead me to look at the least likely as more suspicious.

The last thing that I wanted to add to my player was a system for working out how much every other player knew. Then, if I thought someone was close to the answer, I could guess myself before their turn.

I wanted to do something like this too... I noticed when I played console against the bot there were times when I knew it would get it on the following turn and thought about guessing.

A couple of other things I did too, was if I couldn't ask cards in my hand, I would ask cards that I knew was in the player before me hand.. that way the suggestion would have to go through all the other players first increasing the chance I won't be shown a card I already knew.

One other long shot algo i used that only came in to play maybe 1 out of 3 games was sort of a elimination deduction for example:
In a 5 player game each player has 4 cards, sometimes I could figure out for a particular player the 19 they didn't have, before the 4 they did, but then once i knew that, I knew what the 4 did have. It seems like it would be the long way around but it's not, for example... I have 4 cards in my hand, that brings it down to 15, and anytime he doesn't show a card on a suggestion that knocks as many as 3 more off. He may answer up to 4 suggestions in a round, if he doesn't show a card on just 1 of those, thats up to 3 more cards I could knock off a round. After 5 rounds, I have pretty much guessed that players hand based on what he doesn't have.
Once I know the 4 in that players hand I eliminate those from the other players which maybe I can then figure out their hands as well.

Darryl

EDIT: I was just thinking, since the bots are already submitted, there'd be no harm in exchanging bots to run our own informal test. anyone interested?

[Zemalf]

Excited to see the results, and the actual code of others (especially the winner).. While waiting for that, I share my tactics, like others have done already..

a Lot of same tactics that I used have been mentioned already, and some parts of the improvements I wanted to make but didn't have the skill/time..

"tactics"

1) Track cards shown to me (duh)

2) Track cards in other players' hands
either shown to me, or through analysis of the suggestion
-> this way I can (hopefully) know if card(s) in suggestion are in guessers hand
So if I know that two cards from the guess are in guessers hand (or I know one or more cards in the guess are part of the solution or in my hand, and something happens before it's my turn..)
--> in case a card is shown, I know what card it was, and can mark it as handcard for the player who showed it
--> in case no card was shown by anybody, I know that the guesser knows (e.g. one of the cards is the "right" one)

3) Track cards *not* in other player's hands
- if someone doesn't show a card to suggestion, the three cards in the guess are not in that players hand.
--> if a card is not in anyone's hand (including me of course), that is the right card.

4) Track cards shown by me to other players
--> if possible, show the same card again (usually the location)

5) Try to move to favorable location (unknown loc, loc in my hand, etc.)

6) If possible, include 2 cards from hand to the guess (to "lock" the one unknown).. Some variations here
- if location is in hand, choose weapon or suspect from hand based on the number of unknown cards of that type..
- sometimes go for 2 or 3 (all) unknown cards in guess (I don't remember the rules, but no 1 turn win i think, turn 2 yes)

7) "Memorize" guesses by other players, if no-one showed a card
--> Analyze the guess later (next turn) if I recieve more info (new known cards, new cards known from players' hands, etc.)
- I can also make the same quess next turn if nothing else works (this requires trying to move to the same loc, it doesn't work without that)
--> after this I possibly know what the other guesser knew when that player made the same guess

8) Possibly something I forgot..

Wish list:

1) Thinking ahead on 'Move'
I didn't use the information known about room order in any way, but I think I should've tried to move closer to the room I want instead of random as the last choice..

2)

The last thing that I wanted to add to my player was a system for working out how much every other player knew. Then, if I thought someone was close to the answer, I could guess myself before their turn.

likewise

3) bunch of other crazy stuff I don't remember right now..

[Jubulani]

There seem to be quite a few very good bots in this competition. I too would very much like to be able to pore over the source of all the bots submitted, and analyse tactics. As I said before, I can't wait for the results. And another competition where we can all use the knowlege we get to create true ultimate bots would be great, as mentioned earlier in the thread.

[InterphasicAlien]

Hello All,

Obviously I am new here. . . This is my first post

Anyways I followed the link over from gamedev.net, and decided to participate in the contest. This was my first time implementing a bot (or even taking part in a programming contest ). Any ways, since everyone is shareing stratagies, I thought I might as well.

Well, my strategy was not as sofisticated as those above. I do find it interesting that my algorithm for showing cards wasbackwards to the other strategies here, that is, locations were less important to my bot, and showed those first.

I started from a basic bot, and tried to improve from there.

Basically, the bot has a table mapping every card to a flag that could be set to Yes, No, Maybe no, and maybe yes. For speed, I also stored the identity of the cards my bot knew was it.

It also had a table mapping cards to ranges of suspects, representing who does not have that card. This was a minor upgrade, and did not seem to affect the bot statistically. It was used primarily to decided if a card that was not shown was already in that player's hand. (If the bot knew)

I think the best improvement I made to the base bot was the movement algorithm, simple but relatively useful. It reduced the number of games the bot spent wandering around, learning nothing. Basicly it weighted all possible moves based on the number of available move it could bake from there. If the location was unknown it got a bonus, making it more attractive to the bot.

Anyways simple, but it was fun!

[Reddyx]

Ok, as you've shared your strategies, I'll try to describe my bots inner workings, too

First, the bot keeps a list of, I called it, partial knowledge structures. This is what most of you implemented as a table, but I found it somewhat simpler to use simple structures, which are just structures containing the 3 cards asked for, the one who responded and what he responded (i.e. card shown or not). Additionally it keeps a list of card->player associations. And of course 3 lists with the remaining, i.e. unknown, cards that could be the cards searched for. I called the partial knowledge structures "partial knowledge", and the cards in the remaining lists "safe knowledge".

The bot now logs all cards shown or not shown to himself or other players. From this, it tries to deduct as much as possible. There are several steps, like applying the safe knowledge on the partial knowledge, and the other way round, until nothing changes any more. Also, sometimes you can deduce the final cards by looking if nobody has this card (I called it "negative deduce" in the program). I don't think you can really improve something here...

But my bot doesn't act very intelligently when it's his turn... He just asks for two remaining cards (the location is fixed), no matter if one card would be more probable than another one... Also, when moving he just tries to move to a remaining room, otherwise if he cannot reach one, moves randomly. Those two functions could of course be improved

[Dudi Hatotah]

Some strategies replies:

on the other hand, when no one shows a card on my suggestion and I am holding 2 of them in my hand, your bot will mark the two cards in my hand as more suspicious...

True. It will slow down my progress a bit.

I will advance at same rate or faster. I will either see 1 card (same as asking 3 unknowns) or I will know the guilty card (not possible with 3 unknowns) unless you guessed all 3 correctly.

Not true.
When I ask 3 suspicious cards I get much more information than you when a player DOES NOT show me a card. I know that that player doesn't have the 3 cards. You would only know that the player doesn't have 1 card.
As I've mentioned earlier, when I tested it, a bot who asked mostly its own cards was beat by one who asked suspicious cards. Then again, maybe my testing was wrong. I guess we'll find out when the results will come in.

All the algos I tried had my bots chasing after cards in other players hands. Which almost lead me to look at the least likely as more suspicious.

You are kinda supposed to chase after cards in other players' hands until you know they don't have them?...

A couple of other things I did too, was if I couldn't ask cards in my hand, I would ask cards that I knew was in the player before me hand.. that way the suggestion would have to go through all the other players first increasing the chance I won't be shown a card I already knew.

I kinda implemented that. When I'm forced to ask about a location that I know that some player has, I always ask the location for which the player who has it is the furthest away from me.

It also had a table mapping cards to ranges of suspects, representing who does not have that card. This was a minor upgrade, and did not seem to affect the bot statistically.

That was one of the foundations of my bot... The way I see it, when a player does not have a card, it makes the card more suspicious. This infomation is also very useful when the player does show a card (if you know that the player doesn't have 2 out of the 3 suggested cards, for example, you now KNOW that he has the third card!).

[Darryl]

Some strategies replies:

I will advance at same rate or faster. I will either see 1 card (same as asking 3 unknowns) or I will know the guilty card (not possible with 3 unknowns) unless you guessed all 3 correctly.

Not true.
When I ask 3 suspicious cards I get much more information than you when a player DOES NOT show me a card. I know that that player doesn't have the 3 cards. You would only know that the player doesn't have 1 card.
As I've mentioned earlier, when I tested it, a bot who asked mostly its own cards was beat by one who asked suspicious cards. Then again, maybe my testing was wrong. I guess we'll find out when the results will come in.

When you ask 3 cards and a player does not show you the card... you AND I know the player does not have those three cards... so the same rate.. the only advantage of asking 3 unknowns is that you might stumble upon the right 3.

Darryl

[Darryl]

My Bot can be downloaded here. I would suggest right click, and save as.

Darryl

[Ryan]

My contest script is running now. There are 14 entries, which makes for 1001 unique games of 4. I'll be running each game 10 times, so results should be pretty thorough. There'll be a lot of game logs to download, that's for sure.

Game 261.. game 262... Results should be ready within a couple of hours. Thanks for your patience!

[Ryan]

Ack, technical difficulties. I'll keep you posted.

[Jubulani]

Ack, technical difficulties. I'll keep you posted.

Sorry folks, the delay is my fault. My bot seems to be crashing a lot when compiled with VC++ 7.1. I coded it with Borlands bcc32 5.6.4 and tested with gcc 3.2 under mingwin and it worked fine with both of those.

Something seems to be wrong with it though.

I blame Microsoft. Why blame yourself when you can blame Micro$oft???

Its not like like they don't take the blame for everything else!

I'll submit a bugfix as soon as I can. grrr

[Jubulani]

I'll submit a bugfix as soon as I can. grrr

Done, and all sent off.

It seems I was using a slightly unportable construction while iterating over a list, or maybe cl optimized more than it should have done.

Debuggers are so wonderfull, having to find bugs using only printf is a PITA.

Sorry for the delay everyone.

Let the judging commence!

Good luck all.

[Jubulani]

My Bot can be downloaded here. I would suggest right click, and save as.

My (fixed) bot is here if anyone is interested.