Desc. I am making a game between two players that draw tokens. Player A always starts first. They have 5 options to pick: left, right, left + left + 1, left + right, right + right - 1 If they pick 2 in one turn, the next turn, they have to pick only 2.
Problem It gives me the correct result, but I want to keep track of what turns were made. How do I save only the valid paths through recursion?
Code
#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#include <string.h>
#define MAX_SIZE 100
typedef struct {
int score;
int moves[MAX_SIZE];
int turns;
} SCORE;
/** Drawing tokens
* this is a game where 2 AI opponens draw tokens (numbers)
* Each player can either draw 2 cards, but then has to draw only one card the next turn
* or can draw 1 card only
* player with larger tokenSum wins
* program uses minimax algorithm
*/
void getTokens(int* tokens, size_t* size) {
int token;
printf("Zetony:\n");
while(scanf("%d", &token) == 1) {
tokens[(*size)++] = token;
if (*size > MAX_SIZE) {
*size = 0;
break;
}
}
//if (!feof(stdin) ) *size = 0;
}
//------------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------------
/** A function to get the highest of 5 choices (playerA)
* if player A can draw 2 cards
* @returns max of 5
*/
int maxOfFive (int a, int b, int c, int d, int e) {
int choices[] = {b, c, d, e};
int max = a;
for (int i = 0; i < 4; i++) {
if (choices[i] > max) {
max = choices[i];
}
}
return max;
}
//------------------------------------------------------------------------------------------------
/** A function to get the lowest of 5 choices (playerB)
* if playerB can draw 2 cards
* @returns min of 5 ints
*/
int minOfFive (int a, int b, int c, int d, int e) {
int choices[] = {b, c, d, e};
int min = a;
for (int i = 0; i < 4; i++) {
if (choices[i] < min) {
min = choices[i];
}
}
return min;
}
//------------------------------------------------------------------------------------------------
/**
* @returns max of 2 ints
*/
int max (int a, int b) {
return a > b ? a : b;
}
//------------------------------------------------------------------------------------------------
/**
* @returns min of 2 ints
*/
int min (int a, int b) {
return a < b ? a : b;
}
//------------------------------------------------------------------------------------------------
int minimaxRec (int* tokens, int start, int end, int scoreA, bool maximize, bool twoA, bool twoB) {
if (start > end) return scoreA; //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
if (maximize) {
if(twoA && ( (end - start) >= 1) ) {
int a = minimaxRec(tokens, start + 1, end, scoreA + tokens[start], !maximize, twoA, twoB );
int b = minimaxRec(tokens, start, end - 1, scoreA + tokens[end], !maximize, twoA, twoB );
int c = minimaxRec(tokens, start + 2, end, scoreA + tokens[start] + tokens[start + 1], !maximize, !twoA, twoB );
int d = minimaxRec(tokens, start, end - 2, scoreA + tokens[end] + tokens[end - 1], !maximize, !twoA, twoB );
int e = minimaxRec(tokens, start + 1, end - 1, scoreA + tokens[start] + tokens[end], !maximize, !twoA, twoB );
printf("start:%d end:%d", start, end);
return maxOfFive(a, b, c, d, e);
}
else {
int a = minimaxRec(tokens, start + 1, end, scoreA + tokens[start], !maximize, !twoA, twoB );
int b = minimaxRec(tokens, start, end - 1, scoreA + tokens[end], !maximize, !twoA, twoB );
printf("start:%d end:%d", start, end);
return max(a,b);
}
}
else {
if(twoB && ( (end - start) >= 1) ) {
int a = minimaxRec(tokens, start + 1, end, scoreA, !maximize, twoA, twoB);
int b = minimaxRec(tokens, start, end - 1, scoreA, !maximize, twoA, twoB);
int c = minimaxRec(tokens, start + 2, end, scoreA, !maximize, twoA, !twoB);
int d = minimaxRec(tokens, start, end - 2, scoreA, !maximize, twoA, !twoB);
int e = minimaxRec(tokens, start + 1, end - 1, scoreA, !maximize, twoA, !twoB);
return minOfFive(a, b, c, d, e);
}
else {
int a = minimaxRec(tokens, start + 1, end, scoreA, !maximize, twoA, !twoB );
int b = minimaxRec(tokens, start, end - 1, scoreA, !maximize, twoA, !twoB );
return min(a, b);
}
}
}
//------------------------------------------------------------------------------------------------
SCORE minimax2 (int* tokens, int start, int end, bool maximize, int* turns) {
SCORE result;
if (start > end) {
*turns = 0;
return result;
}
SCORE l = minimax2(tokens, start + 1, end, !maximize, turns);
SCORE r = minimax2(tokens, start, end - 1, !maximize, turns);
if (maximize) {
if (tokens[start] + l.score > tokens[end] + r.score) {
result.score = tokens[start] + l.score;
result.moves[*(turns)++] = start;
return result;
}
else {
result.score = tokens[end] + r.score;
result.moves[*(turns)++] = end;
return result;
}
}
else {
if (l.score < r.score) {
result.score = l.score;
result.moves[*(turns)++] = start;
return result;
}
else {
result.score = r.score;
result.moves[*(turns)++] = end;
return result;
}
}
}
//------------------------------------------------------------------------------------------------
SCORE minimax (int* tokens, size_t size) {
int start = 0, end = size - 1;
bool maximize = true, twoA = true, twoB = true;
SCORE result;
result.score = 0;
result.score = minimaxRec(tokens, start, end, result.score, maximize, twoA, twoB);
return result;
}
//------------------------------------------------------------------------------------------------
int main() {
int tokens[MAX_SIZE], turns = 0;
size_t size = 0;
SCORE result;
getTokens(tokens, &size);
if (!size) {
printf("Nespravny vstup.\n");
return 0;
}
result = minimax(tokens, size);
printf("\n%d\n", result.score);
return 0;
}
I tried saving in into an array and got all tangled up.