#!/usr/bin/env awk

# ttt.awk - Tic-Tac-Toe in awk

# Copyright (c) 2010, Alan Saqui <alan.saqui@gmail.com>
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without 
# modification, are permitted provided that the following conditions are met:
#
# 1. Redistributions of source code must retain the above copyright notice, 
#    this list of conditions and the following disclaimer.
# 2. Redistributions in binary form must reproduce the above copyright notice, 
#    this list of conditions and the following disclaimer in the 
#    documentation and/or other materials provided with the distribution.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
#  DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE 
# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 
# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 
# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 
# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
BEGIN {
	# Some constants to ease readability
	COMPUTER = "O"
	HUMAN = "X"
	COMPUTER_WIN = 1
	DRAW = -1
	HUMAN_WIN = -2

	board = "123456789"
	# Array of regexes describing a win for X
	x_wins[1] = "^XXX......$"
	x_wins[2] = "^...XXX...$"
	x_wins[3] = "^......XXX$"
	x_wins[4] = "^X..X..X..$"
	x_wins[5] = "^.X..X..X.$"
	x_wins[6] = "^..X..X..X$"
	x_wins[7] = "^X...X...X$"
	x_wins[8] = "^..X.X.X..$"

	# Array of regexes describing a win for O
	o_wins[1] = "^OOO......$"
	o_wins[2] = "^...OOO...$"
	o_wins[3] = "^......OOO$"
	o_wins[4] = "^O..O..O..$"
	o_wins[5] = "^.O..O..O.$"
	o_wins[6] = "^..O..O..O$"
	o_wins[7] = "^O...O...O$"
	o_wins[8] = "^..O.O.O..$"
	
	printf "Would you like to go first? (y/n): "
	getline
	if ($0 ~ /[nN]/) {
		# Computer always chooses the middle square first
		board = make_move(board, COMPUTER, 5)
	}
	pp_board(board)
	prompt_move()
}

# Prompt the human to move.
function prompt_move() {
	printf "%s to move (1-9, or 'q' to quit): ", HUMAN	
}

# Returns the status of the game, HUMAN_WIN if human has won, COMPUTER_WIN 
# if the computer has won, DRAW if the game is a draw, and 0 if the game is 
# still 'in progress'.
function game_status(board) {
	if (find_win(board, HUMAN)) {
		return HUMAN_WIN
	} else if (find_win(board, COMPUTER)) {
		return COMPUTER_WIN	
	} else if (is_draw(board)) {
		return DRAW
	} else {
		return 0
	}
}

# Print a message indicating who won, or if the game is a draw.
function pstatus(status,
msgs) {
	msgs[COMPUTER_WIN] = "Computer has won!"
	msgs[HUMAN_WIN] = "You have won!"
	msgs[DRAW] = "Game is a draw."
	if (status) {
		printf "%s\n", msgs[status]
	}
	return status
}

# Returns > 0 if there is a win on the board for the given player, 0 otherwise.
# If the marks for player and computer are switched, then the regex lists have
# to be switched here too.
function find_win(board, player,  
key) {
	if (player == HUMAN) {
		for (key in x_wins) {
			if (match(board, x_wins[key])) {
				return key
			}
		}
	} else {
		for (key in o_wins) {
			if (match(board, o_wins[key]))
				return key
		}
	}
	return 0
}

# Returns 1 if the game is in a draw state, 0 otherwise.
function is_draw(board) {
	return (board ~ /^[XO][XO][XO][XO][XO][XO][XO][XO][XO]$/)
}

# Returns a string with the indices of the open squares on the board.
function find_legal_moves(board, 
legal_moves, i) {
	legal_moves = ""
	for (i = 1; i <= length(board); i++) {
		if (substr(board, i, 1) !~ /^[XO]$/) {
			legal_moves = legal_moves i
		}
	}
	return legal_moves
}

# Record a move on the board.
# Does not alter the original board, but returns the new board instead.
function make_move(board, player, square) {
	return substr(board, 1, (square - 1)) player substr(board, 
	    (square + 1), (9 - square))
}

# Negamax evaluator function. Note this version scans the entire game tree.
function negamax(board, depth, alpha, beta, color,  
to_move, nm_moves, i, new_board, score) {
	to_move = (color == -1) ? HUMAN : COMPUTER
	if (find_win(board, COMPUTER)) {
		return (color * 1)	# Wins are worth 1 
	} else if (find_win(board, HUMAN)) {
		return (color * -1)
	} else if (is_draw(board)) {
		return 0	# Draws are worth 0
	}
	nm_moves = find_legal_moves(board)
	for (i = 1; i <= length(nm_moves); i++) {
		move = substr(nm_moves, i, 1)
		# Create a new board
		new_board = make_move(board, to_move, move)
		score = -negamax(new_board, depth - 1, -beta, -alpha, -color)
		alpha = (score > alpha) ? score : alpha
	}
	return alpha
}

# Use negamax evaluator to find the best move to make.
function find_best_move(board, player,  
my_moves, best_move, best_score, i, move, new_board, score) {
	my_moves = find_legal_moves(board)
	best_move = 0
	best_score = -2
	for (i = 1; i <= length(my_moves); i++) {
		move = substr(my_moves, i, 1)
		new_board = make_move(board, player, move)
		score = -negamax(new_board, 9, -2, 2, -1)
		if (score > best_score) {
			best_score = score
			best_move = move
		}
	}
	return best_move
}

# 'Pretty-print' the game board.
function pp_board(board,  
b_arr) {
	split(board, b_arr, "")
	print ""
	print b_arr[1] "|" b_arr[2] "|" b_arr[3]
	print "-+-+-"
	print b_arr[4] "|" b_arr[5] "|" b_arr[6]
	print "-+-+-"
	print b_arr[7] "|" b_arr[8] "|" b_arr[9]
	print ""
}

# Record a move on the board, redraw board, then check if the game has ended.
function take_turn(player, move,
status) {
	board = make_move(board, player, move)
	pp_board(board)
	status = game_status(board)
	if (status) {
		pstatus(status)
		exit
	}
}

# Event: player has entered a move
/^[123456789]$/ {
	# Check if this is a legal move
	legal_moves = find_legal_moves(board)
	if (!index(legal_moves, $0)) {
		print "Sorry, not a legal move."
		prompt_move()
		next
	}
	take_turn(HUMAN, $0)
	printf "%s to move... ", COMPUTER
	move = find_best_move(board, COMPUTER)
	print move
	take_turn(COMPUTER, move)
	prompt_move()
	next
}
# Event: player has entered 'quit' command
/^[qQ]$/ {
	print "Thanks for playing!"
	exit
}
# Event: unknown command
{
	print "Move must be a number between 1 and 9 (or 'q' to quit)"
	prompt_move()
}