/*
 *  SPL - The SPL Programming Language
 *  Copyright (C) 2004, 2005  Clifford Wolf <clifford@clifford.at>
 *
 *  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 2 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 this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 *  4row.spl: Playing 4-in-a-row. This is a nice benchmark..
 */


/**********************************

The game should end with this output.
If it doesn't, something broke the script.

    1   2   3   4   5   6   7   8
8 |   |   |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+
7 |   |   | X |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+
6 | O |   | O | X |   |   |   |   |
  +---+---+---+---+---+---+---+---+
5 | X | X | O | O |   |   |   |   |
  +---+---+---+---+---+---+---+---+
4 | O | O | X | O |   |   |   |   |
  +---+---+---+---+---+---+---+---+
3 | O | X | X | X | X |   |   |   |
  +---+---+---+---+---+---+---+---+
2 | X | X | O | O | O |   |   |   |
  +---+---+---+---+---+---+---+---+
1 | X | X | O | O | X |   |   |   |
  +---+---+---+---+---+---+---+---+

4 in a row: 5,3 4,3 3,3 2,3

!!! Player X won !!!

**********************************/


function print_board()
{
	var x, y;
	write("\n\n ");
	for (x=1; x<=size; x++)
		write("   $x");
	write("\n");
	for (y=size; y>0; y--) {
		write(y);
		for (x=1; x<=size; x++)
			write(" | ${board.[x].[y]}");
		write(" |\n  ");
		for (x=1; x<=size; x++)
			write("+---");
		write("+\n");
	}
	write("\n");
}

function calc_line(x1, y1, x2, y2, x3, y3, x4, y4, do_checkpos)
{
	if ( x1<1 || x1>size ) return 0;
	if ( y1<1 || y1>size ) return 0;
	if ( x4<1 || x4>size ) return 0;
	if ( y4<1 || y4>size ) return 0;
	var points = 0;

	if ( board.[x1].[y1] ~!= "O" &&
	     board.[x2].[y2] ~!= "O" &&
	     board.[x3].[y3] ~!= "O" &&
	     board.[x4].[y4] ~!= "O" ) {
		var j = 0;
		if ( board.[x1].[y1] ~== "X" ) j++;
		if ( board.[x2].[y2] ~== "X" ) j++;
		if ( board.[x3].[y3] ~== "X" ) j++;
		if ( board.[x4].[y4] ~== "X" ) j++;
		if ( j == 2 ) points += 10;
		if ( j == 3 ) points += 20;
		if ( j == 4 ) points += 100000000;
		if ( j == 4 && do_checkpos )
			write("4 in a row: $x1,$y1 $x2,$y2 $x3,$y3 $x4,$y4\n");
	}
	if ( board.[x1].[y1] ~!= "X" &&
	     board.[x2].[y2] ~!= "X" &&
	     board.[x3].[y3] ~!= "X" &&
	     board.[x4].[y4] ~!= "X" ) {
		var j = 0;
		if ( board.[x1].[y1] ~== "O" ) j++;
		if ( board.[x2].[y2] ~== "O" ) j++;
		if ( board.[x3].[y3] ~== "O" ) j++;
		if ( board.[x4].[y4] ~== "O" ) j++;
		if ( j == 2 ) points -= 10;
		if ( j == 3 ) points -= 20;
		if ( j == 4 ) points -= 100000000;
		if ( j == 4 && do_checkpos )
			write("4 in a row: $x1,$y1 $x2,$y2 $x3,$y3 $x4,$y4\n");
	}

	return points;
}

function calc_situation(do_checkpos, xp, yp)
{
	var i, x, y, points;
	points=0;
	if ( do_checkpos ) {
		for (x=4; x<=size; x++)
		for (y=4; y<=size; y++) {
			points += calc_line(x, y, x-1, y-1, x-2, y-2, x-3, y-3, 1);
			points += calc_line(x-3, y, x-2, y-1, x-1, y-2, x, y-3, 1);
		}
		for (x=4; x<=size; x++)
		for (y=1; y<=size; y++) {
			points += calc_line(x, y, x-1, y, x-2, y, x-3, y, 1);
			points += calc_line(y, x, y, x-1, y, x-2, y, x-3, 1);
		}
	} else {
		for (i=0; i<4; i++) {
			points += calc_line(xp+i, yp+i, xp+i-1, yp+i-1,
					xp+i-2, yp+i-2, xp+i-3, yp+i-3, 0);
			points += calc_line(xp-i, yp+i, xp-i+1, yp+i-1,
					xp-i+2, yp+i-2, xp-i+3, yp+i-3, 0);
			points += calc_line(xp+i, yp, xp+i-1, yp,
					xp+i-2, yp, xp+i-3, yp, 0);
			points += calc_line(xp, yp+i, xp, yp+i-1,
					xp, yp+i-2, xp, yp+i-3, 0);
		}
	}
	return points;
}

function comp_move(xo, recur)
{
	var bnr = -1, bvl = -1;
	var x, y, vl;

	if ( recur == 0 )
		write("Thinking");
	if ( recur == 1 )
		write(".");

	for (x=1; x<=size; x++) {
		var got_break = 0;
		for (y=1; y<=size && got_break == 0; y++) {
			if ( board.[x].[y] ~== " " ) {
				vl = -calc_situation(0, x, y);
				board.[x].[y] = xo;
				vl = vl + calc_situation(0, x, y);
				if ( vl > -10000000 && vl < 10000000 &&
				     recur < recursion_max )
					vl = vl + comp_move( xo ~== "O" ? "X" : "O",
					               recur + 1);
				if ( bnr == -1 || 
				     (xo ~== "X" && bvl < vl) ||
				     (xo ~== "O" && bvl > vl) ) {
					bnr=x;
					bvl=vl;
				}
				board.[x].[y] = " ";
				got_break = 1;
			}
		}
	}
	if ( recur == 0 ) {
		var got_break = 0;
		for (y=1; y<=size && got_break == 0; y++)
			if ( board.[bnr].[y] ~== " " ) {
				board.[bnr].[y] = xo;
				got_break = 1;
			}
		write("\n");
	}
	return bvl;
}

function checkpos()
{
	var val, free, x, y;
	val = calc_situation(1, 0, 0);
	if ( val < -10000000 ) {
		write("\n!!! Player O won !!!\n\n");
		exit;
	}
	if ( val > 10000000 ) {
		write("\n!!! Player X won !!!\n\n");
		exit;
	}
	free=0;
	for (x=1; x<=size; x++)
		if ( board.[x].[size] ~== " " ) free=1;
	if (!free) {
		write("\n!!! Nobody won !!!\n\n");
		exit;
	}
	return val;
}

var board;
var size = 8;
var recursion_max = 2;

for (var x=1; x<=size; x++)
for (var y=1; y<=size; y++)
	board.[x].[y] = " ";
print_board();

while ( 1 ) {
	comp_move("X", 0);
	print_board();
	checkpos();
	comp_move("O", 0);
	print_board();
	checkpos();
}