Hi !
Featured games (85)
games approved by the League of Dukes
Games in Showcase (616)
Games in Android Showcase (173)
games submitted by our members
Games in WIP (659)
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 855 times)
0 Members and 1 Guest are viewing this topic.
Offline cryo75

Junior Newbie

« Posted 2013-03-17 06: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?

Offline Jono
« Reply #1 - Posted 2013-03-17 08:29:24 »

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).

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.

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):
double search(Board board, int depth)
  if( depth=0 )
    return heuristic(board)
     maxValue = 0
     for each move in children(board)
       maxValue = max(maxValue,search(board,depth-1)
     return maxValue
Offline cryo75

Junior Newbie

« Reply #2 - Posted 2013-03-17 13: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 14: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 15: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.

Coldstream24 (16 views)
2015-09-03 00:41:28

Andrew_3ds (27 views)
2015-09-01 19:08:10

afikri (18 views)
2015-08-31 09:30:22

afikri (25 views)
2015-08-31 09:30:07

afikri (13 views)
2015-08-31 09:27:24

afikri (16 views)
2015-08-31 09:26:40

Roquen (30 views)
2015-08-29 11:30:54

GamerC4 (36 views)
2015-08-22 20:38:50

GamerC4 (33 views)
2015-08-22 20:37:18

GamerC4 (40 views)
2015-08-22 20:37:01
HotSpot Options
by Roquen
2015-08-29 11:33:11

Rendering resources
by Roquen
2015-08-17 12:42:29

Rendering resources
by Roquen
2015-08-17 09:36:56

Rendering resources
by Roquen
2015-08-13 07:40:51

Networking Resources
by Roquen
2015-08-13 07:40:43

List of Learning Resources
by gouessej
2015-07-09 11:29:36

How Do I Expand My Game?
by bashfrog
2015-06-14 11:34:43

List of Learning Resources
by PocketCrafter7
2015-05-31 05:37:30 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‑
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!