Implement Figure 5.3 MINIMAX-DECISION

[BusyByte]

function MINIMAX-DECISION
function MAX-VALUE
function MIN-VALUE(state)

pseudo-code

[a1shadows]

Hey, just curious about the abstraction for this. So, a new Game trait/class will have to be defined. Will it extend ProblemSearch?

[a1shadows]

Is this a viable definition for Game?

`package aima.core.search.adversarial

import aima.core.search.{State, StateNode}
import aima.core.agent.Action

trait Player

trait Game {
def initialState: State
def getPlayer(state: State): Player
def getActions(state: State): List[Action]
def result(state: State, action: Action): State
def getUtility(state: State, player: Player): Double
}
`

[BusyByte]

@a1shadows I haven't re-read that chapter yet but reading the algorithm and looking at what you have I think it makes sense. I've been thinking about my use of traits in the past and going to stop trying to do that so much. So in light of that I might try to see if you can make it bit more generic/universal in the definition but more concrete in the implementation.
For example rather than having traits Player, State, Action and leaving them unrestricted/non-sealed (which causes some warnings on compile I don't like)
It might be:

trait Game[Player, State, Action] {
  def initialState: State
  def getPlayer(state: State): Player 
  def getActions(state: State): List[Action]
  def result(state: State, action: Action): State
  def getUtility(state: State, player: Player): Double
}

You don't have to do that and what you have is perfectly fine though.
I've been meaning to go back and refactor existing stuff also but haven't gotten to it. I've also been thinking about moving all definitions of traits and type inside the package specific to the algorithm itself because some algorithms use methods which others don't.

The other thing is I tend to shy away from using primitives as they are not very descriptive/constraining of the domain. I'd maybe rather than using Double for getUtility use:

  final case class UtilityValue[T<: AnyVal](value: T) extends AnyVal
  // or at least
 final case class UtilityValue(value: Double) extends AnyVal

These are intended to be value classes which are eliminated at runtime so have no overhead but improves type safety.
The first could let utility be integers, floats, or doubles
The second is fine but it assumes we want double. I'd probably go with this for simplicity.
I would prefer to use

final case class UtilityValue[T: Numeric](value: T) extends AnyVal

but then I don't think it gets erased as a value class and to get Numeric to work requires a lot of implicit magic which I'm trying to avoid in this project.

[a1shadows]

@BusyByte It makes more sense to me too to parametrize the trait. And the UtilityValue class makes sense too. Thanks. I'll follow your advice.

[a1shadows]

final case class UtilityValue[T: Numeric](value: T) extends AnyVal

Regarding this line, the class UtilityValue has two parameters, an implicit and explicit one, which is giving an error, so will this do ?

final case class UtilityValue[T](val value: Numeric[T]) extends AnyVal

[BusyByte]

@a1shadows that's not quite what you want. You don't want the value to be a type class.
This would probably work:

final case class UtilityValue[T <: AnyVal : Numeric](value: T) extends AnyVal

This says that T must extend AnyVal which abides what value classes require to be erased
The first also says that whatever T is it must have an implicit Numeric[T] type class available (Numbers have this but not Strings)
I don't really want to deal with a lot of implicits in this project so I'd recommend:

final case class UtilityValue(value: Double) extends AnyVal

Let me know if this doesn't make sense.
If you want more information maybe read up on Scala value class and type class patterns.

[a1shadows]

@BusyByte I'll change my code. I can't thank you enough for the guidance.

[a1shadows]

Hey, @BusyByte . The minimax-decision function takes State as an argument and not Game, so do I have to define state as a trait/class, even though I passed it as a parameter it in the Game definition? Or should I just pass an instance of Game as an argument to minimaxDecision and use the initialstate of the Game to make a decision? Sorry for the inconvenience. I'm a novice at design principles.

[BusyByte]

@a1shadows it looks like from looking at https://github.com/aimacode/aima-java/blob/AIMA3e/aima-core/src/main/java/aima/core/search/adversarial/MinimaxSearch.java#L42 that some of the functions in the algorithm come from the game. I think rather than an object oriented solution this could be defined as a function something like:

object MinimaxDecision {
def minMaxDecision[S, A, P](g: Game[S][A][P])(state: S): A = {
  def maxValue(s: S)...
  def minValue(s: S)...
}
}

or even as returning a function from the function:

object MinimaxDecision {
def minMaxDecision[S, A, P](g: Game[S][A][P]): S => A = { s: S =>
  def maxValue(s: S)...
  def minValue(s: S)...
}
}

max and min value functions would be visible only within the scope of the minMaxDecision method itself since they are defined within the main function which is preferable to me because they are never meant to be called by the public api, just the minMaxDecision function
This way when you define the game you can bind it to the first parameter:

val minMaxStateDecisionFunction = MinimaxDecision.minimaxDecision(game)(_)
//and then use it on various states like:
val a1 = minMaxStateDecisionFunction(s1)
val a2 = minMaxStateDecisionFunction(s2)
val a3 = minMaxStateDecisionFunction(s3)

or defined as returning a function

val minMaxStateDecisionFunction = MinimaxDecision.minimaxDecision(game)
//and then use it on various states like:
val a1 = minMaxStateDecisionFunction(s1)
val a2 = minMaxStateDecisionFunction(s2)
val a3 = minMaxStateDecisionFunction(s3)

Let me know if this doesn't make sense.

I'm ok if you want to start with the more object oriented solution like the Java example though.

[a1shadows]

Thanks a lot, Shawn!