0

We're having a sort of hackathon week here at school, and our challenge is to build a client AI which connects to a server and plays Pente against others AI. (Pente - Wikipedia)

The only AI course we had was about the Prologue language and we're kind of lost as far as choosing an algorithm for our AI. We obviously don't want to just apply a bunch of if statements and need something fairly adaptive, so we were wondering what kind of/which algorithm would be best suited for this kind of challenge and why?

So far we've looked over genetic algs but they don't really seem to be suited for this situation since saving any solutions wouldn't really help calculate another.

5unkEn
  • 78
  • 7
  • You can't take a look at API.AI. I'm not sure if you can use it for games (in your case). But it's what Google uses for there Google home. https://api.ai/ – gwesseling Apr 10 '17 at 11:35
  • 2
    There are basically two general approaches for these kind of games: [minmax](https://en.wikipedia.org/wiki/Minimax) and [monte-carlo-tree-search](https://en.wikipedia.org/wiki/Monte_Carlo_tree_search). Sometimes these are combined (they are just frameworks and good AIs use tons of important details wihtin these) with more complex stuff like DeepLearning and co. From these two, i would go with MCTS as your state-space looks huge (and it's easier to obtain *good* results without investing much time into domain-dependent heuristics)! – sascha Apr 10 '17 at 11:36
  • Do you have knowledge about tree algorithm and depth first search algorithm? – kodmanyagha Apr 10 '17 at 11:36
  • @kodmanyagha we're had a look at those but never really applied them. I have a fair understanding of how they work however. – 5unkEn Apr 10 '17 at 11:40
  • Your problem is only a search algorithm in the tree. I can write the pseudo code but implementing it is some difficult. How many times do you have? – kodmanyagha Apr 10 '17 at 11:42
  • @sascha Thank you, I will have a look over it, we're really inexperienced with all this AI thing haha – 5unkEn Apr 10 '17 at 11:43
  • @kodmanyagha we've got till Thursday evening, a pseudo-code example would be cool, we don't want someone else implementing stuff for us anyway and I think we can manage if we have a concrete example. – 5unkEn Apr 10 '17 at 11:45
  • @5unkEn A simple tree-search won't help. The state-space is probably something > 10^100 and this will be infeasible to search. MinMax is based on this kind of search, but theory crafted for these type of zero-sum pefect-information games allows huge prunings (ignoring large parts of the tree; alpha-beta search) and MCTS uses some kind of random-samplings of this state-space to infer information. I very very much recommend to understand either one of those two approaches before approaching anything else (especially the GA stuff; which is more of a possible component within one of these) – sascha Apr 10 '17 at 11:47
  • I'm writing in my phone now. I will write pseudo code when I go to home. – kodmanyagha Apr 10 '17 at 11:48
  • @sascha I'm looking at the MCTS and it does seem to be the best solution. This game is a simpler variant of Go from what I gathered. I understand most of the principles behind this but I'm having some trouble picturing the actual implementation. I'm going to finish reading some theory and look for a git hub repo of a project implementing this most likely. – 5unkEn Apr 10 '17 at 11:55
  • Questions asking us to recommend or find a book, tool, software library, tutorial or other off-site resource are off-topic for Stack Overflow as they tend to attract opinionated answers and spam. http://stackoverflow.com/help/on-topic – Rob Apr 10 '17 at 11:57
  • 1
    @Rob Yes, that's true, I felt this is a rather specific problem however, I don't think it's any different than [this one](http://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048) for example. But that's not the point of this anyway, we've learned a lot already. – 5unkEn Apr 10 '17 at 12:03
  • Note that question is also protected and moderated. Although that's a different case, don't use other questions as examples cause it might be that they haven't been caught yet. – Rob Apr 10 '17 at 12:11
  • 1
    @Rob But the reason for this, as stated, is something else. It's also connected to consistency and fair handling of user-questions. I would be mad too if some other question sharing the same characteristics is working fine while mine got shut off, just because the other is targeting a more popular game. While rule-wise this question here might be off-topic, i would accept it when someone wants to close it because of too broad, but the closing-reason of yours is not what i would call a good fit. (haven't been caught yet is also funny in this case; because it's old and very very popular) – sascha Apr 10 '17 at 12:17
  • @sascha Which is why I point out that the other question is protected and moderated. It falls into the tutorial or documentation category which I don't follow so can't comment on. In any case, this is asking for a recommendation which can draw in opinions and recommendations of libraries, tools and, eventually, spam for someone's course or tool they are selling and you can see where this can all lead to. – Rob Apr 10 '17 at 12:22
  • 1
    This game is not similar to go (although MCTS might still work). Go (Baduk/Weiqi) is a territory game and it's much more complex than Pente. E.g. in Pente you never wanna play more than 5 spaces away from the stones already placed, because you either want to block or make threats or threat potential. – maraca Apr 10 '17 at 12:23
  • I did not check out Pente in detail. But if maraca's rule applies, it's a very very important detail for every approach (incorporate this rule/heuristic; and might even make MinMax attractive again because the state-space collapes into something much smaller)! – sascha Apr 10 '17 at 12:25
  • @sascha wouldn't that only apply if the adversary follows the same principle? If he places pieces far away from the initial area, wouldn't that in turn make the area you need to analyse larger (provided you only select the area that's 5 spaces away from the edge pieces) – 5unkEn Apr 10 '17 at 12:37
  • @5unkEn Check out the MinMax principle and decide yourself. The intuition: if the oponnent is playing bad-moves which can't hurt me, i don't care. I play the good ones and don't need to check the bad ones. So it could be possible, that there is always a better move within these 5 piece-range, so why checking others (implementation-wise this can be simple or not; depends on the problem) – sascha Apr 10 '17 at 12:41
  • @maraca fair ehough, this was a misunderstanding on my part then, we've been introduced to it this morning. I'll note this down, it sounds obvious now that you say it and like sascha said, it's not a detail that should be left out, thank you! – 5unkEn Apr 10 '17 at 12:41
  • @sascha you're right, I was thinking along those lines as well. I'm gonna get to work now, thanks for all the comments, it helped a lot! – 5unkEn Apr 10 '17 at 12:43
  • If you plan to write an evaluation function. This paper inspired me years ago https://link.springer.com/chapter/10.1007%2F978-0-387-35706-5_16 Although it's a different game you can learn how to extract possible features and how to weight them. – maraca Apr 10 '17 at 14:35

0 Answers0