Avoiding dynamic memory allocation in AI board games.

[Ashish Schottky]

One of the worst things possible in AI board game programing is dynamic memory allocation.
I am not finding a way to avoid dynamic memory allocation.
My typical approach is

function()

{
if(depth==0)
return 1;
    Move moves[]=new Moves[number]
    ....
....

}

one way which i find is make it depth dependent, but then is there any other simpler alternative?

[Paul Clapham]

The simpler alternative, of course, is to allocate all of the required memory when you initialize the application.

[Ashish Schottky]

@Paul:
Lets take connect 4 to be the example.
now the number of legal moves changes after every move, and therefore the array has to be cleaned up before storing the new moves.
this can either be done by dynamically allocating memory as

 int moves[]=new int[10];

or by using for loops or by Arrays.fill .
However all approaches require finite time, how can i find a way in which my speed will increase.
-----EDIT-----
Take a look at the snippet below and kindly suggest some way to avoid dynamic memory allocation

public static int Negamax(boolean turn, int depth, int[] board1) {
        int legal_moves[] = Possible_Moves(board1);
        int eval = Win(board1, turn);
    ... Normal negamax.


    }

I am trying to avoid the dynamic memory allocation of legalMoves. however, since the size of number of legal moves change, they have to variable length, this is killing the performance. What to do?

kindly help.
thank you.

[Mich Robinson]

I'd suggest not storing all the legal moves at all!

In fact I'd say that's definitely the wrong approach

You just need to store the current move at each level and have a function which will just look for the next legal move. The current move would be indicated by a board position, a direction(where valid) and a distance (where valid). You need to be able to store the move played at each ply. This can be used to undo moves when you want to add this functionality.

All you'll need to do is alter your current method that returns all the moves to just return either the 1st move available or return the next move possible. When no more moves are available that means you've completed your search at that level.

[Ashish Schottky]

@mich: Thanks for reply.
I think this is advantageous, it would be very helpful if you can provide me with some links of Board games programing using AI as I think I am missing some of the concepts for the same.
Please if possible suggest names of some good begineer books for Board Games Programing.
Thank you.

[Mich Robinson]

I don't know any decent links I'm afraid and many of the links and books can be a little complex for the beginner. Personally I'd suggest doing a simpler game first - OXO or connect 4 are certainly easier.

The advantage of this approach is you learn the general theory of games programming without getting bogged down in the complexities of a difficult game. Then when you're happy with the theory you can move onto the game that interests you. The things you will learn from doing these games will transfer to any other game.

I recently had a bash at chess and, though I managed to finish it quite quickly, I still found it quite a challenge to get it to play well and I'm actually still tinkering with it. It's about 1500 lines long if that gives you an idea of effort required and I imagine it will get to around 2k lines before I'm finished.

My chess program is on the web and I'd welcome any suggestions.

PS - You've got me thinking about a book on games programming now - perhaps going from basics and building up to writing a chess program. There would certainly be enough material for a book. It would be a fun project but I'm sure there must be something out there. Chances are it wouldn't have a big market either.

[Ashish Schottky]

@Mich: Thanks for replying.
I am not a complete begineer. I have already coded games like X's and O's and Connect 4 and hence moved on to chess, I have completed the game in console, and its abasic one with no real sophisticated evaluation routine.

In java, we can dynamically allocate memory, this is bad for programs using recursion. I want a book or link that will provide answers to the questions as how to make use of optimum data structures (preferabley in java), how to make everything quicker? In board games of AI, speed is important.
This will be realized only in games like chess or checkers, where the branching factor is too large. Memory allocation in Tic-Tac-Toe is not a big issue since the search space is far too less. On similar lines its with connect-4.(BTW my program beats yours 5-0 in played matches, its a console based game, I am pretty busy to code it a GUI, also I like your GUI,nicely done). The point is once you code X's and O's, we get used to some data-structure and methodology of programing.(In my case, I have developed a bad habbit of going for dynamic memory allocation, which reduces the speed exponentially).

This is where I want my book to guide me, perhaps even links, so it would be help full if you provide the name of books or link, even at an higher level.
An ideal title for the book might be Programing AI board-games the efficient way.

[Mich Robinson]

It sounds like your program is doing fine if it won 5-0!

Out of curiosity were both programs using roughly the same time. I know the default level on mine only looks 2 ply ahead and I seem to remember yours looked 6 ply ahead but took a minute to think ? Did you record any of the games at all ? it would be interesting to know where I need to improve mine. How does your game fare against yourself (that's usually the most interesting part)? The current version of my little program (d6.1) will show the game history if you click the pawn outside the board.

Must admit mine isn't too strong but I tried to make it fun to play.

[Ashish Schottky]

@Mich: My connect-4 program beats yours 5-0.
I ll try to play a match of chess against your program.
Will post result later after done.
------------------EDIT--------------------------
I played one game MyProgram playing white.
http://imageshack.us/f/97/michp.png/

[Mich Robinson]

Ashish Schottky wrote:My connect-4 program beats yours 5-0.

Can you give any idea what depth it's searching to or for how long? Obviously the ideas of the levels is to allow the user to find an opponent that matches his skill. I can't remember the details of of how my levels were set up - probably different scoring algorithms turned on and off and using different search times. I don't use a database either - some systems have a complete database of the game meaning they can't loose if they play first. I'm not keen on this approach as I can't put the database into a small applet and because the style of play produced tends to be not that much fun - who wants to play something that's unbeatable?

Hat's off to your program by the way.

[Madhan Sundararajan Devaki]

Normally in AI related games, Neural Networks are employed to avoid storing game states, thereby saving memory. These Neural Networks are trained against many moves and mimic human memory to remember the best move. It is quiet challenging to integrate a Neural Network into a normal program.

[Ashish Schottky]

CODE
On this page you will find a tic-tac-toe game.
here is the snippet where i want to modify the code.

    public static int[] possibleMoves(int board[][]) {
        int no = 0;

        int moves[] = new int[size * size];// this can be declared statically. not much of importance.

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (board[i][j] == 0) {
                    moves[no++] = size * i + j;
                }
            }
        }
        int final_moves[] = new int[no];//Speed breaker.
        System.arraycopy(moves, 0, final_moves, 0, no);//Speed breaker
        return final_moves;
    }

The dynamic allocation of final_moves is a huge speed-breaker. I want to avoid this and want to use moves, (which I can declare statically), and but then now to change the size of array, on empty board, there are 9 playable moves. after first turn, there are 8 and so on.. how to avoid this dynamic memory allocation as this method is called several times in my program.

second part where I want to modify this is

    public static int negaMax(int board[][], int depth, boolean turn) {
        int eval = 0;
        int max = -100;
        eval = isWon(board);
        if ((depth == 0) || (boardFull(board) == true)||(isWon(board)==-1)) {
            return eval;
        }

        int moves[] = possibleMoves(board);//Speed breaker.
        for (int i = 0; i < moves.length; i++) {
            makeMove(board, turn, moves[i]);
            eval = -negaMax(board, depth - 1, !turn);
            unmakeMove(board, moves[i]);

            if (eval > max) {
                max = eval;
            }
        }

        return max;
    }

I just wrote this program in 20 mins, so didnt bother to add much of fancy things, just made sure that it worked correctly.
I know things can be optimized by selecting single array rather than arrays of arrays but then that is not the point here.
kindly help to solve this issue. thank you.

[Mich Robinson]

Madhan Sundararajan Devaki wrote:Normally in AI related games, Neural Networks are employed to avoid storing game states

Neural networks haven't had much success in board games outside of backgammon. The easiest way to avoid storing all the states is to just store the current state at each ply ie Pe4 on ply 1, Pe5 for black on ply 2. When you reach your maximum depth just score the position and see if this score is better than the current score for this depth. If it isn't then forget the move else store it and the score as your best. Then try the next move after Pe5 (perhaps Pe6) and repeat the process. It's called "min max" and has been used for decades. Nothing but the current moves will be stored so there is no need to manage huge sets of arrays.

[Ashish Schottky]

@mich: Thanks for replying.
I think this approach will work, but then its going to hard to follow and debug.
There will be innumerable calls to move generation method.
Suppose that there various types of moves as in chess.
,there are captures,enpassant ,castle... so which move to return?


The advantage of using array for the purpose is that we get variety of moves at every depth. we get all knight moves,pawn,queen.. and so on...
try each of them, see the other best moves and so on..
The code is tidy and manageable and this technique is quiet game independent.

I think that there is nothing wrong with working with huge arrays, allocating memory for arrays is the speed-breaker.
Thus want to allocate everything statically.

Can ArrayLists change this and make it efficent?

[Mich Robinson]

Ashish Schottky wrote:but then its going to hard to follow and debug.

Welcome to game programming

Ashish Schottky wrote:There will be innumerable calls to move generation method.

There will be the same number of moves whether you generate them all at once via your method or one at a time via this method.

Ashish Schottky wrote:,there are captures,enpassant ,castle... so which move to return?

Just return the next move - imagine storing all the moves in an array as you do at the moment and then just return them one at a time.

Ashish Schottky wrote:I think that there is nothing wrong with working with huge arrays

Apart from the fact it's extremely slow

Ashish Schottky wrote:Can ArrayLists change this and make it efficent?

I doubt this.

[Nathan Lane]

In Tic-Tac-Toe there actually aren't too many possible winning moves, and therefore, in a C++ implementation that I created a while back I provided a static lookup table to determine whether a player won. My squares were numbered 1-9, but my lookup table looks like:

#include "WinningMoves.h"

namespace Nathandelane
{

	const unsigned int WinningMoves::WINNING_MOVES[8][3]   =
	{
		{1, 4, 7},
		{2, 5, 8},
		{3, 6, 9},
		{1, 2, 3},
		{4, 5, 6},
		{7, 8, 9},
		{1, 5, 9},
		{3, 5, 7}
	};

}

#ifndef _WINNINGMOVES_H
#define _WINNINGMOVES_H

namespace Nathandelane
{

	class WinningMoves
	{
	public:
		static const unsigned int NUMBER_WINNING_MOVES = 8;
		static const unsigned int WINNING_MOVES[8][3];
	};

}

#endif

And this method is fairly performant -- I'm not recalculating every time. Now my implementation doesn't include an AI, so that might change my decision, but I don't think so.

[Mich Robinson]

Probably a little late but ...

I found this wiki on chess programming and it seems to contain everything and there is a chess programming forum though it's quite technical. The developers of the more powerful chess programs all seem to discuss their ideas here though there are a couple of chess programming beginners like me on there.

Oddly enough I found out about MVV-LVA move ordering here which does involve storing an array of the current moves at each ply to improve speed. This isn't a huge array though as only one set of moves are stored at each ply ie 10 ply * 50 moves. They do this to order the moves so moves most likely to return a good score are done first - this improves the alpha beta pruning dramatically.

How is your chess program going?

[Ashish Schottky]

@Mich: I am very busy currently and hence donot have anytime for chess programing.
I have "paused" developing chess long back.However once I get some time, I am planning to rewrite the code in C.
But for sure it wouldnt be anytime soon.

The links you posted are too awsome.