Dominique Longin

Emiliano Lorini

Frédéric Maris

A Logical Modeling of the Yōkai Board Game

We present an epistemic language for representing an artificial player's beliefs and actions in the context of the Yōkai board game. Yōkai is a cooperative game which requires a combination of Theory of Mind (ToM), temporal and spatial reasoning to be played effectively by an artificial agent. We show that the language properly accounts for these three dimensions and that its satisfiability problem is NP-complete. This opens up the possibility of exploiting SAT techniques for automating reasoning of an artificial player in the context of the Yōkai board-game.

Introduction

When one wishes to model socio-cognitive agents and, in particular, agents endowed with a Theory of Mind (ToM) who are capable of reasoning about other agents' beliefs, some of the privileged tools are epistemic logic (EL) [START_REF] Fagin | Reasoning about Knowledge[END_REF][START_REF] Halpern | A guide to completeness and complexity for modal logics of knowledge and belief[END_REF] and its extensions by informative and communicative extensions such as public and private announcements [START_REF] Gerbrandy | Reasoning about information change[END_REF][START_REF] Plaza | Logics of public communications[END_REF][START_REF] Baltag | The logic of public announcements, common knowledge and private suspicions[END_REF]. The latter belongs to the Dynamic Epistemic Logic (DEL) family [START_REF] Van Ditmarsch | Dynamic Epistemic Logic[END_REF].

The major disadvantage of EL and DEL is that they have most of the time a high complexity thereby making them not very well-suited for practical applications. In particular, it has been shown that extending multi-agent EL by simple notions of state eliminating public announcement or arrow eliminating private announcement does not increase its PSPACE complexity (see, e.g., [START_REF] Lutz | Complexity and succinctness of public announcement logic[END_REF][START_REF] Bolander | Announcements to attentive agents[END_REF]). However, the satisfiability problem of full DEL with public, semi-private and private communicative actions was shown to be NEXPTIME-complete [START_REF] Aucher | On the complexity of dynamic epistemic logic[END_REF]. The situation is even worse in the context of epistemic planning: it is known that epistemic planning in public announcement logic (PAL) is decidable, while it becomes undecidable in full DEL, due to the fact that the epistemic model may grow as a consequence of a private announcement [START_REF] Bolander | Epistemic planning for single-and multiagent systems[END_REF].

In [START_REF] Lorini | Rethinking epistemic logic with belief bases[END_REF][START_REF] Lorini | In praise of belief bases: Doing epistemic logic without possible worlds[END_REF], a variant of epistemic logic with a semantics exploiting belief bases is introduced. It distinguishes explicit belief from implicit belief. The former is modeled as a fact in an agent's belief base, while the latter is modeled as a fact that is deducible from the agent's explicit beliefs. The main advantages of the belief base semantics for epistemic logic compared to the standard possible world semantics based on multi-relational structures (so-called Kripke models) are (i) its compactness, and (ii) its closeness to the way artificial cognitivelyinspired agents are traditionally modeled in AI and in the area of knowledge representation and reasoning (KR) by adopting a database perspective [START_REF] Shoham | Logical theories of intention and the database perspective[END_REF]. In [START_REF] Lorini | Decision procedures for epistemic logic exploiting belief bases[END_REF], it is shown that this variant of epistemic logic provides a valuable abstraction for modeling multi-robot scenarios in which each robot is endowed with a ToM whereby being able to ascribe epistemic states to the other robots and to reason about them. 1In this paper, we leverage the belief base semantics for epistemic logic to model interaction in the context of the cooperative board-game Yōkai. 2 We consider its two-player variant in which an artificial agent has to collaborate with a human agent to win it and to obtain the best score as possible. Yōkai is an interesting testbed for artificial agents, as it covers a lot of epistemic and strategic reasoning aspects as well as planning and belief revision aspects. The idea of testing the performance of artificial agents in the context of cooperative board-games in which ToM reasoning plays a role is not new. Some works exist about modeling and implementing artificial players for the card game Hanabi [START_REF] Bard | The hanabi challenge: A new frontier for AI research[END_REF][START_REF] Eger | An intentional AI for hanabi[END_REF][START_REF] Eger | Practical specification of belief manipulation in games[END_REF]. Yōkai adds to the ToM dimension, which is central in Hanabi, the temporal and spatial dimension. First of all, in Yōkai a player's performance relies on her/its capacity to remember the cards she/it and the other player have seen in the past. Secondly, the players must move cards in a shared space and there are spatial restrictions on card movements that should be taken into account by the players. More generally, the interesting feature of Yōkai, from the point view of KR, is the combination of epistemic, temporal and spatial reasoning that is required to completely apprehend all the game facets and dimensions.

The main novelty of our approach to modeling artificial board-game players is the use of SAT-based techniques. Specifically, the language we present for representing the artificial player's beliefs about the static and dynamic aspects of the game as well as about the human player's beliefs has the same complexity as SAT and can be polynomially translated into a propositional logic language. This opens up the possibility of exploiting SAT techniques for automating reasoning of the artificial player in the context of the Yōkai board-game.

The paper is organized as follows. In Section 2, we explain the rules of Yōkai and clarify the representation and reasoning requirements that are necessary for the artificial player to be able to play the game in a clever way. In Section 3, we introduce the specification language for modeling the artificial player's actions and beliefs about the game properties and about the human player's beliefs. It is a timed language for explicit and implicit belief with a semantics exploiting belief bases. The main novelty compared to the epistemic language presented in [START_REF] Lorini | Rethinking epistemic logic with belief bases[END_REF] is the temporal component: the artificial player modeled in the language has knowledge about the current time of the game and beliefs about current and past beliefs of the human player. Section 4 is devoted to the encoding of the game in the language. We first model the static aspects, namely, the artificial agent's beliefs about the rules and properties of the game. Then, we focus on the dynamic aspects by modeling the artificial player's actions and how they are used for planning a sequence of moves at a given round of the game.

Game description

In this section, we explain the rule of the Yōkai game. As pointed out in the introduction, we only consider the two-player variant of the game with an artificial and a human player.

Colored cards and actions. There are 4 types of card, red, yellow, green and blue cards, and 4 cards for each color. This gives us a total amount of 16 cards. The cards are placed face down in a grid of size 4x4 in a random way, so that the players cannot see their colors. The goal of the game is to gather together the cards of the same color. Figure 1a illustrates a winning configuration of the game. The players play sequentially in each round of the game. At each round, each player has to play the following 4 actions in the order she/it prefers:

1. to look at two cards privately (2 actions), 2. to move one card from its current position to a new position adjacent to another card (that is, linked to the latter by one of its sides) and without separating the cards into two disjointed groups, 3. either to activate a hint from the set of available hints (see next paragraph) or to disclose an information by marking one card with an active hint. Figure 1b portrays an example of illegal move. Indeed, the move will make the first and second cards on the left bottom corner of the grid separated from the rest of the cards.

Hints. Three types of hint are available: 1-color, 2-color and 3-color hints. Specifically, 1-color, 2-color and 3-color hints indicate, respectively, a single color, two colors and three colors in the set {red, green, blue, yellow}. There are 14 different hints available, but only seven hints are randomly selected at the beginning of the game: two occurrences of 1-color hint, three occurrences of 2-color hint and two occurrences of 3-color hint.

A hint can be used after being activated, and only available hints can be activated. Moreover, it can be used only once throughout the game. The state of a hint is unique: it is either available, activated, or marking. In particular, after a hint has been activated and used to mark a card, it is no longer available or activated. For example, suppose a player just looked at one card and discovers it is a red card. She can mark it with an active 2-color hint of type red/green to inform the other player that it is either a red card or a green card.

A hint is properly used if one of its colors matches with the color of the card it marks. For example, if a player uses an active 2-color card of type green/blue to mark a blue card, then the hint is properly used. Conversely, it the player uses it to mark a red card, then the hint is improperly used. Note that unless a mistake has been made, hints must be used properly.

Finally, when an active hint marks a card, that card can no longer be moved or observed.

End of the game. When a player thinks that the goal state is achieved, she/it can decide to stop the game. Otherwise, the game ends when all hints have been used by the players. At the end of the game, the cards are turned face up. If the goal state is achieved, the players win the game. Otherwise, they lose it. In case of win, the final score is calculated as follows: score = x 1 -x 2 + 2x 3 + 5x 4 where x 1 is the number of properly used hints, x 2 is the number of improperly used hints, x 3 is the number of activated hints that were not used by the players, and x 4 is the number of non-activated hints. The final score ranges in the interval [-7, 35].

Requirements. As emphasized in the introduction, in order to be able to reason about the static and dynamic aspects of the game, a player must have beliefs about:

• the other player's actual beliefs (ToM reasoning);

• the current positions of the cards and the executable card movements, given the current spatial configuration of the game (spatial reasoning);

• the color of the cards she/it observed in the past as well as the other player's past observations (temporal reasoning).

3 A timed language for explicit and implicit belief

This section presents a two-agent timed variant of the language and the semantics of the logic of explicit and implicit belief presented in [START_REF] Lorini | Rethinking epistemic logic with belief bases[END_REF]. The two agents are the artificial agent (or machine) m and the human user h. Agents m and h are treated asymmetrically. Our language allows us to represent (i) h's explicit beliefs at different points in a game sequence, and (ii) m's actual explicit and implicit beliefs, namely, m's explicit and implicit beliefs at the current time point of the game sequence. Following [START_REF] Lorini | Rethinking epistemic logic with belief bases[END_REF], explicit beliefs are defined to be beliefs in an agent's belief base, while implicit beliefs are those beliefs that are derivable from the agent's explicit beliefs.

We first present the static language in which agent m's beliefs do not change. Then, we present a dynamic extension in which agent m's belief base can be expanded by new information.

Static language

Assume a countably infinite set of atomic propositions ATM . We define the language in two steps.

We first define the language L 0 (ATM ) by the following grammar in BNF:

α ::= p t | t h α | now ≥t | ¬α | α 1 ∧ α 2 | m α
, where p ranges over ATM . L 0 (ATM ) is the language for representing agent h's timed explicit beliefs and agent m's actual explicit beliefs. Specifically, the formula t h α is read "agent h explicitly believes that α at time t", whilst m is read "agent m actually has the explicit belief that α". Atomic propositions are assumed to be timed: p t is read "atomic proposition p is true at time t". Finally, formula now ≥t provides information about the current time point. It is read "the actual time of the game play is at least t".

Then, we define L T 0 (ATM ) to be the subset L 0 (ATM ) including only timed formulas, that is:

L T 0 (ATM ) ={p t : p ∈ ATM and t ∈ N}∪ { t h α : α ∈ L 0 (ATM ) and t ∈ N}∪ {now ≥t : t ∈ N}.
Elements of L T 0 (ATM ) are denoted by x, y, . . . The language L(ATM ) extends the language L 0 (ATM ) by a modal operator of implicit belief for agent m and is defined by the following grammar:

ϕ ::= α | ¬ϕ | ϕ 1 ∧ ϕ 2 | m α,
where α ranges over L 0 (ATM ). For notational convenience we write L 0 instead of L 0 (ATM ), L T 0 instead of L T 0 (ATM ) and L instead of L(ATM ), when the context is unambiguous. The formula m α is read "agent m actually has the implicit belief that α". The other Boolean constructions , ⊥, ∨, → and ↔ are defined in the standard way. Notice that only formulas from the sublanguage L 0 can be in the scope of the implicit belief operator m . Therefore, nesting of this operator is not allowed (e.g., m ¬ m p t is not a well-formed formula). As we will show at the end of the section, this syntactic restriction on our language is useful to make the complexity of its satisfiability problem the same as the complexity of SAT.

The interpretation of the language L exploits the notion of belief base. While the notions of possible world and epistemic alternative are primitive in the standard Kripke semantics for epistemic logic [START_REF] Fagin | Reasoning about Knowledge[END_REF], they are defined from the primitive concept of belief base in our semantics.

Definition 1 (State) A state is a tuple S = (B, V ) where (i) B ⊆ L 0 is agent m's belief base (or, agent m's subjective view of the actual situation), (ii) V ⊆ L T 0 is the actual situation, and such that, for every t, t ∈ N,

now ≥0 ∈ V , (1)
if now ≥t ∈ V and t ≤ t then now ≥t ∈ V , (2)
now ≥t ∈ V iff now ≥t ∈ B, and (3)
now ≥t ∈ V iff ¬now ≥t ∈ B. (4)
The set of all states is denoted by S.

Conditions ( 1) and ( 2) in the previous definition guarantees time consistency, namely, that the current time should be at least 0 and that if the current time is at least t and t ≤ t, then it should be at least t . Conditions ( 3) and ( 4) capture agent m's time-knowledge, namely, the assumption that m has complete information about the current time.

The sublanguage L 0 (ATM ) is interpreted w.r.t. states as follows:

Definition 2 (Satisfaction) Let S = (B, V ) ∈ S. Then: S |= x ⇐⇒ x ∈ V , S |= ¬α ⇐⇒ S |= α, S |= α 1 ∧ α 2 ⇐⇒ S |= α 1 and S |= α 2 , S |= m α ⇐⇒ α ∈ B.
Observe in particular the set-theoretic interpretation of the explicit belief operator for agent m: agent m actually has the explicit belief that α if and only if α is included in her actual belief base. This highlights the asymmetry between agent m and agent h in our semantics. We adopt agent m's internal perspective, that is, the point of view of its belief base. 3 On the contrary, agent h's explicit beliefs are modeled from an external point of view and semantically interpreted in the same way as the other timed formulas in L T 0 (ATM ). A multi-agent belief model (MAB) is defined to be a state supplemented with a set of states, called context. The latter includes all states that are compatible with agent m's background knowledge.

Definition 3 (Model)

A model is a pair (S, Cxt), where S ∈ S and Cxt ⊆ S. The class of all models is denoted by M.

Note that we do not impose that S ∈ Cxt. When Cxt = S then (S, Cxt) is said to be complete, since S is conceivable as the complete (or universal) context which contains all possible states. Definition 4 (Epistemic alternatives) We define R to be the binary relation on the set S such that, for all S = (B, V ), S = (B , V ) ∈ S:

SRS if and only if ∀α ∈ B : S |= α.
SRS means that S is an epistemic alternative for the artificial agent m at S. So m's set of epistemic alternatives at S, noted R(S) = {S ∈ S : SRS }, includes exactly those states that satisfy m's explicit beliefs.

Definition 5 extends Definition 2 to the full language L. Its formulas are interpreted with respect to models. We omit Boolean cases that are defined in the usual way.

Definition 5 (Satisfaction, cont.) Let (S, Cxt) ∈ M. Then:

(S, Cxt) |= α ⇐⇒ S |= α; (S, Cxt) |= m ϕ ⇐⇒ ∀S ∈ Cxt, if SRS then (S , Cxt) |= ϕ. A formula ϕ ∈ L is valid in the class M, noted |= M ϕ, if and only if (S, Cxt) |= ϕ for every (S, Cxt) ∈ M; it is satisfiable in M if and only if ¬ϕ is not valid in M.
As the following theorem indicates, the satisfiability problem for L(ATM ) has the same complexity as SAT.

Theorem 1 Checking satisfiability of L(ATM ) formulas in the class M is an NP-complete problem.

Sketch of Proof.

Hardness is clear since L(ATM ) extends the propositional logic language. As for membership, we can find a polysize satisfiability preserving translation from L(ATM ) to propositional logic. The translation is divided in three steps. First, we transform the input formula in L(ATM ) into negated normal form (NNF). Secondly, we translate the formula in NNF into a restricted mono-modal language with no nesting of the modal operator. Thirdly, we translate the latter into a propositional logic language in a way similar to the standard translation of modal logic into FOL. We take care of translating a finite theory including axioms corresponding to the four constraints of Definition 1. The axioms have the following form: now ≥0 , now ≥t → now ≥t for t ≤ t, now ≥t ↔ m now ≥t and ¬now ≥t ↔ m ¬now ≥t . The theory is finite since we only need to consider instances of the axioms whose symbols occur in the input formula. For example, if t ≤ t and both now ≥t and now ≥t occur in the input formula, then now ≥t → now ≥t should be included in the theory, otherwise not.

Dynamic extension

Let us now move from a static to a dynamic perspective by presenting a extension of the language L(ATM ) with belief expansion operators. Specifically, we introduce the following language L + (ATM ):

ϕ::=α | ¬ϕ | ϕ 1 ∧ ϕ 2 | m α | [+ t m α]ϕ,
where α ranges over L 0 and t ranges over N. The formula [+ t m α]ϕ is read "ϕ holds after agent m has privately learnt that α and that the current time is at least t" or simply "ϕ holds after agent m has privately learnt that α at time at least t".

Our extension has the following semantics relative to a model:

Definition 6 (Satisfaction relation, cont.) Let S = (B, V ) ∈ S and (S, Cxt) ∈ M. Then, (S, Cxt) |= [+ t m α]ϕ ⇐⇒ (S + t m α , Cxt) |= ϕ with S + t m α = (B + t m α , V + t m α ), V + t m α = V ∪ {now ≥t : t ≤ t}, B + t m α = B ∪ {α} ∪ {now ≥t : t ≤ t}.
Intuitively speaking, agent m's private learning that α at time at least t simply consists in (i) adding the information α to m's belief base, and (ii) moving the objective time and m's subjective view of time to index t.

As the following proposition indicates, the dynamic semantics given in Definition 6 is well-defined, as it guarantees that the structure resulting from a belief expansion operation belongs to the class M, if the initial structure also belongs to M.

Proposition 1 Let (S, Cxt) ∈ M. Then, (S + t m α , Cxt) ∈ M.
Interestingly, adding belief expansion operators to the language L does not increase the complexity of the corresponding satisfiability problem.

Theorem 2 Checking satisfiability of L + (ATM ) formulas in the class M is an NP-complete problem.

Sketch of Proof.

The theorem is a consequence of Theorem 1 and the fact that we can a find a polysize reduction of the satisfiability problem for L + (ATM ) to the satisfiability problem for L(ATM ). The reduction makes use of reduction axioms which allow us to eliminate dynamic operators from the input formula and to obtain a logically equivalent formula in L(ATM ).

Let EVT = {+ t m α : α ∈ L 0 , t ∈ N} be the set of belief expansion events. It is reasonable to assume that such events have executability preconditions that are specified by the following function P : EVT -→ L(ATM ). So, we can define the following operator of successful occurrence of an event in EVT :

+ t m α ϕ def = P(+ t m α) ∧ [+ t m α]ϕ.
The formula + t m α ϕ has to be read "agent m can privately learn that α at time t and ϕ holds after the occurrence of this learning event".

In the next section, we will provide a formalization of the Yōkai board-game with the aid of the language L + (ATM ). We will represent agent m's actions in the game as events in EVT affecting m's beliefs. For every action of m, we will specify the corresponding executability precondition.

Game modeling

In this section, we first formalize all the static aspects of the game (the different rules, the initial state of the game, etc.) and then the aspects related to players actions. Finally, we briefly present some aspects that our language offers for planning.

Static aspects

Let be the following sets:

GRID = {1, . . . , 32} × {1, . . . , 32}, IPOS = (l, c) ∈ GRID : l, c ∈ {15, ..., 18} , COLORS = {r, g, b, y}, HINTS = 2 COLORS \ {}, {r, g, b, y} , AvHINTS ⊆ HINTS s.t.          |AvHINTS | = 7, ∃h 1 , h 2 ∈ AvHINTS : |h 1 | = |h 2 | = 1, ∃h 1 , h 2 , h 3 ∈ AvHINTS : |h 1 | = |h 2 | = |h 3 | = 2, ∃h 1 , h 2 ∈ AvHINTS : |h 1 | = |h 2 | = 3, CARDS = {1, . . . , 16} and we note CARDS 4 = {X ∈ 2 CARDS : |X| = 4}
There are seven hints at the start of the game, and each player must take turns activating a hint or using a hint to mark a card. Thus, each player plays 7 times. As each player must take 4 different actions in turn, the game lasts a maximum of (7 × 4) × 2 = 56 time units (56 actions are executed during a game). Let N be the set of time points, including initial state of the game at time 0 (and excluding it for N * ). End of the game is marked by the natural end ∈ N such that end = 56.

However, each player only performs the action of moving a card once among the 4 actions she/it must perform during her/its turn. There are therefore a total of 7 × 2 = 14 card moves. As in the initial state the 16 cards are placed in a square of 4 × 4 cards, whatever the movements made during a game, the cards will evolve in a grid of 32 × 32 positions represented by the set GRID, and IPOS represents the set of cards positions at the start of the game.

A hint is viewed as a subset of 1, 2 or 3 colors among 4 different colors (r for red, g for green, b for blue and y for yellow). HINTS is the set of all hints and |HINTS | = 14. When the game starts, only 7 hints are available for the game (represented by set AvHINTS ).

Vocabulary. We use the following notations: we denote a card by x ∈ CARDS , a color by c ∈ COLORS , a position by p ∈ GRID, a hint by h ∈ HINTS or h ∈ AvHINTS . Moreover, based on the sets defined above, we define the following set atomic propositions q t (for q ∈ ATM , t ∈ N) such that: Moreover, we define a function σ : CARDS -→ IPOS that assigns to each card x a position p in the initial positions set, and a function NEIG : GRID -→ 2 GRID that assigns to each position (l, c) the set of its neighboring positions in the grid NEIG(l, c) = {(l + 1, c), (l -1, c), (l, c + 1), (l, c -1)} ∩ GRID.

• col t x
In the following, we consider that belief bases of agents are divided into two (sub)bases: the core beliefs base (containing all the beliefs that cannot be modified during the game), and the volatile beliefs base (containing all the belief that may change). As we want to model the game from m's perspective, we only model its beliefs about the facts of the game or about the beliefs of agent h.

Initial volatile beliefs of agent m.

Volatile belief base of agent m includes the fact that initial time is at least 0, each card position is known (we assume that function σ is known), the cards color is not known, only seven hints are available, none is activated yet, and none marks a card yet. Moreover, all adjacent positions of each cell are known:

Σ v ⊇ now ≥0 , x∈CARDS pos 0 x,σ(x) , x∈CARDS c∈COLORS ¬ m col 0 x,c h∈AvHINTS avail 0 h , h∈HINTS \AvHINTS ¬avail 0 h , h∈HINTS ¬active 0 h , x∈CARDS h∈HINTS ¬mark 0 x,h , p∈GRID p ∈NEIG(p) neighbors 0 p,p , p∈GRID p ∈GRID\NEIG(p) ¬neighbors 0 p,p ,
In addition, we assume that Σ v also includes 0 h now ≥0 and, for each of facts above of the form X α, a formula of the form X 0 h α. (Agent m believes that the initial state of the game is also known by agent h.)

Initial core beliefs of agent m. Core belief base includes all the agent m's beliefs that cannot change during the game. It concerns both integrity constraints (that describe rules of the game) and successor state axioms (SSAs) that describe the building of the belief base after the execution of an action.

¬(active t h ∧ mark t x,h ) ∧ ¬(avail t h ∧ mark t x,h ) (ICH10)
ICP1 and ICP2 mean that each card has at least one, and at most one, position respectively ; ICP3 means that each position can only accommodate one card.

In the same way, ICC4 and ICC5 means that each card has at least one, and at most one, color respectively. ICC6 means (together with ICC5) that there are 4 cards of each color. ICH7 means a hint cannot marks two different cards. ICH8 means each hint must be either available, or activated, or marking a card. ICH9 and ICH10 mean that the state of a hint is unique: it is either available, activated, or marking.

Frame axioms (FA) describe the facts that does not change after the execution of an action. For convenience, we define the following FA abbreviations (for every C ⊆ COLORS , X ⊆ CARDS , H ⊆ HINTS , P ⊆ GRID, and t ∈ N * ):

posFA t X def = x∈CARDS \X p∈GRID (pos t x,p ↔ pos t-1 x,p ) colFA t X def = x∈CARDS \X c∈COLORS (col t x,c ↔ col t-1 x,c ) ∧ (¬ m col t x,c ↔ ¬ m col t-1 x,c ) hintFA t H def = h∈HINTS \H (avail t h ↔ avail t-1 h ) ∧ (active t h ↔ active t-1 h ) ∧ x∈CARDS h∈HINTS \H (mark t x,h ↔ mark x,h )
posFA t X P (resp. colFA t X C) reads "the position (resp. color) of every cards except those in X is preserved from time t -1 to t". hintFA t X H reads "the status (available, active, or marking) of every hints except those in H is preserved from time t -1 to t".

Finally, we define the following successor state axioms (for every t ∈ N, t ∈ N * ):

(col t x,c ∧ ¬ m col t -1 x,c → posFA t ∅ ∧ colFA t {x} ∧ hintFA t ∅ ) , (SSA13) h∈HINTS (active t h ∧ ¬active t -1 h → posFA t ∅ ∧ colFA t ∅ ∧ hintFA t {h} ) , (SSA14) x∈CARDS h∈HINTS (mark t x,h ∧ ¬mark t -1 x,h → posFA t ∅ ∧ colFA t ∅ ∧ hintFA t {h} ) , (SSA15)
SSA11 means that every neighboring positions of a position p never change.

(Note it is a pure frame axiom because neighboring positions are never affected by any actions.) SSA12 means that if card x has a new position p at time t , the position of others cards, the color of every cards, and the status of all hints, remain unchanged from t -1 to t . SSA13 means that if card x has a new color c at time t , the position of every cards, the color of every other cards, and the status of all hints, remain unchanged from t -1 to t . SSA14 and SSA15 mean that if a hint becomes active (resp. marks a card) between time t -1 and t then neither positions and colors of cards did change nor the status of other hints. Moreover, we assume that at least one action is performed at each time point. Formally, this is represented by the disjunction of antecedents of SSA12 to SSA15. Finally, we suppose that agent m believes that all the fact in its core belief base are also known by the other agent h.

Dynamic aspects

Vocabulary. For convenience, we define the action set ACT ⊆ EVT of agent m (for every t < end , x ∈ CARDS , p ∈ GRID, h ∈ HINTS ):

+ col t+1 x,c m def = + t+1 m col t+1 x,c ∧ ( t+1 h c ∈COLORS m col t+1 x,c ) ∧ t+1 h now ≥t+1 + pos t+1 x,p m def = + t+1 m (pos t+1 x,p ∧ t+1 h pos t+1 x,p ∧ t+1 h now ≥t+1 ) + actHint t+1 h m def = + t+1 m (active t+1 h ∧ t+1 h active t+1 h ∧ t+1 h now ≥t+1 ) + markHint t+1 x,h m def = + t+1 m (mark t+1 x,h ∧ t+1 h mark t+1 x,h ∧ t+1 h now ≥t+1 )
As each action entails a new time point, each action execution entails the fact that the agent learns not only that time increases (which is taken into account directly in the semantics, see Definition 1), but also that time increases for agent h (so, t+1 h now ≥t+1 must be added to m's belief base). Finally, each action about a fact also informs agent m that h believes this fact.

The separation constraint. When moving a card from a position p to a position p , it is forbidden to create two separate groups of cards (see Figure 1b). In other words, there must be a path between a given card x and all the other cards y, which automatically ensures that there is a path between any two different cards y and y of the game. So, for every p, p ∈ GRID : p = p , t ∈ N, and S ⊆ GRID : p, p ∈ S:

linked t p,p ,S def =   1≤i≤|S| path t (p,p ),p ,i   ∧ p ∈S\NEIG(p) ¬path t (p,p ),p ,1 ∧ 2≤i≤|S| p ∈S   path t (p,p ),p ,i → p ∈NEIG(p ) path t (p,p ),p ,i-1  
that reads: "there is a path in S from position p to position p iff: (1) p is reachable in at most |S| steps, (2) no position which is not a neighbor of p in S is reachable from p in 1 step, (3) any position p in the path is reachable from p within i steps only if there is at least a neighbor p of p in S which is reachable in i -1 steps."

Finally, for t ∈ N, p ∈ GRID, x ∈ CARDS : emp t p reads "the position p is empty"; OPOS t is the set of positions occupied by a card at time t; legMov t x,p reads "the move of card x towards position p at time t is authorized by the rules of the game iff p is currently an empty position and there is a sequence of adjacent positions between p and any other occupied positions (except the initial position p of card x) through the set of currently occupied positions (excluding p ).

emp t p def = x∈CARDS ¬pos t x,p OPOS t =
Action preconditions. We assume now that the operators in ACT have the following executability preconditions, for t ∈ N such that t < end , x ∈ CARDS , c ∈ COLORS , h ∈ AvHINTS and now t m def = m now ≥t ∧ ¬ m now ≥t+1 :

P(+ col t+1 x,c m ) def = now t m ∧ m h∈HINTS ¬mark t x,h P(+ pos t+1 x,p m ) def = now t m ∧ m h∈HINTS ¬mark t x,h ∧ m legMov t x,p P(+ actHint t+1 h m ) def = now t m ∧ m avail t h P(+ markHint t+1 x,h m ) def = now t m ∧ m active t h ∧ m c∈h col t x,c ∧ m h ∈HINTS h =h ¬mark t x,h P(+ col t+1
x,c m ) reads "agent m implicitly believes that time is currently equal to t and also implicitly believes that no hint marks card x"; P(+ pos t+1

x,p m ) reads "agent m implicitly believes that time is currently equal to t and also implicitly believes ) reads "agent m implicitly believes that time is currently equal to t and also implicitly believes that hint h is currently available"; P(+ markHint t+1

x,h m ) reads "agent m implicitly believes that time is currently equal to t, that hint h is currently active, that h includes the colors of card x, and that no other hint h already marks card x".

Planning a game round for the artificial agent

At each round of m at time t we consider a planning task which consists in finding a sequence of four relevant actions from ACT to achieve a goal α G . The initial belief state of agent m is given by its core beliefs Σ c and an expansion of its volatile beliefs Σ v after the execution of the actions of the last round of agent h. The construction of the goal α G as a conjunction of subgoals is driven by a game strategy. For example, a strategy could provide a subgoal α G1 which is intended to maximize the number of cards with a neighbor of the same color. α G1 states that, from the point of view of m, there is a card x whose color is known and having no neighbors of the same color, and there exists another card x of the same color as x such that card x was moved to a previously unoccupied neighboring position at the end of the round:

αG 1 = x∈CARDS c∈COLORS p∈OPOS t pos t x,p ∧ col t x,c ∧ x ∈CARDS \{x} p ∈NEIG(p) pos t x ,p → ¬col t x ,c ∨ ¬ m col t x ,c ∧ x ∈CARDS \{x} p ∈OPOS t p ∈NEIG(p )\OPOS t pos t x ,p ∧ col t x ,c ∧ pos t+4
x,p Figure 2 shows an example of game states at the beginning of a round of m.

On this example, we consider that agent m knows that card 7 is green, and that h knows that m knows the color of this card:

Σ v ⊇ {col t 7,g , t h c∈COLORS m col t 7,c }.
At previous round, h just looked at cards 2 and 7, and then moved card 2 near card 7 and marked card 2 with the hint {b, g}. This leads to an expansion of Σ v : where p ∈ NEIG [START_REF] Bolander | Announcements to attentive agents[END_REF] or p ∈ NEIG(2)) which are better choices than moving card 7 near card 13 avoided by the latter implicit belief.

Σ v ⊇ { c∈COLORS t h col t 2,

Conclusion

We have introduced a simple epistemic language for representing an artificial player's knowledge and actions in the context of the cooperative board-game Yōkai. We have shown that this game requires a combination of Theory of Mind (ToM), temporal and spatial reasoning to be played effectively by the artificial agent. Our approach relies on SAT given the existence of a polysize satisfiability preserving translation of the epistemic language into propositional logic.

Future work will be organized in two steps. First, we intend to specify a belief revision module for the artificial player which spells out how it should change its beliefs after the human player's moves. Secondly, we plan to implement an artificial player based on our formalization and to use existing SAT solvers for automating the reasoning and planning for the artificial player during the game play. We plan to formalize and implement a variety of game strategies for the artificial player, in line with the methodology sketched in Section 4.3, and to the test their performances experimentally.

A Detailed proof of Theorem 1

In this section, we are going to provide a polysize reduction of the satisfiability problem of L to SAT. The reduction consists of three steps.

As a first step, we put L formulas in negation normal form (NNF) via the following function nnf :

nnf (p t ) = p t , nnf (now ≥t ) = now ≥t , nnf ( t h α) = t h α, nnf ( m α) = m α, nnf ( m α) = m nnf (α), nnf (♦ m α) = ♦ m nnf (α), nnf (ϕ ∧ ψ) = nnf (ϕ) ∧ nnf (ψ), nnf (ϕ ∨ ψ) = nnf (ϕ) ∨ nnf (ψ), nnf (¬p) = ¬p, nnf (¬now ≥t ) = ¬now ≥t , nnf (¬ t h α) = ¬ t h α, nnf (¬ m ) = ¬ m α, nnf (¬¬ϕ) = nnf (ϕ), nnf ¬(ϕ ∧ ψ) = nnf (¬ϕ ∨ ¬ψ), nnf ¬(ϕ ∨ ψ) = nnf (¬ϕ ∧ ¬ψ), nnf (¬ m α) = ♦ m nnf (¬α), nnf (¬♦ m α) = m nnf (¬α).
Let us define the NNF variant L N N F 0 of the language L 0 by the following grammar:

β ::= p t | ¬p t | now ≥t | ¬now ≥t | t h α | ¬ t h α | m α | ¬ m α | β 1 ∧ β 2 | β 1 ∨ β 2
, where p t ranges over ATM , t ranges over N and α ranges over L 0 .

Furthermore, let us define the language L N N F by the following grammar. For β ranging over L N N F 0 :

ϕ ::= β | ϕ 1 ∧ ϕ 2 | ϕ 1 ∨ ϕ 2 | m β | ♦ m β. Proposition 2 Let ϕ ∈ L. Then, ϕ ↔ nnf (ϕ) is valid in the class M, and nnf (ϕ) ∈ L N N F .
Note that the size of nnf (ϕ) is polynomial in the size of ϕ.

As a second step, we define the following modal language L M od into which the language L N N F will be translated:

ω ::= q | ¬ω | ω 1 ∧ ω 2 | ω 1 ∨ ω 2 , ϕ ::= q | ¬ϕ | ϕ 1 ∧ ϕ 2 | ϕ 1 ∨ ϕ 2 | ω | ω ,
where q ranges over the following set of atomic formulas:

ATM + =ATM ∪ {p now ≥t : t ∈ N} ∪ {p m α : α ∈ L 0 }∪ {p t
h α : t ∈ N and α ∈ L 0 }. So p now ≥t , p m α and p t h α are nothing but special propositional variables. We interpret the language L M od w.r.

(M, w) |= q ⇐⇒w ∈ π(q); (M, w) |= ω ⇐⇒∀v ∈ W, if w ⇒ v then (M, v) |= ω; (M, w) |= ω ⇐⇒∃v ∈ W s.t. w ⇒ v and (M, v) |= ω.
The class of pointed Kripke models is denoted by K. Satisfiability and validity of formulas in L M od relative to the class K is defined in the usual way.

Let tr 0 : L 0 -→ L M od be a translation such that: tr 0 (p t ) = p t , tr 0 (¬α) = ¬tr 0 (α),

tr 0 (α 1 ∧ α 2 ) = tr 0 (α 1 ) ∧ tr 0 (α 2 ), tr 0 ( i α) = p i α
Let tr 1 : L N N F -→ L M od be a translation such that:

tr 1 (p t ) = p t , tr 1 (¬p t ) = ¬p t , tr 1 (now ≥t ) = p now ≥t , tr 1 (¬now ≥t ) = ¬p now ≥t , tr 1 ( t h α) = p t h α , tr 1 (¬ t h α) = ¬p t h α , tr 1 (ϕ 1 ∧ ϕ 2 ) = tr 1 (ϕ 1 ) ∧ tr 1 (ϕ 2 ), tr 1 (ϕ 1 ∨ ϕ 2 ) = tr 1 (ϕ 1 ) ∨ tr 1 (ϕ 2 ), tr 1 ( m α) = p m α ∧ tr 0 (α), tr 1 (¬ m α) = ¬p m α , tr 1 ( m β) = tr 0 (β), tr 1 (♦ m β) = tr 0 (β).
As the following theorem indicates, the polynomial translation tr 1 guarantees the transfer of satisfiability from model class M to model class K. As a last step, we provide a polysize reduction of L M od -satisfiability to SAT, where the underlying propositional logic language L P L is built from the following set of atomic propositions: ATM ++ = {q x : q ∈ ATM + and x ∈ N} ∪ {r x,y : x, y ∈ N}.

Let tr 2 : L M od × N × N -→ L P L be the following translation function: tr 2 (q, x, y) = q x , tr 2 (¬ϕ, x, y) = ¬tr 2 (ϕ, x, y), tr 2 (ϕ 1 ∧ ϕ 2 , x, y) = tr 2 (ϕ 1 , x, y) ∧ tr 2 (ϕ 2 , x, y), tr 2 (ϕ 1 ∨ ϕ 2 , x, y) = tr 2 (ϕ 1 , x, y) ∨ tr 2 (ϕ 2 , x, y), tr 2 ( ω, x, y) = 0≤z≤y r x,z → tr 2 (ω, z, y) , tr 2 ( ω, x, y) = 0≤z≤y r x,z ∧ tr 2 (ω, z, y) .

Translation tr 2 is similar to the translation of modal logic S5 into propositional logic given in [START_REF] Caridroit | A sat-based approach for solving the modal logic s5-satisfiability problem[END_REF] and, more generally, to the standard translation of modal logic into FOL in which accessibility relations are encoded by special predicates.

The size of an L M od formula, size(ϕ), is defined by: Note that the size of tr 2 ϕ, 0, size(ϕ) is polynomial in the size of ϕ.

Theorem 4 Let ϕ ∈ L M od . Then, ϕ is satisfiable in the class K if and only if tr 2 ϕ, 0, size(ϕ) is satisfiable in propositional logic.

Note that the size of tr 2 ϕ, 0, size(ϕ) is polynomial in the size of ϕ. Therefore, Theorem 1 follows from Proposition 2, Theorem 3 and Theorem 4.

B Detailed proof of Theorem 2

The following equivalences are valid in the class M: Thanks to these equivalences we can define the following reduction red transforming every L + formula ϕ into an equivalent L formula red (ϕ):

[+ t m α]α ↔      , if α = m α
red (p t ) = p t , red ( t h α) = t h α, red ( m α) = m α,

Figure 1 :

 1 Figure 1: Examples of game configuration

Figure 2 :

 2 Figure 2: Example of game states

  t. a pair (M, w), called pointed Kripke model, where M = (W, ⇒, π), W is a set of worlds, ⇒ ⊆ W × W and π : ATM + -→ 2 W . (Boolean cases are again omitted as they are defined in the usual way.) Definition 7 The semantic interpretation for formulas in L M od w.r.t. a pointed Kripke model (M, w) is as follows:

Theorem 3

 3 Let ϕ ∈ L N N F . Then, ϕ is satisfiable in the class M if and only if α∈Γϕ tr 1 (α) ∧ tr 1 (ϕ) is satisfiable in the class K, where Γ ϕ is defined as follows:Γ ϕ ={now ≥0 } ∪ {now ≥t → now ≥t : t ≤ t and now ≥t , now ≥t ∈ SF (ϕ)}∪{now ≥t ↔ m now ≥t : now ≥t ∈ SF (ϕ)}∪ {¬now ≥t ↔ m ¬now ≥t : now ≥t ∈ SF (ϕ)},and SF (ϕ) is the set of subformulas of ϕ which is inductively defined as follows:SF (p t ) = {p t }, SF (¬p t ) = {p t } ∪ SF (p t ), SF (now ≥t ) = {now ≥t }, SF (¬now ≥t ) = {¬now ≥t } ∪ SF (now ≥t ), SF ( t h α) = { t h α} ∪ SF (α), SF (¬ t h α) = {¬ t h α} ∪ SF ( t h α), SF ( m α) = { m α} ∪ SF (α), SF (¬ m α) = {¬ m α} ∪ SF ( m α), SF (ϕ 1 ∧ ϕ 2 ) = {ϕ 1 ∧ ϕ 2 } ∪ SF (ϕ 1 ) ∪ SF (ϕ 2 ), SF (ϕ 1 ∨ ϕ 2 ) = {ϕ 1 ∨ ϕ 2 } ∪ SF (ϕ 1 ) ∪ SF (ϕ 2 ), SF ( m β) = { m β} ∪ SF (β), SF (♦ m β) = {♦ m β} ∪ SF (β).

size(p t ) = 1 ,

 1 size(ϕ 1 ∧ ϕ 2 ) = size(ϕ 1 ) + size(ϕ 2 ) + 1, size(ϕ 1 ∨ ϕ 2 ) = size(ϕ 1 ) + size(ϕ 2 ) + 1, size(¬ϕ) = size(ϕ) + 1, size( ω) = size( ω) = size(ω) + 1.

,Proposition 3

 3 red (¬ϕ) = ¬red (ϕ), red (ϕ 1 ∧ ϕ 2 ) = red (ϕ 1 ) ∧ red (ϕ 2 ), red (ϕ 1 ∨ ϕ 2 ) = red (ϕ 1 ) ∨ red (ϕ 2 ), red ( m ϕ) = m red (ϕ), red (♦ m ϕ) = ♦ m red (ϕ), red ([+ t m α]α ) = if α = m α or (α = now ≥t and t ≤ t) or (α = m now ≥t and t ≤ t), red (α ), otherwise; red ([+ t m α]¬ϕ) = red (¬[+ t m α]ϕ), red [+ t m α](ϕ 1 ∧ ϕ 2 ) = red ([+ t m α]ϕ 1 ∧ [+ t m α]ϕ 2 ), red [+ t m α](ϕ 1 ∨ ϕ 2 ) = red ([+ t m α]ϕ 1 ∨ [+ t m α]ϕ 2 ), red ([+ t m α] m α ) = red m (α ∧ t ≤t now ≥t ) → α ; red ([+ t m α]♦ m α ) = red ♦ m (α ∧ t ≤t now ≥t ) ∧ α . Let ϕ ∈ L + .Then, ϕ ↔ red (ϕ) is valid in the class M, and red (ϕ) ∈ L.

  ,c : card x is of color c at time t;

	• pos t x,p : card x is at position p at time t;
	• avail t h : hint h is available at time t;
	• active t

h : hint h is activated at time t; • mark t x,h : card x is marked with hint h at time t; • neighbors t p,p : p and p are two adjacent positions (having one side in common) at time t.

  SSAs describe both what changes in the new state, and what do not (thanks to frame axioms). So, for every t ∈ N, t ∈ N * we define the following integrity constraints (IC):

	Σc ⊇	pos t x,p ,		(ICP1)
	x∈CARDS p∈GRID
	¬(pos t x,p ∧ pos t x,p ) ,		(ICP2)
	x∈CARDS
	p,p ∈GRID:p =p
	¬(pos t x,p ∧ pos t x ,p ) ,		(ICP3)
	p∈GRID
	x,x ∈CARDS :x =x
		col t x,c ,		(ICC4)
	x∈CARDS c∈COLORS
		¬(col t x,c ∧ col t x,c ) ,		(ICC5)
	x∈CARDS
	c,c ∈COLORS :c =c
		col t x,c ,		(ICC6)
	c∈COLORS X∈CARDS 4 x∈X
	¬(mark t x,h ∧ mark t x ,h ) ,		(ICH7)
	h∈HINTS
	x,x ∈CARDS
	x =x
	(avail t h ∨ active t h ∨	mark t x,h ) ,	(ICH8)
	h∈AvHINTS	x∈CARDS
	¬(avail t h ∧ active t h ) ,		(ICH9)
	h∈HINTS
	x∈CARDS
	h∈HINTS

  c , } given by the game strategy, m implicitly deduces that card 2 is green: Σ v |= m col t 2,g . Then, subgoal α G1 leads agent m to move card 13 near card 7 or card 2 (+

					t h col t 7,c ,
				c∈COLORS
		neighbors t 2,7 ∧ ¬neighbors t-1 2,7 , mark t 2,{b,g} ∧ ¬mark t-1 2,{b,g} }
	Hence, thanks to a rule in core beliefs Σ c ⊇ {col t 7,g ∧ t h	c∈COLORS	m col t 7,c
	∧	c∈COLORS	t h col t 2,c ∧	c∈COLORS	t h col t 7,c → col t 2,g pos t+1 13,p
						m

  or (α = now ≥t and t ≤ t) or (α = m now ≥t and t ≤ t), α , otherwise;[+ t m α]¬ϕ ↔ ¬[+ t m α]ϕ; [+ t m α](ϕ 1 ∧ ϕ 2 ) ↔ [+ t m α]ϕ 1 ∧ [+ t m α]ϕ 2 ; [+ t m α](ϕ 1 ∨ ϕ 2 ) ↔ [+ t m α]ϕ 1 ∨ [+ t m α]ϕ 2 ; [+ t m α] m α ↔ m (α ∧

t ≤t now ≥t ) → α ; [+ t m α]♦ m α ↔ ♦ m (α ∧ t ≤t now ≥t ) ∧ α .

See also[START_REF] Bolander | Seeing is believing: Formalising false-belief tasks in dynamic epistemic logic[END_REF][START_REF] Dissing | Implementing theory of mind on a robot using dynamic epistemic logic[END_REF] for a DEL-based approach to modeling and implementing ToM on social robots.

https://boardgamegeek.com/boardgame/269146/ykai

See[START_REF] Aucher | Private announcement and belief expansion: an internal perspective[END_REF] for an in-depth logical analysis of the internal perspective on modeling knowledge and belief.

Theorem 2 is a consequence of Theorem 1, Proposition 3 and the fact that the size of red (ϕ) is polynomial in the size of ϕ.


William Lafargue-Dit-Hauret

Camille Latouche

Stéphane Jobic

Ab initio prediction of the redox potentials of 3d transition metals embedded in a semiconducting host lattice

Here, we report a theoretical investigation devoted to the ab initio determination of the redox potentials E(D n+ /D n+1 ) of a dopant D in a given host lattice. The knowledge of these potentials is of capital importance to anticipate its attainable oxidation states (versus the synthesis conditions).

Hereafter the host lattice has been selected to be the well-known rutile TiO2 compound due to its interest for many applications, the simplicity of its crystal structure and the large number of already collected data. Dopants are 3d transition metals (i.e., V, Mn, Fe, Ni and Cu) substituting titanium atoms. First-principles methods combined to the SCAN functional were used to determine the electronic properties of doped materials considering the supercell approach. The stability of point defects (intrinsic and extrinsic) at different charge states are discussed based on the estimation of their defect formation enthalpies, and the associated charge transition levels are calculated and positioned in the gap of the un-doped material.

Introduction

Physical properties of a semiconducting phase can be significantly improved via the control of its intrinsic defects. Hence, the existence of donor (acceptor) levels has to be privileged at the expense of acceptor (donor) ones to favor n-typeness (p-typeness). Substitutions can also play a major role in engineering the performances of a material or to develop new functionalities. In that framework, the question to be addressed therefore concerns the dopability of the material and the achievable oxidation states of the dopant (also called impurity in the following) in our host lattice.

Hereafter, we assess the ability of DFT calculations to predict the stability of a 3d transition metal (namely, V, Mn, Fe, Ni and Cu hereafter generically named TM) used as dopant in the well-known TiO2 rutile compound.

Beyond the fact that TiO2 is environmentally friendly, this compound presents other advantages such as a high chemical stability and a low cost which strongly encourage its incorporation into daily life objects. Regarding the electronic properties, this wide band gap material belongs to the transparent semiconducting oxide's family. Point defects have already been widely investigated for the rutile TiO2 phase through experimental and theoretical studies, [START_REF] Cronemeyer | Electrical and Optical Properties of Rutile Single Crystals[END_REF][START_REF] Breckenridge | Electrical Properties of Titanium Dioxide Semiconductors[END_REF][START_REF] Cronemeyer | Infrared Absorption of Reduced Rutile TiO2 Single Crystals[END_REF][START_REF] Yahia | Dependence of the Electrical Conductivity and Thermoelectric Power of Pure and Aluminum-Doped Rutile on Equilibrium Oxygen Pressure and Temperature[END_REF][START_REF] Kobayashi | Investigation of Trapping States in a Nb-doped Rutile by Admittance Spectroscopy[END_REF][START_REF] Yagi | Electronic Conduction above 4 K of Slightly Reduced Oxygen-Deficient Rutile TiO2[END_REF][START_REF] Janotti | Hybrid Functional Studies of the Oxygen Vacancy in TiO2[END_REF][START_REF] Mattioli | Deep versus Shallow Behavior of Intrinsic Defects in Rutile and Anatase TiO2 Polymorphs[END_REF][START_REF] Morgan | Intrinsic N-Type Defect Formation in TiO2: A Comparison of Rutile and Anatase from GGA+U Calculations[END_REF][START_REF] Lee | Calculation of Point Defects in Rutile TiO2 by the Screened-Exchange Hybrid Functional[END_REF][START_REF] Bjørheim | Defect Chemistry of Rutile TiO2 from First Principles Calculations[END_REF][START_REF] Deák | Oxygen Deficiency in TiO2: Similarities and Differences between the Ti Self-Interstitial and the O Vacancy in Bulk Rutile and Anatase[END_REF][START_REF] Zainullina | Influence of Oxygen Nonstoichiometry and Doping with 2p-, 3p-, 6p-and 3d-Elements on Electronic Structure, Optical Properties and Photocatalytic Activity of Rutile and Anatase: Ab Initio Approaches[END_REF][START_REF] Zimmermann | Influence of Annealing Atmosphere on Formation of Electrically-Active Defects in Rutile TiO2[END_REF][START_REF] Han | Insights into the Characteristic Gap Level and N-Type Conductivity of Rutile TiO2 from the Hybrid Functional Method[END_REF] even if some conflicting points are still a matter of debate within the community such as the exact nature of the dominant defect or the depth of donor levels for oxygen vacancies. So far, great efforts have been devoted to take benefit of the natural properties of TiO2 and to enlarge its applications spectrum. Notably, TiO2 has been used as an host matrix for chemical doping. These intentionally introduced point defects are well-known to create local structural distortions and in-gap electronic states, [START_REF] Zunger | Electronic Structure of 3d Transition-Atom Impurities in Semiconductors[END_REF][START_REF] Kreissl | Transition-Metal Impurities in II-VI Semiconductors: Characterization and Switching of Charge States[END_REF][START_REF] Neumark | Defects in Wide Band Gap II-VI Crystals[END_REF][START_REF] Van De Walle | Defects and Impurities in Semiconductors[END_REF][START_REF] Feichtinger | Deep Centers in Semiconductors[END_REF] which may significantly modify the electronic, magnetic and/or optical properties of host materials. In the case of the TiO2 compound, the introduction of transition metal (TM) dopants has been reported to enhance photocatalytic, [START_REF] Yamashita | Characterization of Metal Ion-Implanted Titanium Oxide Photocatalysts Operating under Visible Light Irradiation[END_REF][START_REF] Kim | Photocatalytic Activity of Ni 8 Wt%-Doped TiO2 Photocatalyst Synthesized by Mechanical Alloying Under Visible Light[END_REF][START_REF] Mohamed | Adsorption and Photocatalytic Activity of Vanadium-Doped TiO2 and Sulfated TiO2 (Rutile) Catalysts: Degradation of Methylene Blue Dye[END_REF][START_REF] Zhou | Photocatalytic Decomposition of Formic Acid Under Visible Light Irradiation Over V-Ion-Implanted TiO2 Thin Film Photocatalysts Prepared on Quartz Substrate by Ionized Cluster Beam (ICB) Deposition Method[END_REF][START_REF] Zhou | Enhancement of Photocatalytic Activity of P25 TiO2 by Vanadium-Ion Implantation under Visible Light Irradiation[END_REF][START_REF] Li | Study on Activities of Vanadium (IV/V) Doped TiO2 (R) Nanorods Induced by UV and Visible Light[END_REF][START_REF] Yadav | Enhanced Photocatalytic Inactivation of Bacteria on Fe-Containing TiO2 Nanoparticles under Fluorescent Light[END_REF][START_REF] De | Temperature Dependent Optical Characterization of Ni-TiO2 Thin Films as Potential Photocatalytic Material[END_REF][START_REF] Zahid | Fabrication of Visible Light-Induced Antibacterial and Self-Cleaning Cotton Fabrics Using Manganese Doped TiO2 Nanoparticles[END_REF] electrocatalytic [START_REF] Hao | Investigation of V-Doped TiO2 as an Anodic Catalyst Support for SPE Water Electrolysis[END_REF][START_REF] Chang | Electrocatalytic Degradation of Azo Dye by Vanadium-Doped TiO2 Nanocatalyst[END_REF] or ferromagnetic [START_REF] Matsumoto | Room-Temperature Ferromagnetism in Transparent Transition Metal-Doped Titanium Dioxide[END_REF][START_REF] Wang | Ferromagnetism and Transport Properties of Fe-Doped Reduced-Rutile TiO2-δ Thin Films[END_REF][START_REF] Hong | Ferromagnetism at Room Temperature with a Large Magnetic Moment in Anatase V-Doped TiO2 Thin Films[END_REF][START_REF] Meng | Role of Oxygen Vacancies on Ferromagnetism in Fe-Doped TiO2 Thin Films[END_REF][START_REF] Park | Ferromagnetic Properties of Ni-Doped Rutile TiO2-δ[END_REF][START_REF] Tian | Effect of Annealing Conditions on the Magnetism of Vanadium-Doped TiO2 Powders[END_REF][START_REF] Grau-Crespo | The Interplay between Dopants and Oxygen Vacancies in the Magnetism of V-Doped TiO2[END_REF][START_REF] Navarro | Study of the Relation between Oxygen Vacancies and Ferromagnetism in Fe-Doped TiO2 Nano-Powders[END_REF][START_REF] Parveen | Room-Temperature Ferromagnetism in Ni-Doped TiO2 Diluted Magnetic Semiconductor Thin Films[END_REF][START_REF] Xia | Effect of Fe Doping and O Vacancies on the Magnetic Properties of Rutile TiO2[END_REF] properties, but also to alter the irreversible anatase-torutile phase transition. [START_REF] Hanaor | Review of the Anatase to Rutile Phase Transformation[END_REF] It remains evident that properties strongly depend on the electronic configuration of impurities, which is usually discussed through their oxidation state. If the targeted properties (magnetism for instance) are directly related to the electronic configuration of TM, the knowledge of the stability domain of a dopant species in a given charged state is capital. It is thus crucial to determine the redox stability domain of a dopant embedded in a given host lattice versus its charge state. In some aspects, one can make a parallel with the pKa of an acid/base couple that provides information on the acid (base) and conjugate base (acid) species concentrations in solution at a given pH. Determination of the redox potential E(D n+ /D n+1 ) associated to a transition frontier (or level) between a dopant 𝐷 with the charge states 𝑛 + and 𝑛 + 1 opens up the door to anticipate the observed oxidation state of the dopant for a given external potential, or more commonly, a given electronic potential 𝜇 𝐸 𝐹 . More specifically, this potential corresponds to the electrons' electrochemical potential at which the oxidized and reduced species coexist in identical concentrations. When the measured potential leaves the equilibrium point, the expected population of each species drastically evolves according to a Boltzmann distribution. Hereafter, the electronic potential 𝜇 𝐸 𝐹 value at which the concentrations of two charge states 𝑞 and 𝑞′ of the same point defect are equilibrated is called transition level 𝜖(𝑞/𝑞′) (with 𝑞′ possibly different from 𝑞 + 1 or 𝑞 -1). The knowledge of these points is of particular interest for experimentalists who would be able to orientate syntheses to favor specific charge states of defects in a given host structure to achieve the desired properties.

Mizushima et al. [START_REF] Mizushima | Photoconductivity Spectra of Fe-Doped TiO2[END_REF][START_REF] Mizushima | Energy Levels of Iron Group Impurities in TiO2[END_REF][START_REF] Mizushima | One Electron Energy Levels of Iron Group Impurities in TiO2[END_REF] firstly reported combined experimental and theoretical systematic investigation of transition levels for TM impurities in rutile TiO2. Experimentally, oxygen content in synthesis atmosphere and lithium interstitials have been used to tune the position of 𝜇 𝐸 𝐹 and approach the stability domains of charged defects. By the use of a semi-empirical procedure [START_REF] Allen | Proceeding 7th Int. Conf Semicond[END_REF] , transition level positions were estimated for different oxidation states of several TMs. These studies have been completed by photocurrent and ESR measurements few years later [START_REF] Mizushima | Impurity Levels of Iron-Group Ions in TiO2 (II)[END_REF] . Surprisingly, to our knowledge, only few other experimental studies have been reported on systematic characterization of TM doping in this material. [START_REF] Mo | Electron States of Iron Group Impurities in Doped Rutile (TiO2)[END_REF][START_REF] Sangaletti | Ferromagnetism on a Paramagnetic Host Background: The Case of Rutile TM:TiO2 Single Crystals (TM = Cr, Mn, Fe, Co, Ni, Cu)[END_REF][START_REF] Matsumoto | Chemical Trend of Fermi-Level Shift in Transition Metal-Doped TiO2 Films[END_REF][START_REF] Yamaka | Paramagnetic Resonance of Iron Group Elements in Rutile. I. The Ti 47 and Ti 49 Hfs Interaction[END_REF][START_REF] Kernazhitsky | A Comparative Study of Optical Absorption and Photocatalytic Properties of Nanocrystalline Single-Phase Anatase and Rutile TiO2 Doped with Transition Metal Cations[END_REF] In parallel, plenty of first-principles insights have been collected on doped rutile TiO2. Formation energies and charge transition levels of intrinsic defects have been carefully detailed through the use of density functional theory. [START_REF] Janotti | Hybrid Functional Studies of the Oxygen Vacancy in TiO2[END_REF][START_REF] Mattioli | Deep versus Shallow Behavior of Intrinsic Defects in Rutile and Anatase TiO2 Polymorphs[END_REF][START_REF] Morgan | Intrinsic N-Type Defect Formation in TiO2: A Comparison of Rutile and Anatase from GGA+U Calculations[END_REF][START_REF] Lee | Calculation of Point Defects in Rutile TiO2 by the Screened-Exchange Hybrid Functional[END_REF][START_REF] Bjørheim | Defect Chemistry of Rutile TiO2 from First Principles Calculations[END_REF][START_REF] Park | Electronic Correlation Effects in Reduced Rutile TiO2 within the LDA+U Method[END_REF][START_REF] Han | Insights into the Characteristic Gap Level and N-Type Conductivity of Rutile TiO2 from the Hybrid Functional Method[END_REF] However, authors often did not consider extrinsic dopants. Regarding the impurities, most of articles report energy level positions determined through the analysis of densities of states. [START_REF] Zainullina | Influence of Oxygen Nonstoichiometry and Doping with 2p-, 3p-, 6p-and 3d-Elements on Electronic Structure, Optical Properties and Photocatalytic Activity of Rutile and Anatase: Ab Initio Approaches[END_REF][START_REF] Umebayashi | Analysis of Electronic Structures of 3d Transition Metal-Doped TiO2 Based on Band Calculations[END_REF][START_REF] Saini | Ab Initio Study of 3d Transition Metal-Doping Effects in Rutile-TiO2: Role of Bandgap Tunability in Conductivity Behaviour[END_REF][START_REF] Roy | Enhanced Stability and Ferromagnetic Property in Transition Metals Co-Doped Rutile TiO2[END_REF] If few studies have been devoted to the determination of the formation energies associated to the substitution of TM dopants for Ti, different approaches have been used which make their comparison delicate. Herein, we propose to fill this lake by investigating intrinsic defects but also substituting elements as vanadium, manganese, iron, nickel and copper at Ti site. Also, we take benefit of this study to explore defects properties with the fashionable meta-GGA SCAN functional. [START_REF] Sun | Strongly Constrained and Appropriately Normed Semilocal Density Functional[END_REF] If the energy levels of oxygen vacancies have already been studied through densities of states, [START_REF] Zhang | Subtlety of TiO2 Phase Stability: Reliability of the Density Functional Theory Predictions and Persistence of the Self-Interaction Error[END_REF] defect formation energies or charge transition levels have never been reported before.

Methods

Point defects notation

In the current paper, point defects are represented by the 𝐴 𝑋 𝑐 notation where 𝐴 refers to the substituting species (𝑉 in case of vacancy), 𝑋 to the substituted element in the ideal structure (𝑖 in case of an empty interstitial site) and 𝑐 the relative charge state compared to the regular charge of 𝑋. To avoid any confusion between vacancy and vanadium, the chemical symbol of the vanadium element 𝑉 will be arbitrarily written 𝑉𝑎 except when the context precludes any ambiguity.

ab initio calculations

We performed first-principles calculations using the Density Functional Theory (DFT) within the projector augmented wave (PAW) approach, as implemented within the VASP software. [START_REF] Kresse | Efficiency of Ab-Initio Total Energy Calculations for Metals and Semiconductors Using a Plane-Wave Basis Set[END_REF][START_REF] Kresse | Efficient Iterative Schemes for Ab Initio Total-Energy Calculations Using a Plane-Wave Basis Set[END_REF][START_REF] Kresse | From Ultrasoft Pseudopotentials to the Projector Augmented-Wave Method[END_REF] In this study, the expansion of the plane wave basis set is fixed by a cutoff energy of 500 eV, and the meta-GGA SCAN [START_REF] Sun | Strongly Constrained and Appropriately Normed Semilocal Density Functional[END_REF] exchange-correlation functional was used. Full geometry relaxations were performed on the rutile TiO2 unitcell until forces are less than 0.01 eV/Å. 7×7×11 and 9×9×13 Γ-centered 𝑘-points meshes were considered to sample the first Brillouin zone for the geometry relaxations and accurate energy calculations on the unit cell, respectively. A more accurate band gap was determined using the screened hybrid functional HSE06 62 on top of the fully relaxed SCAN structure.

For the sake of comparison, we also performed a full geometry relaxation and band gap calculation with other approaches such as PBE, [START_REF] Perdew | Generalized Gradient Approximation Made Simple[END_REF] PBE+U with 𝑈 𝑒𝑓𝑓 = 4.2 eV, [START_REF] Morgan | Intrinsic N-Type Defect Formation in TiO2: A Comparison of Rutile and Anatase from GGA+U Calculations[END_REF] PBEsol 64 and HSE06. [START_REF] Krukau | Influence of the Exchange Screening Parameter on the Performance of Screened Hybrid Functionals[END_REF] [START_REF] Burdett | Structural-Electronic Relationships in Inorganic Solids: Powder Neutron Diffraction Studies of the Rutile and Anatase Polymorphs of Titanium Dioxide at 15 and 295 K[END_REF] In the following, all calculations are carried out with the SCAN functional.

HSE06@SCAN calculations were used to get a corrected value of the bandgap which is required to accurately study the material's defects.

Defect formation enthalpies (DFEs) were calculated within the supercell approach. A 2×2×4 supercell containing 96 atoms was constructed. Atomic positions were relaxed in faulted structures until forces acting on ions are less than 0.02 eV/Å. We performed the structural optimizations and accurate energy calculations using 4×4×3 and 5×5×4 Γ-centered 𝑘-points meshes, respectively.

The supercell is supposed to be large enough that the insertion of a point defect does not induce (or marginally) any change in the cell volume. In such a situation, DFEs were calculated considering the following formula:

𝛥 𝑓 𝐻 𝐷,𝑞 (𝜇 𝐸 𝐹 ) = 𝐸 𝑡𝑜𝑡 𝐷,𝑞 -𝐸 𝑡𝑜𝑡 ℎ𝑜𝑠𝑡 + ∑ 𝑛 𝑖 𝜇 𝑖 𝑖 + 𝑞(𝐸 𝑉𝐵𝑀 ℎ𝑜𝑠𝑡 + 𝜇 𝐸 𝐹 ) + 𝐸 𝑐𝑜𝑟𝑟 (𝐷, 𝑞)
where 𝛥 𝑓 𝐻 𝐷,𝑞 is the formation enthalpy of a defect 𝐷 in a state of charge 𝑞, 𝐸 𝑡𝑜𝑡 𝐷,𝑞 is the total energy of the faulted supercell, 𝐸 𝑡𝑜𝑡 ℎ𝑜𝑠𝑡 is the total energy of the host supercell, 𝑛 𝑖 is the number of atoms of the 𝑖 𝑡ℎ species added (𝑛 𝑖 < 0) or removed (𝑛 𝑖 > 0) from the ideal probed material, 𝜇 𝑖 is the chemical potential of the 𝑖 𝑡ℎ specie, 𝜇 𝐸 𝐹 is the chemical potential of the electron reservoir and 𝐸 𝑉𝐵𝑀 ℎ𝑜𝑠𝑡 is the energy corresponding to the valence band maximum (VBM) of the host which fixes the 𝜇 𝐸 𝐹 reference. 𝐸 𝑐𝑜𝑟𝑟 corresponds to various corrections of spurious effects, such as electrostatic interactions between point defects or the potential alignment allowing to retrieve the electronic reference of the host material. More details on this term are provided in SI.

The chemical potential 𝜇 𝑖 corresponds to the atomic reservoir of the 𝑖 𝑡ℎ atomic specie during the crystal growth. Obviously, this quantity strongly depends on the synthesis conditions and drives the thermodynamic stability between the different competitive phases. For a given 𝑖 𝑡ℎ atomic species, the chemical potential 𝜇 𝑖 may be decomposed as the sum of the standard chemical potential 𝜇 𝑖 0 and the deviation 𝛥𝜇 𝑖 which depends on synthesis conditions.

The charge transition level 𝜖(𝑞/𝑞′) between two charge states 𝑞 and 𝑞′ corresponds to the 𝜇 𝐸 𝐹 level at which their respective DFEs are equivalents, i.e., the populations of both 𝑞 and 𝑞′ states are identical within the material for this specific potential. Such thermodynamic quantity is expressed as:

𝜖(𝑞/𝑞′) = 𝛥 𝑓 𝐻 𝐷,𝑞 (𝜇 𝐸 𝐹 = 0) -𝛥 𝑓 𝐻 𝐷,𝑞′ (𝜇 𝐸 𝐹 = 0) 𝑞′ -𝑞
where 𝛥 𝑓 𝐻 𝐷,𝑞 and 𝛥 𝑓 𝐻 𝐷,𝑞′ are the formation enthalpies of a defect 𝐷 in the charged states 𝑞 and 𝑞′, respectively.

Assuming all defects are formed during the synthesis process at a given temperature (𝑇 gr )

and their concentration maintained after quenching of the structure to room temperature, the concentration 𝑛 𝐷,𝑞 (𝐸 𝐹 ) of a defect 𝐷 in a charge state 𝑞 can be determined for a given Fermi level 𝐸 𝐹 (i.e., a given temperature T since 𝐸 𝐹 depends on 𝑇) through a Fermi-Dirac distribution commonly approximated by a Boltzmann one of the 𝑁 available sites per volume unit:

𝑛 𝐷,𝑞 (𝐸 𝐹 ) = 𝑁 ⋅ 𝑒𝑥𝑝 (- 𝛥 𝑓 𝐻 𝐷,𝑞 (𝐸 𝐹 ) 𝑘 𝐵 𝑇 )
In that context, the Fermi level is determined by solving iteratively the charge neutrality equation:

-𝑛 𝑒 (𝐸 𝐹 ) + 𝑛 ℎ (𝐸 𝐹 ) + ∑ ∑ 𝑞 𝑖 ⋅ 𝑛 𝐷,𝑞 𝑖 (𝐸 𝐹 )

𝑞 𝑖 ∈𝑞 𝐷 𝐷 = 0 with 𝑛 𝑒 (𝐸 𝐹 ) and 𝑛 ℎ (𝐸 𝐹 ) the concentrations of free electrons in the conduction band and holes in the valence band at 𝑇, respectively. Such quantities are determined through:

𝑛 𝑒 (𝐸 𝐹 ) = ∫ 𝑔 𝑒 (𝐸)𝑓 𝐹𝐷 (𝐸 -𝐸 𝐹 )𝑑𝐸 +∞ 𝐸 𝐶 and 𝑛 ℎ (𝐸 𝐹 ) = ∫ 𝑔 ℎ (𝐸)(1 -𝑓 𝐷𝐹 (𝐸 -𝐸 𝐹 ))𝑑𝐸 𝐸 𝑉 -∞
where 𝑓 𝐹𝐷 (𝐸 -𝐸 𝐹 ) corresponds to the Fermi-Dirac function:

𝑓 𝐹𝐷 (𝐸 -𝐸 𝐹 ) = 1 1 + 𝑒𝑥𝑝 ( 𝐸 -𝐸 𝐹 𝑘 𝐵 𝑇 )
and 𝑔 𝑒 (𝐸) and 𝑔 ℎ (𝐸) are the 3D density of states of electrons and holes, respectively:

𝑔 𝑒,ℎ (𝐸) = 1 4𝜋 2 ( 2𝑚 𝑒,ℎ * ℏ 2 ) 3 2

√𝐸

where 𝑚 𝑒 * and 𝑚 ℎ * are associated to the electron and hole effective masses, respectively.

Experimentally, the reported electron effective mass values are highly disparate, ranging from about 3, 66 10 64 to 25-30, 2,68 according to the authors. Herein, these quantities were determined from the parabolic curve fitting of the conduction band minimum (CBM) and valence band maximum (VBM). We estimated me*/m0 and mh*/m0 values at 0.68 and 2.72. Our results appear slightly larger than those obtained at the PBE level by Zhang et al. [START_REF] Zhang | New Understanding of the Difference of Photocatalytic Activity among Anatase, Rutile and Brookite TiO2[END_REF] (𝑚 𝑒 * /𝑚 0 = 0.10 and 𝑚 ℎ * /𝑚 0 = 0.56).

All defect post-treatments presented above were performed using the PyDEF 2.0 software. [START_REF] Péan | Presentation of the PyDEF Post-Treatment Python Software to Compute Publishable Charts for Defect Energy Formation[END_REF][START_REF] Stoliaroff | 2.0: An Easy to Use Post-Treatment Software for Publishable Charts Featuring a Graphical User Interface[END_REF]

Results and discussions

The TiO2 rutile phase crystallizes in the tetragonal space group 𝑃4 2 /𝑚𝑛𝑚 65 with two formula units per unit cell and only two distinguishable atoms, titanium and oxygen, located at 2𝑎 and 4𝑓 Wyckoff positions, respectively. The electronic band gap of 2.12 eV obtained within the SCAN approach appears underestimated compared to the experiment (3.05-3.1 eV 1,72 or 3.3 eV [START_REF] Tezuka | Photoemission and Bremsstrahlung Isochromat Spectroscopy Studies of TiO2 (Rutile) and SrTiO3[END_REF] or the HSE06 functional (3.36 eV). A more accurate electronic band gap of 3.30 eV was obtained based on HSE06 calculations on optimized SCAN structures (HSE06@SCAN). This procedure was used for the band-edges correction of faulted supercells during the estimation of DFEs (and the determination of the 𝜖(𝑞/𝑞′) transition level positions).

Before investigating substitution of Ti atoms by TM species, the knowledge of the dopability domain delimited by intrinsic species is necessary. This domain is inspected here under O-poor and O-rich atmospheres.

Intrinsic point defects

Chemical potentials

Rutile TiO2 naturally exhibits an intrinsic 𝑛-type conductivity 4,6,74 with a mobility of the charge carriers that can reach half of crystalline silicon values. [START_REF] Yagi | Electronic Conduction above 4 K of Slightly Reduced Oxygen-Deficient Rutile TiO2[END_REF] Surprisingly, the nature of the dominant defect is still controversial. So far, oxygen vacancies 𝑉 𝑂 and titanium interstitials 𝑇𝑖 𝑖 have been pointed out to be responsible for by many theoretical and experimental studies. 7- 9,14,15,53,75 Nevertheless, these electron donor defects, if associated to defects energy levels located in the conduction band (see below), may also retrocede electrons to the host lattice that would be preferentially localized in the direct neighboring of Ti 4+ sites creating Ti 3+ species and small polarons. [START_REF] Deák | Oxygen Deficiency in TiO2: Similarities and Differences between the Ti Self-Interstitial and the O Vacancy in Bulk Rutile and Anatase[END_REF][START_REF] Eagles | Polar Modes of Lattice Vibration and Polaron Coupling Constants in Rutile (TiO2)[END_REF][START_REF] Stoneham | Self-Trapping and the Polaron Family[END_REF][START_REF] Finazzi | Nature of Ti Interstitials in Reduced Bulk Anatase and Rutile TiO2[END_REF][START_REF] Janotti | Dual Behavior of Excess Electrons in Rutile TiO2[END_REF] Moreover, conclusions from theoretical predictions on the depth of 𝑉 𝑂 defects are sometimes conflicting between shallow and deep nature. [START_REF] Janotti | Hybrid Functional Studies of the Oxygen Vacancy in TiO2[END_REF][START_REF] Morgan | Intrinsic N-Type Defect Formation in TiO2: A Comparison of Rutile and Anatase from GGA+U Calculations[END_REF][START_REF] Bjørheim | Defect Chemistry of Rutile TiO2 from First Principles Calculations[END_REF][START_REF] Zimmermann | Influence of Annealing Atmosphere on Formation of Electrically-Active Defects in Rutile TiO2[END_REF][START_REF] Han | Insights into the Characteristic Gap Level and N-Type Conductivity of Rutile TiO2 from the Hybrid Functional Method[END_REF][START_REF] Nowotny | Electrical Properties and Defect Chemistry of TiO2 Single Crystal. I. Electrical Conductivity[END_REF][START_REF] Duckworth | Deep Level Transient Spectroscopy in TiO2:Nb[END_REF] In that context, the thermodynamic stability of rutile TiO2 synthesized under different atmospheres was reinvestigated. To do so, 10 competitive phases (i.e., Ti, O2, Ti6O, Ti3O, Ti2O, TiO, Ti2O3, Ti3O5, Ti4O7 and Ti5O9) were considered in relation with the experimental Ti-O phase diagram, [START_REF] Das | The Al-O-Ti (Aluminum-Oxygen-Titanium) System[END_REF] while previous reported DFT studies took into account only 3 (i.e., Ti, O2 and Ti2O3). [START_REF] Janotti | Hybrid Functional Studies of the Oxygen Vacancy in TiO2[END_REF][START_REF] Morgan | Intrinsic N-Type Defect Formation in TiO2: A Comparison of Rutile and Anatase from GGA+U Calculations[END_REF][START_REF] Han | Insights into the Characteristic Gap Level and N-Type Conductivity of Rutile TiO2 from the Hybrid Functional Method[END_REF] The hcp-Ti(s) and O2(g) phases were used to set the chemical potential references 𝜇 𝑇𝑖 0 and 𝜇 𝑂 0 , respectively. We emphasize the fact that the actual study only focuses on the rutile TiO2 phase and neglects the competition with other stable (i.e., brookite and anatase) and metastable (i.e., columbite, ramsdellite, bronze, hollandite) phases of titania.

Defect formation enthalpies and defect concentrations

For both elements, we considered in our study i) 𝑉 𝑂 and 𝑉 𝑇𝑖 vacancies and ii) the 𝑇𝑖 𝑖 and 𝑂 𝑖 interstitial species (these latter were inserted at a position equivalent to the 4𝑐 Wyckoff position of the 𝑃4 2 /𝑚𝑛𝑚 regular rutile structure (i.e., (0, ½, 0) position) and relaxed in the supercell. Tii turn out to be 6-fold coordinated with Ti-O distances of ca. 2.02 Å; Oi tend to form O2 dimers (ca.

1.46 Å) by moving towards oxygen of the ideal host lattice). The defect formation enthalpies (DFEs) are summarized in Figure 2 for O-poor (T-rich) and O-rich (Ti-poor) synthesis conditions.

Defect concentrations are depicted in Figure 3.

From the examination of Figure 2, it appears that oxygen and titanium vacancies, regardless the synthesis conditions are stable only at the charge states +2 and -4, respectively if the Fermi level is positioned in the TiO2 gap. This result fits nicely with previous HSE calculations. [START_REF] Janotti | Hybrid Functional Studies of the Oxygen Vacancy in TiO2[END_REF][START_REF] Bjørheim | Defect Chemistry of Rutile TiO2 from First Principles Calculations[END_REF] Namely, 𝜖(+2/+1) and 𝜖(+1/0) levels associated to 𝑉 𝑂 species almost overlap and are located just above the bottom of the conduction band. Consequently, if 𝑉 𝑂 and 𝑉 𝑂 +1 would exist, they would have the propensity to retrocede their electron(s) to the host lattice triggering the reduction of Ti 4+ species into Ti 3+ ones, the conduction band being built mainly on the 3d-orbitals of titanium. In a similar way, the 𝜖(0/-1), 𝜖(-1/-2), 𝜖(-2/-3) and 𝜖(-3/-4) levels associated to 𝑉 𝑇𝑖 defect are just below the top of the valence band. However, they are so high in enthalpy that they are unlikely to be created. Moreover, the 𝜖(+4/+2) and 𝜖(+2/0) transition levels of 𝑇𝑖 𝑖 are determined at 0.58 eV below and 0.1 eV above the CBM, respectively; 𝑇𝑖 𝑖 + and 𝑇𝑖 𝑖 +3 species turn to be thermodynamical unstable and tend to disproportionate at the thermodynamical equilibrium into 𝑇𝑖 𝑖 0 and 𝑇𝑖 𝑖 +2 , and 𝑇𝑖 𝑖 +2 and 𝑇𝑖 𝑖 +4 , respectively. Oi may present a 0 or -2 charge states with a 𝜖(0/-2) level located in the mid-gap (i.e., 1.84 eV above the VB).

Under O-poor atmosphere, the Fermi level is expected to lie above 2.61 eV: for lower 𝐸 𝐹 values, 𝑇𝑖 𝑖 species would tend to be formed spontaneously due to negative DFEs leading to a titanium over-stoichiometric material. In the domain defined between 2.61 eV and the CBM, as titanium interstitials present a lesser DFE than oxygen vacancies, 𝑇𝑖 𝑖 point defects are expected to exist in highest concentrations and would be at the origin of the 𝑛-typeness of TiO2 rather than 𝑉 𝑂 .

This assumption is validated by our assessment of defect concentrations depicted in Figure 3a. For example, considering 𝑇 𝑔𝑟 = 1000 K, we found 𝐸 𝐹 𝑔𝑟 = 2.96 eV, [𝑇𝑖 𝑖 ] = 8.43×10 17 cm -3 and [𝑉 𝑂 ] = 9.68×10 14 cm -3 (three order of magnitude less for [𝑉 𝑂 ] compared to [𝑇𝑖 𝑖 ]). Under O-rich atmosphere, the Fermi level at room temperature is expected to range in the [0.54-1.74] eV energy domain defined by the intercept of the 𝜇 𝐸 𝐹 axis with the formation enthalpies of 𝑇𝑖 𝑖 and 𝑉 𝑇𝑖 species. This agrees well with previous HSE results. [START_REF] Bjørheim | Defect Chemistry of Rutile TiO2 from First Principles Calculations[END_REF] As aforementioned, a negative formation enthalpy associated to a defect would conduct to the elimination of the TiO2 phase at the benefit of richer or poorer Ti phases. Consequently, in Ti-poor synthesis conditions, rutile TiO2 is expected to be a material with no interesting conductive properties. By setting 𝑇 𝑔𝑟 at 1000 K, we We conclude that our simulations performed at the SCAN level follow very well the results obtained considering hybrid functionals. More specifically, we evidence that titanium interstitials constitute in oxygen poor condition the dominant defect responsible for the n-type character of TiO2. Under O-rich atmospheres, we evidenced a deep dopability domain delimited by Ti vacancies and interstitials that cannot lead to a n-type semiconductor.

In the following, we will examine specifically Ti-poor/O-rich synthesis conditions to naturally favor the insertion of dopants at Ti sites. We emphasize the fact that the choice of synthesis conditions does not alter at all the position of transition levels 𝜖(𝑞/𝑞′) of inserted dopants, i.e., their redox potentials, for which the prediction constitutes the main purpose of this study.

Calculations devoted to the Ti/V substitution is first presented, and discussion is then enlarged to other TM dopants i.e., manganese, iron, nickel and copper elements.

Transition metal impurities

The bcc-V phase was used to set the standard chemical potential reference 𝜇 𝑉 0 . The stability domain of rutile TiO2 in presence of vanadium has been calculated and is depicted by dashed area in SI Figure 1 (corresponding to formal V 5+ species replacing a Ti 4+ species) to -2 (formal V 2+ ). The evolution of DFEs vs. 𝜇 𝐸 𝐹 is depicted in Figure 4 where vanadium at titanium site is denoted 𝑉 𝑇𝑖 .

Here, the 𝜖(+1/0) and 𝜖(0/-1) transition levels associated to 𝑉 𝑇𝑖 defects were found within the band gap of TiO2 at 2.11 and 2.43 eV from the VBM, respectively. The 𝜖(-1/-2) level appear well above the CBM (0.48 eV) and is excluded from our considerations. We conclude that formal V 5+ (i.e., 𝑉 𝑇𝑖 + ), V 4+ (i.e., 𝑉 𝑇𝑖 0 ),) and V 3+ (i.e., 𝑉 𝑇𝑖 -),) species may be a priori found within TiO2 rutile (as reported by Mizushima et al. [START_REF] Mizushima | Energy Levels of Iron Group Impurities in TiO2[END_REF] ) depending on the synthesis atmosphere, the dopability domain of TiO2 shifting continuously from the 0.54-1.74 eV window to the 2.61-3.30 eV one by modifying the synthesis conditions. Hence, in O-rich and O-poor atmospheres, three charged states are stabilized for the substitution of titanium by vanadium. The stabilization of V 4+ cations will require intermediate synthesis conditions. Moreover, let us mention here that calculations of defect concentrations (see Figure 5) for a hypothetical V doped TiO2 compound synthesized at 1000 K A reasoning similar to the one used for vanadium can be applied to other dopants to anticipate their possible oxidation states once substituted to titanium. The resulting phase diagrams are given in SI, supported by a detailed list of binary and ternary competitive phases. DFEs for TM dopants are reported in Figure 4 for the oxygen rich atmosphere only. In this specific condition, all TMs present DFEs lower than 1.5 eV confirming experimental observations that conclude to the ease to substitute Ti atoms. (eV)

V 2+ Fe 4+ Fe 3+ Ni 3+ Ni 2+ Cu 3+ Cu 4+ Mn 4+ Mn 2+ Mn 5+ V 4+ V 3+ V 5+ Mn 3+ Fe 5+ Ni 4+ Cu 2+ Cu + a) b) w
Stability domains determined for each O-poor and O-rich extreme limit synthesis conditions, are depicted by hashed colored areas. The following levels can be found located within the bandgap: i) 𝜖(+1/0) at 2.11 eV and 𝜖(0/-1) at 2.43 eV for V, ii) 𝜖(0/-1) at 1.82 eV and 𝜖(-1/-2) at 2.26 eV for Mn, iii) 𝜖(+1/0) at 0.81 eV and 𝜖(0/-1) at 1.00 eV for Fe, iv) 𝜖(0/-1) at 1.15 eV and 𝜖(-1/-2) at 1.37 eV for Ni, and v) 𝜖(-1/-2) at 1.28 eV and 𝜖(-2/-3) at 2.02 eV for Cu. From the examination of Figure 6a, we could predict that formal V 3+ (i.e. (transition level find above 5 eV), Mn 5+ or Cu 4+ species for instance. Let us notice that a mixed valence may be observed if the Fermi level is pinned in the direct neighboring of a transition level

𝜖(𝑞/𝑞′).

Many experimental studies reported on the synthesis and the characterization of 3d TM doped rutile TiO2 materials. [START_REF] Li | Study on Activities of Vanadium (IV/V) Doped TiO2 (R) Nanorods Induced by UV and Visible Light[END_REF][START_REF] Park | Ferromagnetic Properties of Ni-Doped Rutile TiO2-δ[END_REF][START_REF] Navarro | Study of the Relation between Oxygen Vacancies and Ferromagnetism in Fe-Doped TiO2 Nano-Powders[END_REF][START_REF] Parveen | Room-Temperature Ferromagnetism in Ni-Doped TiO2 Diluted Magnetic Semiconductor Thin Films[END_REF][START_REF] Mizushima | Photoconductivity Spectra of Fe-Doped TiO2[END_REF][START_REF] Mizushima | Energy Levels of Iron Group Impurities in TiO2[END_REF][START_REF] Mizushima | One Electron Energy Levels of Iron Group Impurities in TiO2[END_REF][START_REF] Mizushima | Impurity Levels of Iron-Group Ions in TiO2 (II)[END_REF][START_REF] Yamaka | Paramagnetic Resonance of Iron Group Elements in Rutile. I. The Ti 47 and Ti 49 Hfs Interaction[END_REF][START_REF] Kim | Room-Temperature Ferromagnetic Properties in Mn-Doped Rutile TiO2-δ Thin Films[END_REF][START_REF] Güler | EPR Study of Mn-Implanted Single Crystal TiO2[END_REF][START_REF] Xia | Origin of Significant Visible-Light Absorption Properties of Mn-Doped TiO2 Thin Films[END_REF][START_REF] Carter | Electron Paramagnetic Resonance of Fe 3+ in TiO2 (Rutile)[END_REF][START_REF] Kim | Growth and Properties of Molecular Beam Epitaxially Grown Ferromagnetic Fe-Doped TiO2 Rutile Films on TiO2 (110)[END_REF][START_REF] He | Iron-Doped Cauliflower-Like Rutile TiO2 with Superior Sodium Storage Properties[END_REF][START_REF] Xia | Structure and Photocatalytic Properties of Copper-Doped Rutile TiO2 Prepared by a Low-Temperature Process[END_REF][START_REF] Tryba | Preparation and Characterization of Rutile-Type TiO2 Doped with Cu[END_REF][START_REF] Navarro | The Relationship between Magnetic Behaviour and Local Structure around Fe Ions in Fe-Doped TiO2 Rutile[END_REF] Figure 6b sums up the domain limits of cationic species in this specific host material as proposed by Mizushima et al. [START_REF] Mizushima | Photoconductivity Spectra of Fe-Doped TiO2[END_REF][START_REF] Mizushima | Energy Levels of Iron Group Impurities in TiO2[END_REF][START_REF] Mizushima | One Electron Energy Levels of Iron Group Impurities in TiO2[END_REF][START_REF] Mizushima | Impurity Levels of Iron-Group Ions in TiO2 (II)[END_REF] based on experimental (e.g., photocurrent) and theoretical (semi-empirical model supported by photoconductivity and photo-ESR measurements) considerations. Namely, experimentally observed ionic species in TiO2rutile, i.e., V 5+ , V 4+ and V 3+ 26,44,51 , Mn 4+ , Mn 3+ and Mn 2+ 47,51,83-85 , Fe 4+ and Fe 3+ 39,43,47,51,86,88,91 , Cu 2+ and possibly Cu + 89,90 , and Ni 3+ and Ni 2+ 36,40,51 , possibly stabilized for different material's shape (nanorods, nanopowders, thin films) are predicted from our simulations. Nevertheless, it has to be noticed that discrepancies exist between theory and experiments. Namely, it is has be noticed that Fe 2+ doped TiO2 (rutile form) has been reported this last decade, [START_REF] Meng | Role of Oxygen Vacancies on Ferromagnetism in Fe-Doped TiO2 Thin Films[END_REF][START_REF] Navarro | Study of the Relation between Oxygen Vacancies and Ferromagnetism in Fe-Doped TiO2 Nano-Powders[END_REF][START_REF] Kim | Growth and Properties of Molecular Beam Epitaxially Grown Ferromagnetic Fe-Doped TiO2 Rutile Films on TiO2 (110)[END_REF][START_REF] Navarro | The Relationship between Magnetic Behaviour and Local Structure around Fe Ions in Fe-Doped TiO2 Rutile[END_REF] contradicting both Mizushima and ours predictions where the 𝜖(-1/-2) level (Fe 3+ /Fe 2+ borderline) lies within the CB (not represented in Figure 6a). This may originate from specific out-of-equilibrium synthesis conditions (beam epitaxy, ball milled, magnetron sputtering) used to stabilize this doped variety.

Concerning the lack of detected Fe 5+ , Ni 4+ and Cu 3+ species in doped TiO2 materials, we may advocate, if calculations are correct, that high enough oxidizing atmospheres have not be used so far to stabilize them, but their existence should be conceivable. Mizushima et al. refute this possibility. At the end, Cu + doped TiO2 probably exists [START_REF] Tryba | Preparation and Characterization of Rutile-Type TiO2 Doped with Cu[END_REF] in good agreement with Figure 6a even if not reported in Figure 6b.

At this stage let us mention that the comparison between Figure 6a and Figure 6b (beyond the energy (potential) domains of existence) may be truncated for multiple reasons. Concerning the semi-empirical simulations [START_REF] Mizushima | Energy Levels of Iron Group Impurities in TiO2[END_REF] , it is worth to note that the model used (proposed by Alen [START_REF] Allen | Proceeding 7th Int. Conf Semicond[END_REF] ) is notably based on electrostatic interactions between d electrons described through parameters arbitrarily sets, extrapolated or taken from other metal organic compounds. These simulated data have been compared to photoconductivity and photo-ESR measurements which allow to access the stability region of charged impurities. During such experiments, the variation of the Fermi level position was controlled for some TM substituted TiO2 samples via the insertion of Li + cations or changing the oxygen content in the synthesis conditions to stabilize preferentially a given oxidation state of the probed element. Thenceforth, the redox E(D n /D n+1 ) potential can be perturbed compared to the ideal situation treated via calculations, the short-range environment of the dopant being perturbed itself.

On our theoretical side, the overall defected structure was drastically simplified in our calculations by tuning the charge state of defects (so the oxidation states of impurities) by changing the global electrical charge of the system and applying a Jellium-like model. Moreover, the control of unintentional defects is a critical point when experiments are performed. These ones may condense to form complexes also not taken into account here. Concerning the calculation method, the recently developed SCAN functional indicate several advantages for the prediction of electronic properties with respect to GGA approaches. Indeed, key physical data have been reported to be significantly improved for a large panel of materials, and accuracy is (sometimes) similar with hybrid methods. [START_REF] Yang | Rationalizing Accurate Structure Prediction in the Meta-GGA SCAN Functional[END_REF][START_REF] Yang | More Realistic Band Gaps from Meta-Generalized Gradient Approximations: Only in a Generalized Kohn-Sham Scheme[END_REF][START_REF] Sun | Accurate First-Principles Structures and Energies of Diversely Bonded Systems from an Efficient Density Functional[END_REF] A Hubbard correction could improve the description of point defects and impact their transition levels positions. This remains beyond the scope of this study but should be considered for future investigations.

Conclusion

Chemically speaking, a transition level 𝜖(𝑞/𝑞′) for the specific case of a dopant D delimits the existence domain in energy between the D n and the D n+1 species. Consequently, this level has to be regarded as the redox potential E(D n /D n+1 ) of the redox D n /D n+1 couple for a dopant D embedded in a given host lattice. This potential will strongly depend upon the chemical environment of the dopant (i.e., the coordination number, the chemical nature of the ligands, the covalency of the chemical bond, etc.) and will change from one host lattice to another. Indeed, ab initio calculations can serve to evaluate the potential towards the bottom of the conduction band or the top of the valence band via the determination of 𝜖(𝑞/𝑞′), and consequently towards an absolute scale if the BV or BC position with respect to vacuum level (or standard hydrogen electrode for instance) has been experimentally measured. Obviously, the positioning of 𝜖(𝑞/𝑞′) values can be impacted by the nature and the accuracy of the chosen approximations (exchange-correlation functional, size and/or type of basis set, relativistic effects, etc.) for calculations. This is especially true for TM species for which the computation of physical properties is particularly sensitive to these parameters, species with single electrons on d orbitals. So far, if the use of accurate approaches remains attractive and performant for this purpose, they suffer from an important computational cost which lets the supercell studies with realistic doping elusive. In that sense, we took benefit of this study to consider the SCAN functional as an alternative for such point defect investigations.

In a more general way, the ab initio determination of the redox potentials of dopants in solids is a contemporary challenge to explain and/or to tune properties of a host lattice and its doped congener. In the specific case of photo-catalysis, the knowledge of these data is crucial to orientate syntheses and uses. Of course, domains of interest are not limited to only this area.

DFT calculations based on the SCAN functional have been done on doped rutile TiO2 phase used as a school case. However, the procedure can be extrapolated to any semiconductors and insulators. Once, the electronic gap and the external dopability limit determined, stability of dopants can be probed in the host lattice versus different synthetic conditions, their attainable oxidation states determined, and their associated redox potential calculated. If accurate electronic information (e.g., electron affinity) on the host lattice are known, potential on an absolute scale can be extrapolated.

Figure 1

 1 Figure 1 displays the stability domain for the rutile TiO2 compound within the theoretical Ti-O phase diagram. Clearly, the chemical potential limits of O and Ti are delimitated by O2 gas and Ti5O9 solid phases. For O-rich/Ti-poor synthesis conditions, 𝜇 𝑇𝑖 and 𝜇 𝑂 are respectively set to -26.43 and -6.02 eV (Δ𝜇 𝑇𝑖 = -10.45 eV and Δ𝜇 𝑂 = 0.00 eV). For O-poor/Ti-rich conditions, 𝜇 𝑇𝑖 and 𝜇 𝑂 are equal to -18.17 and -10.15 eV (Δ𝜇 𝑇𝑖 = -2.19 eV and Δ𝜇 𝑂 = -4.13 eV).

Figure 1

 1 Figure 1 Stability domain of TiO2 as a function of the chemical potential deviations. In oxidized (O-rich) conditions, 𝛥𝜇 𝑂 = 0 eV and 𝛥𝜇 𝑇𝑖 = -10.45 eV, as the formation enthalpy 𝛥 𝑓 𝐻 of TiO2 (𝛥 𝑓 𝐻(𝑇𝑖𝑂 2 ) = 𝛥𝜇 𝑇𝑖 + 2𝛥𝜇 𝑂 ) is found to be -10.45 eV (very close to the experimental value of -9.78 eV). 82 Under reduced (O-poor) atmospheres, the Ti5O9 phase bounds the stability domain of TiO2 at 𝛥𝜇 𝑂 = -4.13 eV and 𝛥𝜇 𝑇𝑖 = -2.19 eV.

Figure 2 :Figure 3 :

 23 Figure 2: Formation enthalpies of the intrinsic defects in TiO2 vs. 𝜇 𝐸 𝐹 in (a) Ti-rich/O-poor and (b) Ti-poor/O-rich synthesis conditions

  (a) Ti-rich/O-poor (b) Ti-poor/O-rich determined 𝐸 𝐹 𝑔𝑟 at 1.30 eV, [𝑉 𝑇𝑖 ] = 4.65×10 13 cm -3 and [𝑂 𝑖 ] = 1.32×10 12 cm -3 . The evolution of concentrations vs. the growth temperature is given in Figure 3b.

  -2 as a function of chemical potential variations 𝛥𝜇 𝑇𝑖 , 𝛥𝜇 𝑂 and 𝛥𝜇 𝑉 . The stability domain shows four summits, each of them being associated to the competition with potential subproducts. Defect formation enthalpies have been determined in O-rich synthesis conditions only for various charge states of substituted vanadium species denoted 𝑉 𝑇𝑖 𝑛 , 𝑛 varying from +1

  under O2 rich atmosphere and quenched to RT lead naturally to [𝑉𝑎 𝑇𝑖 ] = 4.21×10 19 cm -3 and [𝑉 𝑇𝑖 ] = 1.05×10 19 cm -3 , i.e., the exact and expected [𝑉𝑎 𝑇𝑖 ]/ [𝑉 𝑇𝑖 ] ratio of 4 for the Ti 4+  denotes a Ti vacancy). Extra defects (i.e., 𝑉 𝑂 , 𝑂 𝑖 and 𝑇𝑖 𝑖 ) are several orders of magnitude lesser.

Figure 4 :

 4 Figure 4: Defect formation enthalpies for TM substitutions under O-rich atmosphere. The dopability domain defined by intrinsic species is delimited by grey blocks. The transition level positions would be calculated at the same energy in O-poor atmosphere, but DFE would be different.

Figure 5 :

 5 Figure 5: Defect concentrations vs. growth temperature for intrinsic and vanadium impurities point defects. Titanium vacancies and vanadium substitutions are denoted 𝑉 𝑇𝑖 and 𝑉𝑎 𝑇𝑖 , respectively.

Figure 6a gathers the

  Figure 6a gathers the estimated transition levels calculated at the thermodynamic equilibrium, i.e., after geometrical relaxation of the atomic positions whatever the charge state of the defects, for all sound TMs.

Figure 6 :

 6 Figure 6: a) Calculated charge transition levels. O-poor and O-rich dopability domains are evidenced by cyan and grey areas, respectively. b) Charge transition levels proposed by Mizushima et al. based on semi-empirical calculations[START_REF] Mizushima | Energy Levels of Iron Group Impurities in TiO2[END_REF] and photocurrent measurements[START_REF] Mizushima | Impurity Levels of Iron-Group Ions in TiO2 (II)[END_REF] represented by dotted and solid lines, respectively.

Table 2

 2

	in SI summarizes the lattice parameters, electronic band gaps and interatomic
	distances determined with different exchange-correlation functionals. In terms of lattice
	parameters, a great agreement is obtained using the SCAN or HSE06 functionals with respect to
	experimental data, while the three other functionals tend to overestimate these values within the
	PBE error range (~2%). For the SCAN functional, 𝑎 and 𝑐 values of 4.596 Å and 2.968 Å are very
	close to experimental data issued from powder neutron diffraction data (𝑎 = 4.59308(4) Å and 𝑐 =
	2.95889(3) Å).

  ) species can be stabilized in O-rich atmosphere. For intermediate synthesis situations, formal V 5+ , V 4+ and V 3+ , Mn 4+ , Mn 3+ and Mn 2+ , Fe 3+ , Ni 2+ , and Cu 2+ and Cu + (see white zone in-between the O-poor and O-rich domains) may exist in the TiO2 host lattice in contrast with formal V 2+ , Fe 2+

	, 𝑉 𝑇𝑖 -), Mn 2+
	(i.e., 𝑀𝑛 𝑇𝑖 -2 ), Fe 3+ (i.e., 𝐹𝑒 𝑇𝑖 -), Ni 2+ (i.e.,𝑁𝑖 𝑇𝑖 -2 ) and Cu + (i.e., 𝐶𝑢 𝑇𝑖 -3 ) species can be formed under O-
	poor atmosphere, while formal V 5+ (i.e., 𝑉 𝑇𝑖 + ), Mn 4+ (i.e., 𝑀𝑛 𝑇𝑖 0 ), Fe 5+ (i.e., 𝐹𝑒 𝑇𝑖 + ), Fe 4+ (i.e., 𝐹𝑒 𝑇𝑖 0 ),
	Fe 3+ (i.e., 𝐹𝑒 𝑇𝑖 -), Ni 4+ (i.e., 𝑁𝑖 𝑇𝑖 0 ), Ni 3+ (i.e., 𝑁𝑖 𝑇𝑖 -), Ni 2+ (i.e., 𝑁𝑖 𝑇𝑖 -2 ), Cu 3+ (i.e., 𝐶𝑢 𝑇𝑖 -), and Cu 2+ (i.e.,
	𝐶𝑢 𝑇𝑖 -2

Acknowledgments

This work was performed using CCIPL (Centre de Calculs Intensifs des Pays de la Loire) and HPC resources from GENCI-TGCC (Grant 2020-A0080911491). W.L.-D.-H. particularly thanks the financial support by the ANR-18-CE08-0012 PERSIST project of the French National Research Agency and the CNRS. W.L.-D.-H. is also very grateful to Dr. Adrien Stoliaroff for his help on the use of the PyDEF software 70,71 and useful discussions. Crystal structures were represented using the VESTA software. 95

Supporting Informations

Details on the corrections for the defect formation enthalpies, stability domains and concentrations of TM-doped rutile TiO2; representation of the electronic charge density associated to point defects for a representative set of defects species.