Jump to content
  • Advertisement

mudslinger

Member
  • Content Count

    26
  • Joined

  • Last visited

Community Reputation

142 Neutral

About mudslinger

  • Rank
    Member

Personal Information

  • Interests
    Programming

Recent Profile Visitors

The recent visitors block is disabled and is not being shown to other users.

  1. If I use MCTS but with "reward" as -1, 0, and 1 for lose, draw, and win respectively, can I use the UCT formula as is? uct = node.rewards/(node.visits+1.0) + explorationRate * sqrt(ln(node.parent.visits) / (node.visits+1.0)) Afterwards, I still return the node that was most visited as the best move?
  2. mudslinger

    Hidden information games AI

    Hello, I implemented a cheating MCTS. Definitely better, but still beatable. Will improve on that before doing anything fancy.
  3. mudslinger

    Hidden information games AI

    Thank you for your reply. I think this is similar to what I've done for piece prediction: I keep track of piece's possible highest and lowest ranks after challenges. I then use this information to generate plausible board configuraions. Currently reading this paper on Information Set Monte Carlo Tree Search: https://pure.york.ac.uk/portal/files/13014166/CowlingPowleyWhitehouse2012.pdf Longer version: https://pdfs.semanticscholar.org/d10e/31ed85cc6ea79d3d961730da2b07c32aa984.pdf
  4. Edited for brevity. I made a post 8 years ago about this Stratego-like game: https://www.gamedev.net/forums/topic/585572-game-of-the-generals-ai/. Are there advances in AI in the last eight years you recommend? As I understand, MCTS/UCT/AlphaZero is not applicable because of hidden information. My AI implementation uses MC playouts + UCB1 + inference of opponent's pieces. It's not effective, though it makes smart moves on the end game, like the flag piece running away.
  5.   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). 
  6. 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.
  7.   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.
  8. 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
  9. mudslinger

    AI for a simple shedding card game

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

    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. http://pastebin.com/rddWUSzF
  11. mudslinger

    AI for a simple shedding card game

    Yes, I just realized how simple UCB1 is. I'm reading another paper/presentation: http://www.cs.bham.a...ctures/ucb1.pdf. 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 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]
  12. mudslinger

    AI for a simple shedding card game

    This looks like a very good resource: http://www.personeel...ressiveMCTS.pdf 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.
  13. No, it's for this: http://www.gamedev.n...ding-card-game/ I believe this is logically complete, but is still a bit naive: 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 I'm still looking at alvaro's code.
  14. mudslinger

    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.
  15. 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?
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!