Jump to content

  • Log In with Google      Sign In   
  • Create Account

Plusekwal

Member Since 07 Aug 2010
Offline Last Active May 08 2012 07:50 AM

Posts I've Made

In Topic: How to add an exception in port forwarding?

29 September 2011 - 09:06 AM

the error was

directive "netsh add allowedprogram {app}\game.exe AppName ENABLE" has no value

I'm trying to add an exception in the port forwarding table using code. The protocol I use is TCP.

In Topic: Pausing the game in multiplayer

30 July 2011 - 01:19 AM

Thanks for the replies.
I think I will add both the both the automatic player thing Tom Sloper suggested and the pause - it will be without vote, but the player will have to give a reason in order to pause. The pause will be limited to 3 mins and there'll be a small countdown before the game is unpaused if cancelled earlier. There'll be also one pause per player.
During the pause the screen won't go black or gray - infact the only difference will be that players wont be able to make moves and the time will be stopped and it'll write PAUSE with the time remaining somewhere.
What do you think about this?

Also, I think it's important to add that there won't be any teams or stats or even profiles - everyone can play with different nickname every time s/he joins the multiplayer room. Also there won't be any competitions (or atleast there wont be built in system for this) - so I think there isnt really any reason to delay the already lost game.

In Topic: How to make more difficult AI for a board game

18 July 2011 - 12:14 PM

How do you lose pieces? Also, after a new piece is spawned, the coloring of the squares involved goes away?


You just move onto enemy pieces to destroy them. And the colour doesnt go away, so this is a kind of limit for the number of possible pieces. However, the enemy player can always change the squares in your colour into his colour.

In Topic: How to make more difficult AI for a board game

18 July 2011 - 11:32 AM


Analysing the potential moves by even only one turn after the AI will take way too much computing time. It looks like I'll have to use MCTS

Posted Image

From the sound of what little you have told us about your game, your state space can't possibly be THAT big. Either that or your are running the game on a platform with the computing power of an abacus.

Well, three moves per turn can have many possiblities and as far as I understood from that website, minimax needs at least three to four turns to compute. Also, there's some pretty complicated math involved when creating new pieces.



I was asking if minimax can use only the results from one turn ahead.


Oh, ok, gotcha.

From the sound of what little you have told us about your game, your state space can't possibly be THAT big. Either that or your are running the game on a platform with the computing power of an abacus.


I'm not sure about that. The board is small, but each turn is 3 moves long. Naively, he'd have to search 6 plys just to see a full turn ahead -- not so much "min-max" as "min-min-min-max-max-max." Naively, this gives a min-max branching factor of (4*10)^3 , which is huge.* So it's not trivial.

That said, many of these turn sequences result, after 3 moves, in identical gamestates, so I don't think the "true" branching factor needs to be so high. It could be kept down e.g. by hashing visited states, or perhaps by thinking carefully about what states are reachable.

*(I'm assuming 10 pieces, each of which can move in one of 4 directions.)

I was actually considering maximum three moves per piece to be considered - one for eliminating maximum number of enemy pieces, one for colouring(see below) and one for escaping/defending own pieces.



The enormous branching factor that results from compound moves is a serious obstacle to the success of minimax in certain games, as I mentioned in my first response. So MCTS seems promising. You can consider each separate piece moving as a proper move, since MCTS doesn't require turns to alternate, the way minimax does. If the nature of the game is such that random moves will progress towards the end of the game, you might be able to set something up without too much effort. If not, you either need to implement a biased playout policy that will make progress towards the end of the game, or you may have to combine an evaluation function with MCTS, so after a few moves from each side you'll use the evaluation function as reward.

Please, let us know if you are making any progress. Also, it would be cool if you could post a full description of the rules.

I'm still wondering if switching to MTCS will be worth it. I dont know if MCTS will be applieble to this game. Also, computing time might not be that big after all. As for the rules:
-the board is 9x6 squares big
-the game ends when there are pieces of only one player left
-every player starts with one piece only
-one piece can do five actions - moving in the four directions and colouring the square which it is currently on in the colour of the player
-upon colouring if the new coloured square makes a row, a column or a diagonal of three colourd squares in the colour of the player, new pieces are spawned at the empty places


Per piece, you compute a list of potentially reachable spaces on the board (do I move this guy 1, 2, or 3 times?). Then you prune conflicts (i.e. two pieces land on the same square). Then you prune the number of valid combinations using a simple allowance metric (i.e. only 3 moves are allowed per turn). This gives you a finite, bounded set of moves which is not substantially larger than the set of potential moves in an average chess game, if my napkin mathematics does not betray me.


Yeah, that was my thought too, and it might work, but there are some situations that confuse me. E.g.,
XXXX 	XXXX 	XXXX 	XXXX
XX X  	XX X 	XX X 	XX1X
X 2X -> X2 X -> X21X -> X2 X
XX1X  	XX1X 	XX X 	XX X
XXXX 	XXXX 	XXXX 	XXXX

(1, 2, and X denote pieces; spaces denote empty space; this is a three-move sequence where the order of 1 and 2's moves matter.)

[Aside: The code tags do weird things, adding and removing spaces; getting ASCII art to look right is a pain...]

I'm not saying that there isn't an efficient way to resolve this so that you keep the attractive properties of just considering what squares are reachable (in which case you just get something like 3k moves), but how to do it doesn't jump out at me.

As for this situation, piece 2 can move upwards an piece 1 upwards and then leftwards - there is no difference. Besides, due to the nature of the game the board will never get that crowded.

In Topic: How to make more difficult AI for a board game

17 July 2011 - 12:33 AM

I'm sorry, but I don't understand your question. I can't even parse it.

I was asking if minimax can use only the results from one turn ahead.

It sounds like you just don't understand the idea of minimax yet.

Just think of it as propagating numbers up a tree to begin with. They start at the leaf nodes, and work their way to the top. Once you have all the numbers, then think about the actions that they imply.

Play with the Java applet at the bottom of this page for a bit; you'll see how it works.


Anyway, I got a question about the minimax formula: is it a good idea to based on the consequences from the AI's moves only?

Minmax, by definition, needs to iterate through the potential game spaces. Since the other player is likely changing the game state along the way, you pretty much can't derive a realistic result from Minmax unless you are taking the other player's moves into account.

Analysing the potential moves by even only one turn after the AI will take way too much computing time. It looks like I'll have to use MCTS

PARTNERS