• Advertisement

gpmelendez

Member
  • Content count

    22
  • Joined

  • Last visited

Community Reputation

142 Neutral

About gpmelendez

  • Rank
    Member
  1.   I thought of these, it is a yes on all three points. It is the nature of the game that the strength of a piece is partially revealed after a challenge (e.g. opponent's piece won, it's stronger than mine). 
  2. But it is possible to compare two values from different parties without revealing those two values.   http://www.proproco.co.uk/million.html   I believe I currently have a solution in my head.    EDIT: I plan to use the millionaire solution (link above) to compare pieces. To guard against players cheating the system by always sending a high piece, both players exchange encrypted piece positions with each other at game start. at game end, the decryption keys are exchanged to determine if they had been telling the truth.   It's rough, but it looks doable.
  3.   This defeats the point of my question. I don't think it's entirely impossible. Yao's millionaire problem comes pretty close.   This isn't really for a game, it's more of a thought experiment.   EDIT: I believe the problem is Secure Multi-party Computation, I just don't know how to implement it exactly yet.
  4. Hello,     I have a question about how to create a mutual p2p trust between two players of this game. We have this stratego-like board game with game pieces of various ranks. When a there is a challenge between two pieces (they go to the same square) the winner (higher rank) is determined by a third party. The opponent's game pieces are never revealed to the other player.   How would I make a p2p program that doesn't require a third party and doesn't reveal the game pieces?   Problems with some suggestions:   Mental Poker - no, because the cards are revealed at some point. Homomorphic encryption - no, because this requires the same encryption key. Yao's millionare problem - no, because the higher piece doesn't always win, there are exceptions (see Spy and Private in the wiki link below)   http://en.wikipedia.org/wiki/Game_of_the_Generals
  5. AI for a simple shedding card game

    I have more or less finished the game, it can be played here: [url="#"][/url] . Java is needed. I also put the rules here: [url="#"][/url] Everything on the website is still beta, the game doesn't even have drag-and-drop. I was too lazy to write it
  6. AI for a simple shedding card game

    I think I understand the tree part now. The expanding part is not directly dependent on the number of simulations, for example, I can do 1000 simulations, then generate a branch. I can generate another 1000 simulations, then generate another branch. I think I can't apply this to my game since the game has a max 13 moves at the start and this drops quickly. I'd run out of moves for the tree. Your pseudocode is what I had in mind. I'm not familiar with tichu. here's my UCB1 code, it's a bit rough, I apologize. [url="http://pastebin.com/rddWUSzF"]http://pastebin.com/rddWUSzF[/url]
  7. AI for a simple shedding card game

    [quote name='alvaro' timestamp='1349986268' post='4989234'] UCB1 is basically formula (1.1) in that paper. [/quote] Yes, I just realized how simple UCB1 is. I'm reading another paper/presentation: [url="http://www.cs.bham.ac.uk/internal/courses/robotics/lectures/ucb1.pdf"]http://www.cs.bham.a...ctures/ucb1.pdf[/url]. I just made a simple C implementation of UCB1 with the rand() function. It does test more rewarding functions more. This is making more sense to me. I'll start coding again tomorrow. EDIT: I just realized that the tree in the progressiveMCTS paper is not the game tree I think it is. I thought it was something similar to a min-max tree, in which each layer is a turn of each player. It is not - all of it is the turn of the current player. Is this thinking correct? I'm confused as to how this would work though, all of the results are back propagated to the root, and the root is always visited, therefore the root will always be chosen as the move. EDIT2: It does say the child that was visited the most [img]http://public.gamedev.net//public/style_emoticons/default/tongue.png[/img] again, more feelings of realization. Based on the simple rule, since a leaf will be expanded upon simulation, does this mean each leaf is simulated only once? [s]Then again, trees might not be worth it, it's probably better to just list every possible move, then run UCB1 on them.[/s]
  8. AI for a simple shedding card game

    This looks like a very good resource: [url="http://www.personeel.unimaas.nl/g-chaslot/papers/progressiveMCTS.pdf"]http://www.personeel...ressiveMCTS.pdf[/url] as Alvaro pointed, I believe building a deep tree will not be helpful, as uncertainties will compound. maybe trees aren't even helpful at all. I'm doing reading on UCB1.
  9. [quote name='Glass_Knife' timestamp='1349887736' post='4988769'] Is this for open faced Chinese poker? [/quote] No, it's for this: [url="http://www.gamedev.net/topic/632575-ai-for-a-simple-shedding-card-game/"]http://www.gamedev.n...ding-card-game/[/url] I believe this is logically complete, but is still a bit naive: [CODE] straight look for cards with the same face value, keep only one of them in the temporary deck sort, look for cards with consecutive face values 5+n consecutive cards = n+1 straights (so far) substitute cards in the straight with the same face value, add each to list flush sort the cards by suite, 5+n cards with the same suite = n+1 flushes full house sort cards, look for cards that occur >= 3. if none, quit look for cards that occur in pairs. C(n1,3) . C(n2,2) for faces that occur >= 3. C(n,3) . pairs 4 of a kind sort cards, look for 4 same face values 5th card any other card straight flush use previously found straights and flushes, avoid duplicate combinations [/CODE] I'm still looking at alvaro's code.
  10. AI for a simple shedding card game

    I'm not that familiar with Monte Carlo, although I fully understand the pseudocode. What do you mean by "construct/expand a game tree while the playouts are being played"? I'm thinking this means I should use a game tree then randomly playing out the leaves. I'll be reading about UCT and Monte Carlo in general, I hope it will be fruitful.
  11. Hello, We have this game with 4 players where each players take turns to discard cards that must be higher than the ones previously discarded. The last player with remaining cards loses. I have code on the gameplay, and the AI has code that can list valid combinations from the cards that it has. I'm planning to use Monte Carlo playouts. What do you think?
  12. Hello, I'm looking for an algorithm that finds the poker combinations (specifically straight, flush, full house, four of a kind, and straight flush) in a set of 13 cards. The most naive implementations is to check each element in a power set of the cards (hence 1287 possible combinations), but experience tells me there is always a better way. thanks.
  13. Game of The Generals AI

    Quote:Original post by willh Throw in an opening book and you're done! Makes me want to try this out now. lol. :) Please, do try it out. :D
  14. Game of The Generals AI

    Hello again, I'm kinda lost with probabilities. I don't know how to adjust the chances of a piece being a certain piece using Bayes'. Here are the simplified rules of the game: Each player has: amount type 1 flag 6 privates 1 rank 1 1 rank 2 1 rank 3 1 rank 4 1 rank 5 1 rank 6 1 rank 7 1 rank 8 1 rank 9 1 rank 10 1 rank 11 1 rank 12 2 spies --- 21 (1) Higher rank takes out lower rank, privates and flags (2) Spies take out all ranks and flags, except privates (3) Privates take out spies and flag This means every piece has a 1/21 chance of being a flag, 6/21 of being a private, 1/21 of being rank 1, ..., 2/21 chance of being a spy. (Note: I'm speaking in the perspective of the AI) My questions are: (1) How do I adjust piece probabilities if my piece Rank N takes out an enemy piece with Rank M? (N < M, N is known) (2) How do I adjust piece probabilities if an enemy piece Rank N takes out my piece with Rank M? (N < M, M is known) (3) How do I adjust piece probabilities if my piece Rank N takes out an enemy piece with Rank N? (equal pieces, both are taken out) It is obvious that if a piece takes out a spy, that piece must be a private. Also, there must always be a Flag. What I've done so far is to set ranges on enemy pieces. That is, if it takes out my piece Rank N, that piece is sure to be a piece with Rank >N. Spies are counted, so that if my private takes out a spy, then the number of spies of my enemy decreases. Thank you.
  15. Game of The Generals AI

    Quote:Original post by InnocuousFox That said, I don't think Monte Carlo is even necessary. This is the algorithm I might try next: For each move M { Do 1,000 (or more) times { Generate a plausible configuration for the pieces of the opponent using Bayes. Run minimax on M Count points for possible gains and losses for move M } Sum points for move M } Pick the move with most points Thanks to everyone who's been replying.
  • Advertisement