Laborator 6 - Minimax

Two player Zero-sum games
--------------------------

score_1 + score_2 = 0

X si 0:
	- 1 castiga: score_1 = 1, score_2 = -1
  - 2 castiga: score_1 = -1, score_2 = 1
  - remiza: score_1 = score_2 = 0



Minimax
--------

int maxi(State state) {
	if (is_final(state))
  	return score(state); // 1 daca castiga jucatorul 1, -1 daca castiga jucatorul 2, 0 la remiza

  int val = -INF;
  for (new_state: next_states(state)) {
  	int new_state_score = mini(new_state);
    val = max(val, new_state_score);
  }

	return val;
}

int mini(State state) {
	if (is_final(state))
  	return score(state); // 1 daca castiga jucatorul 1, -1 daca castiga jucatorul 2, 0 la remiza

  int val = INF;
  for (new_state: next_states(state)) {
  	int new_state_score = maxi(new_state);
    val = min(val, new_state_score);
  }

	return val;
}


Negamax
--------

int negamax(State state, int player, int depth) {
	if (is_final(state) || depth == 0)
  	return score(state, player);

	int val = -INF;
  Move best_move = null;

  for (move: all_moves) {
  	State new_state = apply_move(state, move);
    int new_state_score = -negamax(new_state, -player, depth - 1);
    if (new_state_score >= val) {
    	val = new_state_score;
      best_move = move;
    }
  }

  return val;
}

int score(state, player) {
	if (is_final(state)) {
  	// return INF daca player a castigat, -INF daca a pierdut, 0 la egal
  }

	// returnam un scor euristic care sa fie cu atat mai mare cu cat player e mai in avantaj
}

main:
	negamax(state, player, 7);

Euristica
----------
Pentru sah: score_1 = nr_piese_1 - nr_piese_2
						score_2 = nr_piese_2 - nr_piese_1

    - o euristica mai buna ar fi sa acordam puncte pieselor: regina - 10p, tura - 5p, ... pion - 1p

Nim
----

1 0 0 -> castiga celelalt jucator (cel care nu e la mutare)
2 0 0 -> castiga jucatorul la mutare

2 5 3

  -> nu implementati euristica (return 0 daca starea nu e finala)

  -> de implementat: apply_move si is_final + minimax (urmariti TODO-urile)


Reversi
--------

Euristica: score_player = nr_bile_player - nr_bile_adversar

Common pitfalls:
----------------
pair<Move, int> negamax(...) {

}

// aveti grija la ce intoarceti in Move (sa fie mutare valida) ... aveti grija la functiile de max/min cu -INF sau INF