// Roughly orders moves in order of most likely to be good to least.
// Examines all checks first, followed by captures, followed by good moves.
// "Good moves" are sorted by their board evaluation after they are played.
// If quiescence is set to true, then only checks and captures are returned.
func orderedMoves(b *engine.Board, quiescence bool) []*engine.Move {
	checks := make([]*engine.Move, 0)
	captures := make([]*engine.Move, 0)
	rest := make([]*engine.Move, 0)
	// parentscore := EvalBoard(b)
	for _, move := range b.AllLegalMoves() {
		b.ForceMove(move)
		if b.IsCheck(b.Turn) {
			checks = append(checks, move)
		} else if move.Capture != 0 {
			captures = append(captures, move)
		} else if !quiescence {
			childscore := EvalBoard(b) * float64(b.Turn*-1)
			// if (b.Turn == -1 && childscore > parentscore) || (b.Turn == 1 && childscore < parentscore) {
			move.Score = childscore
			rest = append(rest, move)
			// }
		}
		b.UndoMove(move)
	}
	if !quiescence {
		sort.Sort(sort.Reverse(ByScore(rest)))
	}
	orderedmoves := make([]*engine.Move, len(checks)+len(captures)+len(rest))
	index := 0
	for _, l := range [][]*engine.Move{checks, captures, rest} {
		for _, m := range l {
			m.Score = 0
			orderedmoves[index] = m
			index++
		}
	}
	return orderedmoves
}

// Returns the score from the point of view of the person whose turn it is.
// Positive numbers indicate a stronger position.
func EvalBoard(b *engine.Board) (score float64) {
	if over := b.IsOver(); over != 0 {
		if over == 1 {
			return DRAW
		} else {
			return float64(WIN / 2 * over * b.Turn)
		}
	}
	attackarray := [8][8]int{}
	mypawns := [8]int{}
	opppawns := [8]int{}
	var heavies int // count of opponent's queens and rooks
	for _, piece := range b.Board {
		// add piece value to score and update attack array
		score += float64(VALUES[piece.Name] * piece.Color * b.Turn)
		updateAttackArray(b, piece, &attackarray)
		if piece.Name == 'p' {
			if piece.Color == b.Turn {
				mypawns[piece.Position.X-1] += 1
			} else {
				opppawns[piece.Position.X-1] += 1
			}
		} else if (piece.Name == 'q' || piece.Name == 'r') && piece.Color == b.Turn*-1 {
			heavies += 1
		}
	}
	score += pawnStructureAnalysis(mypawns)
	score -= pawnStructureAnalysis(opppawns)
	for _, piece := range b.Board {
		if piece.Name == 'k' {
			if heavies > 1 {
				if piece.Color == b.Turn {
					score += checkKingSafety(piece.Position.X, mypawns)
				} else {
					score -= checkKingSafety(piece.Position.X, opppawns)
				}
			} else {
				// endgame stuff
			}
		} else if piece.Name == 'p' {

		} else {

		}
	}
	return score
}

// Child-level negamax search function.
// Unlike NegaMax(), only returns score, not full move.
func NegaMaxChild(b *engine.Board, depth int) float64 {
	if b.IsOver() != 0 || depth == 0 {
		return EvalBoard(b)
	}
	var score float64 = LOSS
	var childscore float64
	for _, board := range b.NewGen() {
		childscore = -NegaMaxChild(board, depth-1)
		if childscore > score {
			score = childscore
			if score == WIN {
				return score
			}
		}
	}
	return score
}

// Measures how many squares a piece can attack in a given direction
func AttackRay(p *engine.Piece, b *engine.Board, dir [2]int) int {
	if p.Captured {
		return 0
	}
	if !p.Infinite_direction {
		return 1
	}
	for n := 1; n < 8; n++ {
		s := &engine.Square{
			X: p.Position.X + dir[0]*n,
			Y: p.Position.Y + dir[1]*n,
		}
		if occupied, _ := b.Occupied(s); occupied != 0 {
			if occupied == -2 {
				return n - 1
			}
			return n
		}
	}
	return 7
}

// Child level NegaScout search function.
// Unlike its parent, only returns score and not full move
func NegaScoutChild(b *engine.Board, depth int, alpha, beta float64) float64 {
	if b.IsOver() != 0 || depth == 0 {
		return EvalBoard(b)
	}

	// not indended for actual use
	orderedmoves := b.AllLegalMoves()

	var score float64
	for i, m := range orderedmoves {
		childboard := b.CopyBoard()
		childboard.Move(m)
		if i != 0 {
			score = -NegaScoutChild(childboard, depth-1, -alpha-1, -alpha)
			if alpha < score && score < beta {
				score = -NegaScoutChild(childboard, depth-1, -beta, -alpha)
			}
		} else {
			score = -NegaScoutChild(childboard, depth-1, -beta, -alpha)
		}
		alpha = math.Max(alpha, score)
		if alpha >= beta {
			break
		}
	}
	return alpha
}

// First-level NegaScout search function.
// When called, alpha and beta should be set to the lowest and highest values possible.
func NegaScout(b *engine.Board, depth int, alpha, beta float64) *engine.Move {
	if b.IsOver() != 0 || depth == 0 {
		b.Lastmove.Score = EvalBoard(b)
		return &b.Lastmove
	}
	var move engine.Move

	// not indended for actual use
	orderedmoves := b.AllLegalMoves()

	var score float64
	for i, m := range orderedmoves {
		childboard := b.CopyBoard()
		childboard.Move(m)
		if i != 0 {
			score = -NegaScoutChild(childboard, depth-1, -alpha-1, -alpha)
			if alpha < score && score < beta {
				score = -NegaScoutChild(childboard, depth-1, -beta, -alpha)
			}
		} else {
			score = -NegaScoutChild(childboard, depth-1, -beta, -alpha)
		}
		alpha = math.Max(alpha, score)
		if alpha >= beta {
			move = *m.CopyMove()
			move.Score = alpha
			break
		}
	}
	return &move
}

// First-level negamax search function.
func NegaMax(b *engine.Board, depth int) *engine.Move {
	if b.IsOver() != 0 || depth == 0 {
		b.Lastmove.Score = EvalBoard(b)
		return &b.Lastmove
	}
	var move engine.Move
	move.Score = LOSS
	for _, m := range b.AllLegalMoves() {
		childboard := b.CopyBoard()
		childboard.Move(m)
		childscore := -NegaMaxChild(childboard, depth-1)
		if childscore > move.Score {
			move = *m.CopyMove()
			move.Score = childscore
			if move.Score == WIN {
				return &move
			}
		}
	}
	return &move
}

// Child level returns an evaluation
func AlphaBetaChild(b *engine.Board, depth int, alpha, beta float64, volatile bool) float64 {
	var movelist []*engine.Move
	if b.IsOver() != 0 {
		return EvalBoard(b)
	} else if depth == 0 {
		if !volatile {
			return EvalBoard(b)
		}
		depth += 1
		movelist = orderedMoves(b, true)
	} else {
		movelist = orderedMoves(b, false)
	}
	var score float64
	if b.Turn == 1 {
		for _, move := range movelist {
			b.ForceMove(move)
			if !volatile && (move.Capture != 0 || b.IsCheck(b.Turn)) {
				score = AlphaBetaChild(b, depth-1, alpha, beta, true)
			} else {
				score = AlphaBetaChild(b, depth-1, alpha, beta, false)
			}
			b.UndoMove(move)
			if score > alpha {
				alpha = score
			}
			if alpha >= beta {
				return alpha
			}
		}
		return alpha
	} else {
		for _, move := range movelist {
			b.ForceMove(move)
			if !volatile && (move.Capture != 0 || b.IsCheck(b.Turn)) {
				score = AlphaBetaChild(b, depth-1, alpha, beta, true)
			} else {
				score = AlphaBetaChild(b, depth-1, alpha, beta, false)
			}
			b.UndoMove(move)
			if score < beta {
				beta = score
			}
			if beta <= alpha {
				return beta
			}
		}
		return beta
	}
	return 0
}

// Standard minmax search with alpha beta pruning.
// Initial call: alpha set to lowest value, beta set to highest.
// Top level returns a move.
func AlphaBeta(b *engine.Board, depth int, alpha, beta float64) *engine.Move {
	if b.IsOver() != 0 || depth == 0 {
		return nil
	}
	var bestmove *engine.Move = nil
	var result float64
	movelist := orderedMoves(b, false)
	if b.Turn == 1 {
		for _, move := range movelist {
			b.ForceMove(move)
			if move.Capture != 0 || b.IsCheck(b.Turn) {
				result = AlphaBetaChild(b, depth-1, alpha, beta, true)
			} else {
				result = AlphaBetaChild(b, depth-1, alpha, beta, false)
			}
			b.UndoMove(move)
			if result > alpha {
				alpha = result
				bestmove = move
				bestmove.Score = alpha
			}
			if alpha >= beta {
				bestmove = move
				bestmove.Score = alpha
				return bestmove
			}
		}
		if bestmove == nil {
			return b.AllLegalMoves()[0]
		}
		return bestmove
	} else {
		for _, move := range movelist {
			b.ForceMove(move)
			if move.Capture != 0 || b.IsCheck(b.Turn) {
				result = AlphaBetaChild(b, depth-1, alpha, beta, true)
			} else {
				result = AlphaBetaChild(b, depth-1, alpha, beta, false)
			}
			if LOG {
				fmt.Println(move.ToString(), result)
			}
			b.UndoMove(move)
			if result < beta {
				beta = result
				bestmove = move
				bestmove.Score = beta
			}
			if beta <= alpha {
				bestmove = move
				bestmove.Score = beta
				return bestmove
			}
		}
		if bestmove == nil {
			return b.AllLegalMoves()[0]
		}
		return bestmove
	}
	if bestmove == nil {
		return b.AllLegalMoves()[0]
	}
	return bestmove
}

// Returns the score from the point of view of the person whose turn it is.
// Positive numbers indicate a stronger position.
func EvalBoard(b *engine.Board) float64 {
	if over := b.IsOver(); over != 0 {
		if over == 1 {
			return DRAW
		} else {
			if over > 0 {
				return WHITEWIN
			} else {
				return BLACKWIN
			}
		}
	}
	attackarray := [8][8]int{}
	whitepawns := []engine.Square{}
	blackpawns := []engine.Square{}
	var score float64
	for _, piece := range b.Board {
		if !piece.Captured {
			score += float64(VALUES[piece.Name] * piece.Color)
			updateAttackArray(b, piece, &attackarray)
			if piece.Name == 'p' {
				if piece.Color == 1 {
					whitepawns = append(whitepawns, piece.Position)
				} else {
					blackpawns = append(blackpawns, piece.Position)
				}
			}
		}
	}
	score += pawnStructureAnalysis(whitepawns, 1)
	score -= pawnStructureAnalysis(blackpawns, -1)
	whiterooks := []engine.Square{}
	blackrooks := []engine.Square{}
	for _, piece := range b.Board {
		if !piece.Captured {
			if piece.Name != 'q' && piece.Name != 'k' {
				if attackarray[piece.Position.X-1][piece.Position.Y-1]*piece.Color < 1 {
					score += float64(piece.Color) * HUNGPIECE
				}
			}
			switch piece.Name {
			case 'k':
				if piece.Color == 1 {
					score += checkKingSafety(piece.Position.X, whitepawns)
				} else {
					score -= checkKingSafety(piece.Position.X, blackpawns)
				}
			case 'p':
				// reward passed pawns
				if piece.Color == 1 {
					if pawnIsPassed(piece, blackpawns) {
						score += PASSEDPAWN
					}
				} else {
					if pawnIsPassed(piece, whitepawns) {
						score -= PASSEDPAWN
					}
				}
			case 'n':
				if piece.Position.X >= 3 && piece.Position.X <= 6 && piece.Position.Y >= 3 && piece.Position.Y <= 6 {
					score += float64(piece.Color) * CENTRALKNIGHT
				}
			case 'b':
				var numattacking int
				for _, dir := range piece.Directions {
					numattacking += AttackRay(piece, b, dir)
				}
				score += float64(piece.Color*numattacking) * BISHOPSQUARES
			case 'r':
				if (piece.Color == -1 && piece.Position.Y == 2) || (piece.Color == 1 && piece.Position.Y == 7) {
					score += float64(piece.Color) * ROOKONSEVENTH
				}
				if piece.Color == 1 {
					whiterooks = append(whiterooks, piece.Position)
				} else {
					blackrooks = append(blackrooks, piece.Position)
				}
			}
		}
	}
	score += rookAnalysis(whiterooks)
	score -= rookAnalysis(blackrooks)
	for x := 0; x < 8; x++ {
		for y := 0; y < 8; y++ {
			if attackarray[x][y] > 0 {
				if x >= 2 && x <= 5 && y >= 2 && y <= 5 {
					score += IMPORTANTSQUARE
				} else {
					score += WEAKSQUARE
				}
			} else if attackarray[x][y] < 0 {
				if x >= 2 && x <= 5 && y >= 2 && y <= 5 {
					score -= IMPORTANTSQUARE
				} else {
					score -= WEAKSQUARE
				}
			}
		}
//.........这里部分代码省略.........