checkers/checkers.rb

#!/usr/bin/ruby

EMPTY = 0
TEAM_1 = 1
TEAM_2 = 2
TEAM_1_MAN = ' w '
TEAM_1_KING = ' W '
TEAM_2_MAN = ' b '
TEAM_2_KING = ' B '
BOARD_EMPTY = ' _ '
BOARD_SIZE = 8

class Board
	attr :stats, true

	def initialize()
		@board = Array.new(BOARD_SIZE) {|i| Array.new(BOARD_SIZE, BOARD_EMPTY)}
		@stats = {TEAM_1 => {}, TEAM_2 => {}}
	end

	def setup()
		0.step(BOARD_SIZE) {|i|
		       	peice = (i < 3 ? TEAM_1_MAN : TEAM_2_MAN)	
			if [0,2,6].include? i
				start = 1
			elsif [1,5,7].include? i
				start = 0
			else
				next
			end
			start.step(BOARD_SIZE-1,2) {|j|
				@board[i][j] = peice
			}
		}
		@stats[TEAM_1]['count'] = 12
		@stats[TEAM_2]['count'] = 12
	end

	def set(x, y, thing)
		@board[y][x] = thing
	end

	def get(x, y)
		@board[y][x]
	end

	def to_s()
		str = '  '
		0.step(BOARD_SIZE-1) {|i|
			str += ' ' + i.to_s + ' '
		}
		str += "\n"
		i = 0;
		@board.each {|row|
			str += ('A'.ord + i).chr + ' '
			i += 1
			row.each {|cell| 
				str += cell
			} 
			str += "\n"
		}
		str += 'White: ' + @stats[TEAM_1]['count'].to_s + ' -- Black: ' + @stats[TEAM_2]['count'].to_s  + "\n" 
		return str
	end

	def piece_team(piece)
		if piece == TEAM_1_MAN or piece == TEAM_1_KING
			return TEAM_1
		elsif piece == TEAM_2_MAN or piece == TEAM_2_KING
			return TEAM_2
		else
			return EMPTY
		end
	end

	def empty?(x, y)
		return @board[y][x] == BOARD_EMPTY
	end

	def valid_coords(x, y)
		return (x >= 0 and x < BOARD_SIZE and y >= 0 and y < BOARD_SIZE)
	end

	def gen_moves(x, y, x_mod, y_mod)
		moves = []
		for xm in x_mod
			new_x = x + xm
			for ym in y_mod
				new_y = y + ym
				if valid_coords(new_x, new_y) and empty?(new_x, new_y)
					moves += [[new_x, new_y]]
				end
			end
		end
		return moves
	end

	# function to chart path of jumps
	# merging them together
	# only returns full paths
	#
	# base case: no jumps avail, return path
	# jumps avail: do all and merge and return
	def gen_jumps(path, x, y, team, x_mod, y_mod, taken=[])
		jumps = []
		for xm in x_mod
			new_x = x + xm
			for ym in y_mod
				new_y = y + ym
				if valid_coords(new_x, new_y) and piece?(new_x, new_y) and !taken.include?([new_x, new_y]) and team != team(new_x, new_y)
					taken.push([new_x, new_y])
					final_x = new_x + xm
					final_y = new_y + ym
					if (valid_coords(final_x, final_y) and empty?(final_x, final_y))
						jumps += gen_jumps(path + [[final_x, final_y]], final_x, final_y, team, x_mod, y_mod, taken)
					end
				end
			end
		end

		if jumps == []
			if path == []
				return []
			else 
				return [path]
			end
		else
			return jumps
		end
	end

	def piece?(x, y)
		return !empty?(x, y)
	end

	def team(x, y)
		if piece?(x, y)
			if @board[y][x] == TEAM_1_MAN or @board[y][x] == TEAM_1_KING
				return TEAM_1
			else
				return TEAM_2
			end
		end
		return EMPTY
	end

	def opposite_team(team)
		return (team == TEAM_1 ? TEAM_2 : TEAM_1)
	end

	def man?(x, y)
		return (@board[y][x] == TEAM_1_MAN or @board[y][x] == TEAM_2_MAN)
	end
	
	def king?(x, y)
		return (@board[y][x] == TEAM_1_KING or @board[y][x] == TEAM_2_KING)
	end

	def piece_valid_moves(x, y, team)
		moves = []
		if piece_team(@board[y][x]) == team
			direction = [1]
			if king?(x, y)
				direction = [-1, 1]
			elsif team == TEAM_2 
				direction = [-1]
			end

			moves = gen_moves(x, y, [-1,1], direction)
			moves += gen_jumps([], x, y, team, [-1, 1], direction)
		end
		return moves
	end

	def dup() 
		b = Board.new
		for x in 0..(BOARD_SIZE-1)
			for y in 0..(BOARD_SIZE-1)
				b.set(x, y, get(x, y))
			end
		end
		b.stats[TEAM_1] = @stats[TEAM_1].dup
		b.stats[TEAM_2] = @stats[TEAM_2].dup
		return b
	end

	def between(c1, c2)
		return [ c2[0] + (c1[0]-c2[0])/2, c2[1] + (c1[1]-c2[1])/2 ]
	end

	def move_piece(c1, c2)
		piece = get(c1[0], c1[1])
		set(c1[0], c1[1], BOARD_EMPTY)
		set(c2[0], c2[1], piece)
		if team(c2[0], c2[1]) == TEAM_1 and c2[1] == BOARD_SIZE-1
			set(c2[0], c2[1], TEAM_1_KING)
		elsif (team(c2[0], c2[1]) == TEAM_2 and c2[1] == 0)
			set(c2[0], c2[1], TEAM_2_KING)
		end
	end


	# doesnt validate
	def do_move(x, y, move, team)
		if move[0].is_a?(Array)
			# jump
			move.each { |jump|
				enemy = between([x,y], jump)
				set(enemy[0], enemy[1], BOARD_EMPTY)
				@stats[opposite_team(team)]['count'] -= 1
				move_piece([x,y], jump)
			}
		else
			# move
			move_piece([x,y], move) 
		end
	end	


	def gen_next_move_boards(team)
		boards = []
		for x in 0..(BOARD_SIZE-1)
			for y in 0..(BOARD_SIZE-1)
				if piece?(x, y) and team(x,y) == team
					moves = piece_valid_moves(x, y, team(x, y))
					moves.each { |move|
						board = dup()
						board.do_move(x, y, move, team(x, y))
						boards.push(board)
					}
				end
			end
		end
		return boards
	end

	def score(team)
		score = 0
		score += @stats[team]['count']
		score += 12 - @stats[opposite_team(team)]['count']
		if @stats[opposite_team(team)]['count'] == 0
			score += 12
		elsif @stats[team]['count'] == 0
			score -= 12
		end
		return score	
	end

	def search(team)
		@top_depth = 10
		search_do(team, @top_depth, 100.0, 0.0, "R")
	end

	def search_do(team, depth, percent, last_percent, location)
		#puts location
		if depth == 0
			#puts "DONE"
			return score(team)
		end
		max = -100

		#if team == TEAM_1
		#	puts depth.to_s + ": TEAM_1's turn:"
		#else
		#	puts depth.to_s + ": TEAM_2's turn:"
		#end
		#puts to_s #moves[0].to_s
		if @stats[TEAM_1]['count'] == 0
			puts "TEAM_2 WON!"
			return score(team) 
		elsif @stats[TEAM_2]['count'] == 0
			puts "TEAM_1 WON!"
			return score(team) 
		else
			moves = gen_next_move_boards(team)
			if moves == []
				puts "NO MOVES AVAILABLE?"
				return score(team)
			else
				done = 0.0
				item_percent = percent/moves.length

				for i in 0..moves.length-1 do
					#moves.each { |move|
					move = moves[i]
					#puts "SEARCH"
        				sub_score = move.search_do(opposite_team(team), depth -1, item_percent, last_percent+done, location + "." +i.to_s )
       					done += item_percent
					if done >= 0.0001
          					last_percent += done;
						puts "%.5f" % last_percent + "% depth: " + depth.to_s + " max: " + max.to_s
						done = 0.0
        				end
					#puts "Score: " + sub_score.to_s
					if sub_score > max
						max = sub_score
					end
				end
				return max
			end
		 end
	end

	def parse_coords(str)
		if str.length != 2
			return false
		end
		
		y = str.downcase[0]
		x = str[1]

		if x >= '0' and x <= '7'
			x = x.ord - '0'.ord
		else 
			return false
		end

		if y >= 'a' and y <= 'h'
			y = y.ord - 'a'.ord
		else 
			return false
		end
		return [x,y]
	end

	# todo: deal with loss when no move avail
	def play()
		setup()
		color = ''
		while color != 'w' and color != 'b'
			print "Choose color ([W]hite or [B]lack): "
			color = gets
			color = color.downcase[0]
		end

		turn = 1
		team = TEAM_1
		while true
			print "Turn " + turn.to_s + ": "
			if team == TEAM_1
				print "white "
				if color == 'w'
					print "(player)"
				else
					print "(ai)"
				end
			else
				print "black "
				if color == 'b'
					print '(player)'
				else
					print '(ai)'
				end
			end
			print "\n"
			puts to_s()

			if (team == TEAM_1 and color == 'w') or (team == TEAM_2 and color == 'b')
				valid = false
				while !valid
					print "Move piece: "
					from = gets().strip!
					print "to: "
					to = gets().strip!
					from = parse_coords(from)
					to = parse_coords(to)
					puts to.to_s + " or " + from.to_s
					if !to or !from
						next
					end
					if team(from[0], from[1]) != team
						next
					end
					if !piece_valid_moves(from[0], from[1], team).include?(to)
						next
					end
					valid = true
				end
				do_move(from[0], from[1], to, team)
			else
				puts "AI MOVE"
			end

			if @stats[TEAM_1]['count'] == 0
				puts "Black wins!"
			elsif @stats[TEAM_2]['count'] == 0
				puts "White wins!"
			end
			team = opposite_team(team)
			turn += 1
		end
	end

end