path: root/include/actions.c

/*
  This file is part of ct.

  This program is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.

  This program is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with ct. If not, see <https://www.gnu.org/licenses/>.
*/

#include "actions.h"

// ===================================================================
// Helper method declarations
// ===================================================================

#define DANGER_MIN(a,b) (((a)<(b))?(a):(b))

#define CLR_STONE NUM_MASK

static inline void
list_append(action_list_t *list, const enum A_TYPE type,
	    const int8_t loc, const uint8_t data0,
	    const uint8_t data1);

static inline void
list_prepend(action_list_t *list, const enum A_TYPE type,
	     const int8_t loc, const uint8_t data0,
	     const uint8_t data1);

static inline void
inline_next_ply(void);

static inline void
inline_prev_ply(void);

// ===================================================================
// Exported method implementations
// ===================================================================

int action_move_to_front(const action_t action,
			 action_list_t *list) {
  action_node_t *n = list->head;

  // TODO: what if it's not in the list?

  while (n) {
    if (n->action == action) {
      const action_t t = list->head->action;
      list->head->action = action;
      n->action = t;
      return EXIT_SUCCESS;
    }
    n = n->next;
  }

  return EXIT_FAILURE;
}


void action_list_free(action_list_t *list) {
  if (list) {
    action_node_t *n = list->head, *nn;
    while (n) {
      nn = n->next;
      free(n);
      n = nn;
    }
    free(list);
  }
}

// Keep track of move offsets
int8_t move_deltas[4];

void action_list_init(void) {
  move_deltas[0] = +board_size;
  move_deltas[1] = -board_size;
  move_deltas[2] = -1;
  move_deltas[3] = +1;
}

// We bias place over move by prepending place actions and appending
// move actions to the generated list
action_list_t *action_list_generate(void) {
  action_list_t *list = malloc(sizeof(struct action_list_s));

  // TODO: trap errno
  list->length = 0;
  list->head = NULL;

  /*
   * The check for whether it's a black piece to be played is actually
   *     black = (ply < 2) ? (ply==1) : (ply & 1),
   * but material will always be sufficient in ply < 2 so we might as
   * well save on the conditional.
   */

  const uint8_t material = (ply & 1) ? black_count : white_count,
    flat = material & 0x7F,
    cap = ((ply >= 2) && (material & 0x80)),
    standing = ((ply >= 2) && flat);

  // Step across the board
  for (int row = 0; row < board_size; row++) {
    for (int col = 0; col < board_size; col++) {
      // We'll need these at various points: the location of this
      // square and the maximum number of stones we could pick up
      const int loc = THE_COORDS(col, row);
      const uint8_t count = DANGER_MIN(COUNT_AT(loc), board_size);

      // Only try moves after CPS and if the colour is correct
      if (count) {
	if (ply >= 2 && ((colours[loc] & 1) == current_colour)) {

	  // Pre-compute end-stops and crushes
	  uint8_t end_stops[4], crushes[4] = {0, 0, 0, 0};

	  // These are upper bounds, not counting walls and such.
	  // UP DOWN LEFT RIGHT
	  end_stops[0] = DANGER_MIN(board_size - row - 1, count);
	  end_stops[1] = DANGER_MIN(row, count);
	  end_stops[2] = DANGER_MIN(col, count);
	  end_stops[3] = DANGER_MIN(board_size - col - 1, count);

	  // Now we check for caps and walls
	  const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE;
	  for (int d = 0; d < 4; d++){
	    const int delta = move_deltas[d];
	    const int stop = end_stops[d];
	    end_stops[d] = 0;
	    for (int k = 1; k <= stop; k++) {
	      const enum STONE_VARIANT stone = STONE_AT(loc+k*delta);
	      if (stone == STONE_STANDING) {
		if (cap_top) {
		  crushes[d] = 0xFF;
		  end_stops[d]++;
		}
		break;
	      } else if (stone == STONE_CAPSTONE) {
		break;
	      }
	      end_stops[d]++;
	    }
	  }
	  /*
	   * For each direction, generate all possible ordered integer
	   * partitions of 1 ≤ num ≤ count whose number of summands is
	   * exactly 1 ≤ summands ≤ min(end_stops[dir], num) -- we
	   * write summands as steps.
	   *
	   * We exploit the `gaps' bijection here and elsewhere
	   * between ordered {integer partitions of n with s summands}
	   * and {binary strings of length n-1 with s-1 set bits}.
	   */
	  for (enum MOVE_DIRECTION dir=M_UP; dir<=M_RIGHT; dir++) {
	    for (uint8_t num = 1; num <= count; num++) {
	      for (uint8_t steps = 1;
		   steps <= end_stops[dir] && steps <= num;
		   steps++) {
		uint8_t gaps =
		  ((1<<(board_size - 2)) - 1) >> (board_size-steps-1);
		// For 5x5 this givess 0b0000[0XXX] where steps-1 of
		// those X's are 1s (starting with LSB) because 4-1=3
		// and 5-1=4
		do  {
		  /*
		   * We skip the partition if it calls for multiple
		   * stones at the end with a crush.
		   */
		  const uint8_t last_drop_check =
		    (num > 1) ? (gaps & (1 << (num - 2))) : 1;
		  if (crushes[dir] == 0 || last_drop_check) {
		    // We have to record a crush!
		    const uint8_t crush =
		      (steps == end_stops[dir]) && crushes[dir];
		    // Store the move

		    list_append(list, A_MOVE, loc,
				(crush << 7) | gaps,
				(dir<<4) | num);
		  }
		  /*
		   * With thanks to
		   * https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
		   * we have the following magic to generate the next
		   * permutation of steps-many set bits
		   */
		  uint8_t t = (gaps | (gaps - 1));
		  gaps = (t + 1)
		    | (((~t & -~t) - 1) >> (__builtin_ctz(gaps) + 1));
		} while (gaps && (gaps + 1 <= (1 << (num - 1))));
	      }
	    }
	  }
	}
      } // end of if (count) { ... }
      else if (material) {
	// Empty square, generate placements
	if (flat) {
	  list_prepend(list, A_PLACE, loc, STONE_FLAT, 0);
	  if (standing)
	    list_prepend(list, A_PLACE, loc, STONE_STANDING,0);
	}
	if (cap)
	  list_prepend(list, A_PLACE, loc, STONE_CAPSTONE, 0);
      }
    }
  }
  return list;
}

void action_take(const action_t action) {
  const int8_t loc = A_GET_LOC(action);
  if (A_GET_TYPE(action) == A_PLACE) {
    const uint8_t black = (current_colour == C_BLACK);
    switch (A_GET_DATA0(action)) {
      case STONE_FLAT: {
	if (black) black_count--;
	else white_count--;
	colours[loc] = current_colour;
	celldat[loc] = NUM_INC | STONE_FLAT;
	break;
      }
      case STONE_STANDING:  {
	if (black) black_count--;
	else white_count--;
	colours[loc] = current_colour;
	celldat[loc] = NUM_INC | STONE_STANDING;
	break;
      }
      default: {
	if (black) black_count &= 0x7F;
	else white_count &= 0x7F;
	colours[loc] = current_colour;
	celldat[loc] = NUM_INC | STONE_CAPSTONE;
	break;
      }
    }
  } else {
    /*
     * See the discussion around line 135 for an explanation of the
     * encoding. Here we are not interested in whether we crushed, it
     * will work out by anyway because we overwrite the top stone
     * type. See (*) later for when we do need to know.
     */
    const uint8_t gaps = A_GET_DATA0(action) & 0x7F,
      num = A_GET_DATA1(action) & 0x0F, // unpack
      dir = A_GET_DATA1(action) >> 4;
    int8_t delta = move_deltas[dir];

    // Use the Kernighan method to count the set bits
    int8_t steps = 1;
    for (uint8_t _gaps = gaps; _gaps; steps++) _gaps &= _gaps - 1;

    // Move top stone type to destination
    celldat[loc+steps*delta] &= CLR_STONE; // necessary for crushing
    celldat[loc+steps*delta] |= STONE_AT(loc);
    celldat[loc] &= CLR_STONE;
    celldat[loc] |= STONE_FLAT; // should be optimised out

    uint8_t total = 1, gap_bit = 1 << (num - 2); // it's not important
    // what negative
    // shifts do here, we
    // don't use gap_bit
    // if num < 2
    // move stuff starting at destination
    for (uint8_t d = 1; d < num; d++, total++, gap_bit >>= 1) {
      // We took a step, move everything over so far
      if (gaps & gap_bit) {
	colours[loc+steps*delta] <<= total;
	colours[loc+steps*delta] |= colours[loc] & ((1 << total) - 1);
	colours[loc] >>= total;
	celldat[loc+steps*delta] += total*NUM_INC;
	celldat[loc] -= total*NUM_INC;
	// Reset for next step
	total = 0;
	steps--;
      }
    }
    // Move what remains (steps == 1 here always, so we simplify)
    colours[loc+delta] <<= total;
    colours[loc+delta] |= colours[loc] & ((1 << total) - 1);
    colours[loc] >>= total;
    celldat[loc+delta] += total*NUM_INC;
    celldat[loc] -= total*NUM_INC;
  }
  // Next ply
  inline_next_ply();
}

void action_undo(const action_t action) {
  // Previous ply
  inline_prev_ply();

  const int8_t loc = A_GET_LOC(action);
  if (A_GET_TYPE(action) == A_PLACE) {
    const uint8_t black = (current_colour == C_BLACK);
    celldat[loc] = 0;
    if (A_GET_DATA0(action) == STONE_CAPSTONE) {
      if (black) black_count |= 0x80;
      else white_count |= 0x80;
    } else {
      if (black) black_count++;
      else white_count++;
    }
  } else {
    // See action_take for comments, this is the time reversal, but
    // there is one caveat -- undoing a crush! (*)
    const uint8_t gaps = A_GET_DATA0(action) & 0x7F,
      crush = A_GET_DATA0(action) & 0x80,
      num = A_GET_DATA1(action) & 0x0F,
      dir = A_GET_DATA1(action) >> 4;
    const int8_t delta = move_deltas[dir];

    int8_t steps = 1;
    uint8_t gap_bit = 1, total = 1;
    for (int8_t d = 1; d < num; d++, total++, gap_bit <<= 1) {
      if (gaps & gap_bit) {
	colours[loc] <<= total;
	colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1);
	colours[loc+steps*delta] >>= total;
	celldat[loc] += total*NUM_INC;
	celldat[loc+steps*delta] -= total*NUM_INC;
	total = 0;
	steps++;
      }
    }
    colours[loc] <<= total;
    colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1);
    colours[loc+steps*delta] >>= total;

    celldat[loc] += total*NUM_INC;
    // celldat[loc] &= CLR_STONE; is not necessary, as STONE_FLAT == 0
    celldat[loc] |= STONE_AT(loc+steps*delta);
    celldat[loc+steps*delta] -= total*NUM_INC;
    celldat[loc+steps*delta] &= CLR_STONE;
    if (crush) {
      celldat[loc+steps*delta] |= STONE_STANDING;
    } else {
      celldat[loc+steps*delta] |= STONE_FLAT; // should be optimised out
    }
  }
}

void action_to_ptn(const action_t action, char* out_ptn) {
  const int8_t loc = A_GET_LOC(action);
  if (A_GET_TYPE(action) == A_PLACE) {
    generate_place(loc, A_GET_DATA0(action), out_ptn);
  } else {
    const uint8_t gaps = A_GET_DATA0(action) & 0x7F,
      num = A_GET_DATA1(action) & 0x0F, // unpack
      dir = A_GET_DATA1(action) >> 4;

    uint8_t drops[board_size]; // we only ever need board_size-1 in
    // drops actually, the last spot is to
    // skip a bounds check at (**)
    uint8_t mask = 1, steps = 0;
    // Translate to a drop sequence
    drops[0] = 1; mask = 1;
    for (uint8_t d = 1; d < num; d++) {
      if (gaps & mask) {
	steps++;
	drops[steps] = 1; // (**) no bounds check
      } else {
	drops[steps] += 1;
      }
      mask <<= 1;
    }
    generate_move(loc, dir, steps+1, drops, out_ptn);
  }
}

// ===================================================================
// Helper method implementations
// ===================================================================

static inline void
list_append(action_list_t *list, const enum A_TYPE type,
	    const int8_t loc, const uint8_t data0,
	    const uint8_t data1) {
  action_node_t *new = malloc(sizeof(action_node_t));
  // TODO: trap errno

  new->next = NULL;
  new->action = A_BUILD(type, loc, data0, data1);

  if (list->length) {
    list->tail->next = new;
    list->tail = new;
  } else {
    list->head = new;
    list->tail = new;
  }

  list->length++;
}

static inline void
list_prepend(action_list_t *list, const enum A_TYPE type,
	     const int8_t loc, const uint8_t data0,
	     const uint8_t data1) {
  action_node_t *new = malloc(sizeof(action_list_t));
  // TODO: trap errno

  new->next = list->head;
  list->head = new;
  new->action = A_BUILD(type, loc, data0, data1);

  if (list->length == 0) {
    list->tail = new;
  }

  list->length++;
}

static inline void
inline_next_ply(void) {
  ply++;
  if (ply == 2) {
    current_colour = C_WHITE;
  } else {
    if (current_colour == C_BLACK) current_colour = C_WHITE;
    else current_colour = C_BLACK;
  }
}

static inline void
inline_prev_ply(void) {
  if (ply>0) ply--;
  if (ply == 1) {
    current_colour = C_WHITE;
  } else {
    if (current_colour == C_BLACK) current_colour = C_WHITE;
    else current_colour = C_BLACK;
  }
}