1

I have a question regarding my implementation of the minimax algorithm for the game called "nim game" in kotlin. It is based on the minimax algorithm that is described in wikipedia.

I do not really know why it is not working. I think the problem is in the evaluate method. If the player is +1 the algorithm should link a great move with a high value and if the player is -1 it should link a great move with a low value.

To understand the Code you may need to know what some methods and variables do:

rows -> IntArray of the current board. If rows = (2,3) the board has 2 matches in the first row and 3 in the second

createAllMoves -> takes rows and creates all possible Moves. If rows = (1,1) there are two Moves: (0,1) take one match out of the first row, or (1,0) take one match out of the second row

play(Move) -> if Move = (3,1) and rows (1,2,3) the output is: rows = (1,2,2) because the Move took 1 match out of the third row

desiredDepth = 5

I'd be pleased if you know how to improve my code. Thanks in advance.

fun evaluate(player: Int) : Int {
    if (player == 1) {
        return 1
    } else if (player == -1) {
        return -1
    }
    return 0
}

fun max(player: Int, depth: Int): Int{

    var tmpAllMoves: MutableList<Move> = createAllMoves(rows)   

    if(depth == 0 || tmpAllMoves.isEmpty()){
        return evaluate(player)
    }

    var maxValue: Int = Int.MIN_VALUE

    while(!tmpAllMoves.isEmpty()){

        var randomMove: Move = tmpAllMoves.random();

        play(randomMove)

        tmpAllMoves.remove(randomMove)

        var value: Int = min(-1*player, depth-1)

        undoMove()

        if(value > maxValue){
            maxValue = value
            if(depth == desiredDepth){
                var savedMove: Move = randomMove
            }
        }
    }
    return maxValue
}

fun min(player: Int, depth: Int): Int{

    var tmpAllMoves: MutableList<Move> = createAllMoves(rows)

    if(depth == 0 || tmpAllMoves.isEmpty()){
        return evaluate(player)
    }

    var minValue: Int = Int.MAX_VALUE

    while(!tmpAllMoves.isEmpty()){

        var randomMove: Move = tmpAllMoves.random();

        play(randomMove)

        tmpAllMoves.remove(randomMove)

        var value: Int = max(-1*player, depth-1)

        undoMove()

        if(value < minValue){
            minValue = value
        }
    }
    return minValue
}
  • 1
    What do you mean by "match"? If relevant, which game is the algorithm implemented for? – MelvinWM May 28 '20 at 18:28
  • 1
    ah i am sorry, forgot to mention that .. :/ it is called nim game – Niklas Flink May 28 '20 at 18:31
  • 1
    I don't quite understand _"If `rows = (1,1)` there are two Moves: `(0,1)` take one match out of the first row, or `(1,0)` take one match out of the second row "_. If `(0,1)` takes one match of of row with index 0, should `(1,0)` not be `(1,1)` instead, taking a match out of the second row with index 1? – MelvinWM May 28 '20 at 19:26
  • 1
    _if `Move = (3,1)` and rows `(1,2,3)`_ If there are 3 rows, should `Move = (3,1)` not be `Move = (2,1)`? Or are move descriptions 1-indexed instead of 0-indexed for rows? – MelvinWM May 28 '20 at 19:32
  • 1
    Move is 0-indexed, yes – Niklas Flink May 28 '20 at 19:34
  • 1
    I think you might be right reg. the evaluation function. I think the game of Nim is a bit special there, because unless you search to the end of the tree, it is difficult to estimate whether a move is good or bad for a given player (or, maybe more accurately in another way, whether a given game state (resulting from some sequence of moves from a starting state) is good or bad for a given player). 1/4 – MelvinWM May 28 '20 at 20:00
  • 1
    As I recall, if you want the correct evaluation (win, draw, lose) of a given game state assuming perfect play for both players, you have to search through the whole possible game tree, which as such requires it to be finite. But for certain games such as Chess, that may not be possible with the given computation resources like CPU time and memory if you want it completed in any reasonable amount of time. 2/4 – MelvinWM May 28 '20 at 20:00
  • 1
    Therefore, a heuristic is typically applied, which gives a guess of how good or bad a given game state is for a given player. For Chess, the number and kinds of pieces are usually used for giving a guess of how good a game state is for a given player. But for Nim, if you don't search all the way, it becomes somewhat difficult, since losing or winning depends on who takes the last piece. 3/4 – MelvinWM May 28 '20 at 20:01
  • 1
    Since Nim has a relatively small game state space for typical variations of it, searching through Nim the whole way is often a viable approach. So it may not be possible to estimate the game reasonably or usefully as long as the whole game tree is not searched. So, I am wondering a bit: What happens if you set the `desiredDepth` to more than the number of matches? Does it then give correct results? 4/4 – MelvinWM May 28 '20 at 20:01
  • 1
    Thanks for all the great tips, i tried to change desiredDepth to "2" but I encountered a new problem by doing that. Not sure if it was there before but if I am creating new "rows" (for example 1,2,3) and making a move with the minimax, I get an error that the chosen Move is something like (-2, -3, -3). Looks like the minimax is changing my possible moves somehow. The function createAllMoves is not the problem, i debugged that, it works fine. – Niklas Flink May 28 '20 at 20:24
  • 1
    Well, you do mutate the game state with `play` and `undoMove`, and when you have mutation, you must be careful about what happens, especially since the ordering matters. For instance, what happens if `play` is called twice, and following that, `undoMove` is called twice? But I would assume that you will be able to investigate and debug that. – MelvinWM May 29 '20 at 06:02
  • 1
    I found my problem. It was my undo function which removed the last Move of the list everytime. Guess it got in trouble with the recursion. Fixed that by handing over the Move that I want to remove. Minimax works fine now. Thanks for your help :) – Niklas Flink May 29 '20 at 10:42

0 Answers0