$18.00
GeekGold Bonus for All Supporters: 100.68

6,373 Supporters

$15 min for supporter badge & GeekGold bonus
40.2% of Goal | left

Support:

Recommend
3 
 Thumb up
 Hide
6 Posts

Kamisado» Forums » News

Subject: Kamisado Free Android App rss

Your Tags: Add tags
Popular Tags: [View All]
Ali AVCI
Turkey
flag msg tools
new user
Hello everyone. I just registered to the forum.

I'm studying computer science in my country and I love game development with AI. So I decided to make Kamisado game to Android.

I used minimax algorithm for game core. But I am pretty new for Kamisado. So that difficulty may be weak. But I can improve AI with your helps. If you want to contact me, my skype : oceanjack35 .

For now, I just made single match version. You can also play 1v1 with your friends.

https://play.google.com/store/apps/details?id=com.alihan.kam...

I am waiting your reviews. Thank you!
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Federico
Italy
Val di Non
Trentino
flag msg tools
mbmbmbmbmb
Thanks for creating it.

The board could be easier to read by increasing the contrast between the colors, going for something more vivid.
On small screens the colored parts of the pieces are quite small. Have you tried to reverse the color scheme of the pieces, using a black/white character on a colored background with a black/white border? I don't know whether it would be an improvement, but I would consider trying it.

It would be nice to have the possibility to set up the board to study specific positions.

AI: how deep is it reading?
I tried only my usual opening, and Medium seemed to answer better than Hard on the first couple moves. But it's probably only because both read fewer than 8 (since Hard in the games I tried seemed to choose the most advanced move on the board not losing within 7).
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Ali AVCI
Turkey
flag msg tools
new user
Firstly, thank you for your reviews and suggestions.

As I said, I am pretty new to Kamisado, my algorithm may be fail sometimes.
That's how I made algorithm to sort all nodes :

List<Point> opponentPoints = node.board.getMovableTiles(!player1, (int)node.tile);//movable tiles for opponent
List<Point> myPoints = node.board.getMovableTiles(player1, (int)node.tile);//movable tiles for me
puan += ((myPoints.Count - opponentPoints.Count) / 15.0d) * 10.0d;
puan += (criticPawns(!player1, node.board) - criticPawns(player1, node.board)) * 10.0d;//critic pawns that only movable to 2 or less tiles.
puan += (tilesEva(node.board, benimPoints) - tilesEva(node.board, karsiPoints)) * 15.0d;// all available unique tiles to move
puan += (tumMovable(player1, node.board) - tumMovable(!player1, node.board)) * 15.0d;//all movable tiles count
puan += (node.board.gerenKoyluler(player1) - node.board.gerenKoyluler(!player1)) * 70.0d; //the piece count that sees win.


In this algorithm, CPU should sort all tree nodes y a heuristic function. If you think you can upgrade this algorithm, just contact me.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Federico
Italy
Val di Non
Trentino
flag msg tools
mbmbmbmbmb
Thanks for sharing, it's very interesting.

If I understand correctly, this is how you weight your heuristics:
a) 70 * win-in-1 differential (towers that can win if activated)
b) 15 * sum of possible moves differential (all possible moves from all towers)
c) 15 * unique reachable tiles differential (all tiles that can be reached)
d) 10 * critic towers (that can move 0-2 spaces) differential
e) 0.67 * move differential (how many moves I can choose from - how many the opponent will chose from)

What is missing to understand how deep it's searching is how many nodes are evaluated. Is it a fixed amount?

What I see is that the AI tends to favour a bit too much moves that are further ahead which will place it in a not great position. It probably depends on b) c) and d) so it should be possible to find a better balance between them.
Also, a) seems over weighted, since (especially in later rounds) it's often possible to force a win when the opponent has a couple of badly positioned towers, even if all the others are great.


Have you seen this essay on building a Kamisado AI?
From page 13 it explains how they built their heuristics function.

In general I assume you too tried different approaches to see which set of weightings produced the better result.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Ali AVCI
Turkey
flag msg tools
new user
I am already using the heuristic function in the essay.

But important thing is priority of sub-functions. For example, I multiplied 70 by win-in-1 function differential. It means win-in-1 result is very important than others. I need to find optimized values for factors.

I am using 6 for hard depth. Because the program calculating 5 different sub-functions. If we think 5 sub functions costs 5 milliseconds and we have 10.000 different moves and I am using 5 threads, it means 10 seconds. If It costs 10 milliseconds, it costs 20 seconds. See the difference.

For optimization, at least I need to reduce sub-function count or find a best sub-function algorithm or find best factor values.

I hope you can help me about that. That's why I post here. Some professional Kamisado players may help me.

Best regards.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Federico
Italy
Val di Non
Trentino
flag msg tools
mbmbmbmbmb
saraceno wrote:
I am already using the heuristic function in the essay.

But important thing is priority of sub-functions. For example, I multiplied 70 by win-in-1 function differential. It means win-in-1 result is very important than others. I need to find optimized values for factors.

Yes, I agree.

What I was asking is: did you try letting your AI play against itself with different priorities in order to find better values?

This may be a bit far-fetched, but what about using an evolutionary algorithm? You could let differently-weighted versions play against each other and use the strongest to breed a generation with better values.


saraceno wrote:
I am using 6 for hard depth. Because the program calculating 5 different sub-functions. If we think 5 sub functions costs 5 milliseconds and we have 10.000 different moves and I am using 5 threads, it means 10 seconds. If It costs 10 milliseconds, it costs 20 seconds. See the difference.

For optimization, at least I need to reduce sub-function count or find a best sub-function algorithm or find best factor values.

Kamisado is very often played on a knife edge: most moves lead to a loss and the player has to find what often feels like the single path leading to a forced win.

I fear 6 is definitely too little to play well, because even we humans can go past that (of course taking MUCH longer than your AI). So it really seems that some aggressive alpha-beta pruning will be needed.

It's very hard to reduce the field though. While I like to read deep, most of the time I simply prioritize which first move seems most sensible, but then if it doesn't win I must search the others too. To me it's not easy to say that a certain sequence should not be evaluated, because sometimes the best move is a very weird looking one.

For example, while playing with your AI, this sequence happened:
(F) Pink straight to Purple
(AI) Purple straight to Yellow [bad, loses in 10]
(F) Yellow straight to Green
(AI) Green straight to Red [best answer, loses in 8]
(F) Red one step right to Blue
The last move is definitely not one that would be considered good by your heuristic nor anyone watching casually, but it's the best. This is the kind of move that it's hard to spot and make alpha-beta pruning hard.

saraceno wrote:
I hope you can help me about that. That's why I post here. Some professional Kamisado players may help me.

I don't think any professional player exists actually.

The strongest I have seen are numbers 1 and 2 on yucata.de. Geier is probably the strongest on the server at the moment. He seems to have a better heuristic than me, since I'm slower. Though we both won against each other.


One more suggestion: the AI that seemed best to me was BoardSpace's. It pays one-round only like yours, but it's very fast and seems to read much deeper.
Either it's doing what you'd like (but I'm not sure how) or it uses some pre-computed data because it's simply both too good and too fast.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Front Page | Welcome | Contact | Privacy Policy | Terms of Service | Advertise | Support BGG | Feeds RSS
Geekdo, BoardGameGeek, the Geekdo logo, and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.