It is currently 19 Jun 2019, 15:51
   
Text Size

[AI] Determining if valid targets are available.

Moderators: TheElk801, BetaSteward, LevelX, North, noxx, JayDi, jeffwadsworth, CCGHQ Admins

[AI] Determining if valid targets are available.

Postby ShivaFang » 01 Jul 2016, 05:36

I'm working on building a MonteCarlo AI for X-Mage and I'm having decent amount of success so far.

one of the main issues I am having at the moment is finding a way to restrict spells and abilities that do not have valid targets. I know the code for this exists somewhere (because it's what is used to highlight the card on the player's side) but I cannot seem to find it.

I've determined how to restrict them if you can't pay costs or if there is a timing restriction (non-instants/flash), but a failure to target eludes me.

Currently my AI hits my arbitrarily defined limit of 2000 nodes because it keeps trying to activate Anointer of Champions over and over again outside of combat. It also tries to cast Auras when there are no valid targets, but that's less of an issue since it doesn't try to do that outside of the main phase. The Anointer of Champions being an activated ability can literally be played every phase.

The other issue I'm having is trying to come up with a good way to have the AI test for all combinations of attackers/blockers. I came up with a way that works, but it's quite slow (Although I'm currently not sure if the slowness is mostly because of the Anointer of Champions issue exceeding my depth limits.)
ShivaFang
 
Posts: 101
Joined: 25 Jun 2016, 01:15
Has thanked: 26 times
Been thanked: 3 times

Re: [AI] Determining if valid targets are available.

Postby ShivaFang » 01 Jul 2016, 14:17

Nevermind. After doing some more digging I found ability.canActivate(), which calls ability.canChooseTargets(). This fixes it trying to activate it (but it still hits my node limit for some reason - but I suspect I'm not properly resetting the node depth each phase like it's supposed to)

As for the combat thing I mentioned - it occurred to me that MonteCarlo is about randomness and probabilities. Rather than populating it with every single possible outcome every time I decided to pick 3 random outcomes each time. Every time it goes through it it adds 3 more random outcomes, but it will check to see if previous random outcomes are legal.
ShivaFang
 
Posts: 101
Joined: 25 Jun 2016, 01:15
Has thanked: 26 times
Been thanked: 3 times

Re: [AI] Determining if valid targets are available.

Postby quercitron » 02 Jul 2016, 13:09

There is already some implementation of AI that uses Monte Carlo tree search - Mage.Player.AIMCTS. Don't know how strong it is. Have you seen it?

Creating a good AI is a great thing, good luck!
quercitron
 
Posts: 17
Joined: 09 Nov 2011, 08:32
Has thanked: 0 time
Been thanked: 1 time

Re: [AI] Determining if valid targets are available.

Postby ShivaFang » 04 Jul 2016, 13:28

I don't see it in the build. I haven't looked at the github - I don't understand how it's structured.

EDIT - yeah I can't find the AI players on GitHub at all. These directories are all very archaic and obscure to me. I don't see them in the server folder anywhere.
EDIT 2 - ok finally found it, having a look at it now.
ShivaFang
 
Posts: 101
Joined: 25 Jun 2016, 01:15
Has thanked: 26 times
Been thanked: 3 times

Re: [AI] Determining if valid targets are available.

Postby LevelX » 04 Jul 2016, 21:00

Nice to hear someone is trying to build an AI.

Probably it's the best to create new code because the old code is very chaotic and modified a lot of times without exactly knowing how it works from different persons (for example by me).

Sure it's worth to have a look to get some inspirations.
User avatar
LevelX
DEVELOPER
 
Posts: 1677
Joined: 08 Dec 2011, 15:08
Has thanked: 174 times
Been thanked: 374 times

Re: [AI] Determining if valid targets are available.

Postby ShivaFang » 04 Jul 2016, 23:09

Yeah - I tried to run it and it kept throwing null pointer exceptions.

I did look at it and found a few tricks. For example, I thought the monte carlo search algorithm was supposed to be a random choice with a weight. They've implemented such that it takes the highest scoring one with the algorithm - and that makes a little more sense to me.

Anyway - I started rewriting it from scratch on Sunday because I thought of a new way to do it - and I'm incorporating some of the AIMCTS into it.
ShivaFang
 
Posts: 101
Joined: 25 Jun 2016, 01:15
Has thanked: 26 times
Been thanked: 3 times

Re: [AI] Determining if valid targets are available.

Postby jeffwadsworth » 08 Jul 2016, 19:11

I assume you noticed that Magarena has an excellent Monte Carlo algorithm. I hope that your version turns out as well. Cheers.
jeffwadsworth
Super Tester
 
Posts: 1164
Joined: 20 Oct 2010, 04:47
Location: USA
Has thanked: 286 times
Been thanked: 68 times

Re: [AI] Determining if valid targets are available.

Postby ShivaFang » 09 Jul 2016, 17:28

jeffwadsworth wrote:I assume you noticed that Magarena has an excellent Monte Carlo algorithm. I hope that your version turns out as well. Cheers.
I noticed, but unfortunately theirs doesn't seem to be as open source (unless I missed it somewhere) so I can't peek at it for inspiration.

Does anyone know offhand if there's a way to update a computer player while the player is thinking? Right now it seems like the only way it gets triggered is when it gets priority or requires another event (attack/block/decision).

Having it think while the player is taking their turn would help.
ShivaFang
 
Posts: 101
Joined: 25 Jun 2016, 01:15
Has thanked: 26 times
Been thanked: 3 times

Re: [AI] Determining if valid targets are available.

Postby jeffwadsworth » 09 Jul 2016, 22:10

https://github.com/magarena/magarena

It has always been open-source.

Specific to the discussion here:

https://github.com/magarena/magarena/bl ... CTSAI.java
jeffwadsworth
Super Tester
 
Posts: 1164
Joined: 20 Oct 2010, 04:47
Location: USA
Has thanked: 286 times
Been thanked: 68 times

Re: [AI] Determining if valid targets are available.

Postby ShivaFang » 10 Jul 2016, 15:22

Thanks - I'll have a look at it in a bit. My AI is doing rather well though. I just fixed something where it was hanging (something I implemented because I thought it was an optimization - turns out it made it 10x WORSE.)
ShivaFang
 
Posts: 101
Joined: 25 Jun 2016, 01:15
Has thanked: 26 times
Been thanked: 3 times

Re: [AI] Determining if valid targets are available.

Postby Agetian » 15 Jul 2016, 16:15

A decent MCTS-based AI for the XMage platform? This sounds like an absolutely amazing project! I wish you the best of luck with it! Are you planning to start a branch on Github or something like that? I'm very interested in following this project.

- Agetian
Agetian
Programmer
 
Posts: 3336
Joined: 14 Mar 2011, 05:58
Has thanked: 638 times
Been thanked: 495 times

Re: [AI] Determining if valid targets are available.

Postby ShivaFang » 18 Jul 2016, 22:52

Agetian wrote:A decent MCTS-based AI for the XMage platform? This sounds like an absolutely amazing project! I wish you the best of luck with it! Are you planning to start a branch on Github or something like that? I'm very interested in following this project.

- Agetian
I honestly don't know enough about git to know how to do that. I'm mostly doing this for my own use - but when it gets to a reasonable state I will post the code and someone could add it to the project if they wanted.

It's actually mostly done. Have to implement a lot of the 'choosing' stuff (choose values for X - choose cards to discard etc). The only thing it can choose right now is boolean yes/no answers (that took some doing, because of the way the game object is coded - I can't run MTCS simulations I had to use the results of prior simulations) It's currently happy as a clam to cast Endless One and Hangarback Walker for 0.

Right now I'm working on genetic algorithms (my REAL project - I want AIs to test decks against each other and switch cards out to optimize decks) and part of that will include evolving some of the variables I'm using for MTCS (weighting factors). Once I know what 'good' general weighting values are I will include those as the default in my AI and submit it.
ShivaFang
 
Posts: 101
Joined: 25 Jun 2016, 01:15
Has thanked: 26 times
Been thanked: 3 times


Return to Developers Talk

Who is online

Users browsing this forum: No registered users and 1 guest


Who is online

In total there is 1 user online :: 0 registered, 0 hidden and 1 guest (based on users active over the past 10 minutes)
Most users ever online was 287 on 31 Mar 2019, 04:11

Users browsing this forum: No registered users and 1 guest

Login Form