Recommend
3 
 Thumb up
 Hide
9 Posts

Onitama» Forums » Strategy

Subject: First/Second player balance issue? rss

Your Tags: Add tags
Popular Tags: [View All]
mingyu cho
msg tools
I am a student planning to major in computer science and this semester, I had to do some kind of project regarding artificial intelligence. I chose to make an AI for Onitama.
Using the movement cards in this link, I managed to use alpha-beta pruning(ABP) to make an AI for Onitama: https://boardgamegeek.com/image/2999035/onitama
I bought a copy of this game at the start of this semester but don't have a friend who likes playing abstract strategy games, so I played this game like 3~4 times and that was all, so do understand me not being able to see whether if the first player or the second player is advantageous.

I am now trying to test the ABP AI of depth 4(meaning it predicts 4 moves before choosing what move to take, in a nutshell) against a random AI which
(1) If it can take the opponent's king, then it takes the king
(2) Otherwise, it takes a random valid move.

My assumption was that since ABP is trivially superior to random, ABP should win for almost all cases. I fully expected that ABP would be winning for more than 90% for all cases.

However, I am finding two peculiar results:
(a) If ABP starts first, it almost always wins(with probability 98~99%)
(b) If ABP starts later, it usually wins(with probability 71~72%), but drastically less than when it starts first.

My question is this: Is this game, in any way, biased against the second player?

EDIT: added my assumptions for the start of this project
4 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Duarte
Portugal
Ponte de Lima
Ponte de Lima
flag msg tools
badge
Avatar
mbmbmbmbmb
In those 4 moves the ABP predicts, does he know that he has to defend first and then attack?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
mingyu cho
msg tools
Yes, the cost of capturing the king(I don't remember what it was called...) is significantly larger than that of capturing the other pieces. That would indicate that the king must be protected before any attack can be made.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jay M
United States
Greenville
South Carolina
flag msg tools
Avatar
mbmbmbmbmb
Just reacting from having played -- the board is small, only five rows. Almost all move cards have only one move forward or less. Tiger is the single exception -- it is the only card that jumps forward 2 spaces.

So moving first puts the player in a position to attack first most of the time, for most of the card combinations. First move a space forward, other player moves a space forward. Now there is a row between them. The first player has the first opportunity to advance and cause the other player's piece to be in jeopardy.

That is the main distinction/advantage I see.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Roxolan
msg tools
Avatar
mbmbmbmbmb
I am very surprised that a near-random AI has such a high win rate, even if there is a bias. What kind of heuristic are you using, when evaluating those 4-deep positions?

As a quick check, have you tried running the ABP AI against itself rather than against a random opponent?

Quote:
(1) If it can take the opponent's king, then it takes the king
Don't forget it can also win by moving its king onto the enemy's starting space (but for your test dummy, maybe you don't really care).
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jay M
United States
Greenville
South Carolina
flag msg tools
Avatar
mbmbmbmbmb
What is the outcome when you run random versus random? It seems like this would also shed light on the first move advantage.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Tysen Streib
United States
San Francisco
California
flag msg tools
badge
Avatar
mbmbmbmbmb
A very strong AI (15-17 move look-ahead) wins as the first player about 53% against itself. Weaker AI's are even closer to 50%. I'd say it's pretty balanced.
5 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
mingyu cho
msg tools
Sorry for the late reply.

For Roxolan's questions:
Quote:
What kind of heuristic are you using, when evaluating those 4-deep positions?

The heuristic I'm using is based on the pieces, the number of moves each piece can take, the number of captures each piece can take, etc. I thought of every possible thing that I can think of which can change the outcome of the heuristic. I can adjust their weights.

Quote:
As a quick check, have you tried running the ABP AI against itself rather than against a random opponent?

Yes, the ABP AI has been run against itself, of which the first player wins with if I remember it correctly, 85% rate.

Quote:
Don't forget it can also win by moving its king onto the enemy's starting space (but for your test dummy, maybe you don't really care).

I didn't really think of that, and this is just a prototype and my advisor told me that not considering the starting space reaching-win is not necessary, though it might be a fun project.

For Jay M's question:
Quote:
What is the outcome when you run random versus random? It seems like this would also shed light on the first move advantage.

Yes, there was a slight advantage to the first player. I don't remember the exact figures, though.

For tysen's note:
Quote:
A very strong AI (15-17 move look-ahead) wins as the first player about 53% against itself. Weaker AI's are even closer to 50%. I'd say it's pretty balanced.

Yes, so I am planning to try other techniques. Perhaps I'll finally install TensorFlow to try some machine learning techniques? But before that, I must upgrade to python3 and adapt to its code, so it might take a while.

I've submitted the project after reading tysen's note, but I'm going to keep working on it. I am trying to upgrade my code to adapt to python3, and am even testing TensorFlow for some learning. I hope more comments to come out, if any tips and/or questions for my AI remains. Wish me some luck!

Edit: Posted all answers for the questions and notes.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher McWhorter
United States
Amarillo
Texas
flag msg tools
You lose....
badge
Think outside the box!
Avatar
mbmbmbmbmb
Quote:
Quote:
As a quick check, have you tried running the ABP AI against itself rather than against a random opponent?

Yes, the ABP AI has been run against itself, of which the first player wins with if I remember it correctly, 85% rate.

Quote:
Don't forget it can also win by moving its king onto the enemy's starting space (but for your test dummy, maybe you don't really care).

I didn't really think of that, and this is just a prototype and my advisor told me that not considering the starting space reaching-win is not necessary, though it might be a fun project.


This is probably your first player advantage balance. If you can add it in, you should be able to verify.
 
 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.