Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length

 
Advanced search

1345208 Posts in 61706 Topics- by 53283 Members - Latest Member: maxnielsen

August 19, 2018, 11:48:18 AM

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsCommunityDevLogsAbalone [Boardgame]
Pages: [1]
Print
Author Topic: Abalone [Boardgame]  (Read 740 times)
lithander
Level 3
***



View Profile WWW
« on: February 17, 2018, 07:45:56 AM »

As a kid I liked to play a boardgame called Abalone



When I recently remembered it I went to the Play store thinking that surely someone would have made an app based on it? Of course... there were a couple of free ones and even the boardgame publisher Asmodee had an official app. But...

I tried every app I could find and each game ended with me winning 6-0.  Shrug I didn't play this game for years... so I doubt I'm that good. The AIs were just bad, really. And the stronger it was the more boring (e.g. defensive) it played so this spawned the idea for a little side project.

I'm going to develop an Abalone AI that can beat me in style. Smiley
« Last Edit: February 25, 2018, 07:16:09 AM by lithander » Logged

lithander
Level 3
***



View Profile WWW
« Reply #1 on: February 25, 2018, 07:15:37 AM »



I'm currently about 400 lines of code into the project. The app takes mouse input, enforces the game rules and visualizes the current game state using SFML. I decided to opt for hardware accelerated procedural rendering (shapes defined in code instead of using texture assets) for now which has the immediate benefit of alias-free rendering on any arbitrary sized surface.

Logged

lithander
Level 3
***



View Profile WWW
« Reply #2 on: March 07, 2018, 04:03:56 PM »



I've started working on the fun part (the AI). After first building a computer player that was merely making random moves this one is using a simple heuristic to score each viable move and then pick the best one. And voila: unlike random moves this looks like someone playing Abalone.
Logged

lithander
Level 3
***



View Profile WWW
« Reply #3 on: March 08, 2018, 08:17:24 AM »

I understand that this project might be of limited interest to most indie-game enthusiasts. But let me know if there's anybody interested in the details of programming a board-game AI but has trouble to follow my process due to brevity of the posts. Until further notice I'll assume my audience is familiar with terms like treesearch, minmax, alpha-beta pruning, heuristics etc! (A reasonable assumption as long there's no evidence of an audience beyond myself^^)
« Last Edit: March 09, 2018, 09:41:44 AM by lithander » Logged

TheCams
Level 0
**


View Profile
« Reply #4 on: March 09, 2018, 08:52:08 AM »

I'm following the thread, I used to love this game as a kid.
I dont know much about AI, all I ever did was a naive min/max algorithm for a Connections game.

I'd be interested in testing the game once you have a prototype to share.
Logged
lithander
Level 3
***



View Profile WWW
« Reply #5 on: March 09, 2018, 12:58:29 PM »

Before I'm trying anything fancy I'll make sure to get a decent minmax based algorithm up and running to have something to benchmark against. But to play against that AI a UI is needed, too. And what I'm currently working on is more like a dev tool rather than a game. It will lack all the audio-visual pleasure and handholding you'd exepect from a real game. But on the flipside the user will have more freedom to goof around. Like rolling moves back, changing the board at any time, moving multiple times in a row etc. I'll PM you a direct link as some kind of early-access when I've reached a minimum viable product. Wink
Logged

TheCams
Level 0
**


View Profile
« Reply #6 on: March 09, 2018, 01:09:39 PM »

Thanks Smiley
Logged
lithander
Level 3
***



View Profile WWW
« Reply #7 on: March 31, 2018, 03:56:50 AM »

That *all* the AIs I've played against were bad could have given me a hint: This project isn't as trivial as I originally thought!

I thought I could write something decent with traditional bruteforce approaches and then move on to the real interesting stuff like deep learning etc. Well... I'm still stuck at the "something decent" phase.

Abalone is a turn-based game with no chance element so there's a game tree you can search. Sadly it's impossible to search it exhaustively - which would mean you'd consider every possible way the game could play out. I tried two bruteforce strategies: Monte-Carlo Tree Search, where you pick random moves until the game terminates and from the result of such playouts you infer the quality of the involved moves. But yu need the results of many playouts to get anywhere. And with Abalone there are two problems: Games can take thousands of random moves to terminate. (This is different in other boardgames) And to generate the list of valid moves in a given position is quite costly. (This is more trivial in other games, too) So I quickly abandoned the depth first approach.

The breadth first search seems more promising. Searching two layers deep using minmax search (e.g. bruteforce breadth first) with a simple heuristic (avoid the edges and stick together) to evaluate the leaf state allready looks like a player that has a basic understanding of the rules. But that's not nearly enough to beat an experienced human. Increasing the search depth to three increases the "thinking time" by the average number of viable moves in a position which can easily approach hundreds. And in my case that meant that a search depth of 3 (which isn't very deep) allready makes the trivial min-max search take way too long for my patience (20s per move)

So what I'm currently doing is to try all kind of optimization approaches to increase the search depth. Alpha-Beta pruning got me to a depth of 3 but I guess that to reach the AI quality I'm looking for i need the AI to be able to look ~5-7 moves ahead. So I'm trying all kind of optimization techniques right now... currently working on a caching approach that allows me to store and lookup the value of known board configurations. There's a lot of literature about that kind of stuff so I'm not doing anything novel here but it's still fun to do and a great learning experience.
« Last Edit: March 31, 2018, 04:06:53 AM by lithander » Logged

Pixelologist
Level 1
*


View Profile
« Reply #8 on: March 31, 2018, 08:42:06 AM »

You might want to look up some videos about chess playing AI. To my knowledge, it's the most highly developed and complex. I forget the developed AI's name, but it's beaten humans at chess who are the best in the world.
Logged
lithander
Level 3
***



View Profile WWW
« Reply #9 on: April 22, 2018, 05:14:11 PM »

...today I lost for the first time against my AI! Grin So there's *some* progress, albeit slow one. (In my experience the biggest risk for hobby projects is that you burn out of motivation and shelve them. Working only when I feel like it conserves that mental energy.)
« Last Edit: April 22, 2018, 05:20:07 PM by lithander » Logged

Pages: [1]
Print
Jump to:  

Theme orange-lt created by panic