Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (475)
Games in Android Showcase (106)
games submitted by our members
Games in WIP (530)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  AI search and Java  (Read 557 times)
0 Members and 1 Guest are viewing this topic.
Offline cryo75

Junior Newbie





« Posted 2013-03-17 07:59:47 »

Hi all,

I'm writing a board game and currently implementing the AI using the standard Negamax. This algorithm calls itself recursively.

To speed up things I implemented a makemove/undomove within the function and I don't pass the board object as a parameter to itself. However, due to the nature of Java not passing objects by reference, the changes to the board state when going deeper into the recursion are also reflected into the upper levels.

When I just copy the board state every time, the function works fine because each recursion works on a new copy based on a copy of one level above it. In this case I do have to pass the board state copy as a parameter and this copy copied immediately.

This has serious issues because as I hit a depth of 6 the search slows down considerably. So I'd rather have the move/undo functionality to speed up things.

So my question is: Is it possible in Java, and if yes, how? Or am I restricted to copying the board each and every time with serious performance issues?

Thanks,
C
Offline Jono
« Reply #1 - Posted 2013-03-17 09:29:24 »

Quote
To speed up things I implemented a makemove/undomove within the function
This will work fine, so long as you are doing depth-first search (which you are, because of the recursive calls).

Quote
due to the nature of Java not passing objects by reference
Typo? You mean Java always passes by reference. So no new copy of an object is made by default.

Quote
and I don't pass the board object as a parameter to itself
This is a little confusing. Does it mean that the search function is within the board class itself? Or that a single static board object exists?

Regardless, I'd have player objects decide their own moves and have any search functions in their classes. These methods should pass a board around as a parameter.

All you need to do is put your move and undo-move before and after each recursive call, as in (pseudocode):
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
double search(Board board, int depth)
  if( depth=0 )
    return heuristic(board)
  else
     maxValue = 0
     for each move in children(board)
       move.makemove(board)
       maxValue = max(maxValue,search(board,depth-1)
       move.undomove(board)
     return maxValue
Offline cryo75

Junior Newbie





« Reply #2 - Posted 2013-03-17 14:15:30 »

Your pseudocode snippet is similar to my function. I'm passing the board as one of the parameters and make/unmake the same way.

My make function does:
1. place new piece on the board
2. increment new pieces for current player
3. switch players (opponent is now the current player)

My unmake function does:
1. remove new piece from the board
2. decrement new pieces for current player
3. switch players

However, after a few plies into the search the number of new pieces for each player are way off (eg. 22, -18, etc)

So what could be wrong?
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Jono
« Reply #3 - Posted 2013-03-17 15:32:53 »

What you're doing sounds right to me so it's probably just a bug.

Are there any other side effects on the board from adding a piece, like removing opponents pieces, that the undo might get wrong? Is the move being used for move/undo being modified at all during the search?
Offline cryo75

Junior Newbie





« Reply #4 - Posted 2013-03-17 16:19:49 »

It's only the piece counters that aren't updated property because the same board is used in the recursion. Placing/undoing a cell position works because it gets the information from the move itself, which btw... doesn't change between and make/unmake.
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

ctomni231 (34 views)
2014-07-18 06:55:21

Zero Volt (30 views)
2014-07-17 23:47:54

danieldean (25 views)
2014-07-17 23:41:23

MustardPeter (27 views)
2014-07-16 23:30:00

Cero (42 views)
2014-07-16 00:42:17

Riven (44 views)
2014-07-14 18:02:53

OpenGLShaders (32 views)
2014-07-14 16:23:47

Riven (34 views)
2014-07-14 11:51:35

quew8 (30 views)
2014-07-13 13:57:52

SHC (66 views)
2014-07-12 17:50:04
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!