#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#define MAX_SCORE 1000000000

typedef struct { } position;
typedef struct { int score0; } move;

// Current position and it's score
position X;
int turn = 1;
int score;
int depth;

// Степень ветвления
const int k = 4;
int count;

// Params
int noalpha = 0;
int nobeta = 0;
int nosort = 0;

void do_move(move a){
   score = a.score0;
    turn = - turn;
}

void undo_move(move a){
    turn = - turn;
}

int generate_moves(move* moves) {
   for (int i = 0; i < k; i++)
    {
       moves[i].score0 = (score + (rand()%20));
    }
    return k;
}

int cmp (const void* aa, const void* bb) {
        return turn*((*(move*)bb).score0 - (*(move*)aa).score0);
}

void sort_moves (int num_moves, move* moves) {
   qsort (moves, num_moves, sizeof(move), cmp );
}

int alphabeta(int alpha = -MAX_SCORE, int beta = MAX_SCORE)
{ 
   count++;
    if (depth == 0) return  turn * score;        // добрались до дна - возвращаем оценку
    int best = -MAX_SCORE;
    if(!noalpha) best = alpha;

    int eval;
 
    depth--;
    int old_score = score;
    move moves[k];                             // тут будет массив возможных ходов
    int num_moves = generate_moves(moves);  // заполняет moves[], возвращает кол-во ходов
    
    if( depth > 1 && !nosort) sort_moves(num_moves, moves);


    for (int i = 0; i < num_moves; i++) 
    {
       do_move (moves[i]);                 // вносит изменения в позицию
       eval = -alphabeta (-beta, -best);    // рекурсивно вызывает себя
        undo_move ( moves[i] );              // восстанавливает исходную позицию
        score = old_score;
        if (eval > best) {
             best = eval;                // запоминает лучшую оценку
             if( !nobeta && best >= beta) {
                break;
             }
        }
    }

    depth++;
    return best;
}

int main ()
{
  depth = 14;
  double mean = 0;
  int T = 10;
    
  for(int i = 0; i < T ;i++) {
    
    nosort = 0;
    noalpha = 0;
    nobeta = 0;
    count = 0;
    alphabeta ();
    int ABS = count;
    
    nosort = 1;
    noalpha = 0;
    nobeta = 0;
    count = 0;
    alphabeta ();
    int AB = count;


    nosort = 1;
    noalpha = 1;
    nobeta = 0;
    count = 0;
    alphabeta ();
    int B = count;
    
    nosort = 0;
    noalpha = 1;
    nobeta = 0;
    count = 0;
    alphabeta ();
    int BS = count;
  
    long NO = (pow(k, depth + 1) - 1)/(k-1);
    double LNO = (double)(depth + 1)*log(k) - log(k-1);
    
    double g;
    printf("ABS\t: %d, %lf\nAB\t: %d, %lf\nBS\t: %d, %lf\nB\t: %d, %lf\nNO\t: %ld, %lf\n ----- %lf\n", 
      ABS, log(ABS), AB, log(AB), BS, log(BS), B, log(B), NO, LNO, g = log(ABS)/LNO);
    mean += g;

  }
  printf ("%lf\n", mean/T);
    
  return 0;
}