Adam's Lair Forum

game development and casual madness
It is currently 2017/10/23, 06:06

All times are UTC + 1 hour [ DST ]




Post new topic Reply to topic  [ 4 posts ] 
Author Message
 Post subject: Negamax AI
PostPosted: 2017/10/08, 21:23 
Junior Member
Junior Member

Joined: 2016/08/03, 22:07
Posts: 43
Location: Florida
Role: Hobbyist
Hey All,

I'm posting because I've really been struggling with porting an old game to Duality. This issue is actually more of a general programming/C# issue than a Duality issue.

The game is based on the concept of flood filling a tile map. Player on owns a territory starting in the top left (0,0) and the AI starts in the opposing corner (sizex - 1, sizey - 1). Each tile may be 1 of 5 colors and during their turn, a player selects a color to expand their owned territory. Any tiles that neighbor any owned tiles that are the same as the selected color become part of that player's territory.

The original game can be downloaded from here: https://github.com/padesso/Nicu

The AI uses the Negamax algorithm, which works well in finding the best move provided a number of levels to search (plies) and the data structures for board ownership and coloring are working fine.

However, for a reason I simply cannot get to the bottom of, duplicate entries are being added to the playerTerritory data structure which is what is used to keep score and determine an end game state. I am quite certain that it's due to the negamax function being called recursively as I can simulate randomly played games calling the FloodFill function and the game always ends with the score equal to the number of tiles in the tile map. (playerTerritory[0].Count + playerTerritory[1].Count == sizeX * sizeY).

If I simulate the games with the AI playing one or both players, the count of the elements in the playerTerritories object is larger that the number of tiles in the tilemap...

The source can be located here: https://github.com/padesso/Nicu2

If anyone can offer any direction, it would be tremendously appreciated.


Top
 Profile  
 
 Post subject: Re: Negamax AI
PostPosted: 2017/10/09, 10:01 
Forum Addict
Forum Addict
User avatar

Joined: 2013/09/19, 14:31
Posts: 850
Location: Italy
Role: Hobbyist
Hey, I sent you a PR on GitHub with the fix (hope I did it good and you don't mind it :D )

There is one thing I just noticed though, don't know if there's an issue on some other part of the code or some rules I don't understand exactly.. in this case:

Code:
[0,0][0,0][4, ][1, ][0, ]          [1,0][1,0][1,0][1,0][0, ]
[0,0][0,0][0,0][0,0][3,1]          [1,0][1,0][1,0][1,0][3,1]
[0,0][0,0][3,1][2, ][3,1]   ===>   [1,0][1,0][3,1][2, ][3,1]
[0,0][0,0][3,1][3,1][3,1]          [1,0][1,0][3,1][3,1][3,1]
[0,0][1, ][3,1][3,1][3,1]          [1,0][1,0][3,1][3,1][3,1]


As you can see, Player 0's move was to choose 1 as the color.. the problem is that ALSO cell(2, 0) - color 4, was switched.. is that correct?

_________________
Come on Duality's Discord channel. It's entertaining and productive! :mrgreen:


Top
 Profile  
 
 Post subject: Re: Negamax AI
PostPosted: 2017/10/10, 14:50 
Junior Member
Junior Member

Joined: 2016/08/03, 22:07
Posts: 43
Location: Florida
Role: Hobbyist
Hey SirePi!

Thanks for much for the help. I see now that by not creating new stacks each time through Negamax, it was working on a reference instead of a value copy of the territory stacks.

Also, great changes to the debug output - thank you for that. Aaaand, my first pull request - very cool!

Not sure if I'm going to focus on UI or networking next...

`Patrick


Top
 Profile  
 
 Post subject: Re: Negamax AI
PostPosted: 2017/10/10, 14:54 
Junior Member
Junior Member

Joined: 2016/08/03, 22:07
Posts: 43
Location: Florida
Role: Hobbyist
SirePi wrote:
Hey, I sent you a PR on GitHub with the fix (hope I did it good and you don't mind it :D )

There is one thing I just noticed though, don't know if there's an issue on some other part of the code or some rules I don't understand exactly.. in this case:

Code:
[0,0][0,0][4, ][1, ][0, ]          [1,0][1,0][1,0][1,0][0, ]
[0,0][0,0][0,0][0,0][3,1]          [1,0][1,0][1,0][1,0][3,1]
[0,0][0,0][3,1][2, ][3,1]   ===>   [1,0][1,0][3,1][2, ][3,1]
[0,0][0,0][3,1][3,1][3,1]          [1,0][1,0][3,1][3,1][3,1]
[0,0][1, ][3,1][3,1][3,1]          [1,0][1,0][3,1][3,1][3,1]


As you can see, Player 0's move was to choose 1 as the color.. the problem is that ALSO cell(2, 0) - color 4, was switched.. is that correct?


Yes, that is intended! The reason is because at that point cell 2,0 becomes completely trapped by Player 0's territory and thus is unplayable by Player 1. The first version of this game didn't implement this and it was very "un-fun" at the end to have to click to clean up trapped cells.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 4 posts ] 

All times are UTC + 1 hour [ DST ]


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group