Jérôme G Prunier
email: jerome.prunier@gmail.com

Bernard Kaufmann

Jean-Paul Léna

Serge Fenet

Francois Pompanon

Pierre Joly

François Pompanon

A 40-year-old divided highway does not prevent gene flow in the alpine newt Ichthyosaura alpestris

Keywords: amphibian, Bayesian clustering methods, correlative analyses, landscape genetics, highway, sPCA

d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Roads constitute one of the most widespread forms of land use in contemporary landscapes and have been the subject of numerous studies aiming to assess their impacts on natural populations [START_REF] Trombulak | Review of ecological effects of roads on terrestrial and aquatic communities[END_REF][START_REF] Balkenhol | Molecular road ecology: exploring the potential of genetics for investigating transportation impacts on wildlife[END_REF]. Roads are known to act as barrier to dispersal and gene flow (isolation-by-barrier, IBB), decreasing functional connectivity and increasing the genetic differentiation among individuals on each side of the infrastructure [START_REF] Balkenhol | Molecular road ecology: exploring the potential of genetics for investigating transportation impacts on wildlife[END_REF][START_REF] Holderegger | The genetic effects of roads: A review of empirical evidence[END_REF]. The larger the size of a road (in terms of traffic volume and spatial dimensions), the higher the expected impact on both landscape configuration [START_REF] Trombulak | Review of ecological effects of roads on terrestrial and aquatic communities[END_REF] and dispersal patterns [START_REF] Holderegger | The genetic effects of roads: A review of empirical evidence[END_REF]. Large-scale transportation infrastructures (LTIs) such as highways and high-speed railways are thus of major concern in conservation biology. Barrier effects may be explained by mortality due to collisions, which obviously decreases gene exchanges across roads [START_REF] Holderegger | The genetic effects of roads: A review of empirical evidence[END_REF], but also by the modification of effective dispersal patterns (e.g. [START_REF] Riley | R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing[END_REF]. The presence of 'Jersey barriers' [START_REF] Lesbarreres | Measures to reduce population fragmentation by roads: what has worked and how do we know?[END_REF] or fences for livestock exclusion [START_REF] Dodd | Effectiveness of a barrier wall and culverts in reducing wildlife mortality on a heavily traveled highway in Florida[END_REF][START_REF] Kuehn | Genetic effect of transportation infrastructure on roe deer Populations (Capreolus capreolus)[END_REF][START_REF] Holderegger | The genetic effects of roads: A review of empirical evidence[END_REF][START_REF] Hepenstrick | Genetic discontinuities in roe deer (Capreolus capreolus) coincide with fenced transportation infrastructure[END_REF], as well as road avoidance due to physical or chemical alteration of the local environment may prevent animals from crossing LTIs and possibly lead them to increase their movement along road verges [START_REF] Trombulak | Review of ecological effects of roads on terrestrial and aquatic communities[END_REF][START_REF] Mcgregor | Do small mammals avoid roads because of the traffic?[END_REF][START_REF] Balkenhol | Molecular road ecology: exploring the potential of genetics for investigating transportation impacts on wildlife[END_REF]. However, barrier effects are often alleviated by bridges, underpasses or specific road crossing structures, often coupled with guide fences [START_REF] Mcgregor | Do small mammals avoid roads because of the traffic?[END_REF]Woltz et al. 2008) that can be used by dispersing animals. Small ground-dwelling animals such as amphibians are nevertheless suspected to be unable to encounter these crossing structures because of poor locomotive performances and specific orientation capabilities [START_REF] Joly | How does a newt find its pond -the role of chemical cues in migrating newts (Triturus alpestris)[END_REF][START_REF] Beebee | Effects of Road Mortality and Mitigation Measures on Amphibian Populations[END_REF]. As mortality due to collisions and road avoidance both depend on traffic volume and infrastructure width, divided highways might be considered stronger barriers to dispersal than high-speed railways. However, rails may also constitute a physical barrier for small ground-dwelling animals [START_REF] Bartoszek | A population divided: railroad tracks as barriers to gene flow in an isolated population of marbled salamanders (Ambystoma opacum)[END_REF], because tracks are in close contact to the ballast, leaving no space for animals to move underneath, while the prominent head of tracks (when considering the cross sectional shape of rail) may prevent animals from climbing over them.

On a larger scale, modifications of the surrounding landscape configuration due to LTI could also impact wildlife dispersal patterns. For instance, LTIs are responsible for the alteration of surface-water habitats through flow re-routing and wetlands destruction [START_REF] Trombulak | Review of ecological effects of roads on terrestrial and aquatic communities[END_REF], impacting both aquatic and semi-aquatic species. In the particular case of highways, road connections to urban areas improve rural-urban access and increase farmland value [START_REF] Drescher | Farmland prices determinants[END_REF]. This often leads to the regrouping of cultivated farmlands, to the detriment of suitable landscape features such as wooded patches, extensively pastured meadows and aquatic or hedgerows networks. Conversely, LTIs may also contribute to the creation of large-scale, non-fragmented linear wetlands such as roadside ditches and grasslands corridors such as roadside verges, favoring movement of native but also exotic species in areas of low-quality or highly fragmented habitats [START_REF] Tikka | Road and railway verges serve as dispersal corridors for grassland plants[END_REF][START_REF] Brisson | Roadside as invasion pathway for common reed (Phragmites australis)[END_REF][START_REF] Holderegger | The genetic effects of roads: A review of empirical evidence[END_REF]. All these potential effects depend on complex interactions between species, infrastructures and landscape-specific characteristics, as well as the interactions with public policies and economic context (Woltz et al. 2008;[START_REF] Balkenhol | Molecular road ecology: exploring the potential of genetics for investigating transportation impacts on wildlife[END_REF].

Direct and indirect effects of roads on wildlife have been described for years [START_REF] Trombulak | Review of ecological effects of roads on terrestrial and aquatic communities[END_REF], leading to the emergence of road ecology as a specific scientific discipline [START_REF] Forman | Road Ecology[END_REF]). Among available tools, molecular genetic techniques recently emerged as particularly useful to detect road impacts on population structures [START_REF] Balkenhol | Molecular road ecology: exploring the potential of genetics for investigating transportation impacts on wildlife[END_REF]. In close collaboration with local road planners, as recommended in [START_REF] Lesbarreres | Measures to reduce population fragmentation by roads: what has worked and how do we know?[END_REF], we carried out a broad-scale analysis of the potential impacts of two LTIs, a divided highway and a high-speed railway, on spatial genetic patterns in the alpine newt Ichthyosaura alpestris. Many landscape genetic studies assessing the impact of roads on amphibians have detected a decrease in genetic diversity and an increase in genetic differentiation in the vicinity of LTIs [START_REF] Lesbarreres | The effects of 20 years of highway presence on the genetic structure of Rana dalmatina populations[END_REF][START_REF] Holderegger | The genetic effects of roads: A review of empirical evidence[END_REF][START_REF] Emel | A decade of amphibian population genetic studies: synthesis and recommendations[END_REF], probably resulting in population fragmentation. The alpine newt is no exception, as shown in a recent study in Switzerland (Van Buskirk 2012). Furthermore, both LTIs are located along the Paris-Lyon axis, a sector already suspected to prevent genetic exchange in another species, the European wildcat Felis silvestris silvestris [START_REF] Say | Distribution and spatial genetic structure of European wildcat in France[END_REF]. We thus expected the two LTIs under study to significantly alter gene flow in the alpine newt: the A6 highway and the LGV-PSE high-speed railway should be associated with a significant increase in genetic distances between individuals located on either side or should coincide with sharp genetic discontinuity between genetic clusters. To test this hypothesis, we used both simulated and empirical genetic data, gathered following a regular individual-based sampling scheme in order to optimize the number of sampled sites across the study area. This kind of sampling scheme is a powerful alternative to the conventional population-based sampling scheme, that proved to be particularly efficient at detecting recent barriers to gene flow when designed as a targeted sampling scheme, that is when sampled sites are localized in the direct vicinity of a putative barrier [START_REF] Anderson | Considering spatial and temporal scale in landscape-genetic studies of gene flow[END_REF][START_REF] Prunier | Optimizing the trade-off between spatial and genetic sampling efforts in patchy populations: towards a better assessment of functional connectivity using an individual-based sampling scheme[END_REF].

Materials and methods

Study area

The study was carried out in eastern central France (Bourgogne), over an area of approximately 60 x 55 km (Fig. 1a), with elevation ranging from 138 to 857 m (mean elevation: 399 m). This area comprised several water catchments and three distinct landscape entities (Fig. 1b): [START_REF] Broquet | Buccal swabs allow efficient and reliable microsatellite genotyping in amphibians[END_REF] In the south-west lies Le Morvan, a massif comprising low elevation fragmented wooded patches and extensively pastured meadows for livestock farming, with a dense hydrographic network (minimum elevation: 400 m). ( 2 Except for the two LTIs, artificial areas are mainly composed of farms, villages and a few small towns, all connected by roads with low to medium traffic. The study area includes high densities of aquatic sites, with one pond per km² on average.

Biological model

The alpine newt is a widespread species in central Europe that strongly depends on permanent fish-free ponds or smaller aquatic sites such as ruts, surrounded by suitable terrestrial habitat such as woods and semi-natural grasslands [START_REF] Joly | Habitat matrix effects on pond occupancy in newts[END_REF]. In Bourgogne, this amphibian benefits from extensive livestock farming that allows the preservation of many natural or artificial ponds in pastures.

The alpine newt is an annual breeder, with reported longevity up to 10 years below 1000m of altitude [START_REF] Miaud | Age, size, and growth of the alpine newt, Triturus alpestris (Urodela : Salamandridae), at high altitude and a review of life-history trait variation throughout its range[END_REF][START_REF] Perret | Transience, dispersal and survival rates in newt patchy populations[END_REF], although skeletochronology of phalanges, the most widely used method of ageing amphibians, has been shown to underestimate the true age of long-lived amphibians [START_REF] Wagner | Skeletochronology of phalanges underestimates the true age of long-lived Alpine newts (Ichthyosaura alpestris)[END_REF]): in our study area, we may thus expect individuals to live up to 15 or 20 years. Age at maturity is estimated at three year-old at low altitudes [START_REF] Miaud | Age, size, and growth of the alpine newt, Triturus alpestris (Urodela : Salamandridae), at high altitude and a review of life-history trait variation throughout its range[END_REF]. Dispersal movements may range from several hundred meters to one kilometer [START_REF] Joly | Colonization dynamics of new ponds, and the age structure of colonizing Alpine newts, Triturus alpestris[END_REF][START_REF] Denoel | Persistence and dispersion of an introduced population of Alpine Newt (Triturus alpestris) in the limestone plateau of Larzac (Southern France)[END_REF][START_REF] Kovar | Spring migration distances of some Central European amphibian species[END_REF], although movements up to four kilometers have been reported [START_REF] Schäfer | Ausbreitung und Entwicklung von Amphibien-Populationen in der Agrarlandschaft[END_REF][START_REF] Schmidt | Dispersal of Triturus alpestris and T. vulgaris in agricultural landscapescomparing estimates from allozyme markers and capturemark-recapture analysis[END_REF].

While juvenile dispersal is rather the doing of male juveniles [START_REF] Joly | Colonization dynamics of new ponds, and the age structure of colonizing Alpine newts, Triturus alpestris[END_REF], several capturemark-recapture studies also reported high rates of breeding dispersal in both sexes, ranging from 4 to 48% of dispersal adults per population (depending on landscape configuration; [START_REF] Perret | Transience, dispersal and survival rates in newt patchy populations[END_REF][START_REF] Schmidt | Dispersal of Triturus alpestris and T. vulgaris in agricultural landscapescomparing estimates from allozyme markers and capturemark-recapture analysis[END_REF][START_REF] Kopecky | Movements of Alpine newts (Mesotriton alpestris) between small aquatic habitats (ruts) during the breeding season[END_REF][START_REF] Kopecky | Sex-specific effect of pool desiccation on the movement of Alpine Newts, Mesotriton alpestris (LAURENTI, 1768), among breeding sites (Caudata: Salamandridae)[END_REF]. This suggests that habitat supplementation is probably as important as habitat complementation in this species [START_REF] Dunning | Ecological processes that affect populations in complex landscapes[END_REF][START_REF] Kopecky | Movements of Alpine newts (Mesotriton alpestris) between small aquatic habitats (ruts) during the breeding season[END_REF]. This highly nomadic behaviour may lead to strong gene flow and weak genetic differentiation among subpopulations despite distances of up to several kilometers [START_REF] Emaresi | Landscape genetics of the Alpine newt (Mesotriton alpestris) inferred from a strip-based approach[END_REF][START_REF] Van Buskirk | Permeability of the landscape matrix between amphibian breeding sites[END_REF][START_REF] Prunier | Optimizing the trade-off between spatial and genetic sampling efforts in patchy populations: towards a better assessment of functional connectivity using an individual-based sampling scheme[END_REF], especially when high densities of aquatic sites are available, which was the case in our study. The alpine newt thus constitutes a pertinent biological model for the study of barrier effects, since individuals with high dispersal abilities may encounter roads at higher rates than less mobile species, thus shortening the time-lag before barrier detection (Landguth et al. 2010;[START_REF] Prunier | Optimizing the trade-off between spatial and genetic sampling efforts in patchy populations: towards a better assessment of functional connectivity using an individual-based sampling scheme[END_REF].

Genetic sampling and genotyping

Fieldwork was conducted during the 2010 and 2011 breeding seasons, and 339 aquatic sites (artificial or natural ponds, flooded ruts, swamps, etc.) were prospected with a dip net for thirty to sixty minutes (depending on site size and configuration) or until a male and a female were captured. Using individuals rather than populations as the operational unit proved to be quite efficient at detecting recent barriers to gene flow in previous studies (Landguth et al. 2010;[START_REF] Prunier | Optimizing the trade-off between spatial and genetic sampling efforts in patchy populations: towards a better assessment of functional connectivity using an individual-based sampling scheme[END_REF]. It notably allows the number of sampled genotypes per aggregate to be reduced in favour of a better coverage of landscape in the vicinity of both LTIs, thus minimizing the number of unsampled populations [START_REF] Beerli | Effect of unsampled populations on the estimation of population sizes and migration rates between sampled populations[END_REF][START_REF] Lowe | What can genetics tell us about population connectivity?[END_REF].

Alpine newts were found in 225 sites (66% of prospected sites). The median distance between neighbouring sites (following a Delaunay triangulation) was 2.88 km, ranging from 184 m to 10.79 km.

Non-destructive genetic samples using buccal swabs were taken from each captured individual [START_REF] Broquet | Buccal swabs allow efficient and reliable microsatellite genotyping in amphibians[END_REF]. Samples were stored at ambient temperature in an air-tight container with silica gel providing total desiccation. DNA extraction, PCR amplifications and genotyping were performed as described in [START_REF] Prunier | Skin swabbing as a new efficient DNA sampling technique in amphibians, and 14 new microsatellite markers in the alpine newt (Ichthyosaura alpestris)[END_REF], using 14 autosomal microsatellite loci: CopTa1, CopTa2, CopTa3, CopTa4, CopTa7, CopTa8, CopTa9, CopTa10, CopTa11, CopTa12, CopTa13 and CopTa14 (Prunier et al. 2012), Ta1Ca1 and Ta1Caga4 (Garner et al. 2003). Significant gametic disequilibrium was detected between

CopTa7, CopTa9 and CopTa10 in a previous study realized at the population-level [START_REF] Prunier | Skin swabbing as a new efficient DNA sampling technique in amphibians, and 14 new microsatellite markers in the alpine newt (Ichthyosaura alpestris)[END_REF].

CopTa7 and CopTa9 were thus discarded from all further analyses except spatial principal component analyses (sPCA; [START_REF] Jombart | Revealing cryptic spatial patterns in genetic variability by a new multivariate method[END_REF], as this method is not contingent on any particular genetic model.

Neither null alleles nor linkage disequilibrium were detected with this new combination of 12 markers [START_REF] Prunier | Skin swabbing as a new efficient DNA sampling technique in amphibians, and 14 new microsatellite markers in the alpine newt (Ichthyosaura alpestris)[END_REF]. To assess the reliability of our genetic data, we estimated the mean error rate per locus e l [START_REF] Pompanon | Genotyping errors: Causes, consequences and solutions[END_REF] In order to take into account possible sex-biased dispersal in the alpine newt [START_REF] Joly | Colonization dynamics of new ponds, and the age structure of colonizing Alpine newts, Triturus alpestris[END_REF][START_REF] Kopecky | Sex-specific effect of pool desiccation on the movement of Alpine Newts, Mesotriton alpestris (LAURENTI, 1768), among breeding sites (Caudata: Salamandridae)[END_REF]), all the following analyses were performed using males (dataset M) and females (dataset F) separately, except when specified. Indeed, provided that only adults are sampled, the use of autosomal nuclear markers does not prevent the detection of sex-specific differences in dispersal [START_REF] Goudet | Tests for sex-biased dispersal using bi-parentally inherited genetic markers[END_REF].

Isolation-by-distance, isolation-by-resistance and isolation-by-barrier

Nearest neighbour mating, the standard process driving genetic differentiation among organisms and leading to patterns of isolation-by-distance IBD [START_REF] Broquet | Genetic isolation by distance and landscape connectivity in the American marten (Martes americana)[END_REF], and landscape fragmentation, leading to patterns such as isolation-by-barrier IBB or isolation-by-resistance IBR, may occur simultaneously. It is therefore of crucial importance to test for IBD prior to any other analysis [START_REF] Schwartz | Why sampling scheme matters: the effect of sampling scheme on landscape genetic results[END_REF]. We performed spatial autocorrelation analyses with non-directional Mantel correlograms [START_REF] Smouse | Spatial autocorrelation analysis of individual multiallele and multilocus genetic structure[END_REF][START_REF] Borcard | Is the Mantel correlogram powerful enough to be useful in ecological analysis? A simulation study[END_REF] to determine the scale S at which IBD patterns occur in each dataset [START_REF] Epperson | Geographical Genetics[END_REF]. For this purpose, we computed inter-individual pairwise genetic distances using the Bray-Curtis percentage dissimilarity measure as described in [START_REF] Cushman | Gene flow in complex landscapes: Testing multiple hypotheses with causal modeling[END_REF]. Euclidean distance classes were defined every 3000 m (up to 30 km), resulting in 10 binary matrices representing the membership of individuals to the distance class being tested (with 0 for pairs of individuals belonging to the same distance class and 1 otherwise). Each binary matrix was compared to the genetic distance matrix using a simple Mantel test with 1000 permutations. We then plotted Mantel correlation values over distance classes, with a 95% confidence interval determined by bootstrap resampling (1000 iterations).

The two LTIs were expected to act as barriers to gene flow, and the spatial individual-based sampling scheme was specifically designed to test this hypothesis. We thus tried to detect such a signal with a priori knowledge on the location of each putative barrier, using correlative analyses and spatial subsets of datasets M and F with selected genotypes located at least S km from each LTI. This targeted sampling scheme was designed to avoid large gaps between sampled points and putative barriers to gene flow [START_REF] Anderson | Considering spatial and temporal scale in landscape-genetic studies of gene flow[END_REF][START_REF] Prunier | Optimizing the trade-off between spatial and genetic sampling efforts in patchy populations: towards a better assessment of functional connectivity using an individual-based sampling scheme[END_REF]. This procedure resulted in the design of four new datasets: M A6 , F A6 , M LGV-PSE and F LGV-PSE . For each dataset, we computed a pairwise genetic distance matrix using the Bray-Curtis percentage dissimilarity measure. The use of inter-individual measures of genetic relatedness is expected to substantially enhance the detection of recent genetic patterns when compared to the use of conventional inter-population genetic distances, as allelic frequencies may suffer from a loss of resolution due to the averaging of genetic information at the population level (Landguth et al. 2010;[START_REF] Prunier | Optimizing the trade-off between spatial and genetic sampling efforts in patchy populations: towards a better assessment of functional connectivity using an individual-based sampling scheme[END_REF]): occurrence of alleles in individual genotypes may actually evolve at higher rates than allelic frequencies. For each dataset, we also computed a pairwise Euclidean distance (IBD) matrix and a pairwise IBB distance matrix, coded with 0 when two individuals were located on the same side of a barrier, or 1 when they were separated by a barrier [START_REF] Epps | Highways block gene flow and cause a rapid decline in genetic diversity of desert bighorn sheep[END_REF]. IBD being regarded as the null hypothesis, competing hypotheses can also be proposed to determine whether genetic structure may be influenced by additional landscape features (e.g. [START_REF] Cushman | Gene flow in complex landscapes: Testing multiple hypotheses with causal modeling[END_REF][START_REF] Goldberg | Comparative landscape genetics of two pond-breeding amphibian species in a highly modified agricultural landscape[END_REF], as controlling for IBR may indeed reveal LTI influences otherwise undetected. For each dataset, we thus computed three pairwise IBR distance matrices based on the potential influence of slope (IBR slope ; [START_REF] Murphy | Landscape genetics of high mountain frog metapopulations[END_REF][START_REF] Emel | A decade of amphibian population genetic studies: synthesis and recommendations[END_REF], land cover (IBR LC ;[START_REF] Spear | Landscape genetics of the blotched tiger salamander (Ambystoma tigrinum melanostictum)[END_REF][START_REF] Goldberg | Comparative landscape genetics of two pond-breeding amphibian species in a highly modified agricultural landscape[END_REF] or a combination of these two features (IBR slopeLC ). Slope, measured in percent and ranging from 0 to 72% in the study area, was derived from a 50-m SRTM-Digital Elevation Model (Shuttle Radar Topography Mission). Wood patches and urbanized areas, respectively known to improve and to impede gene flow in the alpine newt [START_REF] Emaresi | Landscape genetics of the Alpine newt (Mesotriton alpestris) inferred from a strip-based approach[END_REF], were extracted from national maps (BD Topo from National Geographic Institute, France, 1/25 000). We used ARCGIS 9.3 and its extension SPATIAL ANALYST to manage and rasterize these features. We then used the MATLAB software coding environment (Mathworks, Inc.) to compute least-cost-paths between pairwise individuals (Adriaensen et All Mantel tests were performed with 1000 standard permutations using the MATLAB software coding environment (Mathworks, Inc.). All spatial variables (Euclidean distances and least-cost-paths)

were log-transformed following the D=ln(d+1) formula and standardized to meet linearity assumptions.

In order to ensure that IBB detection power was not restricted by a limited number of genotypes, we also performed the same analyses with both males and females located at less than S km from each LTI using Mantel tests with 1000 restricted permutations [START_REF] Prunier | Optimizing the trade-off between spatial and genetic sampling efforts in patchy populations: towards a better assessment of functional connectivity using an individual-based sampling scheme[END_REF].

Genetic structure analyses

The combination of overlay clustering methods with correlative analyses proved to be particularly powerful in detecting recent barriers to gene flow (Landguth et al. 2010;[START_REF] Safner | Comparison of Bayesian Clustering and Edge Detection Methods for Inferring Boundaries in Landscape Genetics[END_REF][START_REF] Blair | A simulation-based evaluation of methods for inferring linear barriers to gene flow[END_REF]. Bayesian clustering algorithms were successfully used in several studies aiming at detecting barriers to dispersal (e.g. [START_REF] Frantz | Comparative landscape genetic analyses show a Belgian motorway to be a gene flow barrier for red deer (Cervus elaphus), but not wild boars (Sus scrofa)[END_REF][START_REF] Hepenstrick | Genetic discontinuities in roe deer (Capreolus capreolus) coincide with fenced transportation infrastructure[END_REF]). We used TESS 2.3.1 [START_REF] Chen | Bayesian clustering algorithms ascertaining spatial population structure: a new computer program and a comparison study[END_REF]), a spatial Bayesian clustering method, to identify clusters of individuals. This program computes probabilities that each individual genotype originates from one of K panmictic populations. Accounting for both the putative barrier effect of LTIs segregating the study area in four distinct sectors (Fig. 1a) and the extent of our study area, we did not expect to detect more than ten distinct genetic clusters (one cluster in sector D and three clusters in each sector A, B or C). Genetic data were analyzed using correlated allele frequencies and other parameters were set to default values. We used the admixture CAR model starting from a neighbour-joining tree based on a Delaunay triangulation (Fig. 1c). Preliminary analyses indicated that setting the spatial interaction parameter to its default value (0.6) was well supported by data. To estimate the true number of genetic clusters K, we made five runs per K for K = 2 to 10, with 100000 sweeps and a burn-in period of 10000 sweeps. We then identified which value of K produced the highest likelihood runs (lowest values of DIC), and made 100 runs for K max , with the same parameters. The 20 best results (lowest values of DIC) were averaged with CLUMPP [START_REF] Jakobsson | CLUMPP: a cluster matching and permutation program for dealing with label switching and multimodality in analysis of population structure[END_REF]. To visualize the results, we used the kriging function provided in the R-package 'gstat' [START_REF] Pebesma | Multivariable geostatistics in S: the gstat package[END_REF]; R Development Core Team 2011) to represent the estimated membership of each individual on a grid with a resolution of 500m, following an inverse distance weighted interpolation function.

We also performed a spatial principal component analysis (sPCA; were carried out with 10000 permutations to evaluate the significance of detected patterns [START_REF] Jombart | Revealing cryptic spatial patterns in genetic variability by a new multivariate method[END_REF]).

In addition, we evaluated the presence of sharp genetic boundaries with no a priori knowledge on the location of putative barriers using the Monmonier's Maximum Difference Algorithm [START_REF] Monmonier | Maximum-difference barriers: An alternative numerical regionalization method[END_REF]) implemented in AIS [START_REF] Miller | Alleles In Space (AIS): Computer software for the joint analysis of interindividual spatial and genetic information[END_REF]. This tool did not provide additional information about genetic structure in I. alpestris: methods and results are thus presented in Appendix A.

Simulations

One of the main issues when trying to detect the impact of roads on gene flow is the time-lag between the creation of infrastructures and the ensuing genetic response [START_REF] Anderson | Considering spatial and temporal scale in landscape-genetic studies of gene flow[END_REF]Landguth et al. 2010). Simulations were thus performed to determine whether the two LTIs were old enough for possible genetic discontinuities to be detected in our study. For this purpose, we used CDPOP (Landguth We considered a total of 450 localities, including the 225 sites were alpine newts were actually sampled along with 225 additional fictive sites (Fig. 1a). Resulting densities of simulated sites were four to five times lower than those encountered in the field, but were optimized according to software memory limitations. Each locality was initiated with 10 individuals and kept at a constant size over generations.

This low number of individuals per aggregate is realistic when high densities of breeding sites are available. For instance, only six aquatic sites out of 72 allowed the capture of more than 20 individuals in a previous study in Bourgogne [START_REF] Prunier | Optimizing the trade-off between spatial and genetic sampling efforts in patchy populations: towards a better assessment of functional connectivity using an individual-based sampling scheme[END_REF]). The age structure was defined according to a normal distribution with a mean µ = 0 and a standard deviation σ = 5 so that the maximal longevity of individuals was 18 years (Appendix B). Age at maturity was fixed at three year-old [START_REF] Miaud | Age, size, and growth of the alpine newt, Triturus alpestris (Urodela : Salamandridae), at high altitude and a review of life-history trait variation throughout its range[END_REF] and both males and females were allowed to mate with replacement (Garner and Schmidt 2003;[START_REF] Hoeck | Female alpine newts (Triturus alpestris) mate initially with males signalling fertility benefits[END_REF]. The simulated number of offspring per mating event was drawn from a Poisson distribution with mean λ = 1, resulting in an average of 4.2 offspring per female and per generation. Although below the reported number of eggs laid by alpine newt females during a single breeding season (between 200 and 300 eggs; Osikowski 2007), this parameter avoided an overproduction of offspring in regard to the total number of available localities at each generation. Offspring sex was randomly assigned following a binomial distribution and an unbiased sex ratio. Genetic polymorphism was defined according to real genetic data, with 12 microsatellite loci and 9 alleles per locus (mean number of alleles per locus in empirical data: 8.67). Genotypes were randomly assigned at the beginning of simulations and the mutation rate was set to 0.0005, as in [START_REF] Blair | A simulation-based evaluation of methods for inferring linear barriers to gene flow[END_REF].

We simulated mating and dispersal movements so that the resulting scale of IBD matches with the observed scale S of IBD in empirical datasets. According to preliminary analyses using non-directional Mantel correlograms as described above, travelled distances were drawn from a probability distribution inversely proportional to a linear function, with the maximal dispersal cost distance that may be travelled (associated with a null probability; Landguth and Cushman 2010) set to 3000 m (Fig. 2c).

Cost distances were based on Euclidean distances between pairwise aggregates. We investigated the time-lag between the creation of both LTIs and the ensuing simulated genetic response by respectively placing the A6 highway and the LGV-PSE railway as impermeable barriers to dispersal at generations 100 (thus corresponding to year 1969) and 112 (thus corresponding to year 1981). We replicated the simulation 10 times to account for demographic stochasticity.

For each replicate, individual genotypes were collected from generation 100 to 200 with an increment of 5. Using only the 225 aggregates corresponding to real aquatic sites in the empirical dataset, we randomly subsampled two individuals per aggregate and computed pairwise genetic distances using the Bray-Curtis percentage dissimilarity measure, as described above. We repeated this subsampling procedure 10 times to account for sampling stochasticity, resulting in a total of 100 genetic matrices per generation. We then used partial Mantel tests with 1000 restricted permutations [START_REF] Prunier | Optimizing the trade-off between spatial and genetic sampling efforts in patchy populations: towards a better assessment of functional connectivity using an individual-based sampling scheme[END_REF] to test for the effects of the highway and the railway while controlling for IBD. Mantel correlations were averaged across all replicates and all subsampling schemes. We finally plotted the averaged Mantel correlation values over generations, with a 95% confidence interval determined by bootstrap resampling (1000 iterations). We considered that a barrier effect was detectable when at least 95 % of partial Mantel tests were significant (P-value ≤ 0.05).

Results

Simulations

Simulations were performed with 3000 m as the maximal distance that may be travelled by juveniles for dispersal and adults for mating. On average, this parameter led to dispersal and mating movements of 1238 m long (± 1000 m) and to annual mean dispersal rates of 14.5% (1.45 dispersal events per year and per population). Mantel correlograms showed significant genetic relatedness between pairwise individuals for the first 12 km (first 4 bins), and either no or negative autocorrelation as distance increased (Fig. 2c). When simulated as totally impermeable, the A6 highway and the LGV-PSE railway were respectively detected as significant barriers to gene flow after 35 and 58 years, that is approximately 11 and 19 generations (Fig. 5). Interestingly, time-lag before detection of a significant barrier effect was longer for the railway than the highway, suggesting that the spatial distribution of sampling points directly influences the detection power of genetic discontinuities in correlative analyses. According to these results, only the highway was old enough for a significant barrier effect to be detected in our study (Fig. 5).

Genetic data

A total of 417 individuals (206 Males, dataset M, and 211 females, dataset F) were sampled in the study area. Both a male and a female were captured in 192 ponds, from a total of 225 ponds where I. alpestris was detected. The mean number of genotypes per site was 1.85. The genotyping error rate, estimated by blind replications as the mean error rate per locus e l , was less than 2.4 % in CopTa1, CopTa4, CopTa14

and Ta1Caga4, and 0% for the 10 other loci.

Isolation-by-distance, isolation-by-resistance and isolation-by-barrier

In both empirical datasets, Mantel correlograms showed significant genetic relatedness between pairwise individuals for the first 12 km (first 4 bins), and either no or negative autocorrelation as distance increased (Fig. 2a-b), as in simulated data (Fig. 2c). These results indicate the existence of a significant IBD process over the study area. However, correlation values in the first distance classes were not as high and did not show any regular decrease as in simulated data. This may be due to the presence of higher densities of aquatic sites in the study area than simulated in CDPOP, allowing a better spread of alleles at close distances. The spatial scale of genetic autocorrelation (S = 12 km) was similar in males and females.

Selecting individuals located at less than S = 12 km from each infrastructure allowed the design of four new datasets (M A6 , F A6 , M LGV-PSE and F LGV-PSE ) with at least 153 genotypes each (Table 1). A significant IBD was detected in each dataset (Table 1). Except in M A6 dataset, in which case the effect of land cover as described in [START_REF] Emaresi | Landscape genetics of the Alpine newt (Mesotriton alpestris) inferred from a strip-based approach[END_REF] was close to significance, neither IBR nor IBB was ever detected whatever the dataset or the considered IBR scenario (Table 1). In the case of IBB detection, Mantel correlation values were always negative in M A6 and F A6 datasets and positive in M LGV-PSE and F LGV-PSE datasets. The same results were obtained when using both males and females data (data not shown).

Genetic structure

When the analyses were performed in males or in females separately, TESS systematically failed to detect any genetic structure (data not shown), which may be explained by the low number of genotypes in each dataset. We thus combined males and females data. The best estimate of the number of clusters using the averaged DIC criterion over the five runs performed per K was 3 (Fig. 3a). However, runs performed for K max = 3 showed high variability in DIC values. Furthermore, for K max > 2, the posterior estimates of cluster membership for each individual systematically displayed only one or two clusters, the additional clusters containing negligible proportions. We thus performed 100 runs with K max = 2. This number of inferred clusters allowed the use of a simple kriging interpolation function. The 20 best runs averaged using CLUMPP led to the progressive discrimination of individuals in two clusters (Fig. 3b):

according to figure 3c, individuals with an estimated membership in cluster 1 higher than 40% were located in Terre-Plaine, while those with a lower estimated membership were located in Le Morvan and L'Auxois. Although most individuals had high probability of assignment to one cluster or the other, high levels of admixture were encountered at the interface of these two clusters, confirming the existence of an IBD pattern. The detected boundary was not related to the presence of LTIs.

All global Monte-Carlo tests performed in sPCA were significant (dataset M, max(t) = 0.0109, p < 10 4 ; dataset F, max(t) = 0.011, p < 10 4 ), indicating the presence of significant global genetic structures in all datasets. On the contrary, local Monte-Carlo tests did not detect any significant local structure (dataset M, max(t) = 0.007, NS; dataset F, max(t) = 0.006, NS). The analyses revealed four kinds of global genetic patterns (Fig. 4e). In both datasets, scores of individuals along the first sPCA axis distinguished Terre-Plaine from the rest of the study area, as did TESS (Fig. 4a, Boundary I). A second pattern was revealed by second sPCA scores in dataset M (Fig. 4b): this structure clearly segregated individuals located in Le Morvan from the rest of the study area (Boundary II); a third group, identified in the west of Terre-Plaine (Boundary III) corresponded to the westernmost water catchment in Terre-Plaine, although further analyses, performed over a more extended study area, may be required to confirm this pattern. Scores of females along the second sPCA axis (dataset F) revealed a slightly different pattern in the south, with higher genetic similarity among individuals located in southern hilly landscapes from Le Morvan and L'Auxois (Fig. 4c, southern white squares, Boundary IV). Finally, third sPCA scores in females (Fig. 4d) displayed a pattern highly similar to the one obtained from the second sPCA scores in dataset M (Boundary II). However, females from Terre-Plaine located next to the highway showed higher scores than females located more distantly (area delimited with white dashes), indicating higher genetic similarity among individuals in the direct vicinity of the highway. Boundaries II and IV in females were also identified as sharp boundaries by Monmonier's algorithm (see Appendix A). LTIs never separated inferred groups.

Discussion

Our study was based on an individual-based targeted sampling scheme in a highly mobile species and was thus designed to optimize barrier detection. However, while simulations provided good insight into the temporal scale before barrier detection in our study and suggested that the A6 highway was old enough for a significant barrier effect to be detected, inferred spatial genetic patterns did not support this hypothesis. Indeed, the LTIs were never detected as barriers to gene flow, observed genetic boundaries rather coinciding with transition zones between major landscape entities.

Simulations were based on parameters reflecting the alpine newt life history and led to realistic IBD patterns in simulated data, with dispersal rates and travelled distances in the range of empirical observations reported in the literature [START_REF] Joly | Colonization dynamics of new ponds, and the age structure of colonizing Alpine newts, Triturus alpestris[END_REF][START_REF] Perret | Transience, dispersal and survival rates in newt patchy populations[END_REF][START_REF] Schmidt | Dispersal of Triturus alpestris and T. vulgaris in agricultural landscapescomparing estimates from allozyme markers and capturemark-recapture analysis[END_REF][START_REF] Kopecky | Movements of Alpine newts (Mesotriton alpestris) between small aquatic habitats (ruts) during the breeding season[END_REF]Fig. 2c). Despite the use of overlapping generations, both simulated LTIs were detected as significant barriers to gene flow in less than 20 generations, as already observed in Landguth et al. ( 2010) with correlative analyses (Fig. 5). However, considering the time-lag between the creation of LTIs and the beginning of genetic sampling, the LGV-PSE high-speed railway was probably too recent for a significant barrier effect to be detected in our study.

A significant IBD pattern was detected in both sexes in empirical data, with higher genetic relatedness among individuals less than 12 km apart. The detection of this long-distance IBD pattern in I.

alpestris is consistent with previous studies [START_REF] Perret | Transience, dispersal and survival rates in newt patchy populations[END_REF][START_REF] Pabijan | Genetic structure in northeastern populations of the Alpine newt (Triturus alpestris): evidence for post-Pleistocene differentiation[END_REF][START_REF] Emaresi | Landscape genetics of the Alpine newt (Mesotriton alpestris) inferred from a strip-based approach[END_REF][START_REF] Prunier | Optimizing the trade-off between spatial and genetic sampling efforts in patchy populations: towards a better assessment of functional connectivity using an individual-based sampling scheme[END_REF]) and suggests that genes spread out according to a 'stepping-stone' model [START_REF] Kimura | The stepping stone model of population structure and the decrease of genetic correlation with distance[END_REF], high densities of aquatic sites in the study area allowing alpine newts to perform several discrete dispersal movements between neighbouring ponds throughout their lifetime [START_REF] Semlitsch | Differentiating migration and dispersal processes for pond-breeding amphibians[END_REF]. This pattern also reinforced the expectation of significant barrier detection in this species. Highly nomadic individuals may actually encounter roads at higher rates than less mobile ones, thus possibly shortening the period of time until barrier detection (Landguth et al. 2010;[START_REF] Blair | A simulation-based evaluation of methods for inferring linear barriers to gene flow[END_REF][START_REF] Prunier | Optimizing the trade-off between spatial and genetic sampling efforts in patchy populations: towards a better assessment of functional connectivity using an individual-based sampling scheme[END_REF]. Indeed, simulations showed that the A6 highway may have been detected as a total barrier to gene flow in no more than 35 years (approximately 11 generations), despite high longevity and overlapping generations in the alpine newt. However, this LTI was never detected as a barrier to gene flow, whatever the approach.

Four main genetic boundaries were detected. The major genetic boundary (I), detected with the sPCA (Fig. 4a) as well as with TESS (Fig. 3), explained most of the spatial and genetic variability in all datasets (Fig. 4e). Boundaries II and IV (Fig. 4b, c andd) were not detected by TESS but were identified as sharp boundaries by Monmonier's algorithm applied to females (see Appendix A). These patterns coincided with transition zones between major landscape entities in the study area (Fig. 1b and Fig. 4), while the A6 highway and the LGV-PSE high-speed railway were always embedded in inferred clusters.

Boundaries I and II respectively distinguished Terre-Plaine and Le Morvan as two distinct homogeneous clusters. In females, boundary IV assigned individuals located in southern higher elevation areas from Le Morvan and L'Auxois to the same group. The observed genetic patterns may be explained by IBD, along with subtle modifications in landscape characteristics such as elevation (Boundaries II and IV), land use (Boundaries I, II and IV), proportions of wooded patches (Boundary II), hydrologic networks (Boundary III), or most probably a combination of these factors. This complexity, as well as the use of a targeted sampling scheme designed to specifically assess the influence of LTIs on gene flow [START_REF] Prunier | Optimizing the trade-off between spatial and genetic sampling efforts in patchy populations: towards a better assessment of functional connectivity using an individual-based sampling scheme[END_REF], may explain why IBR scenarios, based on simple hypotheses regarding the influence of landscape on gene flow, were not better supported than IBD scenario. More complex scenarios and alternative statistical approaches [START_REF] Selkoe | Taking the chaos out of genetic patchiness: seascape genetics reveals ecological and oceanographic drivers of genetic patterns in three temperate reef species[END_REF][START_REF] Van Strien | A new analytical approach to landscape genetic modelling: least-cost transect analysis and linear mixed models[END_REF]) may be needed to confirm the observed genetic structure and identify all its possible drivers. Nevertheless, controlling for IBD or IBR did not improve IBB detection.

The absence of any detectable barrier effect may be first explained by a lack of statistical power due to the use of too few (or too little variable) microsatellite markers [START_REF] Landguth | Effects of sample size, number of markers, and allelic richness on the detection of spatial genetic pattern[END_REF]). However, simulation results suggested that this number of markers was not a limiting factor in our case. A second explanation may be the time-lag between the processes that caused the formation of spatial genetic structure and the observed spatial genetic structure itself (Landguth et al. 2010). This time-lag may be lengthened by the presence of large effective population sizes on each side of infrastructures [START_REF] Gauffre | Spatial genetic structure of a small rodent in a heterogeneous landscape[END_REF], as populations separated by a barrier may still be functionally connected with populations in their hinterland, thus rendering genetic barrier effects difficult to detect. Our study was precisely designed to reduce this time-lag: 1) by considering a species with relatively long range mating and dispersal (Landguth et al. 2010), 2) by using an individual-based sampling scheme and by computing genetic distances based on inter-individual measures of genetic relatedness rather than on conventional interpopulation measures of genetic differentiation (Landguth et al. 2010;[START_REF] Prunier | Optimizing the trade-off between spatial and genetic sampling efforts in patchy populations: towards a better assessment of functional connectivity using an individual-based sampling scheme[END_REF], and 3) by using a targeted sampling design so as to avoid large gaps between sampled points and putative barriers to gene flow [START_REF] Anderson | Considering spatial and temporal scale in landscape-genetic studies of gene flow[END_REF][START_REF] Prunier | Optimizing the trade-off between spatial and genetic sampling efforts in patchy populations: towards a better assessment of functional connectivity using an individual-based sampling scheme[END_REF]. Our simulation results, showing that no more than 35 years would be necessary for the A6 highway to be detected as totally impermeable to dispersal (Fig. 5) despite the simulation of gene flow among 450 highly connected fictive aggregates (Fig. 1a), suggest indeed that our study was not susceptible to this issue, at least in the case of the A6 highway.

Neither simulations nor empirical results allowed us to conclude about the possible barrier effect of the railway (although field observations suggested that newts may be able to move underneath rail tracks). But interestingly, although both LTIs were similarly simulated as total barriers to gene flow, 58 years (approximately 19 generations) were necessary for the detection of the railway as a barrier, as opposed to 35 years in the case of the highway (Fig. 5). This result suggests that the spatial distribution of aggregates in the vicinity of LTIs, and possibly the layout of LTIs itself, may directly influence the timelag before barrier detection, highlighting the need for a case-by-case study of roads effects on wildlife.

Contrary to the LGV-PSE high-speed railway, several clues apart from simulations allow us to reasonably assume that the A6 highway may simply be permeable to gene flow. Firstly, investigating the barrier effect of the A6 highway using correlative analyses led to systematic negative Mantel correlations (Table 1). This pattern may need further investigations to be fully explained, although such negative Mantel correlations were already observed between independent variables in [START_REF] Dutilleul | The Mantel test versus Pearson's correlation analysis: Assessment of the differences for biological and environmental studies[END_REF]. In any case, observed correlations in IBB analyses were far from being positive, suggesting that transverse gene flow was definitely not affected by the A6 highway. Secondly, the detection of a longitudinal genetic pattern in sPCA results, with higher genetic similarity among females located in the direct vicinity of the highway (Figure 4d), suggests that this infrastructure is not only permeable to gene flow, but also that it may serve as a longitudinal dispersal corridor in a low-quality matrix such as Terre-Plaine, characterized by high proportions of fragmented wooded patches and cultivated crops (Fig. 1a; [START_REF] Meunier | Bird communities of highway verges: Influence of adjacent habitat and roadside management[END_REF][START_REF] Tikka | Road and railway verges serve as dispersal corridors for grassland plants[END_REF]. This counterintuitive genetic pattern was only detected with the third sPCA axis, suggesting that it may be the result of recent landscape changes when compared to the main genetic structure coinciding with major historical landscape entities. Direct approaches such as telemetry or capture-mark-recapture protocols will be necessary to confirm this hypothesis. However, this pattern is consistent with sex-biased dispersal abilities observed in the alpine newt: females being less mobile than males at the juvenile stage [START_REF] Joly | Colonization dynamics of new ponds, and the age structure of colonizing Alpine newts, Triturus alpestris[END_REF][START_REF] Perret | Transience, dispersal and survival rates in newt patchy populations[END_REF], they may benefit from the existence of both evenly-spaced transverse passages (e.g. culverts, extended stream crossings or dirt roads; [START_REF] Lesbarreres | What type of amphibian tunnel could reduce road kills?[END_REF][START_REF] Lesbarreres | Measures to reduce population fragmentation by roads: what has worked and how do we know?[END_REF] and favorable roadside structures (e.g. ditches for rainwater drainage or stormwater retention ponds; Le [START_REF] Viol | More amphibians than expected in highway stormwater ponds[END_REF] to disperse through and along the highway. This phenomenon may be facilitated by the water filling of such structures during rainfall events [START_REF] Schalk | Vagility of Aquatic Salamanders: Implications for Wetland Connectivity[END_REF], notably in sectors that are highly resistant to movements such as agricultural plains [START_REF] Joly | Habitat matrix effects on pond occupancy in newts[END_REF][START_REF] Janin | Assessing landscape connectivity with calibrated cost-distance modelling: predicting common toad distribution in a context of spreading agriculture[END_REF][START_REF] Cosentino | Connectivity of agroecosystems: dispersal costs can vary among crops[END_REF].

Roads are usually considered as barriers to the mobility of native species [START_REF] Epps | Highways block gene flow and cause a rapid decline in genetic diversity of desert bighorn sheep[END_REF][START_REF] Hepenstrick | Genetic discontinuities in roe deer (Capreolus capreolus) coincide with fenced transportation infrastructure[END_REF]) and corridors for alien ones [START_REF] Trombulak | Review of ecological effects of roads on terrestrial and aquatic communities[END_REF][START_REF] Tikka | Road and railway verges serve as dispersal corridors for grassland plants[END_REF];

Von der Lippe and Kowarik 2007). For instance, drainage ditches along highways may provide suitable conditions for the establishment and the spread of aquatic invaders such as the common reed Phragmites australis in North America [START_REF] Jodoin | Highways as corridors and habitats for the invasive common reed Phragmites australis in Quebec, Canada[END_REF][START_REF] Brisson | Roadside as invasion pathway for common reed (Phragmites australis)[END_REF]. Road verges may also facilitate dispersal in ground-dwelling exotic species such as the cane toad Bufo marinus in Australia [START_REF] Brown | Toad on the road: Use of roads as dispersal corridors by cane toads (Bufo marinus) at an invasion front in tropical Australia[END_REF]). However, roads may also facilitate dispersal of native species, as recently shown in the lizard Gallotia galloti in Canari islands [START_REF] Garcia | Road edge effect on the abundance of the lizard Gallotia galloti (Sauria : Lacertidae) in two Canary Islands forests[END_REF]). Although we still have to demonstrate that transverse and roadside structures are effectively used by dispersing individuals, our results revealing that the alpine newt is not affected by and may even benefit from the presence of the A6 highway suggest that LTIs do not necessarily lead to systematic conservation issues, as an increase in dispersal abilities of native species is a key parameter in the context of landscape fragmentation and climate change [START_REF] Bonte | Costs of dispersal[END_REF]). However, these results are specific to the highway under study, as any road in a different environmental context may hinder genetic exchanges in the alpine newt (e.g. Van Buskirk 2012):

Considering local interactions between species, infrastructures and landscape-specific characteristics proves to be essential for a better understanding of the potential impacts of LTIs on movement patterns in terrestrial organisms [START_REF] Balkenhol | Molecular road ecology: exploring the potential of genetics for investigating transportation impacts on wildlife[END_REF][START_REF] Knapp | The habitat-specific effects of highway proximity on ground-dwelling arthropods: Implications for biodiversity conservation[END_REF]. Further investigations are thus required to define species-specific benchmarks in terms of permeability of road structures (and road design) to movements [START_REF] Mata | Are motorway wildlife passages worth building? Vertebrate use of road-crossing structures on a Spanish motorway[END_REF]Woltz et al. 2008;[START_REF] Lesbarreres | Measures to reduce population fragmentation by roads: what has worked and how do we know?[END_REF], and to clarify the impact of land use conversion in the vicinity of various LTIs (or sections of LTIs).

  ) In the east, L'Auxois is a cultivated plateau in the continuity of Le Morvan, interrupted by two parallel geologic depressions (minimum elevation: 300m). (3) In the north, Terre-Plaine is a vast low-elevation plain (minimum elevation: 187m). Both Terre-Plaine and geologic depressions in L'Auxois are covered with cultivated fields (mainly cereal crops), extensively pastured meadows and wooded patches. The study area is crossed by two large-scale transportation infrastructures (LTIs) localized along the Paris-Lyon axis: (1) the A6 highway, a divided highway in use since 1969, crosses Terre-Plaine and the eastern geologic depression in L'Auxois; (2) the LGV-PSE high-speed railway, in use since 1981, runs along Le Morvan eastern foothills. These infrastructures were respectively 41 and 29 year-old when the field study was initiated in 2010. For comparison, the oldest road sections studied in Van Buskirk (2012) dated back to 1962, that is, 38 years before the beginning of sampling. Both LTIs are approximately 25 m wide (50 m wide when considering the fenced area). They are regularly crossed by country roads, tracks and natural streams, with approximately one crossing structures every kilometer. They intersect in Terre-Plaine and delimit four distinct sectors (A, B, C and D, Fig. 1a).

  by blind replication of 45 out of 1081 samples (4.2 %) collected from 2009 to 2011 as part of a general research program on the alpine newt.

  al. 2003) over three distinct resistance rasters representing: (1) landscape resistance due to slope (IBR slope ) with grid cell values parameterized according to a linear function ⁄ and ranging from 1 to 3; (2) landscape resistance due to land cover (IBR LC ) with grid cell values set to 1 for wooded patches, 3 for urbanized areas and 2 otherwise; (3) landscape resistance due to a combination of these two features (IBR slopeLC ) and obtained by addition. Using simple and partial Mantel tests in a causal modeling framework (Cushman et al. 2006; Cushman et al. 2013), we first tested for IBD by comparing each pairwise genetic distance matrix to the corresponding Euclidean distance IBD matrix. We then tested for IBR by comparing each pairwise genetic distance matrix to the corresponding IBR slope , IBR LC and IBR slopeLC distance matrices after controlling for the effect of the IBD matrix. Finally, we tested for IBB by comparing each pairwise genetic distance matrix to the corresponding IBB distance matrix after controlling for the effect of the IBD or the IBR distance matrices. Given the objective of our study and the current controversy regarding the use of Mantel tests in model selection (Graves et al. 2013; Guillot and Rousset 2013), IBR matrices were not used for the selection of alternative scenarios but only to improve barrier detection.

and

  Cushman 2010), a spatially explicit, individual-based cost distance genetic program, to simulate realistic gene flow among aggregates over 200 overlapping generations.

Fig. 1

 1 Fig. 1 Characteristics of the study area and sampling scheme in Bourgogne (France). The A6 divided highway and the LGV-PSE highspeed railway are in thick and dotted thick lines respectively. (a) Localisation of the 225 ponds were alpine newts were sampled , of the 225 additional fictive sites used in CDPOP simulations and of main habitat features in the study area. The intersection of the two infrastructures delimits four distinct sectors (A, B, C and D). (b) Relief and main landscape entities in the study area. Western and eastern geologic depressions in L'Auxois are respectively numbered 1 and 2.

Fig. 2

 2 Fig. 2 Mantel correlograms showing the relationships between inter-individual genetic distances and Euclidean distance classes (defined every 3000 m) in (a) males, (b) females and (c) one of the ten simulated datasets at generation 100. r: standard Mantel correlation with 1000 permutations. Error bars bound the 95% confidence interval about r as determined by bootstrap resampling. Upper and lower confidence limits (dotted line) bound the 95% confidence interval about the null hypothesis of no spatial structure as determined by permutation. * : p-value < 0.05; * * : p-value < 0.01; * * * : p-value < 0.001.

Fig. 3

 3 Fig. 3 Spatial genetic structures inferred from TESS. (a) Estimates of the true number K of clusters using the DIC criterion averaged over each five runs (mean ± SD). (b) Estimated membership (y-axis) of each individual (x-axis) in clusters 1 and 2. The 40 % threshold (dotted line) approximately delimits individuals from cluster 1 (Terre-Plaine) according to figure 3c. (c) Spatial distribution of clusters 1 and 2 in the study area. Black dots stand for the sampling points. Contour lines stand for the interpolated membership of individuals in cluster 1, using a kriging function.

Fig. 4 Fig. 5

 45 Fig. 4 Analyses of alpine newt data using sPCA. Large white and black squares stand for highly negative and positive scores respectively. Small squares stand for low sPCA scores. White arrows and corresponding roman numerals indicate various inferred boundaries (see text for details). (a) Map of the first global sPCA scores in dataset M; analyses led to highly similar patterns in dataset F (data not shown). (b) Map of the second global sPCA scores in dataset M; (c) Map of the second global sPCA scores in dataset F. (d) Map of the third global sPCA scores in dataset F; white dashes delimit an area in which females located in the direct vicinity of the highway show high genetic similarity. (e) Screeplots of

  [START_REF] Jombart | Revealing cryptic spatial patterns in genetic variability by a new multivariate method[END_REF], a spatiallyexplicit multivariate method using individual genotypes to investigate the spatial patterns of genetic variability. This method, seeking principal components that optimize the variance of individual allelic frequencies while taking spatial autocorrelation of data into account, does not require Hardy-Weinberg or linkage equilibrium: sPCA analyses were thus performed using all 14 loci, including CopTa7 and CopTa9. This explanatory tool provides maps of individual sPCA scores, allowing a visual assessment of the spatial genetic structures. It disentangles global structures, i.e. strong genetic similarity or positive autocorrelation between neighbors, from local ones, i.e. strong genetic differences or negative autocorrelation between neighbors. For each dataset, we used a distance-based neighborhood network with a distance threshold S consistent with Mantel correlograms. A global and a local Monte Carlo test

Table 1 .

 1 Correlative analyses on pairwise data. Simple and partial Mantel correlations (r) between pairwise genetic distance matrices (G) and various effective distance matrices among males and females located at less than S = 12km from the A6 highway (M A6 and F A6 ) or from the LGV-PSE high-speed railway (M LGV-PSE and F LGV-PSE ). Effective distance matrices were based on the null model of isolation-bydistance (IBD), on the model of isolation-by-barrier (IBB), and on three models of isolation-by-resistance according to the putative effects of slope (IBR slope ), land cover (IBR LC ) or both (IBR slopeLC ). Significant

	Mantel correlations at α = 0.05 are in bold.
	Dataset	n a	Investigated pattern	Mantel test b	Mantel correlation r	P-value
			IBD	G ~ IBD	0.0893	0
				G ~ IBR slope / IBD	-0.0066	0.5854
			IBR	G ~ IBR LC / IBD	0.0534	0.0569
	M A6	153		G ~ IBR slopeLC / IBD G ~ IBB / IBD	0.0089 -0.0388	0.3896 0.962
			IBB	G ~ IBB / IBR slope G ~ IBB / IBR LC	-0.0421 -0.0379	0.981 0.965
				G ~ IBB / IBR slopeLC	-0.041	0.977
			IBD	G ~ IBD	0.0725	0
				G ~ IBR slope / IBD	-0.0178	0.7213
			IBR	G ~ IBR LC / IBD	0.0069	0.4146
	F A6	154		G ~ IBR slopeLC / IBD G ~ IBB / IBD	-0.0099 -0.0285	0.6024 0.9351
			IBB	G ~ IBB / IBR slope G ~ IBB / IBR LC	-0.0304 -0.0277	0.959 0.9291
				G ~ IBB / IBR slopeLC	-0.0298	0.957
			IBD	G ~ IBD	0.0441	0.009
				G ~ IBR slope / IBD	-0.0037	0.5335
			IBR	G ~ IBR LC / IBD	-0.0051	0.5794
	M LGV-PSE 160		G ~ IBR slopeLC / IBD G ~ IBB / IBD	-0.0076 0.0119	0.5804 0.2697
			IBB	G ~ IBB / IBR slope G ~ IBB / IBR LC	0.0128 0.0116	0.2258 0.2727
				G ~ IBB / IBR slopeLC	0.0126	0.2418
			IBD	G ~ IBD	0.0572	0.003
				G ~ IBR slope / IBD	-0.012	0.6533
			IBR	G ~ IBR LC / IBD	0.0068	0.4046
	F LGV-PSE	162		G ~ IBR slopeLC / IBD G ~ IBB / IBD	0.0046 0.0188	0.4565 0.1528
			IBB	G ~ IBB / IBR slope G ~ IBB / IBR LC	0.02 0.0185	0.1369 0.1648
				G ~ IBB / IBR slopeLC	0.0198	0.1189

Woltz HW, Gibbs JP, Ducey PK (2008) Road crossing structures for amphibians and reptiles: Informing design through behavioral analysis. Biol Cons 141 (11):2745-2750. doi:10.1016/j.biocon.2008.08.010

a Number n of genotypes in dataset. b G ~ A corresponds to a simple Mantel test between the genetic distance matrix G and the matrix A; G ~ A/B corresponds to a partial Mantel test between the genetic distance matrix G and the matrix A partialling out the matrix B. Mantel tests were performed with 1000 restricted permutations.

Acknowledgements

This work was supported by the Agence Nationale de la Recherche et de la Technologie (ANRT, agreement 2⁄2009), Réseau Ferré de France (RFF), Autoroutes Paris-Rhin-Rhône (APRR) and the ECOSPHERE company. It was conducted in accordance with French laws and with the approval of the Préfectures de Saône-et-Loire, de Côte-d'Or and de l'Yonne. We warmly thank T. Jombart for helpful comments about sPCA results, P. Allemand for his help in Matlab programing, E. Landguth for clues as to the use of CDPOP and J. Van Buskirk for details about its own study. In addition, we thank C. De Fazio, G. Perez, F. Revollon, F. Ribette, J. Mangin and O. Grolet for their precious help and support in

the field and laboratory, Anne Corrigan for proofreading, and two anonymous reviewers for comments that greatly improved this manuscript.

Electronic supplementary material

Supplementary data associated with this article can be found in the online version.


Julien Fradin
email: julien.fradin@etu.univ-nantes.fr

Florian Richoux
email: florian.richoux@univ-nantes.fr

Robustness and Flexibility of GHOST

GHOST is a framework to help game developers to model and implement their own optimization problems, or to simply instantiate a problem already encoded in GHOST. Previous works show that GHOST leads to highquality solutions in some tens of milliseconds for three RTS-related problems: build order, wall-in placement and target selection. In this paper, we show the robustness of the framework, having very good results for a problem it is not designed for (pathfinding), as well as its flexibility, where it is easy to propose different models of the same problem (resource allocation problem). The goal of the paper is not to improve the state-of-theart on these problems, but to use them as benchmarks to test GHOST properties.

Introduction

This paper shows the robustness and the flexibility of GHOST, a framework including a skeleton to implement our own constraint satisfaction problems and constraint optimization problems (CSP/COP), a constraint solver and a set of ready-to-use problems (?). This framework is available as a C++11 library under GNU GPL v3 licence, available at https://github.com/richoux/GHOST GHOST deals with CSP/COP which are well-known to be NP-complete problems. To solve them, it includes a metaheuristics algorithm to quickly approach an optimal solution. GHOST's purpose is to help the game developer coding an AI to get a high-quality solution of its problem within some tens of milliseconds, since it is not realistic to allocate much computation power dedicated to AI in a game.

To demonstrate our claim, we have included two new ready-to-use problems: the pathfinding problem and the resource allocation problem. The first one is a polynomialtime problem. GHOST's solver has no way to capture and exploit its intrinsic easiness, although it finds very good paths within 1 millisecond only, even if we make the original problem more complex by adding passable dangerous zones to avoid if possible. These good results show the robustness of the framework. GHOST is also flexible since we can implement very different models for the same problems by changing less than 10 C++ lines only, while keeping excellent results. This is illustrated with resource allocation problems now included into the framework, with StarCraft: Brood War as a testbed.

GHOST: A General meta-Heuristic Optimization Solving Tool

A brief introduction to CSP / COP The difference between a CSP and a COP is simple:

• A CSP models a satisfaction problem, i.e., a problem where all solutions are equivalent; the goal is then to just find one of them, if any. For instance: finding a solution of a Sudoku grid. Several solutions may exist, but finding one is sufficient, and no solution seems better than any other one. • A COP models an optimization problem, where some solutions are better than others. For instance: Several paths may exist from home to workplace, but some of them are shorter.

Formally, a CSP is defined by a tuple (V , D, C) such that:

• V is a set of variables, • D is a domain, i.e., a set of values for variables in V , • C is a set of constraints.
A constraint c ∈ C can be seen as a k-ary predicate c : V k → { , ⊥} where can be semantically interpreted by true and ⊥ by false. Thus, regarding the value of the vector V k , we say that c is either satisfied (equals to ) or unsatisfied (equals to ⊥).

A COP a defined by a tuple (V , D, C, f ) where V , D and C represent the same sets as a CSP, and f is an objective function to minimize or maximize.

For GHOST, we have chosen a meta-heuristic algorithm to be the heart of the solver, Adaptive Search from (?). The reason we have chosen a meta-heuristics is simple: to solve combinatorial and optimization problems while playing an RTS game, the solver needs to be very fast to find a solution, within some tens of milliseconds, which is virtually impossible with tree-based search algorithms. The reason we have chosen Adaptive Search is, although it is not a well-known algorithm, it is one of the fastest meta-heuristics at the moment, up to our knowledge (?).

It is essential to keep in mind that meta-heuristics are stochastic methods: two runs on the same problem instance may lead to two different solutions within the same runtime. This is why results in this paper are the average of 100 repeated experiments.

GHOST architecture

GHOST is implemented around five main C++ classes: Variable, Domain, Constraint, Objective and Solver. Implementing a CSP model means inheriting its own classes from the three first classes above. Implementing a COP model means making an additional class inheriting from Objective.

The solving process implemented in class Solver is composed of two main loops: the outer loop for optimization, containing the inner loop for satisfaction. The satisfaction part only tries to find a possible solution among all configurations, i.e., tries to find an assignment of each variable such that all constraints of the CSP are satisfied. The optimization part is triggered when an objective function has been implemented in a descendant class of Objective. It will influence the satisfaction part (finding a valid solution) if the objective implements optional heuristics to select the variable to change and the value to assign, if the current configuration is not a solution. The optimization part also applies two optional post-process optimizations, one on the output of the satisfaction loop to "clean up" the raw solution found, one on the final output to apply to ad-hoc, last-minute optimizations if possible, leading to the solution returned by the solver.

The fundamental thing in the optimization part is the optimization loop itself. To explain how this loop works, we have to introduce the two temporal parameters in GHOST. The function solve takes two parameters: the first one is the satisfaction timeout x in milliseconds. It means that, after x ms top, we leave the satisfaction loop, certainly without a valid solution since the loop stops as soon as it finds a solution. The second parameter is the optimization timeout y, always in milliseconds. It corresponds also to the total runtime of GHOST, modulo the post-process after the optimization loop (which is negligible in practice and should be about 100 times shorter than y).

Thus, the optimization loop repeats n times the satisfaction loop, and receives in total m ≤ n valid solutions. After receiving a new solution from the satisfaction loop, and applying an eventual satisfaction post-process, it calls the objective function to compute the optimization cost, compares it with its saved solution (if any) and keeps the solution with the lower cost. Then it repeats the satisfaction loop to obtain a new solution, and so on, until y ms are reached.

Concerning objective functions, GHOST has been designed to minimize their value. If a developer user needs to maximize an objective function f , this can be simply adapted to GHOST by defining the objective function 1/f . Our solver is designed to deal with mono-objective optimization problem only, thus, one can only choose at most one objective function at the time before running the solver, however the objective function can be dynamically changed between two calls of the solver. The choice of designing a mono-objective solver is pragmatic: multi-objective solvers are in general significantly slower, since they are dealing with more complex problems. Multi-objective are also making models more complex, which goes against one goal of GHOST: to propose a solver both easy to use and easy to extend by implementing new problems.

The pathfinding problem

The pathfinding problem is the very classical problem of finding a path (usually the shortest one) from a starting point s to a target point t. We would not debate if pathfinding is an AI problem or not; our approach is practical: numerous games including RTS games need pathfinding, and GHOST aims to be a well-spread library for helping game developers to solve AI and/or optimization problems. Including a ready-to-use pathfinding solution into GHOST can only be beneficial for users.

Problem statement and model

Before introducing our pathfinding model, we need two notions: the notion of walkable tile and the notion of marked tile.

In StarCraft like many other RTS games, a grid is applied on the map where each cell of the grid, also called tile, can be either walkable or not by ground units. Since pathfinding is relevant for ground units only (flying units do not encounter any obstacles so they can move straight toward their target), a path can only be composed of walkable tiles.

A marked tile is simply a tile where we associate a number. We will see below we only mark some specific tiles in order to find a path.

Therefore, we propose the following pathfinding model:

CSP model for the pathfinding problem:

Variables: Each tile on the map. Domain: Binary: either the variable contributes to the path (value 1) or it does not (value 0). Constraints: A unique constraint: does a series of n variables assigned to 1, going from the starting point and reaching the target point such that each variable is marked by a unique value in [1, . . . , n], exists?

If variables and domains in our model are clear, the constraint deserves further explanations. We did not write how we mark tiles yet, and it is the right moment to do it. Let's say that a variable assigned to the value 1 is a selected variable. Let's call neighbors the eight tiles around a given tile. We only mark tiles if they are selected, following this simple algorithm: Mark all selected neighbors of the starting tile with the number 1. Then, until all selected variables reachable from the starting tile are marked, repeat: for a variable marked with the number k, marked all its unmarked selected neighbors with the number k + 1. To give a picture, we obtain waves of marks equal to 1, then 2, then 3 and so on, beginning from the starting point. This is actually a breadthfirst search done only upon selected variables reachable from the starting point. Notice that this is done by GHOST: it is not a precomputed process.

What our constraint does is, intuitively, looking if a series of marks (1, 2, 3, . . ., n) exists between the starting and the target points.

To give insights about how we model this problem, we had at the beginning two constraints: the first one to check if each tile except the starting and target tile has exactly two selected neighbors, the second one to check if we can reach the target point from the starting point passing by selected variables only. The unique constraint based on mark tiles in our current model assures these properties as well, but in a more efficient way.

For this problem, we have considered two objectives. The first one is obvious: find a path as short as possible from the starting point to the target one. The second one also try to find a path as short as possible, but taking also into account some dangerous zones (like tiles too close from the enemy army) we try to avoid without strictly discarding them.

GHOST implementation and results

For the pathfinding problem, we did not need to apply the classical scheme satisfaction loop + optimization loop in GHOST. Actually, only the satisfaction loop is important to find a rough path between the starting and the target point. Thus, smart post-processes can be applied to modify our path in order to fit the objective. They are computed very quickly and are powerful enough to avoid to repeat the satisfaction process: these post-processes leads to optimal or near-optimal paths according to the applied objective.

Thus, we ran 100 experiments over 8 instances from hand crafted maps illustrated by Figure ??. Maps B and C have their starting and target points fixed and look like small maze one can find in action games for instance. Experiments have been conducted by running GHOST 100 times on map B and map C. Map A looks like more to an RTS map like we have in StarCraft. For this map, we used 6 different instances where the starting and target points where manually such that they are not in the same area, forcing a path to bypass walls or unwalkable blocks.

Since it was not necessary to exploit the optimization loop to solve this problem, we run our experiments with a timeout of 1ms for the satisfaction part and also 1ms for the optimization part, thus bounding the global runtime to 1ms top. Within 1ms, GHOST always find a optimal or near-optimal paths. Figure ?? shows an example of path found by GHOST while considering dangerous zones to avoid if possible, that is, if it makes longer the path reasonably only.

Both source code and experiments results for the pathfinding problem can be found at the following address: http: //www.runmycode.org/companion/view/1391.

Discussion

Both versions of pathfinding presented above, with or without dangerous zones, are in P. This is easy to see: finding the shortest path from s to t can be done by marking all tiles the way we do (without taking into account the notion of selected tile), and then stop as soon as the target in reached. You get your path by following down a series of tiles marked from n to 1. This is done in linear time regarding the number of tiles in your grid. If you consider dangerous zones, you can add some extra tiles to artificially increase the distance between two dangerous tiles, according to the danger level. Then you run the same algorithm looking for the shortest path.

GHOST is designed to output in a couple of milliseconds a high quality solution to NP-complete problems, by doing effective descents into the search space landscape. It has no way to capture and exploit the pathfinding computational easiness, unlike ad-hoc polynomial-time algorithms such as A*-like algorithms. However, GHOST reveals itself to be very effective, finding optimal or near optimal paths within 1ms, even for more complicated pathfinding problems dealing with passable dangerous zones.

At the beginning of this project, we aimed to model pathfinding not for a single unit but for a group, keeping group coherence while moving, to avoid situations like faster units leaving slower ones way behind them. Usually, this is handled by flocking algorithms, potential fields or a mix of both (?). Due to lack of time, we failed to find a satisfying CSP/COP model for this problem but this would be an interesting extension with direct applications for game developers.

The resource allocation problem

Resource allocation and management in RTS games such as StarCraft has been extensively studied, since it is at the heart of game mechanisms for this kind of games. Among others, the reader can find works about an agent applying resource-based strategies (?), a resource production planner (?) and a decision-making process involved in resource management (?).

In StarCraft, resources can be used to obtain units, buildings, upgrades and technologies. Two resources are needed for buying these: minerals and gas, both gathered by workers but differently (gas needs a special building to be extracted, unlike minerals). For training units, a third resource is required: the supply resource (also named "food"), limiting the number of units you can currently possess. Notice we could eventually consider a fourth kind of resource for training Zerg units: larvae. However we would not consider this in our model, since this resource (not universally acknowledged as a real resource) is race-specific.

Problem statement and model

In this section, we focus on the following problem: given an amount of minerals, gas and supply, what units should we train to maximize, say, the global damage per second (DPS). This is actually an instance of the multi-dimensional knapsack problem with three dimensions (one per resource type). The regular knapsack problem is well-known to be NPcomplete, and its multi-dimensional version is even harder: unlike the original knapsack problem, there is no efficient polynomial-time approximation scheme starting from two dimensions (unless P=NP) (?).

We have tried two different models for this problem: a 0-1 multi-dimensional knapsack model (i.e., an operational research-oriented model) and a constraint programmingoriented model. Let's call them Model 1 and Model 2, respectively.

In Model 1, variables represent individual units we can train. Thus, the number of variables must be large enough to cover all possible combinations our current resources allow. For domains, we just need binary values {0, 1} to express the fact we plan to train the considered unit or not.

CSP model for resource allocation -Model 1:

Variables: Each unit we can train. Domain: Binary: 1 means we plan to train the unit, 0 means we do not. Constraints: A unique constraint to check if the sum of the desired units' costs does not exceed one or more resource stocks.

For Model 2, variables do not represent individual units but unit types we can train, such that each possible unit type is represented by a unique variable. Here, the value of a variable represents the number of units of the concerned type we plan to train. Thus, domains must to be large enough to cover all possible combinations.

CSP model for resource allocation -Model 2:

Variables: Each unit type we can train. Domain: N (or a sufficiently large subset) representing the number of units of the considered type we will train. Constraints: Same as Model 1.

Actually, we also have tried a third model which was a variation of Model 2: variables were also unit types, but with the noticeable difference that several variables can concern the same unit type. Domains were of the same nature than Model 2 but smaller. The idea was the following: instead of having a variable for Terran Marines for instance, with a domain [1, . . . , 30], this model would accept, say, three variables for that unit type with domains [1, . . . , 10]. This was to force some diversity in the solution, avoiding the solver to fall into a greedy behavior, training for instance 30 Marines to the detriment of other units. In fact, experiences shown it does not lead to a better diversity than Model 2, and since this third model never output results of higher quality than the second model, we have simply discarded it.

GHOST implementation and results

For this problem, we consider two objectives: ground DPS and air DPS, that is respectively, the damage per second we can inflict on ground enemies and on flying enemies. Indeed in StarCraft, many units cannot attack both kind of units or use different weapons against ground and flying targets.

Unfortunately, we did not find in the literature experimental results we could compare with. Some articles show results such as win rate percentages to evaluate resourceoriented agents, but we think too many factors are in game to estimate how good the resource planning is by just looking if a bot win or loose.

We could also compare our results with other constraintbased solvers on our resource allocation problem instances, Tables ?? and ?? show the average over 100 runs of the resource allocation problem with 500 minerals, 200 gas and 9 supply (medium problem instance), and 1000 minerals, 700 gas and 19 supply (large instance) respectively, considering all anti-ground and anti-air units for each race. All experiments have been done given 1ms for the satisfaction timeout and 4ms for the optimization timeout. Therefore, the total time of each run is 4ms.

Although we did not compare GHOST results with other solvers on this problem, we solved instances from Tables ?? and ?? with a complete solver, GNU Linear Programming Kit (GLPK), to compute the optimal solution for each instance. This is impossible to compute with GHOST because its solver is a meta-heuristics, i.e., an algorithm which does not scan the full search space and then cannot certify the optimality of a solution. However within 4ms and in average among 100 runs, GHOST finds solutions very close to the optimum. Table ?? shows optimal DPS values found by GLPK, and matches them with the average DPS computed by our library.

Both source code and experiments results for the resource allocation problem can be found at the following address: http://www.runmycode.org/companion/ view/1391.

Discussion

We can see Model 2 always outperforms Model 1. This is not surprising, since Model 2 is a more compact way to express this problem, leading to greatly smaller search space. To give an example: consider we can train 10 units from 3 unit types (so 30 units in total). Model 1 leads to 30 binary variables, so a search space of size 2 30 , which is a bit more than one billion combinations. For Model 2, we have 3 variables only, each taking a value in the range [1, . . . , 10]. This leads to 3 10 combinations, i.e., a bit less than 60,000. Some methods like SAT solvers are optimized to find solutions in Boolean domains, but this is not the case of GHOST's solver, which implements the Adaptive Search meta-heuristic designed to handle any kind of finite domains.

Besides GHOST's efficiency on the resource allocation problem, the goal of this section was to show GHOST's flexibility. Indeed even if Models 1 and 2 differ greatly by their variables and domains nature, but in the code they only differ from 8 C++ lines in the implementation of Domain class. Remaining code is unchanged.

An obvious extension can be modeling and implementing other objectives. Focusing on DPS only is very limiting since it does not take into account the diversity one should expect in an RTS game army. This can be done by only modifying Objective class's descendants, without modifying the variable, domain and constraint parts of both the model and the implementation.

Future work

To conclude, we have shown GHOST to be both robust, able to deal with problems it is not designed for (i.e., problems in P, whereas its solver is designed to tackle NP-complete problems) and flexible, showing that changing 8 C++ lines We think the next step is to broadcast GHOST and make it more available, reachable to game developers. A C# version exists (see https://github.com/richoux/ GHOST_C_sharp), with a lighter, simpler structure than the C++ version, making it more user-friendly in particular for developers with no prior knowledge in constraint problems modeling. The first step would be to bring these simplifications into the C++ version, and reciprocally to include the pathfinding problem and the resource allocation problem into the C# version. Then, we would like to propose the C# GHOST as a Unity plugin, to reach the broadest game developer audience as possible, and to make it really easy to use within the famous game engine.

Finally, a proprietary C# version of GHOST is currently under a technology transfer process for the game company Insane Unity (http://www.insaneunity.com) for their MMORTS Win That War! in alpha version. GHOST would be used both for developing an adversary AI player, but also for making a taking-the-reins AI when the player is not connected, since this MMORTS would be a persistent world.

Figure 1 :

 1 Figure 1: Three crafted maps A, B and C used for our path-finding experiments. The blue rectangle shows the walkable tile size. For B and C, the red crossed circle is the starting point and the green empty circle the target.

Figure 2 :

 2 Figure 2: A computed path (in blue) in map C where dangerous zones are marked by red blocks. Parts where the path crossed dangerous zones are circled in red.

  Constraint Satisfaction Problems (CSP) and Constraint Optimization Problems (COP) are two close formalisms intensively used in Artificial Intelligence to solve combinatorial and optimization problems. Constraint Programming allows an intuitive and uniform way to model problems, as well as different general algorithms able to solve any problems modeled by a CSP or a COP.

Table 1 :

 1 Mean of 100 (1,4)-runs for the resources allocation problem with 500 mineral units, 200 gas units and 9 supply units

			Model 1			Model 2
		DPS minerals	gas	supply	DPS minerals	gas	supply
	Protoss	ground 97.9 air 64.0	50.2 0.0	0.0 0.0	1.0 1.0	98.0 64.0	50.0 0.0	0.0 0.0	1.0 1.0
	Terran	ground 116.7 air 94.7	48.2 26.5	25.0 8.0	0.1 0.0	143.1 95.9	65.0 50.0	9.0 1.5	0.3 0.0
	Zerg	ground 212.7 air 94.7	11.0 56.0	118.5 52.0	0.1 3.0	270.0 96.0	50.0 50.0	200.0 50.0	0.0 3.0
	Table 2: Mean of 100 (1,4)-runs for the resources allocation problem with 1000 mineral units, 700 gas units and 19 supply units
			Model 1			Model 2
		DPS minerals	gas	supply	DPS minerals	gas	supply
	Protoss	ground 211.3 air 141.4	29.5 40.5	161.5 23.0	1.4 2.0	236.2 148.0	36.0 25.0	11.5 50.0	3.0 1.0
	Terran	ground 215.3 air 200.9	57.2 39.2	193.0 103.7	0.4 0.0	326.8 205.9	56.0 91.7	221.0 144.7	0.1 0.0
	Zerg	ground 335.8 air 169.9	20.0 47.2	303.7 231.7	1.7 4.8	567.9 208.0	53.5 25.0	700.0 375.0	0.0 6.0
	but we do not think it is a pertinent approach. GHOST should
	not be reduced to a solver: it is an entire library aiming first
	and foremost to help game developers modeling and imple-
	menting (and then solving automatically) their own combi-
	natorial optimization problems, or to let them simply reuse
	an available model in the library. We have the feeling that
	comparing GHOST with CSP/COP solvers like one usually
	does in constraint programming papers is not scientifically
	relevant. However, it would have been relevant to com-
	pare GHOST results on resource allocation planning for RTS
	games with other Game AI methods, if such results are avail-
	able.

Table 3 :

 3 Optimal DPS versus average GHOST DPS over 100 runs P=Protoss, T=Terran, Z=Zerg, m=medium instance (500/200/9), l=large instance (1000/700/19), g=ground, a=air 100% 100% 97.8% 100% 95.9% 99.0% 98.5% 99.4% 100% 100% 99.6% 100% only is sufficient to express very different models to the same problem.

		Pmg	Pma	Plg	Pla	Tmg	Tma	Tlg	Tla	Zmg	Zma	Zlg	Zla
	Optimal	98.0	64.0	241.4 148.0 149.2	96.9	331.6	207.2 270.0	96.0	570.0 208.0
	GHOST	98.0	64.0	236.2 148.0 143.1	95.9	326.8	205.9 270.0	96.0	567.9 208.0
	wrt opt.


Luis Pineda-Morales

Balaji Subramaniam

Kate Keahey

Gabriel Antoniu

Alexandru Costan

Shaowen Wang

Anand Padmanabhan

Aiman Soliman

Scaling Smart Appliances for Spatial Data Synthesis

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.